АЛГОРИТМИ И ПРОГРАМИ В ТЕКСТООБРАБОТКАТА

(дипломна работа, София, ФМИ, 1995 г.)

 

Миналото ми принадлежи,
познавам бъдещето.

текстове от саркофазите, гл. 335

 

3. Автоматизирано откриване и отстраняване на грешки в текст

3.1. Дефиниции и понятия

Нека се въведе дефиниция на понятието текст от гледна точка на задачата, която трябва да бъде решена.

Def:Всеки текст е съставен от множество от параграфи.

Def:Всеки параграф се състои от множество от изречения и завършва със знака за нов ред.

Def:Нов ред ::= '^l' (последователността от аскизнаковете с кодове 13 и 10).

Def:Всяко изречение се състои от множество от думи, разделени помежду си с препинателни знакове.

Def:Препинателен знак е всеки знак от множеството {' ', '. ', ') ', ...}.

Def:Думите са низове от знакове от азбуката и са ограничени с препинателни знакове. Всяка дума има своя дължина. Над думите могат да се прилагат известните действия над множества като конкатенация, декатенация, пресичане, допълнение и т. н.

Преди да се пристъпи към същината на предлаганите по-долу алгоритми, нека си припомним и някои важни неща от компютърната лингвистика и дискретната математика [8].

В компютърната лингвистика терминът „представка“ се заменя с „префикс“, „окончание“ – със „суфикс“, а „поддума“ – с „подниз".

Def:Азбуката (обикновено се бележи с гръцката буква ) в нашия случай е кой да е елемент от множеството на аскизнаковете и има мощност 256.

В термините на компютърната лингвистика текстът е език (ще го означа с L) над азбуката Σ или, ако трябва по-голяма точност, той се образува чрез позитивна итерация над езика над азбуката Σ. Езикът L може да се опише чрез пораждаща система – граматика (Г), с краен брой правила.

Известно е, че пораждащата граматика може да се опише чрез четворката

G = {Σ, N, P, S},

където

Σ е азбука на езика (крайно множество от терминални (основни) знакове);

N – множество от нетерминални знакове (граматични категории), при това N U S = empty

Р – крайно множество от правила (продукции);

S – нетерминален знак (начален символ, аксиома).

Правилата могат да се опишат като таблица например с продукциите на Хомски от вида (α, β) на множеството Р (или чрез малко по-друга сигнатура -  α->β).

Граматиката определя езика рекурсивно. При работа с текстове е най-добре да се използват непосредствени пораждания при спазване на определени условия. Думите са сентенциални форми на граматиката Г, тъй като се пораждат непосредствено. Също така всяко изречение е сентенциална форма, която съдържа само терминални символи, а текстът, както вече отбелязахме, е поредица от параграфи и следователно – от изречения. Тъй като върху текста се поставят известни ограничения, конкретната граматика, на която ще се спра, принадлежи на граматиките с ограничения. За по-голяма простота множеството от условия може да се трансформира в един нетерминален символ (единствен!), който всъщност представлява поле от паметта, достатъчно голямо за да може последователно да се запишат всички предвидени флагове за наличните условия в текста. Граматиката, която поражда текста, е дяснолинейна автоматна граматика, т.е. продукциите са от вида А->αB или А->α, където А, В in N, α in Σ*. Така един текст може да бъде определен с помощта на краен автомат. По-точно – чрез детерминиран краен автомат, защото в дадения случай функцията на преходите δ, описана в [8], е определена еднозначно.

За целите, които са поставени, е необходим преобразувател (който всъщност е разпознавател, снабден с изходна лента (файл)). Крайният преобразувател представлява модел на лексически анализатор. Определя се чрез шесторката:

КП = {Q, Σ1, Σ2, δ, q0, F},

където

Q

е крайно множество от състояния;

Σ1

– крайна входна азбука;

Σ2

– крайна изходна азбука;

δ

функция на преходите: Q x (Σ1∩{ε}) -> Q x Σ2*;

q0

начално състояние;

F

– множество на крайните състояния.

Често лексическият анализатор извършва паралелно разпознаване на няколко класа лексически единици – чрез множество паралелно работещи автомати, като във всяко състояние на обединения автомат се представят състоянията на съставящите го автомати, а началното състояние обединява всички начални състояния. Една от съществените разлики с типичните лексически анализатори е, че в текста няма незначещи знакове (т. е. от вниманието не бива да се изпуснат празните позиции – препинателните знакове). Нещо повече – огромната част от усилията и състоянията в нашия краен автомат са насочени именно към анализ на елементите от низа, които стоят между думите. Това е необходимо, защото стремежът е да открием и отстраним пунктуационните грешки.

Функцията на преходите естествено може да се зададе чрез таблица. Известно е, че от структурата на една таблица зависи до голяма степен бързодействието и ефективността на транслаторите/преобразувателите, така че това трябва да залегне в основата на оптимизирането на програмата. Засега не е известен алгоритъм за намиране на абсолютно минимална програма. Така че може да се говори единствено за подобряване на работата на алгоритмите, но не и за доказано идеално решение, като трябва да се обърне повече внимание върху подобряване на скоростта и ефективността, а не върху намаляване на обема. Това може да се постигне, ако алгоритъмът достига по най-бърз начин до мястото в логическата схема за решение на конкретната ситуация. Тъй като текстът донякъде може да се разглежда като случайна величина, за цялостното решение на този проблем трябва да се прибегне до методите на вероятностите и статистиката, с които в момента няма да се занимаваме. Подобни статистически изследвания са правени в [6].

Def:<С>::=б|в|г|... |щ|Б|В|Г|... |Щ.

Def:<Г>::=а|е|и|о|у|ъ|ю|я|А|Е|И|О|У|Ъ|Ю|Я.

Def:<неразделно буквосъчетание>::=ск|ст|гр|пр.

Def:<твърд интервал>::=интервал (шпация), който се намира между две думи, които не бива да се разделят. Отбелязва се с '^ '.

Def:<неразделно тире>::=тире, което се намира между две думи, които не бива да се разделят. Отбелязва се с '^-'.

Def:<цифра>::=0|1|2|3|4|5|6|7|8|9.

Def:<цяло число>::=<цифра>|<цифра><цяло число>.

Def:<реално число по БДС>::=<цяло число>|<цяло число>','<цяло число>.

Def:<реално число на лат.>::=<цяло число>|<цяло число>'.'<цяло число>.

Def:<реално число>::=<реално число по БДС>|<реално число на лат.>.

Def:<редовна латинска буква>::=a|b|... |z.

Def:<редовна българска буква>::=а|б|... |я.

Def:<главна латинска буква> ::= A|B|... |Z.

Def:<главна българска буква>::=А|Б|... |Я.

Def:<латинска буква>::=<редовна латинска буква>|<главна латинска буква>.

Def:<българска буква>::=<редовна българска буква>|<главна българска буква>.

Def:<българска дума> е дума от лексикалния речник на българския език, написана с редовни български букви.

Def:<латинска дума> е дума от лексикалните речници на езиците с латинска азбука и написана с редовни латински букви.

Def:<дума>::=<латинска дума>|<българска дума>

Def:<БЪЛГАРСКА ДУМА> е дума от лексикалния речник на българския език, написана с главни български букви.

Def:<ЛАТИНСКА ДУМА> е дума от лексикалните речници на езиците с латинска азбука и написана с главни латински букви.

Def:<ДУМА>::=<БЪЛГАРСКА ДУМА>|<ЛАТИНСКА ДУМА>.

Def:<българска Дума> е дума от лексикалния речник на българския език, като първата й буква е главна български буква, а останалите – редовни български букви.

Def:<латинска Дума> е дума от лексикалните речници на езиците с латинска азбука, като първата й буква е главна латинска буква, а останалите – редовни латински букви.

Def:<Дума>::=<българска Дума>|<латинска Дума>.

Def:<препинателен знак>::=''|'.'|'!'|'?'|','|''|'('|')'|'"'|';'|...

Def:<отварящ препинателен знак>::='"'|'('|...

Def:<затварящ препинателен знак>::='"'|')'|'!'|'?'|'...'|';'|...

Def:<съкращение> в българския език ще наричаме дума, която представлява непълен вариант на друга дума от езика и завършва с точка. Съкращението може да се състои от една, две или повече думи (напр. 'напр. ', 'т. н.', 'г. пр. н. е.').

Def:<еднобуквена дума>::='а'|'в'|'е'|'и'|'й'|'о'|'с'|'у'|'я'.

Def:<речник на съкращенията> ще наричаме множеството от всички съкращения в българския език.

Def:<съкращение след> е подмножество от <речник на съкращенията>, състоящо се от съкращения, които са неделими от думата, която ги предхожда (напр. '1992 г.', '110 кг.').

Def:<съкращение пред> е подмножество от <речник на съкращенията>, състоящо се от съкращения, които са неделими от думата, която ги следва (напр. 'гр. София', 'доц. Христов').

Def:Ще наричаме една дума w <съмнителна>, ако според дефинираните от нас правила, е възможно в нея да се съдържат грешки. Освен това съмнителните области на даден текст са източник на потенциални неприятности в графичния етап.

<< назад | отгоре | напред >>

Съдържание

0. Встъпление

1. Увод

2. Сричкопренасяне

2.1. Малко история

2.2. Правила за сричкопренасяне от 1983 г.

2.3. Метод на скандирането

2.4. Алгоритъм на сричкопренасянето по фонетичен и морфологичен принцип

2.4.1. Алгоритъм за откриване на морфема в дума

2.4.2. Алгоритъм за анализ на буква

2.4.3. Алгоритъм за анализ на дума

2.4.4. Алгоритъм за анализ на текст

2.4.5. Други възможности

3. Автоматизирано откриване и отстраняване на грешки в текст

3.1. Дефиниции и понятия

3.2. Често допускани грешки

3.3. Класификация на правилата

3.4. Примерна програмна реализация на локалните правила

3.4.1. Нови дефиниции, променливи, флагове и множества

3.4.2. Таблица на локалните правила

3.4.3. Функции, необходими за реализация на локалните правила

3.5. Глобални правила

3.5.1. Класификация на думите в текст на равнище знакове

3.5.2. Функции, необходими за реализация на глобалните правила

3.5.3. Функции и идеи, които предстоят да бъдат осъществени

4. Някои метрики в текстообработката

4.1. Текстови и шрифтови метрики

4.2. Сложност на текст

4.3. Професионализъм на предпечатната подготовка

4.3.1. Използване на възможностите на програмите чрез дефиниране на различни стилове

4.3.2. Премахване на излишното форматиране

4.3.3. Използване на възможностите за настройка на основните отношения между и в параграфите

5. Заключение

6. Литература

7. Приложениe

7.1. Списък на книгите, върху които са направени експерименти

7.2. Някои статистики и резултати от проведени изследвания