1УНИВЕРЗИТЕТ У НОВОМ САДУ 2ФАКУЛТЕТ ТЕХНИЧКИХ НАУКА 3ИНСТИТУТ ЗА РАЧУНАРСТВО И АУТОМАТИКУ 4Vladimir Weinstein 5Објектно оријентисана спецификација и имплементaција система за детекцију и корекцију грeшака у тексту на српском језику 6- МАГИСТАРСКА ТЕЗА - 7Нови Сад, 1999. година 8Садржај: 9ПРЕДГОВОР: V 101. УВОД: 1 112. ИЗВОРИ ГРЕШАКА 5 122.1. ОСНОВНИ ТИПОВИ ГРЕШАКА 5 132.2. ЕФЕКТИ ДУЖИНЕ РЕЧИ 6 142.3. ГРЕШКЕ НА ПРВОЈ ПОЗИЦИЈИ У РЕЧИ 7 152.4. ЕФЕКТИ РАСПОРЕДА СИМБОЛА НА ТАСТАТУРИ 8 162.5. ФРЕКВЕНЦИЈЕ ГРЕШАКА 8 172.6. ФОНОЛОШКЕ ГРЕШКЕ 10 182.7. ХЕУРИСТИЧКА ПРАВИЛА И ПРОБАБИЛИСТИЧКЕ ТЕНДЕНЦИЈЕ 11 192.8. УОБИЧАЈЕНЕ ГРЕШКЕ 12 202.9. ПРЕГЛЕД РЕЗУЛТАТА ИСПИТИВАЊА ГРЕШАКА 12 213. ТЕХНИКЕ КОРЕКЦИЈЕ ГРЕШАКА 15 223.1. ТЕХНИКЕ НА БАЗИ МИНИМАЛНОГ ЕДИТ РАСТОЈАЊА 16 233.2. ТЕХНИКЕ НА БАЗИ КЉУЧЕВА СЛИЧНОСТИ 25 243.3. ТЕХНИКЕ ЗАСНОВАНЕ НА ПРАВИЛИМА 30 253.4. ТЕХНИКЕ ЗАСНОВАНЕ НА N-ГРАМИМА 32 263.5. ПРОБАБИЛИСТИЧКЕ ТЕХНИКЕ 38 273.6. НЕУРАЛНЕ МРЕЖЕ 47 283.7. ПРЕГЛЕД РЕЗУЛТАТА ТЕХНИКА ЗА КОРЕКЦИЈУ ГРЕШАКА 54 294. УТИЦАЈ ОРГАНИЗАЦИЈЕ ПОДАТАКА НА ПРОБЛЕМ КОРЕКЦИЈЕ ГРЕШАКА У ТЕКСТУ 55 304.1. О САДРЖАЈУ И ВЕЛИЧИНИ РЕЧНИКА 55 314.2. НАЈЧЕШЋЕ ТЕХНИКЕ ОРГАНИЗОВАЊА РЕЧНИКА 56 324.2.1. Бинарна стабла 57 334.2.2. Trie меморије 62 344.2.3. Hash технике 65 355. ДИЗАЈН СПЕЦИФИКАЦИЈА СИСТЕМА ЗА ПРОВЕРУ ТЕКСТА 67 365.1. ОСНОВНЕ ФУНКЦИЈЕ СИСТЕМА ЗА ПРОВЕРУ ТЕКСТА 67 375.2. СТРУКТУРА СИСТЕМА 77 385.3. ДИНАМИЧКИ ДИЈАГРАМИ 82 396. ИМПЛЕМЕНТАЦИОНИ ДЕТАЉИ 85 406.1. АРХИТЕКТУРА СИСТЕМА 85 416.2. СТРУКТУРА ПОДАТАКА РЕЧНИКА 89 426.3. ИМПЛЕМЕНТАЦИЈА ПРОЦЕСА ПРЕТРАГЕ РЕЧНИКА 93 436.4. ИМПЛЕМЕНТАЦИЈА ПРОЦЕСА ГЕНЕРИСАЊА СКУПА СЛИЧНИХ РЕЧИ 96 446.5. ПРОВЕРА ТЕКСТА 99 456.6. ПРОБЛЕМ КОРИШЋЕЊА НАШЕГ ЈЕЗИКА У JAVA ОКРУЖЕЊУ 102 466.7. ЗАВРШНЕ НАПОМЕНЕ 105 477. СПЕЦИФИЧНОСТИ И МОГУЋНОСТИ ПРИМЕНЕ ТЕХНИКА У ТЕКСТУ НА СРПСКОМ ЈЕЗИКУ 109 487.1. ПРЕГЛЕД МОГУЋНОСТИ ПРИМЕНЕ ТЕХНИКА ЗА КОРЕКЦИЈУ СТРИНГОВА НА СРПСКИ ЈЕЗИК 111 497.2. МОРФОЛОШКЕ ОСОБИНЕ СРПСКОГ ЈЕЗИКА 113 507.3. ДИЗАЈН СПЕЦИФИКАЦИЈА ИМЕНИЦА СРПСКОГ ЈЕЗИКА 116 517.4. ОРГАНИЗАЦИЈА РЕЧНИКА РЕЧИ СРПСКОГ ЈЕЗИКА 122 528. ЗАКЉУЧАК 125 53КОРИШЋЕНА ЛИТЕРАТУРА: 127 54I have a spelling checker 55I disk covered four my PC. 56It plane lee marks four my revue 57Miss steaks aye can knot see. 58Eye ran this poem threw it. 59Your sure real glad two no. 60Its very polished in its weigh, 61My checker tolled me sew. 62A checker is a blessing. 63It freeze yew lodes of thyme. 64It helps me right awl stiles two reed, 65And aides me when aye rime. 66Each frays comes posed up on my screen 67Eye trussed too bee a joule. 68The checker pours o'er every word 69To cheque sum spelling rule. 70Bee fore wee rote with checkers 71Hour spelling was inn deck line, 72Butt now when wee dew have a laps, 73Wee are not maid to wine. 74And now bee cause my spelling 75Is checked with such grate flare, 76There are know faults in awl this peace, 77Of nun eye am a wear. 78To rite with care is quite a feet 79Of witch won should be proud, 80And wee mussed dew the best wee can, 81Sew flaws are knot aloud. 82That's why eye brake in two averse 83Cuz Eye dew want too please. 84Sow glad eye yam that aye did bye 85This soft wear four pea seas. 86 Непознати аутор 87Предговор: 88Проблем детекције и корекције грешака у тексту се незаобилазно сусреће при готово свакој врсти обраде текста, како због инхерентне особине људских бића да чине грешке, тако и због несавршености уређаја за аутоматско уношење текста. Како је у многим применама од велике важности располагање исправним подацима, веома је битно имати могућност детекције и корекције грешака у тексту који се обрађује. 89Овај проблем је обрађиван коришћењем великог броја метода из разних области рачунарске науке са мање или више успеха. Приметна је, међутим, знатна оријентисаност аутора на примену ових техника на англосаксонске језике, примарно на енглески језик. Мало је, међутим, рађено на могућностима примена ових техника у случају текста писаног на српском језику. 90Централно место магистарске тезе је објектно - оријентисана спецификација система за решавање проблема детекције и корекције грешака у случају примене на текст писан на српском језику. 91Магистарска теза садржи следећа поглавља: 921. Увод 932. Извори грешака у тексту 943. Технике корекције грешака 954. Утицај организације података на проблем корекције грешака у тексту 965. Дизајн спецификација система за проверу текста 976. Имплементациони детаљи 987. Специфичности и могућности примене техника у тексту на српском језику 998. Закључак 100У првом поглављу дат је кратак преглед проблема детекције и корекције грешака, као и генерална структура система који решава овај задатак. 101У другом поглављу се расправља о изворима грешака. Детаљно се описују основни типови грешака и указује се на особине грешака од важности за решавање проблема детекције и корекције грешака. Такође се расправља о важним факторима који утичу на појаву грешака. 102Треће поглавље садржи детаљан преглед техника за корекцију грешака у тексту. Технике су подељене у шест карактеристичних група, које су мање или више адекватне за различите врсте грешака. Дати су и експериментални резултати ефикасности описаних техника до којих су дошли поједини истраживачи. Избор технике за корекцију грешака у великој мери утиче на перформансе система за детекцију и корекцију грешака, те је од велике важности одабир праве технике за примену у одређеном случају. 103У четвртом поглављу дат је преглед популарних техника организовања речника који у највећем броју случајева учествује и у детекцији и у корекцији грешака. Већина техника за детекцију и корекцију у великој мери зависи од организације речника која омогућава адекватан и брз приступ складиштеним речима. 104Пето поглавље, које је и централно место у магистарској тези, даје дизајн спецификацију система за детекцију и корекцију грешака у тексту на српском језику. Дизајн спецификација је дата у обједињеном језику за моделирање (Unified Modeling Language - UML), који постаје de facto стандард за објектно оријентисани дизајн. Акценат је стављен на пројектовање система у коме је са лакоћом могуће мењати технике за детекцију и корекцију грешака, као и на спецификацију одговарајуће информационе структуре. 105Шесто поглавље представља анализу могуће имплементације оваквог система и указује на могуће проблеме при реализацији. Такође је размотрен проблем прилагођавања система за развој софтвера у случају писања програма који се користе на различитим језицима од енглеског. 106Као што је већ раније напоменуто, већина ових проблема се решава за текстове на енглеском језику. Седмо поглавље указује на специфичне проблеме који се јављају при покушају решавања овог проблема када се разматра текст писан на српском језику. Један од главних проблема се јавља због специфичних морфолошких особина српског језика, нарочито приликом организације речника који садржи исправне речи. Такође, српски језик има и своје статистичке карактеристике, које се природно разликују од статистичких карактеристика других језика. 107Осмо поглавље садржи закључке везане за проблем детекције и корекције грешака, као и специфичности везане за примену у случају текста писаног на српском језику. 108Захваљујем се свим члановима Комисије који су од самог почетка пратили ток израде тезе и корисним сугестијама допринели да буде јаснија и прегледнија. 109Посебну захвалност дугујем ментору др Зори Коњовић, др Душану Сурли и мр Душанки Вујовић на несебичној подршци у току израде тезе. 110Посебно се захваљујем својој супрузи Татјани на помоћи, разумевању и стрпљењу. 111Нови Сад, 1999. Аутор 1121. УВОД: 113Свака обрада текста, било да се ради о преписивању, писању, аутоматском читању или уношењу података, подразумева појављивање грешака. Ефекат ових грешака је непредвидљив - од безазлених, до грешака које изазивају велике губитке. Зато је решавању проблема корекције грешака у тексту посвећено много пажње у области рачунарских наука. 114Могућности примене техника корекције грешака у тексту су многоструке. У оквиру корисничког интерфејса, технике корекције текста служе за повећавање поузданости уноса података. У оквиру база података, релативно честа појава је дуплирање слогова због грешака у уносу података. Овде се технике детекције и корекције грешака користе и у превентивне и у корективне сврхе (проналажење дуплих записа). Свакако да се ове технике најчешће примењују у оквиру обраде текста, а за проверу исправности написаног текста. Пошто проблем корекције грешака подразумева проналажење сличних речи задатој речи, то се алатке које решавају ове проблеме могу користити и за све врсте претраживања, када је потребно пронаћи сличне записе. 115Генерално, проблему корекције грешака је могуће приступити са или без коришћења информација о контексту у коме се реч јавља. У другом случају, на који се ова теза и односи, се разматра изолована реч, тако да је немогуће избећи неке проблеме о којима ће касније бити речи. 116За решавање проблема детектовања и кориговања грешака у изолованим речима, потребно је уочити постојање четири потпроблема: 1171. детекција грешке, 1182. генерисање кандидата који исправљају грешку, 1193. рангирање кандидата, 1204. одабир једног од понуђених кандидата за корекцију грешке. 121Ови потпроблеми се најчешће третирају као засебни процеси који се најчешће извршавају секвенцјално. Ипак, неке од метода подразумевају готово истовремено решавање прва три подпроблема. 122Детекција грешке се, принципијелно, врши на два начина. Први начин подразумева проверавање постојања речи у речнику који садржи исправне речи (Dictionary lookup). Ова техника подразумева употребу меморијског простора за складиштење речника. Алтернативни начин је нешто ређи и своди се на проверу усклађености свих компонената речи (било да се ради о појединачним симболима или о групама симбола исте или различите дужине) са статистичким особинама речника. Добра страна овог метода су знатно мањи захтеви за меморијским простором, али са друге стране постоји опасност да непостојећа реч буде проглашена исправном у случају да се састоји од релативно честих компоненти речника. Перформансе обе технике за детекцију грешака нису од значаја, пошто се речи у речнику могу организовати на начин који пружа једнако брзу проверу као и проверавање појединачних компонената. 123Генерисање кандидата треба да одреди скуп речи које су довољно сличне оној речи која је детектована као погрешна. Ваља напоменути да је овај потпроблем знатно сложенији од проблема детекције грешке, пошто подразумева упоређивање одређене речи са одређеним подскупом речника који се понекад поклапа са целим речником и то техникама које су често рачунски веома сложене. Веома битна карактеристика овог проблема је критеријум који служи за проглашавање неке речи сличном или несличном посматраној речи, што утиче на величину генерисаног скупа кандидата за корекцију. Ваља напоменути да је и овај процес могуће извршити са или без употребе речника, када се генеришу статистички најчешће комбинације компонената речи неког језика. И у овом случају је могуће да резултат буду непостојеће речи, али овај пут уз знатно убрзавање процеса генерисања скупа кандидата. Такође постоје технике које не подразумевају постојање речника као таквог, већ имају уграђено (или научено) знање о речнику, као што су неуралне мреже, које често спајају функције детекције и корекције грешака. 124Рангирање кандидата има задатак да у оквиру скупа кандидата издвоји ону реч која, по неком критеријуму, највише одговара корекцији детектоване грешке. Рангирање се врши на основу израчунавања мере сличности речи са грешком и кандидата или на процени вероватноће да је неки кандидат управо исправна варијанта речи са грешком. У већини случајева рангирање се врши истовремено са одабиром, јер је у оба случаја потребно упоредити реч са грешком и реч из речника. У другим случајевима, рангирање се своди на сортирање листе кандидата по опадајућој вредности критеријума мере сличности. 125Одабир корекције је проглашавање једне од речи из листе кандидата за корекцију речи са грешком. Логично би било претпоставити да је то кандидат са највећом сличношћу са речи са грешком. На жалост, у случају који се разматра у овој тези, тј. онда када се посматрају само изоловане речи без информације о контексту, нема никакве гаранције да је одабрана права реч. Зато је у овом кораку неопходна интервенција корисника, осим у специјалним случајевима када се ради о малим речницима са међусобно веома различитим речима, као што су командни процесори или интелигентни едитори програмског кода. Већа прецизност у "погађању" праве речи - корекције за одређену грешку би се постигла коришћењем информације о контексту у коме се реч налази, уз додатно усложњавање структуре речника. 126Ваља напоменути да се перформансе раније споменутих процеса могу знатно побољшати уграђивањем знања о грешкама у систем за корекцију грешака, као и добро одабраном организацијом речника. 1272. ИЗВОРИ ГРЕШАКА 128Грешке у тексту немају једнозначне узроке. Познавање узрока и статистичких особина појава грешака у тексту може у великој мери допринети успешном развоју метода за детекцију и корекцију грешака. 129У писању текста на енглеском језику, генерално се могу уочити три врсте грешака које резултују речима које не припадају језику (не - речи). То су: 1301. Типографске грешке (the -> teh, spell -> speel) настају као резултат лоше моторне координације особе која уноси текст. Претпоставља се да је особа упозната са правилним начином писања те речи. 1312. Когнитивне грешке (receive -> recieve, conspiracy -> conspiricy) настају као резултат незнања корисника. 1323. Фонолошке грешке (abyss -> abiss, naturally -> nacherly) су специјалан случај когнитивних грешака при којима особа уноси фонетски исправну, али ортографски неисправну верзију речи. 133Најчешће је тешко распознати прави тип грешке у уносу, али, срећом, за разматрање проблема корекције грешака, то није ни битно. 134И у српском језику се јављају типографске (лоша моторика, нпр. уносу -> иносу, грешка -> гершка), когнитивне (непознавање граматике, нпр. чаршав -> чаршаф, брав -> бравца, нахраним -> нараним) и фонолошке грешке (углавном у случају једначења по звучности, нпр. врапца -> врабца, потпроблем -> подпроблем). 135Посебан проблем, којим се овај рад не бави, су грешке које као резултат дају исправне речи језика. Исправљање грешака у оваквим речима није могуће без разматрања ширег контекста. 1362.1. Основни типови грешака 137Damareu [Damareu 64] је извршио једно од првих испитивања грешака које настају при уносу текста. Ова анализа је дала резултате који се још увек користе. По његовим налазима 80% свих неисправних речи садржи тачно једну од следећа четири типа грешака: уметање, брисање, супституција и транспозиција. Погрешно написане речи које спадају у ову широку категорију се називају речи са једноструком грешком. Остале погрешне речи спадају у категорију речи са вишеструком грешком. 138Грешке које настају приликом примене OCR (Optical Character Recognition - уређај за оптичко препознавање симбола) уређаја се не јављају по истим правилима као у случају текста који уносе људи. Jones [Jones 91] примећује да: "типови {OCR} грешака широко варирају, не само у случају различитих уређаја, већ зависе и од величине фонта, квалитета улазног документа и других фактора", као и да "незанемарљив проценат OCR грешака нису један на један грешке (на пример ri - n или m - iii)". Rhyne i Wolf [Rhyne 93] класификују грешке у препознавању у четири категорије: (1) супституције; (2) неуспеси (ни један симбол не прелази праг препознавања); (3) уметања и брисања; и (4) framing грешке (грешке у мапирању један на један). 1392.2. Ефекти дужине речи 140Још један генералан закључак проистекао из испитивања грешака је да се већина речи са грешкама по дужини не разликују од оригиналних речи за више од два симбола. Овај закључак је довео до тога да већина истраживача из ове области почне да дели речнике које користе на подречнике по дужинама речи, у циљу смањивања времена претраживања. 141На жалост, не постоји много података о фреквенцији појаве грешака у функцији дужине речи. Ова карактеристика ће засигурно утицати на перформансе техника за корекцију, зато што су грешке у краћим речима теже за корекцију због мање количине информације о контексту унутар речи. Такође, по Zipf-овом закону [Zipf 35], краће речи се јављају чешће од дугих. Даље, по налазима емпиријске студије Landauer-а и Streeter-а [Landauer 73], речи високе фреквенције (то јест кратке) имају више суседа у околини једне грешке него нискофреквентне речи, што додатно отежава одабирање кандидата за исправљање грешке. Са друге стране, мања фреквенција појаве грешака у кратким речима би олакшала решавање проблема. 142Студија Pollock-а и Zamora-а [Pollock 83] извршена над 50.000 грешака које су резултовале не-речима, показује да грешке у кратким речима заиста отежавају исправљање грешака, иако им је фреквенција појаве ниска. Закључују: "иако грешке на речима дужине 3 - 4 симбола учествују са свега 9,2% у укупном броју грешака, генеришу 42% грешака у исправљању". Изгледа да опсег пропорције грешака у кратким речима зависи од случаја до случаја. На пример, Yannakoudakis и Fawthrop [Yannakoudakis 83b] су закључили да грешке у кратким речима учествују са свега 1,5% у њиховој анализи 1.377 грешака у литератури. Супротно овоме, Kukich [Kukich 90] анализом преко 2.000 типова грешака у корпусу TDD (Telecommunications Device for the Deaf - телекомуникациони уређај за глуве) конверзација долази до закључка да се преко 63% грешака јавља у речима дужине 2, 3 и 4 симбола. Ове разлике наглашавају потребу за одређивањем стварних карактеристика грешака у писању за одређену примену, пре дизајнирања и имплементације система за корекцију грешака. 1432.3. Грешке на првој позицији у речи 144Широко распрострањено веровање је да се мало грешака јавља на првом симболу у речи. Само неколико студија документује статистике грешака на првом симболу у речи. Pollock и Zamora [Pollock 83] су закључили да се 3.3% од 50.000 грешака јавља на првом симболу, а Yannakoudakis и Fawthrop [Yannakoudakis 83b] су у скупу од 568 грешака нашли 1.4% случајева грешке на првом симболу. Mitton [Mitton 87] добија резултат од 7%. Насупрот овим резултатима, Kukich [Kukich 92] наилази на 15% грешака у првом симболу током проучавања корпуса транскрибованих конверзација величине 40.000 речи. 145Занемаривање грешака на првом симболу омогућава партиционисање речника на 26 (30 у случају српског језика) подскупова, где сваки садржи речи које почињу истим симболом, редукујући тиме време претраживања. Многе технике за корекцију грешака користе ову карактеристику. Међутим, код сваког партиционисања речника, јавља се опасност да се тражена реч не налази у одабраној партицији. Потребно је направити компромис између брзог одзива и смањене тачности због могућности одабирања погрешне партиције речника. 1462.4. Ефекти распореда симбола на тастатури 147Обимне студије о дактилографији је обавила LNR Typing Research Group [Gentner 83]. Њихов циљ је био развој рачунарске симулације дактилографије. Као део истраживања Grudin [Grudin 83] је подробно анализирао дактилографске грешке које су начинили 6 искусних дактилографа и 8 почетника у процесу транскрипције 60.000 симбола из часописа. Он је открио да постоје велике индивидуалне разлике у брзини куцања и типовима грешака које настају. На пример, проценат грешака се кретао од 0.4% до 1.9% код експерата и 3.2% у случају почетника. Већина грешака коју су начинили експерти су биле грешке уметања, настале због случајног истовременог притискивања два суседна тастера, док су код почетника преовлађивале грешке супституције. 148Ипак, Grudin је открио нека генерална правила. После састављања матрице конфузије1 на основу 3.800 грешака супституције, приметио је да је 58% свих грешака супституције настало мешањем суседних тастера на тастатури. Такође је уочио да се симбол са нижом фреквенцијом појављивања обично замењује симболом са вишом фреквенцијом појављивања у тексту. На основу ових испитивања, Grudin [Grudin 81] је развио рачунарски модел способан да генерише исте типове грешака које праве људи. Неколико техника за корекцију грешака је покушало да директно искористи пробабилистичка правила која произилазе из положаја симбола на тастатури и фреквенције симбола. 1492.5. Фреквенције грешака 150Подаци о фреквенцији појаве грешака у писању су ретки. Коришћење резултата ових студија, мора да узме у обзир следеће услове: (1) величина корпуса који је испитиван; (2) начин на који је уношен корпус; (3) време настанка студије (пошто новије студије, које укључују обрађен текст у машински читљивој форми вероватно дају ниже фреквенције грешака због коришћења аутоматске провере исправности писања. Такође, потребно је одредити да ли је прављена разлика између не-речи и постојећих речи. 151Grudinova [Grudin 83] студија транскрипционе дактилографије је пронашла просечне фреквенције грешака од 1% за искусне дактилографе и 3.2% за почетнике. Корпус се састојао од 60.000 симбола куцаног текста. Није правио разлику између грешака које су резултовале не-речима и оних које су дале постојеће речи. 152Такође, Kukich [Kukich 92] и Tsao [Tsao 90] су израдили две студије грешака у писаним текстуалним конверзацијама између глувих корисника TDD-а. Резултати ових студија су дали резултате од, респективно, 6% и 5% грешака које су дале не - речи као резултат. Корпус који је користила Kukich се састојао од 40.000 стрингова, док је Tsao-ов корпус имао 130.000 стрингова. 153Pollock и Zamora [Pollock 84] су испитивали скуп база података у машински читљивом облику који се састојао од 25 милиона речи текста. Пронашли су 50.000 грешака које су дале не-речи, уз проценат појаве грешака од 0,2%. Још нижи проценат грешака је пронађен у корпусу текстова агенције AP (Associated Press) који су изучавали Church и Gale [Church 91]. Њихово испитивање је дефинисало грешку као сваку реч писану малим словима коју је одбио UNIX spell програм. Користећи ову методологију, закључили су да "AP генерише око милион речи и 500 грешака сваке недеље", што даје проценат грешака од 0,05%. 154Фреквенције грешака од 1,5% и 2,5% за текст писан руком су утврдили Wing и Baddeley [Wing 80] и Mitton [Mitton 87] респективно. Корпус који су користили Wing и Baddeley се састојао од 40 есеја са пријемних испита колеџа у Кембриџу, са укупно 80.000 речи, од којих су 1.185 имале грешку. Mitton-ов корпус се састојао од 925 есеја студената и укупно 170.016 речи од којих су 4.128 садржавале грешке. Обе студије су разматрале и речи и не-речи. Грешке које су резултовале валидним речима су учествовале у укупном броју грешака са 30%, односно 40%. Оне су углавном укључивале погрешну функцијску реч (he уместо her), замена погрешном инфлектованом формом (arrive уместо arrived) и погрешно растављање речи (my self уместо myself). Ни један од ових типова грешака се не може детектовати програмима који користе технике за детекцију грешака у изолованим речима. Petersonova [Peterson 86] студија недетектованих грешака у писању индицира да једноструке грешке доводе до валидних речи у најмање 16% случајева. Ови налази упућују на велику потребу за техникама за детекцију и корекцију које зависе од контекста. 155Грешке које настају применом OCR уређаја, по њиховим произвођачима износе 1 - 2% што резултује грешкама у речима од 5 - 10%. Ипак, недавна истраживања [Santos 92; Jones 91] указују на то да проценат речи са грешком износи од 7 - 16%, у случају примене у реалним условима (за разлику од идеалних, лабораторијских тестова). Ипак, једна недавна студија [Nielsen 92] открива да су, упркос 8,8% процената погрешних речи, перформансе претраживања информација скоро једнако добре за документе писане руком, као и за текст без грешака. Аутори упозоравају да ови резултати важе за документе чија је средња дужина 185 речи, и да би се "веома кратки записи тешко проналазили без додатних атрибута, као што су време или контекст писања". 1562.6. Фонолошке грешке 157Примери примена које обилују фонолошким грешкама укључују (1) аутоматске пословне адресаре у француском Minitel систему [Veronis 88b], (2) програме за проналажење имена у директоријуму великих предузећа [Boivie 81; Oshika 88] и (3) интерфејсе према електронским енциклопедијама који користе природни језик [Van Berkel 88]. Доминантна фонолошка природа грешака у овим апликацијама се интуитивно може објаснити тежњом људи да користе фонолошки запис за непозната имена и речи. 158Позната су два закључка везана за фреквенцију појаве фонолошких грешака. Први су дали Van Berkel и DeSmedt [Berkel 88]. Њихово истраживање се састојало у транскрипцији 123 холандских презимена, случајно бираних из телефонског именика, од стране 10 Холанђана. Открили су да је 38% презимена била погрешно записана, иако су фонолошки била исправна. Mitton [Mitton 87] је пронашао да је 44% грешака у корпусу од 925 есеја укључивало хомофоне. 1592.7. Хеуристичка правила и пробабилистичке тенденције 160Три исцрпне анализе правила појаве грешака су извршене са циљем развијања техника за корекцију грешака. Yannakoudakis и Fawthrop [Yannakoudakis 83b], су за циљ имали откривање специфичних правила по којима се јављају грешке, са намером да дизајнирају алгоритам за корекцију базиран на правилима. Саставили су базу података од 1.377 грешака издвојених из неколико извора. Пронашли су да се велики проценат грешака може предвидети коришћењем скупа од 17 хеуристичких правила, од којих се 12 своди на погрешно коришћење сугласника и самогласника у графемама2, а 5 на продукцију секвенци. На пример правила која се односе на сугласнике укључују и следећа: (1) симбол h се често изоставља у речима које садрже графеме ch, gh, ph и rh, као што су agast и tecniques; и (2) честа је грешка дуплирање или изостављање дупликата сугласника који се често јављају дуплирани. Правила везана за продукцију секвенци укључују и следећа: (3) најчешће се дужина речи са грешком разликује за један симбол од коректне речи; (4) грешке у куцању су проузроковане притискањем суседног тастера на тастатури или истовременим притискањем два тастера; (5) грешке у кратким речима су обично једноструке, итд. 161У својој студији, Pollock и Zamora [Pollock 83] су покушавали да одреде пробабилистичке тенденције, као што су откривање симбола и позиција на којима је највероватнија појава грешке, са циљем развијања технике базиране на сличности кључева. Развијали су апликацију за обраду текста у машински читљивој форми за библиотечки информациони систем. Издвојили су преко 50.000 речи из корпуса од 25 милиона речи узетих из седам база података сервиса за хемијске апстракте. Између осталог, закључили су да: (1) 0,2% речи у корпусу садржи грешке; (2) 94% посто грешака у речима су једноструке; (3) 34% свих грешака су изостављања; (4) 23% грешака се јавља на трећој позицији у речи; и (5) изузимајући неколико честих грешака у писању (the - teh), већина грешака се ретко понавља. 162Трећа студија, Kernighan-а и осталих [Kernighan 90] је срачунавала табеле вероватноће грешака за четири класе грешака у циљу директног истраживања ових вероватноћа. Ово истраживање је користило програм spell за детекцију грешака у корпусу од 44 милиона речи из вести агенције AP. Такође је коришћена техника за генерисање кандидата, која је лоцирала све могуће речи из речника које се могу добити једноструким уметањем, брисањем, супституцијом и транспозицијом од одређене не - речи. Пронађено је преко 25.000 речи са грешкама за које је постојала тачно једна исправна реч која јој одговара (неке од речи нису имале корекције зато што су садржавале више од једне грешке, док су друге имале више од једне корекције, нпр. acress - actress, acres, access). Добијена листа од 25.000 парова погрешних/исправних речи је искоришћена за састављане табела фреквенција грешака (тзв. матрице конфузије) за сваки од четири типа грешака (уметање, брисање, супституције и транспозиције). Ове фреквенције су искоришћене за процењивање вероватноће појаве сваке потенцијалне грешке. 1632.8. Уобичајене грешке 164Други извори података о грешкама у писању су листе уобичајених грешака и њихових исправки. Webster's New World Misspeller's Dictionary [Webster 83] даје 12 класа уобичајених грешака. Нажалост, мали је број техника које користе ове податке. Један изузетак је техника коју су развили Pollock и Zamora код које се проверава кратка листа речи које су често погрешно написане. 1652.9. Преглед резултата испитивања грешака 166Уопштено гледано, фреквенција појава грешака које резултују не - речима јако варира у зависности од примене, начина уноса података и времена када је истраживање обављано. Процене варирају од 0,05% у обрађеном тексту до 38% у фонетички оријентисаним апликацијама за претраживање база података. Грешке при практичној примени OCR уређаја се тренутно крећу између 7% и 16%, и у великој мери варирају у зависности од уређаја и фонтова. 167Генерални закључци везани за грешке које се јављају при дактилографском уносу података укључују и следеће: (1) већина грешака (око 80%) су једноструке инстанце уметања, брисања, супституције или транспозиције; (2) као правило, већина речи са грешком се по дужини разликује највише за 1 од исправне речи; (3) мали број грешака се јавља на првом симболу у речи. Ови закључци се употребљавају за имплементацију брзих алгоритама за корекцију једноструких грешака, као и за партиционисање речника по првом симболу речи и/или дужини речи у циљу скраћивања времена тражења. Остали закључци су: (4) распоред тастера на тастатури знатно утиче на грешке које се јављају и (5) фреквенција јављања симбола у тексту се може искористити за поправљање тачности корекције. Такође, фонолошке грешке се теже исправљају зато што резултују већим разликовањем речи од оригиналне у односу на једноструке грешке. 168Нека истраживања су се бавила индивидуалним грешкама у циљу идентификовања уобичајених грешака које би се могле описати генералним правилима, као што је тенденција дуплирања или синглирања сугласника. У другим пак студијама је покушана идентификација тенденција вероватноће појава грешака, као што је чињеница да више од трећине свих грешака представља изостављање симбола. Такође, израђене су табеле вероватноћа грешака за уметање, брисање, супституцију и транспозицију. 169Ваља напоменути да ови закључци не важе за све примене. Важно је прикупити довољно велик узорак карактеристичних грешака за одређену примену да би било могуће одабрати или развити технику за корекцију која је оптимална за ту примену. На крају, важно је приметити да су чак 40% свих грешака резултовале реалним речима, то јест онима које је немогуће детектовати техникама које разматрају изоловане речи, што појачава потребу за развијањем алгоритама који разматрају речи заједно са контекстом у коме се налазе. 1703. ТЕХНИКЕ КОРЕКЦИЈЕ ГРЕШАКА 171Корекција грешака у тексту подразумева, као што је већ раније споменуто, процесе детекције грешке и одређивања скупа погодних кандидата за корекцију грешке. Најчешће се реализација ова два процеса разматра и решава одвојено, при чему се акценат ставља на генерисање скупа кандидата за корекцију, док се процес детекције грешака своди на претраживање речника. 172Ово поглавље се бави техникама које омогућавају генерисање скупа речи сличних задатој. Основне карактеристике свих ових техника су: 173- одређивање мере сличности, односно различитости између две речи 174- операције над изолованим речима, тј. изузимање контекста у коме се налази реч у процесу одређивања сличности речи. 175Под појмом "мера сличности" се не подразумева обавезно мера у математичком смислу, већ број (реалан у општем случају) који је једнак нули ако су два стринга иста и различит од нуле ако су стрингови различити. Веома је повољно ако резултат поређења на ваљан начин рефлектује разлику или сличност два стринга. 176Такође, треба нагласити чињеницу да овде описане технике узимају у обзир само изоловане речи, што битно ограничава могућност аутоматске корекције текста и подразумева учешће оператера у процесу корекције грешака. 177Ове технике, саме по себи не омогућују аутоматску корекцију текста, зато што се не баве класификацијом скупа речи по сличности, као ни навигацијом по речнику. Зато их је потребно допунити енкапсулирајућим механизмима који ће обезбедити подршку за одабирање и класификацију речи. 178Неке од ових техника се чврсто ослањају на структуру и начин организације речника, што донекле условљава и њихово повезивање са процесом детекције грешака. 1793.1. Технике на бази минималног едит растојања 180Минимално едит растојање [Wagner 74] је минималан број едит операција (тј. уметања, брисања и супституција) потребних да се један стринг трансформише у други. 181Под едит операцијома се подразумевају брисање, уметање, супституција и транспозиција симбола у стрингу. Едит операције се поклапају са типовима грешака које је идентификовао Damerau и практично, грешке јесу едит операције. Ваља такође напоменути да се транспозиција два симбола може представити као комбинација две операције из скупа од преосталих три. На овај начин праћење и записивање трансформација се поједностављује, што битно утиче на даља разматрања. 182Такође, ради једноставније анализе, често се уметање и брисање симбола сврставају у једну групу операција која се назива indel (insertion - deletion) због њиховог симетричног ефекта на полазни и резултујући стринг. У току текста ће ова група операција често бити референцирана као индел. 183Вршење едит операција се ограничава тако да се оне морају вршити у секвенци, од првог ка последњем симболу стринга, тако да, на пример, после извршене едит операције на првом симболу стринга више није могуће поново интервенисати на тој позицији. Такође, на једном симболу је дозвољено извршити само једну едит операцију. 184Када се један стринг трансформише у други, могуће је бележити све операције које су извршене да би се од почетног стринга дошло до завршног. Постоји више техника за бележење ових операција. Неке од њих су: праћење (trace), поравнавање (alignment или matching) и листа операција (listing). 185Праћење се своди на исцртавање веза између симбола два стринга по следећим правилима (Слика 1): 1861. сваки симбол сме да има највише једну придружену везу, 1872. везе не смеју да се секу, 1883. веза између два иста симбола у изворном и резултујућем стрингу значи да није дошло до измена, 1894. веза између два различита симбола значи да је дошло до супституције симбола из изворног стринга симболом из резултујућег стринга, 1905. симбол у изворном стрингу коме није придружена веза је обрисан, 1916. симбол у резултујућем стрингу коме није придружена веза је уметнут. 192и 193н 194д 195у 196с 197т 198р 199и 200ј 201а 202и 203н 204т 205е 206р 207е 208с 209Слика 1 - Пример методе праћења 210На овај начин, гледајући са лева на десно, могуће је утврдити које су едит операције трансформисале полазни у резултујући стринг; међутим, није могуће утврдити њихов тачан редослед. Метода праћења је аналитички најсиромашнија у скупу овде описаних метода за записивање трансформације стрингова. 211Други начин за записивање се назива поравнавање. У овом случају два стринга се записују тако да буду једнаке дужине уз евентуално уметање празног симбола (ø), по следећим правилима (Слика 2): 2121. испод симбола почетног стринга који се бришу, у резултујући стринг се уписује знак ø, 2132. изнад симбола резултујућег стринга који се умећу, у почетни стринг се такође уписује знак ø, 2143. уколико су симболи на истим позицијама различити, долази до супституције, 2154. уколико су симболи на истим позицијама у почетном и резултујућем стрингу исти, није било промене. 216Из овог записа је могуће реконструисати след едит операција које су довеле до трансформације полазног у резултујући стринг. Метода поравнавања је аналитички богатија од методе праћења, тако да је од једне анализе добијене методом праћења могуће конструисати неколико анализа методом поравнавања. 217и н д у с т ø р и ј а 218и н ø ø ø т е р е с ø 219Слика 2 - Пример методе поравнавања 220Листа операција је начин записивања едит операција у коме се са леве стране наводи стринг у различитим фазама трансформације, а са десне стране едит операција која се извршава. На тај начин се добија директан след едит операција који је трансформисао полазни у резултујући стринг (Слика 3). Једино ограничење које се мора поштовати је да се два суседна стринга са леве стране смеју разликовати само за резултат елементарне едит операције која се налази између њих са десне стране. 221Ова метода је најпрактичнија за анализу, пошто носи највише информација и практично даје алгоритам за превођење почетног у резултујући стринг, док претходне две методе највећу примену имају као начини репрезентације трансформација. 222индустрија 223обриши д 224инустрија 225обриши у 226инстрија 227обриши с 228интрија 229уметни е 230интерија 231замени и са е 232интереја 233замени ј са с 234интереса 235обриши а 236интерес 237Слика 3 - Пример листе операција 238Очевидно је да је трансформација једног стринга у други коришћењем елементарних едит операција уз поштовање раније наведених ограничења, могућа на много различитих начина. Ипак, питање од суштинског значаја је: да ли је могуће одредити минималан број едит операција које ће довести од почетног до резултујућег стринга? 239Одговор на ово питање је потврдан. Постоји начин да се одреди горе наведени број који се назива Damerau-Levenshtein мера [Damerau 64] [Levenshtein 66]. 240Levenshtein је увео два веома сродна концепта растојања d(a,b) између два стринга. Први је најмањи број супституција и индела који су потребни да би се стринг a трансформисао у стринг b. Други концепт је нешто строжији и дефинише d(a,b) као најмањи број индела потребних да се полазни стринг трансформише у резултујући, с тим што супституције нису дозвољене. 241У складу са претходно изнетим методама, растојање између два стринга се може дефинисати на следећи начин: 2421. Нека су елементарне операције супституција и индели. 2432. Посматрајмо све листе операција трансформације a у b. 2443. Нека је дужина сваке листе операција број елементарних операција које садржи. 2454. Растојање је тада једнако минималној дужини листе из скупа листа операција. 246Да би се дошло до строжијег концепта, могуће је ограничити скуп елементарних операција само на инделе, или редефинисати дужину листе операција као: 247(број индела) + w(број супституција), где је w>2 248Алгоритми за одређивање растојања дефинисаног под тачком 4 претходне дефиниције су централни део техника базираних на минималном едит растојању. 249Једна од често коришћених функција растојања, која се популарно зове једноставно растојање је базирана на тежинским факторима везаним уз елементарне операције. Тачније, узима се да свака могућа супституција и индел имају придружен тежински фактор који је већи или једнак нули. Једноставно растојање је тада сума тежинских фактора елементарних операција садржаних у листи операција. Ако су сви тежински фактори једнаки јединици тада је једноставно растојање једнако броју елементарних операција и добија се прво Levenshtein-ово растојање. Друго растојање се добија у случају када се свим инделима додели тежински фактор 1, а свим супституцијама тежински фактор већи или једнак са 2. 250За означавање тежинских фактора и елементарних операција, обично се користи следећа нотација: 251Супституција x→y 252w(x,y) 253Брисање x 254w(х,ø)или wdel(x) или w-(x) 255Уметање у 256w(ø,у)или wins(у) или w+(у) 257Ако је дозвољено коришћење празног симбола ø као аргумента функције w, тада се још дефинише да је w(ø,ø)=0 и w се назива проширеним w. Ако је алфабет симбола коначан, тежински фактори се могу представити матрицом, где се х налази у врстама, а у у колонама матрице (Слика 4). 258ø 259у 260Ø 2610 262тежински фактори уметања w+(у)= w(ø,у) 263Х 264тежински фактори брисања w-(x)= w(х,ø) 265тежински фактори супституције 266Слика 4 - Матрица проширених тежинских фактора 267Свако проширено w води до неке функције растојања d. пошто је сваки симбол такође и стринг дужине један, а ø је стринг дужине нула, за све елементе х и у могуће је упоредити 268w(х,у) са d(х,у) 269w(х, ø) са d(х, ø) 270w(ø,у) са d(ø,у). 271Може се догодити да w и d буду једнаки у свим поређењима. Ако је ова претпоставка тачна, каже се да се d слаже са w. У том случају, w се може сматрати ограничењем функције d које важи за стрингове дужине 1 и 0. Такође, процес извођења функције d из тежинског фактора w се може сматрати проширивањем дефиниције растојања тако да важи за стрингове свих дужина. 272У математичкој литератури, реч "растојање" се обично користи да опише функцију која задовољава аксиоме метрике: 2731. Особина ненегативности: d(a,b) ≥ 0 ( a и b; 2742. Особина нуле: d(a,b) = 0 akko a = b; 2753. Симетрија: d(a,b) = d(b,a) ( a и b; 2764. Неједнакост троугла: d(a,b) + d(b,c) ≥ d(a,c) ( a, b, c; 277Иако се у овом разматрању реч "растојање" не ограничава на овај начин, ипак се мора нагласити да су ове особине веома интересантне. Често се тежински фактори одређују управо на такав начин да изведена функција d задовољава аксиоме метрике. 278Алгоритми који се најчешће користе за израчунавање растојања између два стринга се углавном заснивају на коришћењу особина метода праћења и поравнавања, зато што би се коришћењем методе листе операција генерално дошло до споријег и компликованијег алгоритма. 279Први корак у алгоритму је да се пронађе једноставно растојање на основу методе поравнавања, док други корак подразумева проналажење оптималног поравнавања, које одговара најмањем броју едит операција. Ако су стрингови дужине m и n тада су доминантни делови временске и просторне сложености оваквог алгоритма пропорционални mn. За m = n, сложеност је пропорционална n2, што ову класу техника сврстава у алгоритме квадратне сложености. 280Нека су два стринга а и b са појединачним симболима означеним са аi и bj, дужине m и n. Нека су тежински фактори за супституцију дати са w(х,у), за брисање са w(х, ø) и за уметање са w(ø,у). Нека аi и bj означавају почетне сегменте стрингова a1 a2... ai и b1 b2... bj. (укључујући ту и случајеве када су почетни сегменти дужине нула, a0 и b0, то јест празни стрингови). Такође важе релације am=a и bn=b. 281Угао æ 2820 2831 2842 2853 286. 287. 288. 289n 2900 291МАРГИНА 292<--Врста 0 2931 2942 295МАРГИНА 296. 297ТЕЛО 298. 299. 300m 301á Колона 0 302Слика 5 - Матрица која се користи за динамички алгоритам 303Поступак тече рекурзивно унапред, и проналазе се растојања d(ai,bj), за сукцесивно веће i и j, док се не дође до d(am,bn)= d(a,b) што је и тражено растојање. Ове вредности се обично бележе у матрици димензија m x n, с тим што вредност на позицији (i, j) одговара растојању d(ai,bj). 304Поступак за одређивање растојања почиње од очевидне вредности d(a0,b0)=0, које одговара пољу (0,0). Потом се користи рекурзивна релација која повезује вредност ћелије са координатама (i, j) са вредностима претходних ћелија (i-1, j), (i-1, j-1) и (i, j-1). У случају када су i или j једнаки нули, што значи да ћелије претходнице имају негативне координате, користе се вредности ћелија које имају ненегативне координате. Вредност за одређену ћелију се рачуна тек после израчунавања вредности ћелија претходница. 305Следи рекурзивна релација која служи за израчунавање вредности ћелије са координатама (i, j): 306Тежински фактор w се одређује на основу области у којој се примењује алгоритам, односно на основу карактеристика појаве различитих врста грешака. Ваља приметити да овај фактор може бити представљен скаларом (обично 1 тј. догодила се промена), једнодимензионалним вектором (карактеризација вероватноћа догађања различитих класа грешака) те вишедимензиналним матрицама (карактеризација вероватноћа догађања сваке појединачне могуће грешке, као и позиције у речи где се грешка догађа). Из овога следи да је алгоритам могуће профињавати на основу емпиријски добијених карактеристика појаве грешака. Veronis [Veronis 88a] је развио алгоритам који је рачунао едит растојање на основу сличности фонема, као покушај да реши проблем фонетских грешака које су честе у енглеском језику. 307Процес генерисања скупа кандидата за корекцију грешке се своди на израчунавање едит растојања речи са грешком и речи из постојећег речника. У скуп кандидата улазе оне речи које имају растојање мање од задатог (претпостављеног) растојања. Одређивање референтног растојања у великој мери зависи од захтеване финоће претраживања речника, као и од тежинских фактора. 308У конкретној имплементацији алгоритама из ове групе могуће је знатно побољшати перформансе, првенствено путем увођења претпоставки о фреквенцији и природи грешака, те погодним организовањем структура података. 309Специјалан случај примене ове технике се заснива на коришћењу претпоставке да се у највећем броју случајева јављају грешке које су резултат само једне едит операције над стрингом, што значи да се оштећени стринг од оригиналног разликује само за један симбол по садржају, те да се по дужини не разликује за више од један. У том случају се конструишу технике које подразумевају генерисање скупа кандидата који се састоји од свих речи које се добијају од дате речи генерисањем једне грешке и проверавањем добијених речи у речнику. За реч дужине n и алфабет од 30 слова, потребно је генерисати и проверити 30(n+1) речи добијених уметањем, n речи добијених брисањем, 29n речи добијених заменом и n-1 речи добијених транспозицијом слова, што укупно даје 61n + 29 речи за проверу. 310Постоји техника која смањује време одзива а своди се на складиштење сваке речи у речник |x|+1 пута, где је |x| дужина речи, при чему се сваки пут изоставља по једно слово. Техника се заснива на претпоставци да је најчешћа врста грешака брисање и користи hash технику. 311Као алтернатива динамичком програмирању се користе trie структуре ради скраћивања времена претраживања. Ове технике се своде на коришћење хеуристичких техника у којима се речник исправних речи смешта слово по слово у псеудо-бинарно стабло. Претражује се мали подскуп базе података (одабране гране стабла) уз проверавање грешака уметања, брисања, замене и транспозиције. [Muth 77]. Dunlavey [Dunlavey 81] описује алгоритам назван SPROOF, који складишти речник у trie структуру тј. "огромни коначни аутомат који препознаје све и само оне речи које су у речнику". Претраживање се изводи тако што се пролази кроз чворове структуре уз повећавање едит растојања све док се не дође до кандидата за корекцију на листовима стабла. Сличну технику је користио и Boivie [Boivie 81] у програму da који је служио као помоћ у претраживању података и постао основа за Taylor-ов [Taylor 81] програм за исправку текста grope. 312Технике на бази минималног едит растојања су примењене на готово све проблеме у корекцији текста, укључујући ту процесирање текста, командне процесоре, интерфејсе на бази природног језика итд. Тачност ових техника зависи од коришћеног алгоритма и апликације у којој се примењују. Damerau даје податак да је техника достигла степен корекције од 95% за једноструке грешке у писању на тест скупу од 964 погрешно написаних речи дужине 5 и више симбола, уз коришћење речника од 1.593 речи. У случају урачунавања и вишеструких грешака, овај проценат је био 84%. Durham и остали [Durham 83] су дошли до резултата од 27% за веома једноставан, брз и "ненаметљив" алгоритам за исправку једноструких грешака са речником од око 100 кључних речи. Иако се овај проценат чини веома ниским, алгоритам који је примењен у командном процесору је наишао на велико одобравања код крајњих корисника управо због своје "ненаметљивости". Kukich [Kukich 90] је испитивала алгоритам примењен у програму grope у истраживању везаном за примену у захтевној апликацији за синтезу говора на основу текста. У тест скупу се налазило 170 речи са грешком, од тога 25% са вишеструким грешкама, а са чак 63% кратких речи (дужине 2, 3 и 4 симбола). Добијени резултат је износио 62% уз коришћење речника од 1.142 речи. Друге технике, као што су векторско растојање и неуралне мреже су давале боље резултате и до 10%. Muth и Tharp [Muth 77] пријављују проценат исправљених речи од чак 97% за свој алгоритам базиран на trie структури уз коришћење тест скупа од 1.487 речи, мада не дају величину речника и средњу дужину речи. 3133.2. Технике на бази кључева сличности 314Идеја коју користи ова техника је да се сви стрингови мапирају (трансформишу) у такав кључ да слични стрингови имају исти или слични кључ. Тако, када се генерише кључ оштећеног стринга, као резултат се добија показивач на све сличне стрингове у речнику. Ова техника пружа велику брзину, зато што није потребно да се оштећени стринг директно упоређује са свим осталим стринговима у речнику. Кључеви се најчешће генеришу на основу симбола речи и неких статистичких резултата. 315Једна од првих имплементација алгоритама на бази кључева сличности је патентирана још 1918. године [Odell 18] и назива се SOUNDEX. Она се заснива на мапирању речи из речника и речи са грешком у кључ који се састоји од првог симбола речи и низа цифара које се одређују на основу пратећих симбола речи по правилима из следеће табеле, уз елиминисање вишеструког појављивања симбола из речи и избацивање нула и вишестурког појављивања цифара из кључа. 316A, E, I, O, U, H, W, Y 317 0 318B, F, P, V 319 1 320C, G, J, K, Q, S, X, Z 321 2 322D, T 323 3 324L 325 4 326M, N 327 5 328R 329 6 330Табела 1 - Вредности за SOUNDEX кључ 331Пример: 332Стринг 333Кодирање 334Избацивање нула и дуплих симбола 335Bush 336B020 337B2 338Busch 339B0220 340B2 341Weinstein 342W00523005 343W523 344Wejnstejn 345W02523025 346W253 347Quayle 348Q00040 349Q4 350Kwail 351K0004 352K4 353Sarvan 354S06105 355S615 356Savran 357S01605 358S165 359Saravan 360S060105 361S615 362Savrak 363S01602 364S162 365Chemical 366C0050204 367C524 368Chemicial 369C00502004 370C524 371Chemcial 372C0052004 373C524 374Chemcal 375C005204 376C524 377Очевидно је да овакав систем даје прилично непрецизне резултате, уз наглашене проблеме приликом примене на фонетске грешке. Такође, не постоји повољан алгоритам који би рангирао резултате по сличности. Очевидна предност овакве технике је у могућности брзог израчунавања кључа за задати стринг. Ова техника је позната по имплементацији у систему за резервацију авионских карата [Davidson 62]. Приметна је употреба SOUNDEX система за упоређивање стрингова у савременим системима за управљање базама података (Oracle, Access). 378Још једна интересантна техника на бази кључева сличности се назива SPEEDCOP [Pollock 84] и служи за исправљање погрешно написаних речи које садрже највише једну грешку. Развијена је на основу резултата истраживања 50.000 грешака из седам база података апстраката из области хемијских наука. 379За сваку реч из речника се конструише кључ, а потом се речник индексира по новим кључевима. Грешка се исправља тако што се конструише кључ за погрешно написану реч и проналази у листи кључева. Потом се све суседне речи (потенцијални кандидати за корекцију) у оба смера секвенцијално проверавају и траже се речи које би се могле добити модификацијом речи са грешком применом једне операције уметања, брисања, супституције или транспозиције. 380Ова техника, заправо, користи два типа кључева формираних на основу статистичких закључака. Оба садрже по једну појаву свих слова која се јављају у речи, сортираних на одређени начин. 381Први је тзв. skeleton (кичмени) кључ, који се генерише тако што се на првој позицији оставља први симбол стринга који прате сугласници речи са елиминисаним понављањима симбола по реду појављивања у речи а потом самогласници по реду појављивања, са такође елиминисаним понављањима симбола. Овај кључ се генерише на наведени начин због следећих претпоставки: 3821. први симбол у речи је највероватније исправан, 3832. сугласници обично носе већу количину информација од самогласника, 3843. ова организација чува оригинални след сугласника, 3854. кључ се не мења у случају дуплирања или укидања дуплирања симбола, као ни у случају већине грешака транспозиције (зато што ту обично мењају место сугласник и самогласник). 386Део кључа који је најосетљивији на грешке је у подручју првих сугласника. Што се пре појави грешка у речи, веће је растојање између кључева исправне и речи са грешком. Овај кључ је прилично интуитиван и сличне речи имају сличне кључеве. 387Други, omission (кључ испуштања) кључ садржи прво сугласнике поређане по обрнутом редоследу фреквенције појављивања испуштених симбола, статистички: RSTNLCHDPGMFBYWVZXQKJ (симбол R се најчешће испушта, док се симбол J најређе испушта). Потом следе самогласници, уз елиминисано понављање симбола, по реду појављивања. Овај кључ треба да исправи проблем кичменог кључа, тј. његову осетљивост на појаве грешака на почетку речи. Из статистичког испитивања грешака, закључено је да се најчешће појављују грешке испуштања (брисања) симбола. За разлику од претходног кључа, овај је много мање интуитиван. Нарочито ваља приметити да нека реч има исти кључ испуштања као и њени анаграми. 388Пример: 389Стринг 390Skeleton кључ 391Omission кључ 392BUSH 393BSHU 394BHSU 395BUSCH 396BSCHU 397BHCSU 398WEINSTEIN 399WNSTEI 400WNTSEI 401WEJNSTEJN 402WJNSTE 403JWNTSE 404QUAYLE 405QYLUAE 406QYLUAE 407KWAIL 408KWLAI 409KWLAI 410SARVAN 411SRVNA 412VNSRA 413SAVRAN 414SVRNA 415VNSRA 416SARAVAN 417SRVNA 418VNSRA 419SAVRAK 420SVRKA 421KVSRA 422CHEMICAL 423CHMLEIA 424MHCLEIA 425CHEMICIAL 426CHMLEIA 427MHCLEIA 428CHEMCIAL 429CHMLEIA 430MHCLEIA 431CHEMCAL 432CHMLEA 433MHCLEA 434CHIMICAL 435CHMLIA 436MHCLIA 437MICROELECTRONICS 438MCRLTNSIOE 439MCLNTSRIOE 440CIRCUMSTANTIAL 441CRMSTNLIUA 442MCLNTSRIUA 443LUMINESCENT 444LMNSCTUIE 445MCLNTSUIE 446MULTINUCLEATE 447MLTNCUIEA 448MCLNTUIEA 449MULTINUCLEON 450MLTNCUIEO 451MCLNTUIEO 452CUMULENE 453CMLNUE 454MCLNUE 455LUMINANCE 456LMNCUIAE 457MCLNUIAE 458COELOMIC 459CLMOEI 460MCLOEI 461MOLECULE 462MLCOEU 463MCLOEU 464CAMERAL 465CMRLAE 466MCLRAE 467CARAMEL 468CRMLAE 469MCLRAE 470MACERAL 471MCRLAE 472MCLRAE 473LACRIMAL 474LCRMAI 475MCLRAI 476Из примера се види да, и поред побољшане финоће, остаје уочљив проблем са фонолошким грешкама (ваља ипак приметити да је ова техника ограничена на речи са једном грешком). 477SPEEDCOP техника, у циљу максимизирања брзине одзива уз што тачније резултате, користи алгоритам из четири корака од којих се следећи користи ако претходни корак не доведе до решења. Ови кораци су следећи: 4781. проверава се речник честих грешака у писању, 4792. примењује се корекција коришћењем skeleton кључа, 4803. примењује се корекција коришћењем omission кључа, 4814. користи се потпрограм који проверава спојеност функцијских речи (речи које немају лексичко значење већ само синтаксичку функцију). 482По извештају Pollock-а и Zamora-е, последњи корак је повећавао проценат корекције за свега 1%-2%, али је био потпуно прецизан. 483Рангирање кандидата за исправљање грешке је вршено по два критеријума: 4841. релативна фреквенција одређене речи у бази података, 4852. вероватноће догађања грешака које од речи из речника доводе до погрешно написане речи. 486Проценат успешно исправљених грешака при примени ове технике износио је од 77% до 96% приликом исправљања једноструких грешака у седам база података које су коришћене у експерименту. Ове грешке су се појавиле у 94% грешака које су разматрали. Укупна тачност алгоритма је процењена на 74% до 88%. У експерименту је коришћен речник од 40.000 речи. 487Аутоматизовани систем за обуку PLATO [Tenczar 72] користи технику која спада у технике на бази кључева сличности у ширем смислу. И у овом случају се генеришу кључеви за сваку реч из речника и речник се индексира по кључевима. Међутим, кључеви који се користе се формирају на основу скупа људских когнитивних карактеристика, састављеног од стране аутора. Карактеристике по којима се формирају кључеви укључују следеће: 488* дужина речи, 489* први симбол речи, 490* садржај речи, 491* редослед симбола у речи, 492* изговор речи. 493Свака од карактеристика у кључу је представљена пољем битова одређене дужине. Кључеви могу да се проширују додавањем нових поља. 494Кључеви речи из речника се сортирају. Приликом обраде улаза, за унету реч се конструише кључ по задатим правилима и проналази се исти или сличан кључ методом бинарног претраживања. 495Технику су развили Tenczar и Golden и тестирали је на речнику који је садржавао уобичајене грешке у писању. Техника је успела да исправи 95% примера узетих из речника. Такође су испробали примену на речнику од 500 најчешће коришћених енглеских речи и дошли до закључка да техника даје задовољавајуће резултате тј. парови који су били проглашени грешком и корекцијом су се углавном разликовали за само један симбол. 496Алгоритам назван реконструкција токена је патентирао Bocast [Bocast 91]. Заснива се на израчунавању мере fuzzy сличности између речи. Алгоритам прима оштећени стринг и реч из речника и враћа меру сличности која се срачунава на основу средње вредности суме четири индекса са емпиријски придруженим тежинама, који мере најдуже поклапајуће подстрингове са почетка и краја речи. Техника раздељује речник на подскупове у којима су речи које имају исти почетни симбол c и дужину n. Простор по коме се претражује се простире од подскупа ci,nj до подскупова c*i,nj ( 1, тако да се прво прегледају речи са малим разликама у дужини, а потом речи које почињу осталим симболима у речи са грешком. 497По извештају аутора, алгоритам заснован на овој техници је довољно једноставан да буде веома брз. Показана тачност од 78% при првом покушају на тест скупу од 123 речи који је укључивао 15 речи са више грешака, превазилази тачност четири популарна комерцијална програма за корекцију текста примењена на истом тест скупу. 4983.3. Технике засноване на правилима 499Технике засноване на правилима су алгоритми или хеуристички програми који представљају директан покушај трансформације знања о уобичајеним правилима појаве грешка у правила за превођење речи са грешком у исправне речи. Процес генерисања кандидата се састоји у примењивању свих применљивих правила на оштећен стринг и памћењу свих исправних речи из речника које се појаве током овог процеса. Рангирање се најчешће врши додељивањем нумеричког резултата сваком кандидату на основу раније одређене процене вероватноће да се појавила грешка коју је примењено правило исправило. 500Yannadoudakis и Fawthrop [Yannakoudakis 83] су развили knowledge-based програм за корекцију текста заснован на скупу правила добијених из испитивања 1.377 речи са грешкама. Њихов циљ је био развијање свеобухватног система за корекцију. Систем је тестиран на скупу од 1.534 речи са грешкама уз речник од 93.769 речи. Због тога што су нека од правила користила знање о највероватнијој дужини исправљене речи, техника користи речник који је партиционисан на велики број подскупова у зависности од дужине речи и првог слова. Генерисање кандидата се састоји од претраживања специфичне партиције речника у потрази за речима које се од оштећене речи разликују за само једну или две грешке. У случају проналажења више кандидата, они се рангирају по предефинисаној процени вероватноће догађања правила. Резултати су показали да се исправна реч налазила у одабраној партицији 1.153 пута или у 75% случајева, при чему се, после рангирања, исправна реч налазила на првом месту у 90% случајева, што даје тачност од 68% (90% од 75%). 501Специјализован систем за корекцију на бази правила је дизајниран [Means 88] за уношење текстова који по садржају представљају природан језик, али са великом фреквенцијом скраћеница, акронима и речи из жаргона. Овај систем прво проверава скуп морфолошких правила у потрази за уобичајеним грешкама (у енглеском, нпр. пропуштање удвајања сугласника пре додавања суфикса -ing). После тога, користи се скуп правила за проширивање скраћеница, у циљу утврђивања могућности да се реч са грешком прошири у реч из речника. Уколико нема резултата после примене обе методе, користе се правила за трансформисање стринга са једном грешком, укључујући и могућност да је случајно уметнута празнина у реч. 5023.4. Технике засноване на n-грамима 503Под словним n-грамима се подразумевају подсеквенце речи дужине n симбола, где је n обично један (када се говори о униграмима), два (биграми) или три (триграми). 504Пре свега, технике коришћења n-грама пружају алтернативни метод детекције грешака у тексту. Наиме, могуће је испитивати све n-граме речи неког текста и тражити их у статистичкој табели n-грама. Уколико се покаже да реч садржи n-грам који не постоји или има јако малу фреквенцију, могуће је да се ради о грешци. Ове технике захтевају претходну обраду веома великог речника или корпуса да би се могла саставити задовољавајућа табела. 505N-грами се обично организују у векторе (у случају униграма) или матрице (у општем случају n-димензионалне). Ове матрице су у општем случају квадратног облика, димензије броја симбола у разматраном алфабету, евентуално увећаном за бланко знак и/или знакове интерпункције. Садржај поља табеле могу бити фреквенције или проценти/вероватноће појаве n-грама одређених координатама у речима, или просто нуле и јединице који указују на то да се одређени n-грами не јављају или јављају у неком речнику. У потоњем случају ради се о бинарним n-грамима. На овакав начин се складиште непозициони n-грами, тј. не узима се у обзир информација о томе на коју позицију у речи се односи информација о појави n-грама. 506Са друге стране, користе се и позициони n-грами, који се генерално смештају у матрице димензионалности n+1, где додатна димензија означава позицију у речи на којој се налази n-грам. 507Словни n-грами, укључујући ту и триграме, биграме и/или униграме, се користе на више начина у оквиру техника за препознавање и исправљање текста. Такође се користе у оквиру OCR програма за утврђивање лексичке синтаксе речника и сугерисање исправних решења. Користе се у програмима за кориговање спеловања као приступни кључеви у речник за лоцирање кандидата за корекцију и као лексичка обележја за срачунавање мере сличности. Такође се користе за представљање речи и грешака као вектора лексичких обележја на које је могуће применити традиционалне и остале векторске мере, у циљу лоцирања и рангирања кандидата за корекцију. Неке од техника за корекцију базираних на n-грамима извршавају процесе детекције грешке, проналажења и рангирања кандидата као три посебна корака, док друге технике сва три корака спајају у један процес. 508Објашњење традиционалног коришћења n-грама за коришћење у OCR-у су дали Riseman и Hanson [Riseman 74]. Речник се партиционише на субречнике по дужини речи и за сваки субречник се конструише бинарна n-грам матрица. Ове матрице дају одговор на питање "Да ли постоји реч у речнику која има слова ( и ( на позицијама i и j, респективно" и на тај начин одражавају синтаксу речника. Исправност стринга који се добија као резултат OCR процеса се тестира тако што се проверава да ли сви његови n-грами имају вредност 1. Ако стринг има једну грешку, имаће вредност 0 за бар један бинарни n-грам. Ако се пронађе више од једне вредности 0, позиција грешке је одређена индексом матрице који је заједнички за n-граме са вредношћу 0. Кандидати за корекцију се могу пронаћи тражењем логичког пресека врста и колона одређених заједничким индексом неисправних n-грама. Ако пресек резултује само једним n-грамом са вредношћу 1, грешка се може исправити, а ако се пронађе више од једне могућности за корекцију, реч се одбацује као недовољно јасна. 509Ова техника је тестирана на скупу од 2.755 речи од 6 симбола. Пронађено је да су позиционе три-грам матрице (које су показале најбоље резултате у поређењу са осталим позиционим и непозиционим n-грам матрицама) у стању да детектују 98,6% грешака и да исправе 62,4% грешака. Ова техника има најмање једну предност у односу на прегледање речника, а то је да уклања потребу за великом количином претраживања у речнику. Мана је могућност да корекција грешке резултује у неисправној речи у ретким случајевима, док је много озбиљнија мана у томе што је техника дизајнирана да реагује само на грешке замене, док није јасно какви су резултати у случају појаве осталих типова грешака, као што су уметања, брисања, транспозиције и framing грешке. 510Предложене су и две технике засноване на хардверу које би користиле базу n-грама паралелно [Ullman 77]. Предложена техника је у стању да пронађе све исправне речи које се разликују од улазног стринга за до две грешке уметања, брисања, супституције и обртања и користи процесирање бинарних n-грама у паралели. Имплементиран је и алгоритам за OCR препознавање и исправљање на 16 процесорској машини облика хиперкоцке [Henseler 87]. Ова техника је користила базу триграмских фреквенција уместо биграма. Резултати су показали да је пронађено 95% грешака, од којих је 100% исправљено. 511Angell и остали [Angell 83] су дали технику која користи триграме за исправљање грешака у тексту. Ова техника израчунава меру сличности базирану на броју (непозиционих бинарних) триграма заједничких речи са грешком и речи из речника. Мера сличности је једноставна фунцкција облика 2(c/(n+n')), где је c број триграма заједничких речи из речника и речи са грешком, док су n и n' дужине посматраних речи. Аутори ову функцију називају "добро познати Dice-ов коефицијент". Такође предлажу формирање инверзног индекса за речник који користи триграме као кључеве за приступ. Триграми речи са грешком се могу искористити за приступање само оним речима из речника које имају најмање један заједнички триграм са посматраном речи са грешком, тако да је онда потребно израчунавати сличност само за речи из тог подскупа. 512Ова техника је постигла укупну тачност од 76% на тест скупу од 1.544 речи са грешкама, уз коришћење речника од 64.636 речи. Аутори технике су анализирали зависност перформанси у односу на врсте грешака и дошли до закључка да техника ради "веома добро за грешке брисања и уметања, адекватно за грешке замене, али веома лоше за грешке транспозиције". Иако нису анализирали зависност перформанси од дужине посматраних речи, приметили су да није за очекивати добре резултате на кратким речима, зато што једна грешка може да проузрокује да ни један триграм у речи не буде исправан. Средња дужина речи са грешком у њиховом тест скупу је била 8,4 симбола. 513Проблем са Dice-овим коефицијентом је тај што тежи да прави грешке у ситуацијама када се реч са грешком цела налази у исправној речи и обрнуто. На пример, за реч са грешком concider техника је доделила меру сличности 0,70 речи cider, а 0,71 речи consider. Овај проблем је разрешен коришћењем чињенице да се реч са грешком углавном не разликује од речи из речника за више од једног симбола и последичним мењањем функције мере сличности у (c/max(n,n')). Показало се да оваква функција исправља грешку која се јавља у случају садржавања једне у другој речи, без битног утицаја на тачност приликом примене на речи са више грешака. 514Слична технике за корекцију засноване на триграмима су предложили и развили Kohonen [Kohonen 80] и DeHeer [DeHeer 82] за обраду текста у апликацији за проналажење информација. Сличну техику, анализу трифона су развили Van Berkel и DeSmedt [VanBerkel 88] за примену у апликацији са интерфејсом који користи природни језик уз претпоставку појављивања правилних именица код којих се често јављају фонетичке грешке. Она прво примењује скуп правила за конверзију из графема у фонеме, а потом користи инверзни трифонски индекс за проналажење кандидата за корекцију. Ова техника се у тестовима показала веома успешном, успевајући да исправи 94% из тест скупа од 123 погрешно написана холандска презимена. Коришћени речник се састојао од 254 холандских презимена одабраних на случајан начин из телефонског именика. Упоређивањем са неким познатим нефонетским техникама дошли су до закључка да ова техника даје боље резултате за 4 до 40 процената на овом тест скупу. 515Поред већ наведених, имплементиран је и тестиран већи број техника које користе традиционалне и нове векторске метрике, а заснивају се на репрезентацији речи у облику n-грамских вектора. Већина ових техника спаја сва три потпроцеса у један процес. Главна идеја код свих ових техника се може представити на следећи начин: (1) Сваки елеменат речника се представља као једна тачка у n-димензионалном простору лексичких особина и (2) Оштећен стринг се потом пројектује у тај простор и испитује се његово растојање до најближих суседа. Униграми, биграми и триграми су три могућа кандидата за координате лексичког простора. Исправне и речи са грешкама се могу представити као ретко распоређени вектори у таквом простору. За мерење растојања између таквих вектора између осталих у обзир долазе Хамингова, косинусна и еуклидска метрика. 516У свом раду Kukich [Kukich 92] је испитивала тачност три векторске метрике над истим тест скупом и речником који је коришћен за тестирање grope технике (која има тачност од 62%). Тест скуп је садржао 170 речи са једноструким и вишеструким грешкама (при чему је било готово две трећине кратких речи дужине до 5 симбола), док је речник садржавао 1.142 речи. Коришћени су вектори са 790 координата заснованих на униграмима и биграмима за репрезентацију речи и грешака. Ова техника је показала тачност од 54% за метрику која користи еуклидско растојање, 67% за Хамингово растојање и 75% за метрику која користи косинусно растојање. 517Следећи скуп техника је веома сличан n-грамским техникама које користе векторске просторе. То су меморије корелационих матрица (Correlation Matrix Memory - CMM). Оне представљају речник од m речи као матрицу n x m n-димензионалних вектора са лексичким карактеристикама. Процес корекције грешака се изводи множењем n-димензионалног вектора који представља лексичку структуру речи са грешком са n x m димензионалном матрицом која представља речник. Као резултат се добија m-димензионални вектор у којем i-ти елемент представља i-ту реч из речника. Елеменат који има највећу вредност је онај који има највећу корелацију са речи са грешком и стога се проглашава исправном вредношћу. 518Cherkassky и остали [Cherkassky 92] су детаљно испитивали коришћење биграмских и триграмских карактеристичних вектора у CMM моделима. Коришћена су два тест скупа случајно генерисаних једноструких грешака и то један за речи средње дужине (5-7 симбола) и други за дуже речи (10-12 симбола), и речници величине од 500 до 11.000 речи. Експерименти су дали одличне резултате (преко 90%) за дуже речи коришћењем триграмских карактеристичних вектора и задовољавајуће до добре резултате (у просеку од 60% до 90%, зависно од величине речника) за речи средњих дужина коришћењем биграмских карактеристичних вектора. Још детаљније проучавање су извели Dahl и Cherkassky [Dahl 90] упоређујући коришћење униграма, биграма и триграма на речима различитих дужина за сваки од четири типа једноструких грешака. Дошли су до закључка да "биграмско и триграмско кодирање дају боље резултате за све врсте грешака осим за транспозиције за све дужине речи", док униграмско кодирање даје много боље резултате при раду са грешкама транспозиције. 519Ваља споменути и покушаје трансформисања простора лексичких карактеристика коришћењем математичких техника у циљу бољег истицања сличности лексичких карактеристика и консеквентно повећавање тачности корекције. Позната је техника рачунања генералисане инверзне матрице, која је базирана на проналажењу инверзне вредности минималне грешке средњих квадрата матрице речника, са циљем смањивања интерференције сличних речи у речнику. Међутим, касније је доказано, на основу теореме из линеарне алгебре, да се генералисана инверзна матрица засићује када се број речи у речнику ближи димензионалности простора лексичких карактеристика, што је праћено битним смањењем у тачности корекција. 520Још једну технику трансформисања простора карактеристика, декомпозицију сингуларних вредности (Singular Value Decomposition - SVD) је испитала Kukich [Kukich 90]. SVD се може употребити за декомпозицију матрице речника у производ три матрице, где прва представља n-граме индивидуалних симбола као вектор фактора, друга дијагонална матрица се састоји од сингуларних вредности које се користе као тежински коефицијенти фактора, док трећа матрица представља сваку од речи из речника у облику факторског вектора. Циљ процеса декомпозиције је идентификација и рангирање најважнијих фактора који одређују битне релације сличности у лексичком простору. Најмање важни фактори, који заправо могу представљати шум у подацима, могу се одбацити, остављајући на тај начин три матрице смањених димензија које боље репрезентују сличности између речи у речнику. SVD је успешно искоришћен у експериментима претраживања информација [Deerwerster 90]. У овим експериментима, библиотечке базе података са хиљадама докумената и речи у речнику су репрезентоване ретким матрицама које комбинују појмове и документе. Ова техника је додатно названа латентно семантичко индексирање због тога што изгледа да је занимљив пропратни ефекат коришћења SVD извлачење инхерентних семантичких релација између појмова и докумената. 521Насупрот применама у претраживању информација, матрице за примену у корекцији текста где су речи представљене биграмима и униграмима су много гушће. Када се таква матрица декомпонује у три факторске матрице и редукује, реч са грешком се коригује тако што се прво сумирају вектори за сваки од n-грама за индивидуалне симболе у речи (као што је то представљено у првој матрици), потом се сумарни вектор множи са матрицом сингуларних вредности (друга матрица). Резултујући вектор одређује положај речи са грешком у n-димензионалном простору лексичких карактеристика. Тада је могуће, коришћењем било које метрике (као што су еуклидска или косинусна метрика), одредити растојање речи са грешком и вектора за сваку од исправних речи (репрезентованих трећом матрицом) у циљу пронажења и рангирања најближих исправних речи. У проучавањима које је извела Kukich, SVD матрице су дале побољшане резултате у корекцији грешака у односу на недекомпоноване матрице за мале речнике (са 76% на 81% за речник од 521 речи), док није примећено значајно побољшање у случају великих речника. Ови емпиријски резултати се слажу са теоретским налазима који указују на засићење генералисане инверзне матрице. 522Хибридну технику која користи униграмске векторе комбиноване са хеуристичким техникама је развио Bickel [Bickel 87], за потребе претраживања података у бази података којој се приступа коришћењем имена запослених у улози кључева. Речник за ову апликацију се састојао од близу хиљаду личних имена запослених. Техника представља свако исправно име као униграмски вектор. Вредност сваке компоненте униграмског вектора је нула уколико се симбол не јавља у имену, или цео број између 3 и 9 у супротном случају. Бројне вредности за сваку компоненту алфабета се одређују у складу са фреквенцијом појављивања симбола у речнику имена, с тим што најређи симболи добијају највеће вредности. Претпоставка је да су ређи симболи важнији као информација у претраживању. Имена, која су потенцијалне грешке, представљају се као бинарни униграмски вектори. Техника за корекцију грешака претпоставља да је први симбол имена исправан и тако ограничава подручје претраге. Употребљена је мера сличности, за унето име и свако исправно име из речника, која израчунава унутрашњи производ два вектора. Bickel је утврдио да ова мера сличности у 90% случајева успешно одређује право име када јој се зада податак са грешком. 5233.5. Пробабилистичке технике 524Технике базиране на n-грамима су природно довеле до развијања пробабилистичких техника за коришћење у проблемима препознавања текста и корекције грешака. Истраживана су два типа вероватноћа: вероватноће транзиције и вероватноће конфузије. 525Вероватноћа транзиције је вероватноћа да ће неки симбол или секвенца симбола бити праћен одређеним симболом. Ове вероватноће зависе од језика који се разматра. У неким случајевима, када се језик сматра Марковљевим извором, ове се вероватноће називају Марковљевим вероватноћама. Могуће их је одредити статистичком анализом фреквенција n-грама над великим корпусом текста из дискурса. 526Вероватноћа конфузије је процена колико често се неки симбол погрешно сматра или замењује неким другим симболом. Ове вероватноће у великој мери зависе од извора текста. На пример, различити уређаји за OCR користе различите технике за препознавање симбола, што резултује јединственом расподелом вероватноћа конфузије. Ове вероватноће се називају и карактеристикама канала. Такође, исти уређај за OCR може генерисати различите вероватноће конфузије за различите врсте фонтова или величина симбола. 527Модел вероватноће конфузије за одређен уређај се може проценити употребљавањем уређаја за препознавање пробног текста и обрадом статистике грешака. Овај процес се понекад назива фаза тренирања, зато што се резултати испитивања користе за развој постпроцесора за корекцију грешака. Такође, у моменту препознавања симбола, уређај може генерисати вектор (са онолико димензија колико има симбола у алфабету) који садржи процену сличности за сваки симбол из алфабета. Тада је могуће процене сличности интерпретирати као вероватноће конфузије. 528Вероватноће конфузије, базиране на људским грешкама се називају вероватноће грешака. Оне се, такође, процењују статистичком обрадом грешака из великог корпуса куцаног текста који садржи грешке у куцању и спеловању. Друге класе пробабилистичких информација које се користе за корекцију грешака на изолованим речима су фреквенције појаве речи у тексту и вероватноће појаве униграма у речи. 529Ваља напоменути да се пробабилистичке информације већ дуже време интензивно користе у подручјима препознавања текста, за разлику од примене приликом корекције грешака у тексту. Управо су истраживања на пољу препознавања текста показала да је недовољно коришћење само вероватноћа, те да комбинација вероватноћа и коришћења речника знатно побољшава одзив и тачност корекције грешака. 530Bledsoe и Browning [Bledsoe 59] су међу првима искористили вероватноће у решавању проблема препознавања текста. Њихова техника се састоји из две фазе: 5311. фаза препознавања индивидуалних симбола у којој се генерише вектор од 26 елемената процене очекивања појаве одређеног симбола у речи која се уноси, 5322. фаза препознавања целих речи у којој се користи речник да би се помогло одабирање индивидуалних симбола чија очекивања заједнички максимизирају вероватноћу продуковања валидне речи из речника. 533Као резултат, препознавање целих речи побољшава препознавање индивидуалних симбола увођењем ограничења из речника која помажу у разрешавању нејасних ситуација и исправљају грешке које се јаве на нивоу препознавања појединачних симбола. 534Bledsoe-Browning техника користи Bayes-ово правило за израчунавање a posteriori вероватноће за сваку реч у речнику, на основу a priori очекивања за индивидуалне симболе. Ако је X реч из речника, а Y стринг који се добија применом OCR техника, Bayes-ова формула даје 535где је P(X|Y) условна вероватноћа да је X тачна реч, P(Y|X) је условна вероватноћа да се појави Y у случају да је X коректна реч, а P(X) и P(Y) су независне вероватноће речи X и Y. Проналажење речи X из речника са највећом вероватноћом, ако је дата реч Y добијена OCR-ом се своди на максимизирање функције 536G(Y|X)=log P(Y|X)+log P(X), 537где се за P(X) најчешће узима униграмска вероватноћа речи X. A posteriori вероватноћа за сваку реч из речника се може лако израчунати из a priori вероватноће очекивања за индивидуалне симболе по формули: 538где је n дужина речи, а i индекси индивидуалних симбола у речи. 539У Bledsoe - Browning техници процене очекивања сваког симбола се добијају од OCR уређаја, униграмска фреквенција речи се игнорише а бира се реч са највећом вероватноћом. 540Рачунска сложеност ове технике је линеарно зависна од дужине речника. Због тога је рад са великим речницима проблематичан, чак и у случају да су партиционисани по дужинама речи. Burr [Burr83] је проширио ову технику морфолошким процесирањем, које је омогућило формирање мањих речника уз додатну префиксално-суфиксалну анализу. 541Kahan [Kahan 87] је такође комбиновао вероватноће конфузије са техникама претраге речника у постпроцесору за OCR. Када би се наишло на реч коју програм за проверу текста не може да препозна, генерисани су кандидати одређени на основу вероватноћа конфузије које су добијене тренирањем, све док се не би дошло до прихватљиве речи из речника или док се не би прешао одређени праг. У извештају је наведена тачност препознавања симбола од 97% уз игнорисање симбола који се не могу распознати као што су парови 0/O (нула/о) и 1/l (један/л). 542Такође, испробаване су технике које користе вероватноће конфузије и транзиције без употребљавања речника. Hanson и остали [Hanson 76] извештавају о експерименту са коришћењем вероватноћа очекивања у комбинацијама са троструким вероватноћама транзиције или позиционим бинарним триграмима. На примеру тест скупа од 2.755 6-словних речи је закључено да коришћење троструких вероватноћа транзиције за додељивање тежинских фактора очекивањима појаве индивидуалних симбола у OCR излазу смањује грешке, али само са 49% на 29%. Закључено је да технике базиране на вероватноћама транзиције нису ефикасне. Такође, утврђено је да су позициони бинарни триграми сами по себи довели до преко 50% корекција грешака у тест скупу, а да је додатно коришћење вероватноћа сличности смањило ефикасност поступка за ред величине. 543Toussaint [Toussaint 78] и Hull и Srihari [Hull 82] дају генералан преглед техника за корекцију грешака базираних искључиво на вероватноћама транзиције и конфузије. Ове две вероватноће се могу комбиновати Bayes-овом формулом, тако што се вероватноћа појаве униграма у речима замењује сумом вероватноћа транзиције. Уобичајен начин комбиновања ове две технике је поступак заснован на динамичком програмирању назван Витербијев алгоритам [Forney 73]. Овај поступак користи оријентисан граф (trellis), за записивање структуре речника (вероватноће транзиције) и карактеристика канала (вероватноће конфузије). Почетни и крајњи чвор су маркери почетка и краја речи. Међучворови представљају процењена очекивања за индивидуалне симболе. Границе представљају вероватноће транзиције између симбола. Граф се ефикасно претражује применом техника динамичког програмирања у циљу проналажења секвенце симбола која има највећу вероватноћу, ако су дате процене очекивања за OCR уређај и вероватноће транзиције језика који се посматра. 544Развијене су и многе модификације Витербијевог алгоритма које ограничавају дубину претраживања на основу очекивања и/или других фактора [Shingal 79a]. Мана ових техника је да стринг са највећом вероватноћом не мора увек бити валидна реч. Такође, закључено је да је тачност корекеције техника базираних искључиво на ова два пробабилистичка извора осредња. 545Технику коју такође вреди поменути су описали Goshtasby и Ehrich [Goshtaby 88]. Она користи иницијално постављене вероватноће симбола у складу са процењеним очекивањем за сваки симбол. На њих се примењује Rosenfeld-ова релаксациона формула [Rosenfeld 76] и у итеративном поступку се мењају вероватноће очекивања за сваки симбол као функција вероватноће транзиције суседних симбола. Број кандидата конфузије за сваки симбол се тако може редуковати на мали скуп оних који прелазе одређени праг, што чини релаксациони процес рачунски једноставним (рачунске сложености 10n2 за реч дужине n). На жалост, као и у случају Витербијевог алгоритма, процес може конвергирати ка непостојећој речи. Један тест је довео до конверзије исправне речи biomass у неисправну biomess. Аутори предлажу увођење додатног знања у поступак како би се избегли овакви резултати, као и коришћење информација о карактеристичним диграмима. Такође, препоручује се да се релаксациони процес угради у неку од техника базираних на речнику. 546Пробабилистички подаци су ефикасно коришћени као претпроцесори за примене корекције текста. Oshika и остали [Oshika 88] су имплементирали процедуру скривеног Марковљевог модела (Hidden Markov Model - HMM) за претходну класификацију презимена у зависности од етничког порекла. HMM су били аутоматски генерисани за сваки од пет различитих језика на бази вероватноћа транзиције низова симбола 2.000 презимена из сваког језика. Потом се HMM користио за аутоматско класификовање унетих презимена, пре генерисања варијанти исправног записа за одређени језик. Утврђено је да је ова техника довела до побољшавања претраге података од 69% до 88% на тест примеру од 160 презимена. 547Добри резултати су постигнути техникама које комбинују пробабилистичке информације са речницима. Shingal и Toussaint [Shingal 79b] примећују да технике које користе речнике имају ниске проценте грешака, али пате од великих захтева за простором и велике речунске сложености, док Марковљеви методи имају управо обрнуте карактеристике, те су предложили предиктор - коректор технику која достиже способност корекције грешака коју имају методе претраживања речника у пола цене. Техника тражи сортирање речника по унапред израчунатој вредности V која је код сваке речи базирана на основу вероватноћа транзиције. Алгоритам прво користи Витербијев алгоритам за препознавање речи са улаза. Тада се срачунава V за препознату реч и речник се бинарно претражује са циљем налажења речи која има исту вредност. Уколико се не пронађе иста реч, срачунава се V за речи у суседству и бира се она која има најбољи резултат. У експерименту са речником од 11.603 речи и два тест скупа од 2.521 и 2.256 речи постигнуто су резултати од 96.6% и 96.4% препознатих речи. На жалост, како сами аутори тврде, техника најбоље ради у случају када се суседством сматра цео речник, па препоручују другачије организовање речника. Међутим, и тада се време процесирања речника скраћује, зато што Витербијев алгоритам даје тачну реч у више од 50% случајева. 548Srihari и остали [Srihari 83] су развили технику у којој се речник представља као trie структура која се интегрише са Витербијевим алгоритмом у циљу задржавања ефикасности Витербијевог алгоритма уз гаранцију да ће се као резултат претраживања добити највероватнија реч. Ова техника је тестирана на тексту од 6.372 речи из којег је генерисан речник од 1.742 речи. Витербијев алгоритам је успео да исправи 35% грешака које је направио OCR уређај, техника заснована само на претраживању речника је исправила 82% грешака, док је комбинација речника и Витербијевог алгоритма је успела да исправи 87% грешака. 549Sinha и Prasada [Sinha 88] су развили технику која, поред интегрисања пробабилистичких метода и метода претраживања речника, укључује и неколико хеуристичких поступака. Главна мотивација је била решавање реалног проблема да се у пракси често не може сматрати да ће речник садржати све речи које се налазе у тексту. Састављен је парцијални речник који се састоји од 10.000 најчешћих речи из Брауновог корпуса [Kucera 67]. Овај речник је потом повећан уметањем свих исправних речи које се добијају заменом једног симбола. Техника користи два корака. У првом исправља само грешке код којих вероватноће конфузије резултују речју која се налази у парцијалном речнику. Потом се користи модификовани Витербијев алгоритам за процену највероватније исправке за реч која се не налази у речнику. Речник се претражује као trie структура, и техника користи неколико хеуристичких поступака за рангирање кандидата конфузије, ограничавање претраге по структури, те ограничавање грана Витербијеве мреже по којој се претражује. Ова техника је тестирана на тест скупу од 5.000 речи (25.000 симбола) текста који је куцан на писаћој машини или штампан коришћењем седам различитих величина и типова слова и показала је тачност од преко 98% на препознавању индивидуалних симбола и 97% на препознавању речи. Закључено је да повећани речник доводи до бољих перформанси у односу на смањену верзију у случају текстова који нису превише конвенционални (као што су текстови техничке и литерарне природе). Ипак, перформансе на конвенционалним текстовима се битно умањују када се користе лошији OCR уређаји зато што се генерише већи број кандидата за корекцију и доста речи са већом фреквенцијом појављивања се мапирају на ређе речи у повећаном речнику. 550Jones и остали [Jones 91] су имплементирали постпроцесор за OCR који интегрише Бајесовски приступ предикцији са више извора знања. У фази тренинга се изграђују статистички модели и за OCR уређај и за документе које ваља обрадити. Модели укључују фреквенције униграма и биграма симбола, бинарне триграме симбола и n-граме са почетним симболима, као и фреквенције униграма речи и диграма неких речи. Такође укључују диграме симбола и речи који садрже знаке интерпункције и велика слова. Статистике се подешавају тако да речи за које систем није утрениран не утичу превише на резултате претраживања. 551Коректор ради у три фазе: 5521. генерише рангирану листу кандидата за сваку реч из улаза на основу вероватноћа конфузије и речника организованог као trie, 5532. спаја речи да би се избациле евентуалне грешке у раздвајању речи 5543. пресортира листу кандидата на основу диграмских вероватноћа. 555Фазе 2 и 3 враћају резултате анализе у прву фазу ради поновне анализе. 556Техника је тестирана у два експеримента. У првом, систем је трениран на шест докумената за тестирање софтвера са укупно 8.170 речи и тестиран на седмом документу од 2.229 речи. Проценат грешке OCR уређаја је био 16,2%. Систем је кориговао 89,4% грешака. У другом експерименту систем је трениран на 33 странице текста новинске агенције AP и тестиран на следећих 12 страница. Проценат грешке OCR уређаја је варирао од 6,8% до 10,3%, а систем за корекцију је успео да исправи 72,5% ових грешака. Значај ове технике корекције је у томе што је то прва техника која користи контекстуално знање у виду диграма речи и знакова интерпункције. 557Јављају се такође и технике које експлицитно користе вероватноће појаве грешака за корекцију грешака. Kashyap и Oomen [Kashyap 84], мотивисани слабим перформансама техника за корекцију у случају примене на кратке речи (краће од 6 симбола), су саставили табелу субјективних процена вероватноћа замене симбола на основу распореда тастера на тастатури. Такође су саставили табеле субјективних процена грешака једноструког брисања и уметања симбола на различитим позицијама у речи. Претпостављајући да се свака грешка у писању може свести на комбинацију таквих брисања, уметања и замена, развили су рекурзивни алгоритам који је користио њихове процене за рачунање вероватноће да је дата реч заправо погрешно написана реч из речника. 558Техника је тестирана уз помоћ вештачки генерисаних грешака на речима дужине три, четири и пет симбола. Грешке су генерисане на основу вероватноћа њиховог догађања и прављено је између 1,65 и 1,90 грешака по једној речи. Коришћен је речник од 1.025 најчешћих речи. Проценти корекције су износили између 30% и 92% у зависности од дужине речи и броја грешака по речи. Ови резултати су бољи од оних које су дали Okuda и остали [Okuda 76] а који су износили од 28% до 64% за речи са сличним дужинама и бројем грешака. У том експерименту је коришћена Damerau-Levenshtein техника минималног едит растојања. 559Kernighan и остали [Kernighan 90] и Church и Gale [Church 91] су развили алгоритам који исправља једноструке грешке у речима. Коришћена је база правих грешака из корпуса од 44 милиона речи новинских текстова агенције AP за састављање четири матрице конфузије, по једну за сваки од стандардних типова грешки (уметање, брисање, замена и транспозиција). На основу ових статистика су процењене вероватноће конфузије. Програм correct је користио обрнуту технику минималног едит растојања да би генерисао скуп кандидата са једном грешком и да би идентификовао грешку код сваког кандидата. Потом је користио Bayes-ову формулу за рангирање кандидата. 560Као улаз, програм correct прима реч коју детектује програм spell. Прво генерише скуп кандидата за исправку тако што систематски тестира све могуће једноструке грешке на речи да би се утврдило да ли се нека од таквих речи појављује као исправна реч у речнику. Унапред генерисана табела брисања и hash техника се користе за минимизирање приступа речнику током процеса генерисања кандидата. Потом се кандидати рангирају множењем a priori вероватноће појаве тог кандидата (тј. са његовом нормализованом фреквенцијом) са вероватноћом појаве специфичне грешке која је узрок разлике исправне и погрешне речи. 561Програм је тестиран на скупу од 332 погрешне речи, такође из текстова новинске агенције AP. Свака од тих речи је имала тачно два кандидата за корекцију. Програму и тројици људских судија је задато да одаберу најбољег кандидата, с тим што је људима било дозвољено да одлуче да ниједан кандидат не задовољава, уз додатне информације о контексту. Correct се сложио са најмање двојицом судија у 87% случајева. 562Касније је верзија овог програма уграђена у конвертер текста у говор који је саставни део уређаја за TDD конверзацију [Kernighan 91]. Пре изговарања речи, компонента за изговарање је израчунавала индекс сложености изговора да би се избегло непотребно исправљање лоше написаних речи чији би изговор ипак био прихватљив, као што су operater и wud. Погрешно написана реч је слата на обраду програму correct само у случају када је индекс сложености изговора прекорачивао неки праг. У експерименту са живим слушаоцима показало се да је систем битно побољшавао степен разумевања синтетизованог текста. Вршени су експерименти и са варијацијама прилагођеним шпанском језику. 563У повезаном истраживању, Troy [Troy 90] је испитивала ефекте комбиновања пробабилистичких информација са техникама одређивања удаљености вектора. Користила је косинусну метрику, вероватноће униграма речи, Kernighan-Church-Gale (KCG) вероватноће грешака, речник од 1.142 речи и тест скуп од 170 речи који је користила и Kukich. Косинусна метрика је служила за генерисање скупа кандидата за корекцију, техника динамичког програмирања је проналазила специфичне грешке у кандидатима, а вероватноће униграма речи или KCG вероватноће су служиле за поновно рангирање кандидата. Пошто косинусна метрика може да ради са речима и са једноструким и са вишеструким грешкама, експеримент је извођен и на речима са вишеструким грешкама. Примећено је да информација о фреквенцији речи није побољшала тачност корекције косинусне метрике, али информација о вероватноћама грешака јесте, и то за 3% (са 75% на 78%). 5643.6. Неуралне мреже 565Под неуралним мрежама се подразумева скуп међусобно синхронизованих елемената са m улаза и једним излазом y који се називају неурони3, међусобно повезаних тако што се излаз сваког неурона дели на више линија од којих се неке или све линије користе као улаз у друге неуроне. Излаз може водити до већег броја улаза, али улаз може доћи од највише једног излаза. [Arbib 87] 566Неуралне мреже су погодни кандидати за корекцију спеловања због своје инхерентне способности за асоцијативан приступ на основу непотпуног или улаза оштећеног шумом. Такође, због могућности да се обучавају на реалним грешкама у писању, имају потенцијал да се адаптирају на специфичне грешке групе корисника, чиме се максимизира тачност за одређену популацију. Није тешко замислити хардверски имплементирану неуралну мрежу у оквиру радне станице која се адаптира на грешке корисника. 567За обучавање неуралних мрежа се најчешће користи алгоритам простирања уназад (back-propagation) [Rumelhart 86]. Типична мрежа са простирањем уназад се састоји од три слоја чворова: улазног, средњег (скривеног) и излазног слоја. Сваки чвор у улазном слоју је повезан тежинским везама са сваким чвором у скривеном слоју. Такође, сваки чвор у скривеном слоју је повезан тежинским везама са сваким чвором у излазном слоју. Улазно-излазне информације су представљене низом бинарних цифара на улазном и излазном слоју. Укључен чвор се обележава са 1, а искључен са 0. Такође, могу се користити и реални бројеви који репрезентују степен активације чвора. 568Процесирање у оквиру мреже са простирањем уназад се састоји од постављања облика на улазне чворове. Облик се потом простире напред кроз тежинске везе у скривене чворове, где се срачунава скривени облик, па у излазне чворове, где се добија излазни облик. Тежине представљају снагу веза између чворова. Оне делују као отпорници у циљу модификовања количине активности између чворова. Тотална активност која стиже до неког чвора је сума активности свих чворова испод њега, помножена са снагама њихових веза. Ова сума се обично дискретизује одређеним прагом, тако да се као резултат добија 0 или 1, или се пак пропушта кроз сажимајућу функцију у циљу добијања реалног броја између 0,1 и 0,9. 569Алгоритам простирања уназад пружа начин за проналажење скупа таквих тежинских фактора који омогућавају да мрежа да тачан, или скоро тачан резултат за сваки улазни облик. Он се ослања на обучавање мреже примерима и корекцију тежинских фактора у складу са резултатима експеримената. Тежински фактори се иницијализују на мале случајне вредности. Потом се за сваки улазно-излазни пар у скупу за обучавање, улазни облик поставља на улазне чворове мреже, чиме се изазива прослеђивање активације кроз тежинске факторе у скривене и излазне чворове, што даје излазни облик на излазним чворовима. Тада се добијени излазни облик упоређује са жељеним обликом и рачуна се разлика за сваки чвор у излазном нивоу. Праћењем уназад кроз мрежу, разлика се користи за промену сваког тежинског фактора за малу вредност која је инверзно пропорционална грешци. Овом процедуром се итеративно пролази кроз све примере у скупу за обучавање све док тежински фактори не почну да конвергирају. Резултат обуке је скуп тежинских фактора који даје готово тачне излазне облике за сваки улазни облик из скупа за обучавање, као и за сличне улазне облике који нису у скупу за обучавање. Ова последња особина је карактеристика неуралних мрежа да се адаптирају на нове улазне облике или облике оштећене шумом. 570Један начин коришћења неуралне мреже у апликацији за корекцију спеловања је коришћење бинарног n - грама као улазног облика, док је излазни облик вектор од m елемената, где је m број речи у речнику, а само чвор који одговара тачној речи је активиран. Оваква мрежа се назива још и 1 - m класификатор, зато што је циљ функционисања мреже максимизација активације на излазном чвору који представља исправну реч и минимизација активације на свим осталим излазним чворовима. Такође, могуће је интерпретирати вредности на излазним чворовима као меру сличности улазне речи са осталим речима из речника. 1 - m шема за представљање речника се још назива и локална шема за представљање зато што је свака реч из речника представљена са по једним чвором на излазном нивоу. Насупрот томе, бинарна n-грамска шема представљања која се користи за улазни облик се назива и дистрибуирана шема представљања, зато што ни једеан чвор не садржи све информације потребне за представљање речи, већ су оне дистрибуиране на све чворове улазног нивоа. 571Неуралне мреже се највише користе у OCR апликацијама, и то углавном за препознавање бројева и симбола писаних руком [Matan 92], [Keeler 92], [Burr 87] као што су очитавање поштанских бројева, чекова или признаница за кредитне картице. Знатно је мања примена неуралних мрежа за препознавање речи, због проблема инхерентних OCR применама који се односе на недостатак информација о контексту. Ипак, вршени су неки експерименти и на препознавању речи. Burr [Burr 87] је имплементирао препознавач речи писаних руком и штампаним словима, који се састоји од две фазе и комбинује неуралну мрежу са пробабилистичком техником. У првој фази, систем користи неуралну мрежу са 26 излазних чворова од којих сваки представља један симбол из алфабета и 13 улазних чворова, где сваки представља један сегмент маске која служи за одређивање карактеристика штампаног симбола. Излаз из неуралне мреже је корисна апроксимација дистрибуције вероватноћа максималне сличности са 26 симбола из алфабета. У другој фази, систем користи Bayes-ову формулу да израчуна процену вероватноће за сваку реч у речнику на бази вероватноћа сличности индивидуалних симбола и униграмских вероватноћа речи. У експерименту, Burr је саставио скуп од 208 руком писаних симбола, по осам инстанци сваког симбола из алфабета. Обучавао је неуралну мрежу коришћењем половине овог скупа, док је другу половину користио за тестирање. Мрежа је имала способност да препозна 94% симбола на тест скупу. Потом је техника тестирана симулирањем ручног писања сваке речи из речника од 20.000 речи коришћењем инстанци симбола у тест скупу. Добијен је резултат од 99,7% препознатих речи дужине не мање од 6 симбола. 572Примену неуралних мрежа за корекцију грешака у тексту, тј. специфичније за корекцију унетих имена су испитивали Kukich [Kukich 88a,b] и Cherkassky и Vassilas [Cherkassky 89a,b] обучавањем мреже пропагацијом уназад. Kukich је такође [Kukich 90] користила неуралне мреже за синтезу говора из текста, док су Gersho и Reiter [Gersho 90] користили самоорганизујуће и мреже са пропагацијом уназад за корекцију адреса. Коначно, Deffner и остали [Deffner 90a,b] су користили неуралне мреже за имплементацију интерфејса заснованог на природном језику. 573У експерименту са корекцијом презимена Kukich је користила речник од 183 презимена за обучавање стандардне мреже са пропагацијом уназад. Излазни ниво се састојао од 183 чвора од којих је сваки представљао по један за свако презиме. Улазни ниво се састојао од 450 чворова груписаних у 15 група од 30 чворова, тако да би се могла представљати презимена дужине до 15 симбола. Сваки блок од 30 чворова је садржавао по један чвор за сваки симбол из алфабета од 30 симбола. Тако на пример, уколико је први симбол речи R, тада се активира (тј. поставља на 1) чвор који представља симбол R у првом блоку, а осталих 29 чворова у том блоку се деактивирају (тј. постављају на 0). У овој примени може се говорити о позиционално кодираном улазном вектору осетљивом на померање. 574Мрежа је тестирана на стотинама вештачки генерисаних речи са грешком од сваког од 183 презимена. Било је потребно неколико десетина сати на Sun SPARCStation 2 радној станици да би мрежа конвергирала. Тестирана је додатним речима са једном грешком. Процес препознавања је узимао само неколико секунди, а добијени су скоро савршени резултати (близу 100%) за сва четири типа грешака укључујући ту и грешке брисања и уметања које резултују померањем и које су одузеле највише времена приликом обучавања мреже. 575Неки од резултата добијених у експерименту указују да: 5761. мреже које се обучавају и на именима са грешком се боље обучавају од оних које као улаз добијају само исправна имена, 5772. повећавање броја скривених чворова је резултирало побољшавањем перформанси, али само до броја од 183 чвора (колико има и излазних чворова), док се даљим повећавањем нису добијала побољшања, 5783. мреже које су користиле локалне шеме репрезентације података су се много брже обучавале од варијанти које су користиле дистрибуиране шеме репрезентације. 579Даљи експерименти су показали да се мреже које користе позиционе улазне шеме осетљиве на померање без скривеног нивоа заправо брже обучавају уз исте перформансе, него мреже са оптимално конфигурисаним скривеним слојем. Међутим, мреже које користе бинарне n-граме (униграм плус биграм) тј. оне које нису осетљиве на померање, дају веома лоше перформансе без скривеног нивоа, уз осетљиво побољшавање перформанси приликом повећавања броја чворова у скривеном нивоу. 580Експерименти које су изводили Cherkassky и Vassilas су потврдили већину резултата до којих је дошла Kukich. У овом случају су посебно тестиране униграмске и биграмске векторске шеме репрезентације као улази у мрежу, док је излазни слој поново користио локалну шему репрезентације (по један чвор за сваку реч из речника). Дакле, и ове мреже су представљале 1-m класификатор. Обучаване су на исправно написаним презименима и тестиране на презименима са вештачки генерисаним грешкама брисања и уметања. Величине речника су ишле од 24 до 100 презимена. Добијени резултати указују на корекцију грешака од готово 100% за најмање речнике, уз напомену да избор начина обучавања и броја скривених чворова у великој мери утиче на перформансе мреже. Још један закључак је био да је оптималан број чворова у скривеном нивоу близак броју речи у речнику. Ови закључци могу довести до претпоставке да се ове неуралне мреже понашају као неинтелигентни алгоритми за претраживање. Доказ против ове претпоставке је чињеница да су мреже биле тестиране на речима са новим грешкама које се као такве нису појављивале приликом обуке. Cherkassky и Vassilas су закључили да су мреже, због велике осетљивости на различите параметре обучавања, као и због велике рачунских захтева током обучавања мање погодне за корекцију грешака у тексту од модела корелационих матрица. 581Kukich [Kukich 90] је наставила са истраживањима на пољу примене неуралних мрежа за исправку грешака у системима за синтезу говора на основу текста. У овим применама карактеристична је употреба великог речника и незанемарљива количина (око 25%) вишеструких грешака у речима. Коришћена је стандардна трослојна мрежа са пропагацијом уназад, која је за улазни ниво имала 420 чворова који су примали униграмски плус биграмски вектор, 500 чворова у скривеном нивоу и 1.142 чвора у излазном нивоу који користе шему локалне репрезентације података. Мрежа је поново обучавана на вештачки генерисаним грешкама зато што није било могуће пронаћи довољан број правих грешака. Тестирана је истим тест скупом од 170 правих грешака који су раније коришћени за тестирање векторских простора и других техника. Ова метода је дала резултате сличне онима који су добијени код коришћења векторских простора (око 75%). Међутим, цена обучавања овакве мреже је била веома висока - реда величине стотина сати рада Sun SPARCStation 2 радне станице. Показало се да се оштри захтеви у погледу рачунске сложености обучавања неуралних мрежа, поготову стандардних тронивоиских 1-m класификатора са пропагацијом уназад постављају практична ограничења за скалабилност, нарочито у односу на величину речника. Свакако да ово ограничење свакодневно губи на значају због присутног тренда раста рачунарске снаге модерних система. 582Са друге стране, испитиване су технике које би довеле до скраћивања времена потребног за обучавање партиционисањем речника или коришћењем алтернативних архитектура неуралних мрежа. Једну такву варијацију су испитивали Gersho и Reiter [Gersho 90] за примену у претраживању података у бази података са 1.000 имена улица. Развијена је хијерархијска мрежа са два нивоа која се састоји од само-организујућих Kohonen-ових неуралних мрежа [Kohonen 88] и великог броја малих мрежа са пропагацијом уназад. Улазни податак система се прво даје Кохоненовој мрежи која га класификује у једну од грубо одређених категорија, а потом у одговарајућу мрежу са пропагацијом уназад за финију класификацију. Ова техника је дала резултате у опсегу од 74% до 97% за базу података од 800 имена улица. 583Систем за корекцију текста заснован на неуралним мрежама који су имплементирали Deffner и остали [Deffner 90a] је део интерфејса према бази података који користи природни језик. Током претраживања информација, неке карактеристике (као што су синтаксичке и семантичке карактеристике) се могу ближе одредити контекстом упита у базу података. Речи из речника и погрешно написане речи се представљају векторима карактеристика који садрже n-граме симбола, фонетске карактеристике, синтаксне карактеристике (као што су је_придев) и семантичке карактеристике (нпр. је_боја). Потом се користи Хамингова метрика за израчунавање мере сличности између потенцијално погрешних или некомплетних улазних речи и сваког члана ограниченог подскупа речника. Ова техника успешно користи и неке контекстне информације у примени у уско одређеној области). 5843.7. Преглед резултата техника за корекцију грешака 585Табела која следи даје преглед тачности неких од техника за корекцију грешака, на основу експеримената изведених од 170 речи [Kukich92а]. 586Техника 587Речник од 521 речи 588Речник од 1142 речи 589Речник од 1872 речи 590Минимално едит растојање 591Grope 59264% 59362% 59460% 595Технике на бази кључева сличности 596Bocastova реконструкција токена 59780% 59878% 59975% 600Једноставна n - грамска векторска растојања 601Скаларни производ 602Хамингово растојање 603Косинусно растојање 60458% 60569% 60676% 60754% 60868% 60975% 61052% 61167% 61274% 613SVD n - грамска векторска растојања 614Косинусно растојање 61578% 616Неуралне мреже 617Класификатор са пропагацијом уназад 61875% 61975% 620Табела 2 - Преглед тачности неких техника за корекцију 6214. УТИЦАЈ ОРГАНИЗАЦИЈЕ ПОДАТАКА НА ПРОБЛЕМ КОРЕКЦИЈЕ ГРЕШАКА У ТЕКСТУ 622Потребан услов исправности неке речи из текста је њено постојање у речнику који садржи валидне речи. 623Први критеријум за одређивање квалитета начина организације речника је брзина којом је могуће одредити да ли се неки стринг налази у речнику или не. Следећи критеријум, изузетно важан током поступка корекције грешке, везан је за потребу брзог секвенцијалног приступа свим стринговима у речнику. У случају да је одабрана техника за одређивање сличности стрингова која омогућава партиционисање скупа стрингова, речник би требао да омогући једноставно одређивање скупа стрингова који задовољавају одређен критеријум сличности. У поступку пројектовања речника потребно је водити рачуна о ограничењима која намеће рачунарска опрема у употреби. Ова ограничења најчешће доводе до потребе да речник заузима што мање меморије, као и обезбеђивање једноставног коришћења секундарне меморије за смештање делова речника који се тренутно не користе. Уколико речник садржи као стрингове речи неког живог језика, потребно је размотрити предности и ограничења које ова чињеница намеће. Наиме, ако се ради о реалном језику, речник може да чува само корене речи уз скуп правила за генерисање других облика речи (на пример, начин генерисања падежа неке именице и сл.). 6244.1. О садржају и величини речника 625Речник који се користи у апликацијама за корекцију грешака или препознавање текста се мора пажљиво саставити и зависи од предвиђене области дискурса. Премали речник ће оптеретити корисника са превише одбијања исправних речи, док ће превелик речник резултовати неприхватљиво великим бројем прихватања неисправних речи (тј. грешака које су резултовале ретком исправном речи - lave, fen, veery...). Ипак, зависност између грешака и фреквенције појава речи није директна. 626Peterson [Peterson 86] је израчунао да приближно пола процента свих речи са једноструком грешком у речнику од 350.000 речи резултује другим речима из речника. Такође је приметио да је број недетектованих грешака у пракси још и већи, зато што краће речи, које се чешће јављају, имају тенденцију да се уношењем једноструке грешке трансформишу у другу, валидну реч. Проценио је проценат грешака које неће бити детековане у функције величине речника. Процене се крећу од 2% за мали речник, преко 10% за речник од 50.000, до 16% за речник од 350.000 речи. Овај закључак наводи на потребу да речник за примену у корекцији грешака буде релативно мали. 627Ипак, Damerau и Mays [Damerau 89] сматрају супротно. У експерименту са корпусом од 22 милиона речи текста из различитих експеримената, утврдили су да је повећавање речника сортираног по фреквенцији са 50.000 на 60.000 речи елиминисало 1.348 неисправних одбијања, уз уношење свега 23 нова неисправна прихватања речи. Пошто овај резултат представља значајно побољшање у прецизности исправљања, препоручују коришћење већег речника. 628Речници су често недовољни извори за конструисање рачунарских речника. Walker и Amsler [Walker 86] су приметили да се скоро две трећине (61%) речи из Merriam-Webster Seventh Collegiate Dictionary није појавило у корпусу од 8 милиона речи текстова из New York Times, и обрнуто две трећине (64%) речи из корпуса нису биле речнику. 6294.2. Најчешће технике организовања речника 630Речник се складишти у структуру података. Одабир одговарајуће структуре података је од критичне важности за добро решавање проблема. У даљем тексту ће бити описане структуре података које се често користе за складиштење речника. Ваља напоменути да је за складиштење речника могуће искористити и комерцијално доступне системе за управљање базама података, мада таква одлука доводи до усложњавања система за проналажење и исправљање грешака у тексту, те се у овом одељку неће разматрати. 631Важно питање је и смештање структура података. У овом поглављу се подразумева да су разматране структуре података смештене у меморији. Уколико је потребно, на секундарној меморији се такође организују структуре података, о чему ће више бити речи у дизајн спецификацији система. 6324.2.1. Бинарна стабла 633Бинарна стабла су структура података која се релативно често користи у пракси. Оно се састоји од међусобно повезаних чворова са следећом организационом структуром: састоји се од корена који је чвор и повезан је са два потомка, од којих је сваки бинарно стабло (подстабло). Чвор који нема ни једног потомка се назива лист. Најчешћи начин организовања бинарног стабла је да се у лево подстабло умећу елементи мањи (по утврђеном критеријуму) од елемента у посматраном чвору, док се у десно подстабло умећу елементи који су већи од елемента у корену стабла [Knuth 73]. 634Алгоритам за уметање елемената у стабло је еквивалентан алгоритму за претрагу стабла, с тим што се елеменат умеће као потомак елемента код кога је утврђено да је дошло до коначног неуспеха у претраживању. Слика 6 шематски приказује структуру чвора стабла на коме се заснива алгоритам за претраживање, односно уметање елемената у бинарно стабло. 635Vrednost 636potLevi 637potDesni 638Слика 6 - Изглед чвора стабла (Cvor) 639cvor novi = new Cvor(k); 640cvor r = Koren; 641if (novi.vrednost < r.vrednost) { 642 if (r.potLevi <> null) { 643 r = r.potLevi; 644 } else { 645 r.potLevi = novi; 646// Vrednost nije pronadjena 647 } 648} else if (novi.vrednost > r.vrednost) { 649 if (r.potDesni <> null) { 650 r = r.potDesni; 651 } else { 652 r.potDesni = novi; 653// Vrednost nije pronadjena 654 } 655} 656else { 657// Vrednost je pronadjena 658// Nema umetanja elementa 659} 660У случају речника са стринговима, лево подстабло садржи стрингове који, при сортирању, долазе пре задатог стринга, а десно подстабло стрингове који долазе после задатог стринга (Слика 7). Редослед уметања речи у ово стабло је следио календарски редослед хороскопских знакова (јарац, водолија, риба, ован, бик, близанац, рак, лав, девица, вага, скорпија, стрелац). 661Као што се из алгоритма види, прва реч која се умеће постаје корен стабла. Удаљеност речи од корена зависи од односа речи која се уноси и речи које се већ налазе у стаблу и од редног броја речи у листи која се убацује у стабло. Ова особина може довести до последица које нису занемариве, као што ће то ускоро бити и показано. 662Слика 7 - Изглед бинарног стабла 663Овакав начин организације омогућава релативно брзо утврђивање постојања задатог стринга у речнику. Уколико је стабло добро балансирано, просечан број приступа који је потребан за проналажење одређеног стринга износи log N, где је N број стрингова у речнику. 664Важна особина коју бинарно стабло треба да задовољи у циљу одржања просечног броја приступа од log N је балансираност. Она подразумева да се висина левог подстабла, посматрана из сваког чвора, не разликује од висине десног подстабла за више од 1. Проблеми се могу јавити уколико се у бинарно стабло уносе већ сортирани подаци. У том случају долази до веома изражених поремећаја у балансу стабла. 665Слика 8 приказује драматичан пример изгледа стабла у које су уметани називи хороскопских знакова сортираних по абецеди (бик, близанац, девица, јарац, лав, ован, рак, риба, скорпија, стрелац, вага, водолија). У овом случају претраживање стабла се своди на, у основи, секвенцијално претраживање. 666Додавањем посебних информација у сваки чвор и додатним процедурама, могуће је формирати и одржавати стабло са оваквим особинама. Ипак, мора се напоменути да је одржавање балансираности стабла операција која је исплатива само у случају структуре која се слабо мења у функцији времена. 667Додатна погодност коју бинарна стабла нуде је могућност да одређене елементе поставимо ближе корену стабла (тако што ћемо их прве уносити у стабло). Ова чињеница омогућава да се стрингови који имају највећу фреквенцију у анализираним текстовима поставе близу корена стабла [Knuth 73], [Sheil 78], чиме се убрзава приступ стринговима којима се најчешће приступа. 668Може се, дакле, закључити да бинарно стабло представља добар начин организовања података за решавање проблема провере постојања речи у речнику. Могућност појаве дегенерисаног стабла се може апсорбовати периодичним балансирањем стабла речника. 669Ова структура омогућава релативно једноставан, секвенцијални приступ свим елементима који се постиже обилажењем стабла методом "прво у дубину". Овај начин подразумева пролажење кроз све елементе стабла и то углавном коришћењем рекурзивних техника, што условљава слабе перформансе секвенцијалног пролаза. 670Слика 8 - Изглед бинарног стабла у које су уметане унапред сортиране информације 671Даље, ваља напоменути и то да се слични елементи бинарних стабала не морају налазити у близини (у односу на организацију података). Самим тим, прилично је отежано издвајање скупа сличних речи - кандидата за корекцију одређене грешке. 672Може се закључити да бинарна стабла представљају добро решење за потребе провере постојања речи у речнику, док је за примену техника корекције грешака готово неопходно опремити бинарно стабло додатном погодном структуром података. 6734.2.2. Trie меморије 674Trie информациона структура се заснива, уместо на складиштењу целих речи (односно кључева у општем случају), на складиштењу појединачних симбола речи из речника. Ова структура у великој мери подсећа на свеске са словним индексима. 675Назив "trie" долази као део израза "information retrieval", и први га је употребио Fredkin [Fredkin 60]. Trie меморија се обично приказује као m-арно стабло [Knuth 73], где потомци сваког чвора представљају симболе речи које на почетку имају исте симболе. 676Слика 9 даје табеларни приказ trie стабла у које су убачене следеће речи: mi, mir, miris, mira, mirko, milo, mila, veo, vrt, vi, visoko, vitko, vrelo, veselo, vek, vetar, velik, veto, vera, vest, oblo, oblutak, obla, oblast, oblak, obe, svitac, svetao, sve, svet, svoj, sloj, svaki, svraka, soj, sam, bura, bure, burmut, bal, bol, brz, bog, bis, bistar, beo, blag, bos, film, grub, grm, gord, gad, gnev. Бројеви у заградама означавају чворове стабла, док симболи алфабета означавају потомке који садрже баш тај симбол. Комбинација симбола '' означава чвор који завршава реч, то јест служи за складиштење речи које представљају префикс неких других речи у структури. Ваља приметити да је овакав начин складиштења веома захтеван што се тиче меморијске потрошње, јер сваки чвор садржи везе према свим симболима из алфабета. 677a 678b 679c 680d 681e 682f 683g 684h 685i 686j 687k 688l 689m 690n 691o 692p 693q 694r 695s 696t 697u 698v 699w 700x 701y 702z 703' ' 704(1) 705- - - 706(20) 707- - - 708- - - 709- - - 710film 711- - - 712- - - 713- - - 714- - - 715- - - 716- - - 717(2) 718- - - 719(12) 720- - - 721- - - 722- - - 723(16) 724- - - 725- - - 726(6) 727- - - 728- - - 729- - - 730- - - 731- - - 732(2) 733- - - 734- - - 735- - - 736- - - 737- - - 738- - - 739- - - 740- - - 741(3) 742- - - 743- - - 744- - - 745- - - 746- - - 747- - - 748- - - 749- - - 750- - - 751- - - 752- - - 753- - - 754- - - 755- - - 756- - - 757- - - 758- - - 759- - - 760(3) 761- - - 762- - - 763- - - 764- - - 765- - - 766- - - 767- - - 768- - - 769- - - 770- - - 771- - - 772(4) 773- - - 774- - - 775- - - 776- - - 777- - - 778(5) 779- - - 780mit 781- - - 782- - - 783- - - 784- - - 785- - - 786- - - 787mi 788(4) 789mila 790- - - 791- - - 792- - - 793- - - 794- - - 795- - - 796- - - 797- - - 798- - - 799- - - 800- - - 801- - - 802- - - 803milo 804- - - 805- - - 806- - - 807- - - 808- - - 809- - - 810- - - 811- - - 812- - - 813- - - 814- - - 815- - - 816(5) 817mira 818- - - 819- - - 820- - - 821- - - 822- - - 823- - - 824- - - 825miris 826- - - 827mirko 828- - - 829- - - 830- - - 831- - - 832- - - 833- - - 834- - - 835- - - 836- - - 837- - - 838- - - 839- - - 840- - - 841- - - 842- - - 843mir 844(6) 845- - - 846- - - 847- - - 848- - - 849(7) 850- - - 851- - - 852- - - 853(8) 854- - - 855- - - 856- - - 857- - - 858- - - 859- - - 860- - - 861- - - 862(11) 863- - - 864- - - 865- - - 866- - - 867- - - 868- - - 869- - - 870- - - 871- - - 872(7) 873- - - 874- - - 875- - - 876- - - 877- - - 878- - - 879- - - 880- - - 881- - - 882- - - 883vek 884velik 885- - - 886- - - 887veo 888- - - 889- - - 890vera 891(10) 892(9) 893- - - 894- - - 895- - - 896- - - 897- - - 898- - - 899- - - 900(8) 901- - - 902- - - 903- - - 904- - - 905- - - 906- - - 907- - - 908- - - 909- - - 910- - - 911- - - 912- - - 913- - - 914- - - 915- - - 916- - - 917- - - 918- - - 919visoko 920vitko 921- - - 922- - - 923- - - 924- - - 925- - - 926- - - 927vi 928(9) 929vetar 930- - - 931- - - 932- - - 933- - - 934- - - 935- - - 936- - - 937- - - 938- - - 939- - - 940- - - 941- - - 942- - - 943veto 944- - - 945- - - 946- - - 947- - - 948- - - 949- - - 950- - - 951- - - 952- - - 953- - - 954- - - 955- - - 956(10) 957- - - 958- - - 959- - - 960- - - 961veselo 962- - - 963- - - 964- - - 965- - - 966- - - 967- - - 968- - - 969- - - 970- - - 971- - - 972- - - 973- - - 974- - - 975- - - 976vest 977- - - 978- - - 979- - - 980- - - 981- - - 982- - - 983- - - 984(11) 985- - - 986- - - 987- - - 988- - - 989vrelo 990- - - 991- - - 992- - - 993- - - 994- - - 995- - - 996- - - 997- - - 998- - - 999- - - 1000- - - 1001- - - 1002- - - 1003- - - 1004vrt 1005- - - 1006- - - 1007- - - 1008- - - 1009- - - 1010- - - 1011- - - 1012(12) 1013- - - 1014(13) 1015- - - 1016- - - 1017- - - 1018- - - 1019- - - 1020- - - 1021- - - 1022- - - 1023- - - 1024- - - 1025- - - 1026- - - 1027- - - 1028- - - 1029- - - 1030- - - 1031- - - 1032- - - 1033- - - 1034- - - 1035- - - 1036- - - 1037- - - 1038- - - 1039- - - 1040(13) 1041- - - 1042- - - 1043- - - 1044- - - 1045obe 1046- - - 1047- - - 1048- - - 1049- - - 1050- - - 1051- - - 1052(14) 1053- - - 1054- - - 1055- - - 1056- - - 1057- - - 1058- - - 1059- - - 1060- - - 1061- - - 1062- - - 1063- - - 1064- - - 1065- - - 1066- - - 1067- - - 1068(14) 1069(15) 1070- - - 1071- - - 1072- - - 1073- - - 1074- - - 1075- - - 1076- - - 1077- - - 1078- - - 1079- - - 1080- - - 1081- - - 1082- - - 1083oblo 1084- - - 1085- - - 1086- - - 1087- - - 1088- - - 1089oblutak 1090- - - 1091- - - 1092- - - 1093- - - 1094- - - 1095- - - 1096(15) 1097- - - 1098- - - 1099- - - 1100- - - 1101- - - 1102- - - 1103- - - 1104- - - 1105- - - 1106- - - 1107oblak 1108- - - 1109- - - 1110- - - 1111- - - 1112- - - 1113- - - 1114- - - 1115oblast 1116- - - 1117- - - 1118- - - 1119- - - 1120- - - 1121- - - 1122- - - 1123obla 1124(16) 1125sam 1126- - - 1127- - - 1128- - - 1129- - - 1130- - - 1131- - - 1132- - - 1133- - - 1134- - - 1135- - - 1136sloj 1137- - - 1138- - - 1139soj 1140- - - 1141- - - 1142- - - 1143- - - 1144- - - 1145- - - 1146(17) 1147- - - 1148- - - 1149- - - 1150- - - 1151- - - 1152(17) 1153svaki 1154- - - 1155- - - 1156- - - 1157(18) 1158- - - 1159- - - 1160- - - 1161svitac 1162- - - 1163- - - 1164- - - 1165- - - 1166- - - 1167svoj 1168- - - 1169- - - 1170svraka 1171- - - 1172- - - 1173- - - 1174- - - 1175- - - 1176- - - 1177- - - 1178- - - 1179- - - 1180(18) 1181- - - 1182- - - 1183- - - 1184- - - 1185- - - 1186- - - 1187- - - 1188- - - 1189- - - 1190- - - 1191- - - 1192- - - 1193- - - 1194- - - 1195- - - 1196- - - 1197- - - 1198- - - 1199- - - 1200(19) 1201- - - 1202- - - 1203- - - 1204- - - 1205- - - 1206- - - 1207sve 1208(19) 1209svetao 1210- - - 1211- - - 1212- - - 1213- - - 1214- - - 1215- - - 1216- - - 1217- - - 1218- - - 1219- - - 1220- - - 1221- - - 1222- - - 1223- - - 1224- - - 1225- - - 1226- - - 1227- - - 1228- - - 1229- - - 1230- - - 1231- - - 1232- - - 1233- - - 1234- - - 1235svet 1236(20) 1237bal 1238- - - 1239- - - 1240- - - 1241beo 1242- - - 1243- - - 1244- - - 1245bis 1246- - - 1247- - - 1248blag 1249- - - 1250- - - 1251(22) 1252- - - 1253- - - 1254brz 1255- - - 1256- - - 1257(23) 1258- - - 1259- - - 1260- - - 1261- - - 1262- - - 1263- - - 1264(21) 1265- - - 1266- - - 1267- - - 1268- - - 1269- - - 1270- - - 1271- - - 1272- - - 1273- - - 1274- - - 1275- - - 1276- - - 1277- - - 1278- - - 1279- - - 1280- - - 1281- - - 1282- - - 1283- - - 1284bistar 1285- - - 1286- - - 1287- - - 1288- - - 1289- - - 1290- - - 1291bis 1292(22) 1293- - - 1294- - - 1295- - - 1296- - - 1297- - - 1298- - - 1299bog 1300- - - 1301- - - 1302- - - 1303- - - 1304bol 1305- - - 1306- - - 1307- - - 1308- - - 1309- - - 1310- - - 1311bos 1312- - - 1313- - - 1314- - - 1315- - - 1316- - - 1317- - - 1318- - - 1319- - - 1320(23) 1321- - - 1322- - - 1323- - - 1324- - - 1325- - - 1326- - - 1327- - - 1328- - - 1329- - - 1330- - - 1331- - - 1332- - - 1333- - - 1334- - - 1335- - - 1336- - - 1337- - - 1338(24) 1339- - - 1340- - - 1341- - - 1342- - - 1343- - - 1344- - - 1345- - - 1346- - - 1347- - - 1348(24) 1349bura 1350- - - 1351- - - 1352- - - 1353bure 1354- - - 1355- - - 1356- - - 1357- - - 1358- - - 1359- - - 1360- - - 1361burmut 1362- - - 1363- - - 1364- - - 1365- - - 1366- - - 1367- - - 1368- - - 1369- - - 1370- - - 1371- - - 1372- - - 1373- - - 1374- - - 1375- - - 1376Слика 9 -Табеларни приказ trie стабла 1377Алтернативни начин записивања trie структуре је погоднији што се тиче меморијског заузећа, а своди се на придруживање повезане листе потомака сваком чвору. Слика 10 приказује типичну trie структуру код које је сваки чвор путем повезане листе у вези само са потребним чворовима. 1378Слика 10 - Trie структура 1379Такође, није редак случај да се trie структура имплементира у облику бинарног стабла, са измењеним тумачењем семантике левог и десног потомка [Sinha 88], [Srihari 83], то јест, леви потомак представља симболе на истом месту у стрингу, а десни потомак представља симболе на следећој позицији у стрингу. 1380Са становишта организације речника, trie структура има неколико предности у односу на технике које смештају целе стрингове у записе. Наиме, сам процес одређивања да ли се неки стринг налази у речнику или не је веома брз и не зависи од величине речника, већ само од дужине стринга. Ако је број симбола у алфабету |(|, а дужина стринга N, онда је максималан број број приступа потребан да се утврди постојање неког стринга у речнику |(|N. Међутим, како је код реалних језика број различитих комбинација симбола веома ограничен, то је и број приступа много мањи од овог теоретског максимума. Такође, ова информациона структура је боље прилагођена честој ситуацији када је стринговима могуће приступити само секвенцијално, симбол по симбол. На крају, треба додати, да после неуспешног тражења, у trie структури остаје 'означен' најдужи део у коме се задати стринг и речник поклапају. 13814.2.3. Hash технике 1382Hash технике (to hash - исецкати и/или измешати нешто) подразумевају одређивање функције која као аргумент прима један или више најважнијих атрибута записа у некој информационој структури, а као резултат даје нумеричку вредност, која служи за брзо приступање одређеном запису. У идеалном случају, овом техником се знатно убрзава приступ записима у информационој структури. Међутим, треба указати на проблеме који се јављају приликом имплементације и примене ове технике, нарочито у светлу начина организације речника. Веома је тежак задатак пронаћи једнозначно пресликавање скупа обележја у скуп целих бројева. За решавање овог проблема се углавном користи операција дељења нумеричке представе атрибута по модулу са неким великим простим бројем [Knuth 73]. Уколико је структура која се посматра статичка, задатак је решив. Међутим, у случају да се подаци у структури мењају, често долази до ситуације да се два обележја пресликају у исти број, па је потребно разрешавати конфликтне ситуације. 1383У случају пресликавања више обележја у исти број, користе се технике које омогућавају да се више записа представи истим бројем. И у овом случају се знатно убрзава приступ записима, пошто се углавном мали број кључева поклапа. У ванредним ситуацијама, када се наруши равномеран распоред hash кључева, потребно је променити формулу за израчунавање. 1384Са друге стране, ако се разматра проблем формирања речника, мора се нагласити да технике хеширања поседују додатну неповољну особину. Већина функција које се користе за хеширање као резултат примене на слична обележја даје веома различите резултате, што додатно отежава могућност тражења стрингова сличних задатом у речнику. Уколико би се пројектовала функција која као излаз даје резултате који одсликавају неке важне особине стрингова, она би вероватно могла да послужи за конструисање речника. Посебан случај представљају технике на бази кључева сличности, које покушавају да дају алтернативан начин кодирања стрингова тако да се добију јединствени представници - кључеви, уз истовремено задржавање сличних кључева сличних речи у близини. Ове технике у великој мери зависе од статистичких особина језика и слабо подржавају кодирање великог броја сличних облика једне речи. 13855. ДИЗАЈН СПЕЦИФИКАЦИЈА СИСТЕМА ЗА ПРОВЕРУ ТЕКСТА 1386Ово поглавље даје спецификацију у UML [Booch 97, Eriksson 98] језику једног могућег решења које би подржало проверу исправности текста написаног на српском језику, као и генерисање скупа речи које могу бити кандидати за исправку речи која се не налази у речнику, засновано на разматрању изложеном у претходном поглављу. 13875.1. Основне функције система за проверу текста 1388Систем за проверу текста треба да реализује следеће групе функција: 1389* групу функција за коришћење речника, намењену крајњем кориснику, 1390* групу функција за ажурирање садржаја речника (брисање, додавање и мењање речи из речника), намењену администраторима речника и 1391* групу функција за подешавање параметара рада речника, намењену и администраторима и крајњим корисницима речника. 1392Слика 11 приказује use-case дијаграм система за проверу текста. 1393Прва група функција (за коришћење речника) подразумева следеће сценарије коришћења: 1394* провера постојања речи у речнику: као улазни параметар за сценарио се јавља реч за коју корисник жели да провери да ли се налази у речнику. Резултат извршавања овог сценарија је логичка вредност која потврђује или оповргава претпоставку да се задата реч налази у речнику, 1395* одређивање сличне речи задатој: корисник задаје реч која може и не мора припадати речнику, а као резултат се добија скуп речи које су (по одређеном критеријуму) сличне задатој речи, 1396* провера постојања грешака и њихова корекција у задатом тексту: овај сценарио подразумева комбиновано догађање два претходно описана сценарија. Улазни параметар је текст чија исправност се проверава. Систем потом проверава постојање сваке речи из текста у речнику. У случају да се посматрана реч не налази у речнику, кориснику се предочава листа сличних речи и од њега се захтева да донесе одлуку о прихватању једне од понуђених речи или о наставку рада без измене садржаја текста. 1397Слика 11 - Use-case дијаграм система за проверу текста 1398Друга група функција (за администрирање речника) подразумева следеће сценарије коришћења: 1399* додавање речи у речник: администратор уноси нову реч у речник. Уносе се сви облици речи, као и граматички подаци о њој (врста речи, облик итд.), 1400* брисање речи из речника: задата реч се уклања из речника, 1401* мењање речи из речника: администратор мења облике и/или податке о одабраној речи. 1402Трећа група функција (за подешавање параметара рада речника) својом имплементацијом омогућава прилагођавање начина рада речника конкретним применама. 1403У наставку су дати текстуални описи приказаних use case са слике. 1404Use case: 1405Провера постојања речи у речнику 1406Спољашњи корисник: Корисник 1407Услови који морају бити задовољени пре извршавања: Речник се мора налазити у стању за примање и извршавање упита. Корисник мора да зада реч за коју жели да изврши проверу да ли постоји у речнику. 1408Опис: Омогућава проверу да ли одређена реч постоји у речнику. Уколико корисник није задао реч, јавља се [Грешка реч није задата]. На основу задате речи, речник врши проверу својих структура података. Уколико реч постоји у речнику, Корисник добија потврдан одговор, уз евентуалне податке о типу задате речи и њеном облику у зависности од стања опција система. Ако реч не постоји у речнику, Корисник добија негативан одговор. Уколико током рада речника дође до грешке у интерном функционисању система или систем доспе у неконзистентно стање, јавља се [Интерна грешка у раду система]. 1409Специјални случајеви: [Интерна грешка у раду система] Корисник добија поруку о интерној грешци у раду система. Рад система се зауставља и шаље се упозорење Администратору. 1410[Грешка реч није задата] Корисник се обавештава о томе да мора да зада реч да би проверио да ли она постоји у речнику. 1411Услови који морају бити задовољени након извршавања: Корисник добија одговор на питање о постојању речи у речнику. 1412Use case: 1413Одређивање сличних речи задатој 1414Спољашњи корисник: Корисник 1415Услови који морају бити задовољени пре извршавања: Речник се мора налазити у стању за примање и извршавање упита. Корисник мора да зада реч за коју жели да пронађе скуп сличних речи. 1416Опис: Омогућава да се за одређену реч пронађу све сличне речи у речнику. Уколико корисник није задао реч, јавља се [Грешка реч није задата]. На основу задате речи, речник користи своје операције и генерише скуп сличних речи. Корисник добија скуп речи сличних задатој речи, уз евентуалне податке о типовима задате речи и њеном облику. Уколико током рада речника дође до грешке у интерном функционисању система или систем доспе у неконзистентно стање, јавља се [Интерна грешка у раду система]. 1417Специјални случајеви: [Интерна грешка у раду система] Корисник добија поруку о интерној грешци у раду система. Рад система се зауставља и шаље се упозорење Администратору. 1418[Грешка реч није задата] Корисник се обавештава о томе да мора да зада реч да би добио скуп сличних речи. 1419Услови који морају бити задовољени након извршавања: Корисник добија листу речи сличних задатој. 1420Use case: 1421Провера постојања грешака и њихова корекција у задатом тексту 1422Спољашњи корисник: Корисник 1423Услови који морају бити задовољени пре извршавања: Речник се мора налазити у стању за примање и извршавање упита. Корисник мора да зада текст чију исправност жели да провери. 1424Опис: Омогућава да се провери исправност написаног текста. Уколико корисник није задао текст, јавља се [Грешка текст није задат]. Текст се раставља на засебне речи (токенизује) и проверава. За сваку реч из текста, врши се провера да ли та реч постоји у речнику. Уколико се утврди да реч не постоји у речнику, јавља се [Грешка реч не постоји у речнику]. По завршетку провере, Корисник се обавештава о резултатима провере: броју утврђених грешака и броју промењених речи. Уколико током рада речника дође до грешке у интерном функционисању система или систем доспе у неконзистентно стање, јавља се [Интерна грешка у раду система]. 1425Специјални случајеви: [Интерна грешка у раду система] Корисник добија поруку о интерној грешци у раду система. Рад система се зауставља и шаље се упозорење Администратору. 1426[Грешка текст није задат] Корисник се обавештава о томе да мора да зада текст да би могао да га провери. 1427[Грешка реч не постоји у речнику] Систем прибавља скуп сличних речи. Корисник добија дијалог који га обавештава о томе да је реч погрешно написана и добија листу сличних речи које су потенцијална исправка. После корисникове одлуке о корекцији грешке, провера се наставља. Такође, корисник има могућност да упути поруку администратору система са захтевом да се садржај речника ажурира, то јест да се одређена реч унесе у речник. 1428Услови који морају бити задовољени након извршавања: Корисник добија текст над којим је извршена провера. Корисник је имао могућност да исправи уочене грешке. 1429Use case: 1430Ажурирање садржаја речника 1431Спољашњи корисник: Администратор 1432Услови који морају бити задовољени пре извршавања: Речник се мора налазити у стању за примање и извршавање упита. Администратор мора да изда захтев за покретање операција за ажурирање речника. 1433Опис: Омогућава одабирање опција за ажурирање садржаја речника (додавање, брисање и мењање речи). Речник из стања за примање и извршавање упита прелази у стање за администрирање. Приказује се маска за одабир опција за ажурирање речника. У случају одабира једне од опција за ажурирање, активира се одговарајућа операција за ажурирање. Ако се одабере опција за завршетак ажурирања, речник прелази у стање за примање и извршавање упита. Уколико се одабере непостојећа опција, јавља се [Грешка непостојећа опција]. Уколико током рада речника дође до грешке у интерном функционисању система или систем доспе у неконзистентно стање, јавља се [Интерна грешка у раду система]. 1434Специјални случајеви: [Интерна грешка у раду система] Администратор добија поруку о интерној грешци у раду система. Рад система се зауставља. 1435[Грешка непостојећа опција] Администратор добија поруку о томе да је одабрао непостојећу опцију за ажурирање речника. Рад се наставља. 1436Услови који морају бити задовољени након извршавања: Администратор стартује опцију за ажурирање речника коју је желео, односно завршава ажурирање речника. 1437Use case: 1438Додавање речи у речник 1439Спољашњи корисник: Администратор 1440Услови који морају бити задовољени пре извршавања: Речник се мора налазити у стању за администрирање. Администратор мора да изда захтев за покретање операције за додавање одређеног типа речи у речник. 1441Опис: Омогућава уношење нове речи у речник, укључујући ту и све додатне податке о задатој речи. На основу типа речи, систем приказује форму за унос нове речи. Администратор испуњава форму. Прво се врши провера да ли таква реч већ постоји у речнику, уколико се утврди да реч постоји у речнику, јавља се [Грешка реч већ постоји у речнику]. Потом се од Администратора тражи да потврди унос речи у речник или да одустане од уноса речи. Уколико се потврди унос речи, речник ажурира своје интерне структуре и додаје реч. Ако Администратор одлучи да одустане од уноса речи, садржај форме се поништава и реч се не уноси. Уколико током рада речника дође до грешке у интерном функционисању система или систем доспе у неконзистентно стање, јавља се [Интерна грешка у раду система]. 1442Специјални случајеви: [Интерна грешка у раду система] Администратор добија поруку о интерној грешци у раду система. Рад система се зауставља. 1443[Грешка реч већ постоји у речнику] Администратор добија поруку о томе да задата реч већ постоји у речнику и унос речи се прекида. 1444Услови који морају бити задовољени након извршавања: Администратор добија извештај о додавању речи. Речник остаје у стању за администрирање, приказује се маска за одабир администраторских опција. 1445Use case: 1446Мењање речи у речнику 1447Спољашњи корисник: Администратор 1448Услови који морају бити задовољени пре извршавања: Речник се мора налазити у стању за администрирање. Администратор мора да изда захтев за мењање речи у речнику. 1449Опис: Администратор задаје реч коју жели да мења. Задата реч се тражи у речнику. Уколико реч не постоји у речнику, јавља се [Грешка реч не постоји у речнику]. У случају да је задата реч облик више од једне речи, јавља се [Грешка реч није јединствена]. На основу задате речи, приказује се форма у којој је могућа измена свих облика речи, као и додатних информација о речи. По уносу података, врши се провера да ли промењена реч већ постоји у речнику, то јест, да ли би предложеном изменом дошло до дуплирања речи у речнику; у случају да нова варијанта речи постоји у речнику, јавља се [Грешка реч већ постоји у речнику]. Администратору се пружа могућност да потврди измене или да одустане од измена. Уколико се потврди промена речи, речник ажурира своје интерне структуре, брише стару реч и додаје измењену реч. Ако Администратор одлучи да одустане од промене речи, садржај маске се поништава и реч се не мења. Уколико током рада речника дође до грешке у интерном функционисању система или систем доспе у неконзистентно стање, јавља се [Интерна грешка у раду система]. 1450Специјални случајеви: [Интерна грешка у раду система] Администратор добија поруку о интерној грешци у раду система. Рад система се зауставља. 1451[Грешка реч не постоји у речнику] Администратор добија поруку о томе да је одабрао реч која не постоји у речнику и тражи се да унесе реч из речника. [Грешка реч није јединствена] Администратор добија поруку о томе да је одабрао реч која се као облик различитих речи јавља на више места у речнику и презентује му се листа речи да би одабрао ону коју жели да мења. По одабирању речи из листе рад се наставља. 1452[Грешка реч већ постоји у речнику] Администратор добија поруку о томе да задата реч већ постоји у речнику и промена речи се прекида. 1453Услови који морају бити задовољени након извршавања: Администратор добија извештај о мењању речи. Речник остаје у стању за администрирање, приказује се форма за одабир администраторских опција. 1454Use case: 1455Брисање речи из речника 1456Спољашњи корисник: Администратор 1457Услови који морају бити задовољени пре извршавања: Речник се мора налазити у стању за администрирање. Администратор мора да изда захтев за мењање речи у речнику. 1458Опис: Администратор задаје реч коју жели да обрише. На основу задате речи, приказују се подаци о речи. Задата реч се тражи у речнику. Уколико реч не постоји у речнику, јавља се [Грешка реч не постоји у речнику]. У случају да је задата реч облик више од једне речи, јавља се [Грешка реч није јединствена]. 1459На основу задате речи, приказују се сви подаци о речи и Администратору се пружа могућност да реч обрише или да одустане од брисања. Уколико администратор потврди брисање речи, речник ажурира своје интерне структуре и брише реч из свог садржаја. У случају да администратор одустане од брисања речи до брисања не долази. Уколико током рада речника дође до грешке у интерном функционисању система или систем доспе у неконзистентно стање, јавља се [Интерна грешка у раду система]. 1460Специјални случајеви: [Интерна грешка у раду система] Администратор добија поруку о интерној грешци у раду система. Рад система се зауставља. 1461[Грешка реч не постоји у речнику] Администратор добија поруку о томе да је одабрао реч која не постоји у речнику и тражи се да унесе реч из речника. 1462[Грешка реч није јединствена] Администратор добија поруку о томе да је одабрао реч која се као облик различитих речи јавља на више места у речнику и презентује му се листа речи да би одабрао ону коју жели да мења. По одабирању речи из листе рад се наставља. 1463Услови који морају бити задовољени након извршавања: Администратор добија извештај о брисању речи. Речник остаје у стању за администрирање, приказује се маска за одабир администраторских опција. 1464Use case: 1465Подешавање параметара рада речника 1466Спољашњи корисник: Администратор, Корисник (корисник система) 1467Услови који морају бити задовољени пре извршавања: Речник се мора налазити у стању за примање и извршавање упита. Администратор или Корисник морају да издају захтев за подешавање параметара рада речника. 1468Опис: Приказује се форма за подешавање параметара рада система (одређивање технике за упоређивање, финоћа претраге и сл.). Корисник система мења параметре рада. Приказују се и команде за примену промењених параметара (Apply), завршетак рада уз примену промењених параметара (Ok) и завршетак рада уз одбацивање промена параметара (Cancel). У случају акција са позитивним дејством (Ok и Apply), врши се провера права корисника система за промену параметра, као и исправност вредности задатог параметра. У случају да се нека од провера заврши неуспехом, јављају се [Грешка забрањена промена параметра] и [Грешка недозвољена вредност параметра]. Иначе, систем мења своје интерне параметре у складу са задатим вредностима. 1469Уколико се позове акција за одбацивање промена параметара, нове вредности се одбацују. Уколико током рада речника дође до грешке у интерном функционисању система или систем доспе у неконзистентно стање, јавља се [Интерна грешка у раду система]. 1470Специјални случајеви: [Интерна грешка у раду система] Корисник система добија поруку о интерној грешци у раду система. Рад система се зауставља и шаље се упозорење Администратору. 1471[Грешка забрањена промена параметра] Корисник добија поруку о томе да је покушао да промени параметар за који нема дозволу за мењање и онемогућава се промена параметра. 1472[Грешка недозвољена вредност параметра] Корисник добија поруку о томе да је покушао да зада недозвољену вредност одређеног параметра и онемогућава се промена параметра. 1473Услови који морају бити задовољени након извршавања: Корисник система добија извештај о промењеним параметрима. 1474Из ове анализе уочавају се два (условно речно) пасивна стања речника у коме је могућа комуникација са корисницима система. То су стање за примање и извршавање упита и стање за администрацију система. Остала стања су стања заузетости система. Слика 12 приказује дијаграм стања система. Због прегледности, на дијаграму нису приказани сви специјални случајеви и нису разрађена стања при администрацији система. 1475Слика 12 - Дијаграм стања система за проверу 14765.2. Структура система 1477Слика 13 приказује дијаграм класа речника, на коме се виде односи класа које га сачињавају. 1478Основна класа структуре је речник (Recnik) коме се приступа са захтевима преко интерфејс класе RecnikInterface. На нивоу речника се изводи основна манипулација садржајем: додавање, мењање и брисање речи, као и издавање захтева за провером постојања речи и проналажењем сличних речи. Речник такође остварује везу са техникама за упоређивање стрингова и самих података. У току самог организовања речника, речник може да користи услуге техника за упоређивање стрингова за одређивање идентификатора речи. Карактеристика ове класе је да врши превођење између интерног формата класе Rec и стрингова које враћа као резултат. Речник садржи и своје опције, које чува класа OpcijeRecnika. 1479Садржај речника је организован у структуру речи (StrukturaReci). Ова класа искључиво служи за одвајање података од извршног дела и организује речи у структуру која је погодна за брзо проверавање садржаја, као и за организацију по сличности. На нивоу структуре речи се решава претраживање садржаја и приступ свим или одређеним речима, због чега је опремљена погодним операцијама. 1480Речник се састоји од речи (Rec). Ова класа омогућава смештања саме речи и њених особина, уз могућност провере садржаја. Свака реч има свој идентификатор (idReci) који служи за организовање речи у структуру на вишем нивоу. Идентификатор је обележје које се одређује на основу једне или комбинације одабраних особина речи, као што су корен речи, распоред симбола речи, фреквенција појаве симбола у речи или појаве саме речи, дужина речи и слично. Ово обележје у општем случају није јединствено. 1481На нижем хијерархијском нивоу је извршена специјализација класе Rec која је карактеристична за српски језик. У зависности од начина специјализације, могуће је описати морфолошке структуре других језика. Класу Rec наслеђују две (условно) апстрактне класе (Promenljiva и Nepromenljiva) и тиме омогућавају различит начин складиштења и поступања са речима које имају један или више облика. 1482Класа Promenljiva служи за складиштење променљивих речи српског језика. Код променљивих речи се посебно чува корен речи, а посебно наставци (суфикси) речи агрегирањем класе Sufix. Ова класа организује наставке речи и омогућава да се конструишу сви облици речи. Са друге стране, класа Nepromenljiva је по структури много једноставнија, зато што чува само један облик речи. 1483Најнижа подела резултује класама које представљају посебне врсте речи. На овом нивоу се могу дефинисати и посебна правила за промену променљивих речи. Ова систематизација оставља могућност даљег надограђивања елементима који се баве граматичком и семантичком анализом, као и проширивање речника речима других језика уз могућност рудиментарног превођења. Даља анализа може, по потреби, да укључи и даљу систематизацију речи (на пример, поделу именица по деклинацијама). 1484Други есенцијални део речника је скуп класа које имплементирају технике за упоређивање стрингова, којима се приступа преко интерфејс класе ComparerInterface. Ове класе се имплементирају као потомци апстрактне класе Comparer која дефинише основне методе које свака од техника мора да има да би успешно била коришћена од стране речника. Те методе служе за упоређивање стрингова, као и за одређивање неких карактеристичних вредности за речи (које могу бити употребљене као део идентификатора). Свака од класа самостално организује структуре података које су јој потребне. Такође, класама је омогућен и директан приступ садржају речника, да би се класама омогућило да формирају сопствене податке о садржају речника (на пример, неопходне статистичке податке). 1485На основу претходне анализе, следе дијаграм и структуре класа речника. 1486Слика 13 - Дијаграм класа речника 1487<<interface>> 1488RecnikInterface 1489<<selektor>> 1490+proveriEgzistenciju(rec:String):boolean 1491+nadjiSlicne(rec:String):StringVector 1492+proveriTekst(tekst:String):boolean 1493+podesiOpcije() 1494<<modifikator>> 1495+dodajRec():boolean 1496+brisiRec():boolean 1497+promeniRec():boolean 1498Recnik 1499-reci:StrukturaReci 1500-opcije:OpcijeRecnika 1501<<selektor>> 1502+proveriEgzistenciju(rec:String):boolean 1503+nadjiSlicne(rec:String):StringVector 1504+proveriTekst(tekst:String) 1505+dajOpcije():OpcijeRecnika 1506<<modifikator>> 1507+dodajRec(rec:Reč):boolean 1508+brisiRec(rec:String):StringVector 1509+promeniRec(novaRec:Reč, staraRec:Reč):boolean 1510+primiOpcije():(opcije:OpcijeRecnika):boolean 1511OpcijeRecnika {persistent} 1512-opcije:StrukturaOpcija 1513<<selektor>> 1514+dajOpciju(opcija:String):String 1515<<modifikator>> 1516+primiOpciju():(opcija:String):boolean 1517StrukturaReci {persistent} 1518-reci: InternaOrganizacijaReci 1519<<selektor>> 1520+dajSekvencu():RecEnumeration 1521+dajOkolinu(rec:String):RecEnumeration 1522+proveriRec(rec:String):Boolean 1523+dajRec(rec:String):RecVector 1524<<modifikator>> 1525+brisiRec(idReci:integer):Boolean 1526+dodajRec(rec:Rec):integer 1527+promeniRec(novaRec:Rec, staraRec:Rec):integer 1528Rec {abstract}, {persistent} 1529-idReci:String 1530-sadrzaj:String 1531<<selektor>> 1532+dajId():integer 1533+proveri(rec:String):boolean {abstract} 1534+svioblici():StringVector {abstract} 1535+osnovniOblik():String 1536+oblik(idoblika:String):String {abstract} 1537+listaoblika():StringVector {abstract} 1538<<modifikator>> 1539+postaviId(id:String) 1540Promenljiva {abstract} 1541-nastavci:Sufix 1542<<selektor>> 1543+proveri(rec:String):boolean 1544+svioblici():StringVector 1545+oblik(nazivoblika:String):String 1546+listaoblika():StringVector 1547Sufix 1548-idSufix:String 1549-nastavci:StringVector 1550-imenanastavaka:StringVector 1551<<selektor>> 1552+proveri(nastavak:String):boolean 1553+svinastavci():StringVector 1554+nastavakbroj(broj:Integer):String 1555+oblik(nazivoblika:String):String 1556Nepromenljiva {abstract} 1557<<selektor>> 1558+proveri(rec:String):boolean 1559+svioblici():StringVector 1560+oblik(nazivoblika:String):String 1561+listaoblika():StringVector 1562Comparer {abstract} 1563+difference(X:String,Y:String):Real {abstract} 1564+calcID(X:String):String {abstract} 1565EditDistance 1566+difference(X:String, Y:String):Real 1567+calcID(X:String):String {abstract} 1568SoundEx 1569+difference(X:String, Y:String):Real 1570+calcID(X:String):String 1571Ngram 1572+difference (X:String, Y:String) 1573+calcID(X:String):String 15745.3. Динамички дијаграми 1575Начин и логика рада рада најважнијих операција система за проверу текста дате су динамичким дијаграмима. 1576Слика 14 приказује дијаграм секвенци процеса провере постојања речи, посматран са нивоа речника. Класа Recnik је снабдевена методом proveriEgzistenciju(rec) која се ослања на методу proveriRec(rec) класе StrukturaReci. Структура у којој су смештене речи испитује речи из околине задате речи. Уколико се ради о променљивој речи, ова тада проверава и своје суфиксе. Резултат ове операције је логичка вредност која је постављена на тачно уколико се реч налази у речнику, односно на нетачно, ако се реч не налази у речнику. 1577Слика 15 приказује дијаграм секвенци генерисања скупа речи сличних задатој. У овај скуп улазе све речи чија разлика од задате речи одговара критеријуму. Разлику између речи, као број, одређује класа за упоређивање речи (Comparer). Сличне речи се враћају у облику вектора речи. Речник прво издаје структури речи захтев да генерише околину речи. Креира се привремена енумерација речи која служи за приступ. Потом се креира вектор стрингова у који ће бити смештане довољно сличне речи. Овим су завршене припреме за започињање главног циклуса у коме се свака реч упоређује са задатом, и оне које су довољно сличне се смештају у резултујући вектор сличних речи. 1578Слика 14 - Дијаграм секвенце провере постојања речи 1579Слика 15 - Дијаграм секвенци за процес генерисања сличних речи 15806. ИМПЛЕМЕНТАЦИОНИ ДЕТАЉИ 1581У претходном поглављу дата је дизајн спецификација система за проверу текста. У циљу провере исправности претпоставки из спецификације, извршена је имплементација система за проверу текста. Ово поглавље указује на најбитније моменте у имплементацији. 1582Постоји неколико важних одлука које, у случају имплементације овог система, треба донети. Најважнији моменти су: 1583* архитектура система, 1584* избор структуре података за организацију речи, 1585* имплементација операције претраживања, 1586* имплементација операције генерисања сличних речи и 1587* имплементација процеса провере текста 1588У овом поглављу ће такође бити размотрен проблем коришћења симбола који нису у енглеском алфабету. 15896.1. Архитектура система 1590За архитектуру система је одабрана клијент - сервер дистрибуирана архитектура. Ово решење је одабрано због тога што представља омогућава централизовано ажурирање садржаја речника и смањује захтеве за процесорском снагом и оперативном меморијом клијената. 1591За имплементацију клијентског дела система одабран је програмски језик JAVA због своје портабилности, добро дефинисаног превођења UML модела у класе писане овим програмским језиком, одличне подршке за мрежну комуникацију и интернационализацију, као и због могућности брзог развоја апликација у овом програмском језику. 1592Серверски део система је знатно сложенији у погледу имплементације, са више могућности за реализацију. Један од једноставнијих начина је коришћење већ развијених серверских система са подршком за писање модула који се извршавају на њима, као што су WWW сервери (преко CGI процедура, Active Server Pages модула, Servlet класа) или коришћење протокола за дистрибуирану обраду као што су CORBA, DCOM или RMI. У овој имплементацији за реализацију сервера је коришћен Sun Java Web Server. Последица ове одлуке је да се и сервер имплементира у програмском језику JAVA. 1593Слика 16 приказује модел структуре дистрибуираног система. 1594Серверски део система се састоји од једног или више речника, који су агрегирани у пакет RecnikServer. Он има задатак да обрађује захтеве које добија од клијената и служи као спој између корисника и сервера. Према томе, задаци пакета RecnikServer су следећи: 1595* пријем захтева од клијената, било да се ради о администраторима или обичним корисницима, 1596* директна комуникација са речницима и 1597* слање резултата обраде корисницима. 1598Како се у реалној примени врши провера текстова а не индивидуалних речи, то је потребно донети одлуку о томе где ће се извршити раздвајање текста на индивидуалне речи. Овај процес, познат још и као токенизација, могу обављати како сервер, тако и клијент. Међутим, треба напоменути да је процес исправљања грешака полу-аутоматски, то јест да сам корисник одлучује да ли ће исправити пријављену грешку и коју ће од понуђених речи одабрати као исправку. Из овог разматрања следи природна одлука да токенизацију врши клијент и да шаље појединачне речи серверу на проверу. У случају да се утврди да је у питању грешка, клијент добија листу речи, потенцијалних исправки грешке. 1599Серверски систем је, природно, снабдевен пакетом класа за мрежну подршку (NetworkSupport), која је задужена за комуникацију у мрежном окружењу. Ова класа представља интерфејс према окружењу и одређује комуникациони протокол. 1600Важан део система је и подршка за исправно примање и слање информација које нису писане на енглеском језику. Овим задатком се бави пакет класа InternationalSupport, која обезбеђује исправно тумачење примљених симбола, као и исправно слање симбола намењених клијенту. 1601Клијентски подсистем се извршава на корисничком рачунару. У принципу, могуће је разликовати две врсте клијентских апликација: корисничку и администраторску, мада оне могу бити обједињене. Задаци клијентског подсистема су: 1602* слање захтева серверу, 1603* обрада података примљених од сервера, 1604* раздвајање корисничког текста на речи (токенизација) и 1605* рад корисничког интерфејса (уз алтернативну могућност комуникације са корисничком апликацијом). 1606Најважнија класа клијентског дела система је класа Klijent која обрађује текст. Следи структура ове класе. 1607Klijent 1608-tekstZaProveru:String 1609-reciIzTeksta:StringVector 1610-adresaServera:RecnikServerURL 1611<<selektor>> 1612+proveriTekst(tekst:String) 1613+proveriRec(rec:String):StringVector 1614-tokenizujTekst(tekst:String):StringVector 1615<<modifikator>> 1616+prikaziKandidateZaKorekciju(kandidati:StringVector):String 1617Клијентски подсистем такође користи клијентске пакете за мрежну комуникацију и интернационализацију (NetworkSupport и InternationalSupport), у циљу обезбеђивања исправне комуникације са сервером. 1618Подсистеми користе услужне пакете класа преко дефинисаних интерфејса за приступ. Операције неких од интерфејса следе. 1619<<interface>> 1620NetInterface 1621<<selektor>> 1622+posaljiString(adresa:String, s:String):Boolean 1623<<modifikator>> 1624+slusaj() 1625+primiString():String 1626<<interface>> 1627IntlInterface 1628<<selektor>> 1629+encodeString(s:String):String 1630+decodeString(s:String):String 1631<<interface>> 1632GUIInterface 1633<<selektor>> 1634+initGUI():Boolean 1635+prikaziDijalogZaKorekciju 1636(rec:String, kandidati:StringVector):String 1637+getTekst():String 1638<<modifikator>> 1639+setTekst(tekst:String) 1640Слика 16 - Дијаграм елемената дистрибуираног система 1641Слика 17 приказује дијаграм развоја (deployment diagram) система за проверу и корекцију текста. У систему се појављује један тип сервера на коме се налази речник. Постоје две врсте клијента, кориснички и администраторски. Са корисничког клијента је могуће вршити само операције везане за проверу текста и претрагу речника. Администраторски клијент омогућава, поред претходних операција, и подешавање параметара рада сервера, као и ажурирање речника. 1642Претпостављени, али не и обавезни начин комуникације између подсистема је TCP/IP протокол. 1643Слика 17 - Дијаграм развоја елемента система 16446.2. Структура података речника 1645Класа StrukturaReci система за проверу текста треба да имплементира информациону структуру која треба да на одговарајући начин омогући обављање основних функција речника: проверу постојања речи и генерисање сличних речи. 1646Прво питање везано за имплементацију структуре речи је одлука о томе да ли развијати посебну структуру, односно користити већ развијене структуре података или се ослонити на систем за управљање базама података. Ова структура мора бити опремљена методама за претраживање садржаја и приступ свим или одређеним речима. Интерно, речи су организоване по својим идентификаторима, који могу, а не морају бити јединствени. У случају да се ради о нејединственим идентификаторима, сваком идентификатору се додељује информациона структура која садржи све речи са истим идентификатором. Питање одабира погодне структуре података је од критичне важности за перформансе речника, нарочито у ситуацијама када речник има велики број речи. Одлука о томе да ли користити посебно конструисане структуре података или систем за управљање базом података је условљена пре свега могућношћу складиштења речника у оперативну меморију. У сваком случају, структура речи мора имати начин да оствари перзистенцију, то јест могућност да свој садржај забележи и учита са трајних медијума. 1647Ова имплементација организује структуру речи као hash табелу. Идентификатор за приступ речи у табели је њен корен. Због начина одређивања корена речи (видети одељак 7.4 за детаљнију дискусију о начину кодирања речи), могуће да више различитих речи има исти корен. Стога, објекат који се референцира у табели је вектор који садржи инстанце класа изведених из класе Rec, а које имају исти корен. 1648StrukturaReci 1649-orgReci: Hashtable 1650<<selektor>> 1651+dajSekvencu():Enumeration 1652+dajOkolinu(rec:String):Vector 1653+dajRec(rec:String):Vector 1654+proveriRec(rec:String):boolean 1655+proveriRec(rec:Rec):Rec 1656+snimi(datoteka:DataOutputStream):boolean 1657<<modifikator>> 1658+brisiRec(rec:Rec):boolean 1659+dodajRec(rec:Rec):boolean 1660+promeniRec(novaRec:Rec, staraRec:Rec):boolean 1661+ucitaj(datoteka:DataInputStream):boolean 1662Структура речи оперише искључиво са инстанцама класе Rec. Једини изузетак су операције за проверу постојања одређеног облика речи, приступања речима и приступања околини речи које као параметар примају стринг. 1663Речи су у структури речи смештене у инстанцама класа изведених из класе Rec. Ово је апстрактна класа која садржи једну реч српског језика која је истовремено и основни елемент речника. Врста речи и њени могући облици су одређени у класама потомцима. 1664Реч је записана као корен и низ суфикса чијим се додавањем на корен добија исправан облик речи. Корен и суфикси су записани у облику JAVA String класе у којој су поједини симболи кодирани по UNICODE стандарду. Основни облик речи у општем случају није граматички корен речи, већ се одређује као најдужа заједничка почетна подсеквенца свих облика неке речи. 1665Свака реч има свој идентификатор који служи за организовање речи у структуру на вишем нивоу. За идентификатор речи је могуће узети корен речи или неки други кључ. У случају да се одабере корен речи, који у случају непроменљивих речи представља саму реч, веома је вероватна ситуација у којој ови идентификатори нису јединствени. Међутим, могуће је одабрати и неку другу вредност која ће бити јединствена за сваку реч. Још је боље уколико се за идентификатор одабере неки од кључева сличности (као што су SOUNDEX, skeleton или omission кључ). Ова одлука се доноси на нивоу речника, приликом уношења речи и јединствена је за све речи у речнику. Одабирање кључева сличности за идентификаторе олакшава структури речи проналажење сличних речи. Основна класа такође смешта и основни облик речи. Нове речи се конструишу коришћењем креационог шаблона factory да би се постигао униформни прилаз формирању речи. 1666Rec {abstract}, {persistent} 1667-idReci:String 1668-osnOblik:String 1669+factory(data:Vector):Rec 1670<<selektor>> 1671+dajid():integer 1672+proveri(rec:String):boolean {abstract} 1673+svioblici():Vector {abstract} 1674+osnovniOblik():String 1675+oblik(idoblika:String {abstract} 1676+listaoblika():Vector {abstract} 1677-snimi(datoteka:DataOutputStream):boolean 1678<<modifikator>> 1679+postaviid(id:String) 1680-ucitaj(datoteka:DataInputStream):boolean 1681Основну класу речи наслеђују две (условно) апстрактне класе (Promenljiva и Nepromenljiva) тиме омогућавају различит (а због перформанси потребан) начин складиштења и поступања са речима које имају један или више облика. 1682Класа за променљиве речи служи за складиштење природних језика који садрже велику количину променљивих речи, као што је случај са српским језиком. Она агрегира класу која организује наставке (суфиксе) речи (Sufix). Класа за складиштење наставака може да врати све наставке, одређени (именовани) наставак или наставак по редном броју, као и да провери да ли одређени наставак постоји у листи наставака. Наставци су смештени у једноставну и брзу структуру података, као што је hash табела, зато што у овом домену није потребно вршити апроксимативно упоређивање (оно се врши на нивоу целе речи) и зато што речи имају релативно мали број облика, што повлачи мали број кратких наставака. Основни облик променљиве речи је корен који се одређује као почетни део стринга који заједнички свим облицима речи. 1683Promenljiva {abstract}, {persistent} 1684-nastavci:Sufix 1685<<selektor>> 1686+proveri(rec:String):boolean 1687+svioblici():StringVector 1688+oblik(nazivoblika:String):String 1689+listaoblika():StringVector 1690-snimi(datoteka:DataOutputStream):boolean 1691<<modifikator>> 1692-ucitaj(datoteka:DataInputStream):boolean 1693Sufix {persistent} 1694-nastavci:Hashtable 1695-imenanastavaka:Vector 1696<<selektor>> 1697+proveri(nastavak:String):boolean 1698+svinastavci():Vector 1699+nastavakbroj(broj:Integer):String 1700+oblik(nazivoblika:String):String 1701-snimi(datoteka:DataOutputStream):boolean 1702<<modifikator>> 1703-ucitaj(datoteka:DataInputStream):boolean 1704Nepromenljiva {abstract}, {persistent} 1705<<selektor>> 1706+proveri(rec:String):boolean 1707+svioblici():StringVector 1708+oblik(nazivoblika:String):String 1709+listaoblika():StringVector 1710-snimi(datoteka:DataOutputStream):boolean 1711<<modifikator>> 1712-ucitaj(datoteka:DataInputStream):boolean 1713Сви наставци речи се чувају у hash табели sufixes. Кључеви за прилаз наставцима су кодирани називи наставака. Именовање наставака није битно за решавање проблема корекције текста, али може да олакша евентуалну граматичку или семантичку анализу текста. 1714Најнижа подела резултује конкретним класама које представљају врсте речи и имају могућност различите имплементације, у зависности од потреба. Ова систематизација оставља могућност даљег надограђивања елементима који се баве граматичком и семантичком анализом, као и проширивање речника речима других језика уз могућност рудиментарног превођења. На нивоу ових класа се такође конкретизују и називи наставака у случају променљивих речи. 17156.3. Имплементација процеса претраге речника 1716Као што је већ раније напоменуто, претрагом речника се решава проблем установљавања чињенице да се у тексту налази грешка, то јест, уколико се реч из текста не нађе у речнику, закључак је да је нађена грешка у тексту. Слика 14 даје дијаграм секвенци утврђивања постојања неке речи у тексту. Као што се са дијаграма може видети, процес претраге речника се одвија у неколико етапа. 1717Прва етапа претраге се ослања на способност структуре речи да издвоји подскуп речника који садржи блиске речи задатој. Овај задатак се решава тако што се узима подскуп речи које почињу истим првим униграмом или диграмом као и тражена реч. Претпоставка на којој почива ово решење је да се грешке на првом симболу у речи релативно ретко јављају. Такође, ако се за идентификатор речи одреди нека врста кључа сличности (на пример, SOUNDEX кључ заснован на статистичким подацима српског језика), могу се узимати и већи делови кључа. Издвајање оваквог подскупа се, у случају коришћења система за управљање базама података, изводи упитом са дефинисаним префиксом и слободним крајем упита (like 'p*'). У случају меморијске структуре података, структуру је добро организовати као низ hash табела, којима се приступа или преко табеле са првим симболима речи, или преко trie структуре дубине 2 или 3. 1718Други етапа претраге укључује приступ ускладиштеним коренима речи. У случају да се ради о непроменљивој речи, на овом нивоу се врши упоређивање речи са задатом - тражењем на основу речи по hash табели у случају меморијске структуре, односно директном претрагом подскупа табеле из базе података. 1719Трећа етапа се односи само на променљиве речи. За сваки од облика променљивих речи се проверава да ли је једнак траженој речи. 1720Слика 18 приказује дијаграм активности процеса за проверу постојања речи у речнику. 1721Слика 18 - Дијаграм активности провере постојања речи у речнику 17226.4. Имплементација процеса генерисања скупа сличних речи 1723Вероватно најважнији процес који треба имплементирати у оквиру система за проверу текста је операција генерисања скупа сличних речи. 1724У случају генерисања скупа сличних речи (Слика 19), први ниво претраге остаје исти као и у случају претраге речника. На другом нивоу претраге се генерише шири скуп кандидата коришћењем следећих елиминационих корака: 1725* у случају непроменљивих речи, одбацују се све речи које се по дужини разликују од задате речи за више од одређеног броја који се задаје као опција речника, 1726* код променљивих речи, одбацују се оне речи код којих се дужина корена увећана за средњу дужину наставака речи разликује од дужине задате речи за више од горе наведеног броја, 1727* корени преосталих речи се упоређују апроксимативним методама са почетним подстрингом задате речи одговарајуће дужине (непроменљиве речи се упоређују са целом задатом речи) и одбацују се све речи чија је разлика од задате речи већа од задатог фактора грубе селекције, који је такође опција речника. Резултати овог упоређивања се бележе. 1728Трећи ниво претраге се обавља над овако суженим скупом. Непроменљиве речи чија је сличност са задатом речи довољно велика одмах иду у скуп сличних речи. Код променљивих речи се врши још једно упоређивање, овај пут целих облика речи. Од речи чија сличност задовољава фактор фине селекције формира скуп сличних речи. 1729Слика 19 - Дијаграм активности проналажења сличних речи 1730Као пример методе за упоређивање стрингова која се користи за упоређивање стрингова, дат је листинг операције за упоређивање на бази едит растојања. 1731public class EditDistance implements Comparer 1732{ 1733 /**Calculates difference between two strings according to 1734 edit distance algorithm */ 1735 public double difference(String X, String Y) 1736 { 1737 int Xlen = X.length(); 1738 int Ylen = Y.length(); 1739 int i = 0; 1740 int j = 0; 1741 // This is matrix for calculation 1742 int[][] dist = new int[Xlen+1][Ylen+1]; 1743 // Initializing starting values 1744 dist[0][0]=0; 1745 for(i = 1; i<= Xlen; i++) 1746 dist[i][0] = dist[i-1][0]+delf(X.charAt(i-1)); 1747 for(j = 1; j<= Ylen; j++) 1748 dist[0][j] = dist[0][j-1]+insf(Y.charAt(j-1)); 1749 // Calculating distance 1750 for(i = 1; i<=Xlen; i++) 1751 for(j = 1; j<=Ylen; j++) 1752 dist[i][j]=Math.min(dist[i-1][j-1] 1753 +subf(X.charAt(i-1),Y.charAt(j-1)), 1754 Math.min(dist[i-1][j]+delf(X.charAt(i-1)), 1755 dist[i][j-1]+insf(Y.charAt(j-1)))); 1756 return dist[Xlen][Ylen]; 1757 } 1758 /**Returns distance for substitution*/ 1759 int subf(char X, char Y) 1760 { 1761 if(X == Y) 1762 return(0); 1763 else 1764 return(1); 1765 } 1766 /**Returns distance for insertion*/ 1767 int insf(char Y) 1768 { 1769 return(1); 1770 } 1771 /**Returns distance for deletion*/ 1772 int delf(char X) 1773 { 1774 return(1); 1775 } 1776} 1777Коришћење техника за упоређивање стрингова у случају симбола карактеристичних за српски језик не захтева уношење већих концепционих измена. Сама чињеница да програмски језик JAVA за смештање симбола користи тип char који је шеснаестобитни значи да стрингови могу садржати све симболе који су дефинисани UNICODE стандардом. Једини евентуални проблем су различити кодови симбола за ћирилицу и латиницу. Овај проблем се решава униформном репрезентацијом симбола у речнику (или ћирилицом или латиницом) уз развој одговарајућих метода за конверзију из једног писма у друго. 17786.5. Провера текста 1779Главни процес током коришћења система је провера исправности текста. Овај процес интерно користи процесе претраживања речника и генерисања скупа сличних речи. Овај процес је дистрибуиран - догађа се и на клијенту и на серверу. 1780Слика 20 приказује дијаграм секвенци процеса провере текста у дистрибуираном окружењу. У њему учествују клијент и сервер. На клијентској страни се врши рашчлањивање текста на појединачне речи. Серверска страна прво проверава постојања речи и у случају да се задата реч не налази у речнику, проналази скуп сличних речи, који враћа клијенту. 1781Претпоставка везана за овај дијаграм секвенци је да клијент самостално одржава кориснички интерфејс, то јест да не постоји спољна апликација која позива методе клијента. 1782Слика 20 - Дијаграм секвенци процеса провере текста 1783На почетку процеса, клијент генерише текст за проверу на основу садржаја откуцаног текста. Токенизација текста за проверу се врши паралелно са провером свих речи из текста у главној петљи. Из текста се издваја реч по реч. Свака реч се шаље речничком серверу на проверу. Уколико се добије негативан одговор, клијент шаље серверу захтев за генерисање сличних речи. Као одговор, добија се вектор речи које су сличне задатој. Клијент тада формира дијалог за исправку текста и корисник је у могућности да исправи текст, односно да игнорише пријављену грешку. 1784Треба напоменути да у систему није предвиђена могућност да корисник сам додаје речи у речник. Наиме, главна идеја је да постоји један, централни речник о чијем се ажурирању брину администратори речника. Евентуално, може се омогућити кориснику да пошаље захтев администраторима за унос нове речи у речник. 17856.6. 1786Проблем коришћења нашег језика у JAVA окружењу 1787Примарни језик везан за коришћење рачунара је енглески. Веома дуго су рачунари били прилагођени искључиво коришћењу на енглеском језику. Ипак, тренд глобализације светског рачунарског тржишта довео је до тога да су се програми прилагођавали и другим језицима, углавном онима који се користе на осталим великим тржиштима (Француска, Немачка). У задњих неколико година, актуелан је тренд локализације, тј. прилагођавања и софтвера и хардвера тржиштима које користе различите језике. Локализација подразумева конзистентно и задовољавајуће решавање следећих проблема: складиштење и кодирање симбола алфабета неког језика, приказ симбола у оквиру кор???????? ??????????, ????????? ??????????? ? ??????????? ??????? ?????? ????? ???? ????????????? ??????? (?????????, ?????????? ????...), као и приказивање порука и података на језику корисника рачунара. 1788С обзиром на то да наша земља представља релативно мало тржиште на глобалној рачунарској сцени, проблем складиштења и приказивања симбола специфичних за наш језик је дуго био занемариван од стране произвођача хардвера и софтвера. Ова ситуација је довела до тога да су се корисници рачунара у Југославији довијали на разне начине да би користили слова која су специфична за наш језик, што је опет довело до појаве великог броја међусобно некомпатибилних начина кодирања (YUSCII, ????????...). Сви ови распореди су користили неке симболе који се ретко користе у нашем језику за смештање слова специфичних за српски језик. Поштовање српске азбуке у задацима сортирања је била реткост, пре него правило. 1789Први покушај стандардизације је изведен од стране софтверске куће Microsoft. За DOS окружење је предложена кодна страна 852, а за Windows окружење кодне стране 1250 за латиницу и 1251 за ћирилицу. Ови распореди делимично решавају проблем коришћења српског језика. Међутим, ваља напоменути да ови распореди користе 8-битни начин кодирања, што значи да је могуће дефинисати свега 256 симбола, од којих су 128 унапред резервисани ASCII стандардом. На подручју наше земље се равноправно користе два писма: ћирилица и латиница. Ни један од ових распореда, због тога што представљају решење које покрива више од једне земље, не покрива истовремено и ћирилицу и латиницу. Такође, проблеми се повећавају у случају појављивања потребе за коришћењем више различитих писама и скупова симбола у једном тексту (без информације о фонтовима), као што апликације у библиотечким информационим системима (где се истовремено могу појавити латиница, ћирилица, грчки алфабет и математички симболи). 1790Решење ових проблема представља стандард UNICODE, који прописује 16-битно кодирање симбола и омогућава запис 65535 симбола, што је довољан број за све симболе језика који се користе на нашој планети, искључујући ту идеограмска писма. Нажалост, подршка оваквом начину кодирања подразумева опсежан и компликован прелаз са 8-битног кодирања, које је веома дуго коришћено (већина програмских језика за складиштење променљивих типа карактер користи 8 бита). Такође, ова промена аутоматски доводи до дуплирања простора који заузимају текстуалне датотеке. Корак ка прихватању овог типа стандардизације је направљен у оперативном систему Windows NT (од верзије 3.51), пословном програмском пакету Office 97, као и у програмском језику JAVA, који сви интерно користе UNICODE начин записивања симбола. 1791Проблем заузећа простора 16-битним симболима, као и кодирање симбола независно од платформе је решено UTF-8 стандардом, који прописује једнозначно превођење UNICODE текста у скуп 8, 16 и 24-битних низова симбола у зависности од њиховог положаја у UNICODE табели (видети прилог 3). На овај начин је решен пренос текстова између различитих платформи. 1792Што се тиче решавања осталих проблема везаних за локализацију програма, веома је уочљив тренд писања програма само за једно тржиште, уз накнадно преправљање програма на нивоу изворног кода за неко друго тржиште. Овај приступ знатно повећава време потребно за одржавање апликације и поскупљује развој. Добро решење би била конзистентна подршка интернационализацији софтвера, што подразумева априорно издвајање компоненти које зависе од локације коришћења софтвера у засебне модуле чија примена управо зависи од корисника програма. Оперативни систем Windows од верзије 95 и Windows NT од верзије 3.51 пружају ограничену подршку локализацији преко Win32 API. 1793Програмски језик JAVA даје комплетну спецификацију за решавање проблема локализације. Спецификација овог језика посматра локализацију програма као решавање следећих проблема: идентификација језика и правила корисника, подршка подацима зависним од локације извршавања, форматирање података, сортирање података, подршка кодирању, обради и приказивању симбола алфабета неког језика. 1794Идентификација језика и правила корисника се обавља класом Locale. Конструктори ове класе захтевају податак о језику и земљи, и евентуално о специфичној ужој спецификацији правила (варијанта). Апликација може да има дефинисане своје Locale објекте, док их елементи корисничког интерфејса обавезно имају. Све процедуре које зависе од локално специфичних података би требало да консултују објекат ове класе и прилагоде своје извршавање на основу добијених података. 1795За подршку смештању података зависних од локације извршавања се користе класе изведене из класе ResourceBundle. Ове класе садрже све објекте који су различити у верзијама програма који се користе на различитим локацијама. Подаци за једну локацију се налазе у изведеној класи чије се име завршава са скраћеницом језика и земље. У већини случајева, ови објекти су стрингови, али не постоји ограничење на тип објекта. Подржано је, такође, и именовање аргумената у оквиру стринга, чиме је могуће премештање потребних аргумената у испису на одговарајуће место. 1796Форматирање података у зависности од језика је подржано класама изведеним из класе Format, као што су MessageFormat, DateFormat и сличне. Ове класе подржавају српски језик, у латиничном и ћирилићном писму. 1797Сортирање текстуалних података се увек своди на поређење појединачних симбола по величини. ASCII распоред симбола одговара само енглеском говорном подручју. За сортирање по правилима неког другог језика, потребно је дефинисати табеле за упоређивање симбола. У JAVA програмском језику овај задатак обавља класа Collator, која подржава српску латиницу и ћирилицу. 1798Програмски језик JAVA интерно у потпуности подржава и UNICODE и UTF-8 запис. Тип података char, који служи за смештање симбола је 16-битни. Класе за улаз (DataInputStream) и излаз (DataOutputStream) су снабдевене методама које пишу и читају UTF-8 кодиране стрингове (readUTF и writeUTF). Од ревизије 1.1, JAVA у свом новом скупу улазно/излазних класа (класе изведене из апстрактних Reader и Writer класа) подржава произвољно кодирање симбола путем дефинисања садржаја системске променљиве file.encoding. 1799Обрада симбола је подржана класом Character, која поседује методе за испитивање симбола, као што су isDigit, isLetter и сличне, који узимају у обзир специфичности алфабета дефинисаног Locale класом. Такође, постоји и класа BreakIterator, која омогућава кретање по тексту у произвољном смеру и са скоковима величине индивидуалних симбола, речи, реченица или линија текста. 1800Приказ симбола је, нажалост, најслабија тачка подршке програмског језика JAVA за интернационализацију и локализацију. Подршка за приказ фонтова јесте добра и методи типа drawChars ће коректно исписати UNICODE кодиране симболе. Међутим, компоненте корисничког интерфејса се у великој мери ослањају на платформу на којој се програм извршава и зависе од њених могућности за приказ симбола. Иако Windows NT и 95 платформе могу да раде са UNICODE симболима (та подршка је задовољавајућа у програмском пакету Office 97), системска подршка коју користи JAVA виртуелна машина не подржава приказивање пуног UNICODE скупа симбола одједном. Ово је случај са класама корисничког интерфејса као што су TextComponent, TextField, и TextArea, које се користе за комуникацију са корисником. Овај проблем се може решити писањем платформски независних компонената корисничког интерфејса. Вероватно је да ће нова верзија JAVA програмског језика (1.2) употребити управо овакав приступ. 18016.7. Завршне напомене 1802Пројектована структура је погодна за примену у реалној ситуацији. Генерисање скупа сличних речи је рачунски захтеван процес, те је потребно ограничити скуп над којим се примењује у реалној ситуацији. Дизајн система омогућава партиционисање речника на више подскупова, чиме се убрзава генерисање скупа сличних речи. 1803Показало се да оваква анализа проблема омогућава примену пројектованог система и за друге језике сем српског. Два аспекта разматрања проблема у којима коришћење српског језика утиче на изведбу су технике за проналажење сличних речи које се ослањају на статистичке особине циљног језика и могућност препознавања типа речи, то јест проширивање речника информацијама о семантици. Дакле, нема проблема да се оваква структура искористи за писање система за проверу текста и на неком другом језику, као и да се оствари систем који може да проверава текст писан на више језика. 1804Информације о конкретном језику се могу искористити у пројектовању система и тако што се користе морфолошка правила за речи које не спадају у изузетке. На овај начин, одређен број променљивих речи се чува као корен речи уз додатну информацију о функцији која аутоматски одређује потребне наставке, што утиче на смањење меморијских захтева. Променљиве речи које се не могу сматрати правилним се чувају на раније предложен начин. 1805Што се тиче перформанси и заузећа меморијског простора, закључак је да овакав систем генерално треба имплементирати у више нивоа. Меморијски захтеви структура за смештање података (реда величине 100 бајта) омогућавају коришћење меморијских структура за речнике средње величине (око 50.000 речи), што даје добре перформансе код текстова општег карактера. Важна је напомена да се смањење потребе за меморијом у највећој мери остварује организовањем променљивих речи у структуру која чува корен и наставке речи. Остатак речника, као и специјализовани, стручни речници се имплементирају у коришћењем услуга система за управљање базама података. 1806Систем је тестиран на платформи са процесором Pentium на 150Mhz, са 32 мегабајта меморије. Тестирање је обухватило проверу перформанси система приликом провере постојања речи у речнику и генерисања скупа сличних речи. И клијент и сервер су се налазили на истом рачунару. Речник се састојао од око 100 речи. Приликом тестирања, време претраге речника, без обзира на то да ли се завршавало успехом или неуспехом је износило мање од 10ms. Процес генерисања сличних речи је захтевао између 10 и 50ms, што указује на прихватљиве перформансе за коришћење на савременим рачунарским системима са подршком за извршавање програма писаних на програмском језику JAVA. 1807Такође, ваља нагласити да опредељење за клијент - сервер архитектуру генерално ослобађа клијентске рачунаре од превеликих захтева за ресурсима, пошто се главно процесирање обавља на серверу. На овај начин је омогућено и централизовано администрирање садржаја речника, што омогућује да сви клијенти користе исте податке. 1808Побољшање перформанси система се може постићи надограђивањем основне структуре података приступном структуром која се заснива на додатним знањима о статистици грешака које се јављају у текстовима на српском језику. Ова структура је по природи trie стабло, са два до три нивоа, која ефективно може рашчланити речник на подскупове реда величине до сто речи. 18097. СПЕЦИФИЧНОСТИ И МОГУЋНОСТИ ПРИМЕНЕ ТЕХНИКА У ТЕКСТУ НА СРПСКОМ ЈЕЗИКУ 1810У претходним поглављима је размотрена спецификација система за детекцију и корекцију грешака, као и могућности имплементације оваквог система. Ово поглавље указује на специфичности српског језика и последице које те специфичности имају на решавање проблема детекције и корекције грешака. 1811Иако се текст на српском језику рачунарски обрађује већ дуже време, тешко да се може рећи да је на подручју аутоматске корекције текста на српском језику учињен велики помак. 1812Постоје програмски пакети који проверавају текст писан на српском језику, али их карактерише одсуство доброг система за генерисање кандидата за корекцију и мали речник, односно речник који не препознаје различите облике речи. Типичан пример оваквог система је додатак за проверу писања у пакету MS Office прилагођен српском језику [Microsoft 98]. Наиме, у случају да се реч из текста не налази у речнику, програм сигнализира грешку у писању. Уколико корисник одабере да непознату реч унесе у речник, при наиласку на исту реч али у другом облику (на пример други падеж за именице), програм ће поново сигнализирати грешку (Слика 21). Ово понашање је неприхватљиво, поготово због тога што је уграђени речник непотпун (Слика 22). Разлог оваквом понашању програма је интерна структура података која није прилагођена примени у случају српског језика. 1813Слика 21 - Унета реч постоји само у једном облику 1814Слика 22 - Речник је непотпун 18157.1. Преглед могућности примене техника за корекцију стрингова на српски језик 1816У поглављу број 3 је споменут одређен број метода за корекцију грешака у тексту. Овај одељак оцењује могућност примене ових техника у случају да их треба применити на српски језик. 1817Због начина рачунања растојања између стрингова, минимално едит растојање је практично независно од језика. Наиме, минимално едит растојање се динамички рачуна поредећи симболе који се налазе у стрингу. Уколико је програмски језик опремљен типовима података који омогућавају складиштење свих симбола неког језика, процедуре за рачунање ограниченог едит растојања није потребно мењати. Ове технике се такође одликују гарантованом временском и просторном комплексношћу. Могу се примењивати без икаквог претходног знања о конкретном језику на који се примењују, док се одређивањем статистичких особина језика могу подесити да дају финије резултате. 1818Технике на бази кључева сличности се у великој мери ослањају на статистичке податке о учесталости појављивања одређених симбола у тексту писаном на неком језику. Наиме, да би се остварила довољна дистинкција између кључева различитих речи и кључева сличних речи, потребно је одабрати одговарајући начин кодирања симбола у кључеве. Познато је да највећу количину информације носе управо симболи који се ређе јављају у тексту. Примена правила оваквог типа за корекцију текста захтева статистичко испитивање текстова писаних на српском језику. 1819Технике на бази правила захтевају опсежна испитивања грешака које се праве приликом уношења текста на српском језику. Овакво истраживање захтева велику количину текста у рачунарски читљивом облику и добар корпус или речник српског језика без грешака, такође у рачунарски читљивом облику. Да би се ове технике, које дају веома добре резултате у комбинацији са другим класама техника могле применити на српски језик, потребно је извршити радове на формирању рачунарског корпуса српског језика, како би се могла формирати одговарајућа правила. 1820Технике на бази n-грама такође захтевају резултате статистичких испитивања на великом корпусу. Ова испитивања се могу изводити заједно са испитивањима фреквенције појаве одређених симбола. Потребно је одредити фреквенције појаве одређених n-грама, као и фреквенције појаве n-грама на одређеном месту у речима да би се на задовољавајући начин могле конструисати технике на бази n-грама. 1821Пробабилистичке технике такође у великој мери зависе од статистичких особина језика. За конструкцију техника за упоређивање и корекцију потребно је направити добар статистички модел транзиције симбола у српском језику. Вероватноће конфузије се могу лакше одредити пошто се заснивају на графичкој сличности симбола одређеног језика. На жалост, оне имају примену која је углавном ограничена на грешке које се догађају приликом машинског читања текста (OCR). 1822Неуралне мреже су друга техника која се може користити за српски језик без већих измена за упоређивање стрингова на нивоу симбола. Оне се могу обучити да разазнају разлике између стрингова и за такву врсту обуке је потребан велики скуп улазних података. Ипак, без одговарајућег хардвера, неуралне мреже су по перформансама инфериорније у односу на технике на бази минималног едит растојања. 1823Може се рећи да се, у овом моменту, од свих наведених група техника, за одређивање мере сличности стрингова на српском језику најједноставније могу искористити технике на бази минималног едит растојања. За њима следе технике које користе неуралне мреже, које су по перформансама слабије и захтевају одређен период обучавања. Све остале технике захтевају формирање опсежног корпуса српског језика и то пречишћеног од грешака. Под претпоставком да је тај услов испуњен, релативно би се лако дошло до података потребних за имплементирање и коришћење техника на бази кључева сличности и n-грама. За пројектовање пробабилистичких и техника на бази правила је потребна дужа сарадња између лингвиста, математичара и стручњака за рачунарске науке на одређивању правила и статистичких особина текста писаног на српском језику. 18247.2. Морфолошке особине српског језика 1825Иако је српски језик изразито непогодан за рачунарску обраду, ипак је могуће уочити неке особине начина грађења речи у њему, које могу олакшати изградњу речника. 1826Речи српског језика се деле на десет врста. Променљиве врсте речи су: именице, придеви, глаголи, бројеви и заменице. Непроменљиве врсте речи су прилози, предлози, везници, речце и узвици. Променљиве речи обично имају посебне облике за лице, број и род. Речи српског језика се такође деле на самосталне и несамосталне речи. Несамосталне речи се не могу јавити без самосталних и њихове граматичке особине (лице, број и род) зависе од самосталних речи уз које се јављају. 1827Постоје ознаке за три лица: оно које говори, оно са којим се говори и лице које није присутно, односно оно коме се нешто приписује. Ова лица се означавају речима: ја, ти, он (она, оно) односно у множини ми, ви, они (оне, она), и називају се прво, друго и треће лице. Глаголи имају различите облике за различита лица. 1828Нека реч се може односити на једно или више лица или предмета (појмова). У зависности од тога, користи се различит облик речи. Ови облици који означавају број лица, предмета или појмова се називају граматички бројеви. Разликују се једнина (која означава једно лице, предмет или појам) и множина (која означава више лица, предмета или појмова). Раније је постојао и облик који означава два лица, такозвана двојина, али се она више не користи. 1829Самосталне речи, именице, имају свој род. У српском језику, оне могу бити мушког, женског или средњег рода. Именице различитог рода имају различите облике, али то није правило. Род именице може бити природан, код именица које означавају жива бића са препознатљивим полним каркетристикама код којих је род очигледан, мада ваља напоменути да се у природан род рачуна само мушки и женски, јер у природи не постоји средњи пол, па тако ни средњи род. Такође, постоје именице код којих се род разликује од пола (нпр. девојчурак, бабац, јуначина). Остале именице имају граматички род и код њих је род одређен по морфолошком облику. Граматички род се јавља код именица које означавају недорасла жива бића (младунчад) и именица које означавају шта неживо. Несамосталне речи преузимају свој род од самосталних речи. 1830Према правилу грађења речи српског језика, оне се добијају додавањем одговарајућих наставака на основу речи. Свака реч која спада у променљиве речи има свој начин мењања који зависи од њене врсте [Стевановић 81]. 1831Именице се деле у неколико група које се различито мењају по падежима, али по утврђеним правилима. Припадност групи или врсти промене се код именица одређује на основу рода именице и завршетка номинатива једнине. Постоје именице које се јављају само у облику једнине (градивне, збирне или колективне именице и сингуларија тантум) или само у множини (плуралија тантум). Ваља напоменути да постоје и непроменљиве (индеклинабилне) именице, које су углавном преузете из страних језика (нпр. леди). 1832Придеви преузимају свој род и број од именица уз које стоје. Разликују се два вида придева: одређени и неодређени. Они се различито мењају код мушког и средњег рода. Данас се у великој мери изгубила разлика у значењу између ордеђеног и неодређеног придевског вида. Неки придеви имају и различите облике за означавање интензитета особине које означавају. Основни облик се назива позитив, облик којим се исказује већи интензитет особине се назива компаратив, док се облик који исказује највећи могући интензитет особине у односу на појмове са којима се упоређује назива суперлатив. Други придеви имају само позитив (нпр. мртав). 1833Постоје именичке и придевске заменице. Именичке замењују именице, док придевских има више врста. Присвојене заменице означавају припадност. Показне заменице упућују на лице или предмет који се налази у близини (просторној или временској) лица које говори. Односно-упитне заменице се користе за питања и означавање односа. Неодређене заменице упућују на неодређена лица или предмете. Одричним заменицама се пориче неко постојање или активност. Опште заменице упућују на опште појмове. 1834Бројеви имају свој род и такође се мењају по падежима, с тим што облици за мушки и средњи род имају исту деклинацију (парадигму). 1835Глаголи се по промени разликују од осталих врста речи. По прелазности, деле се на прелазне, непрелазне и повратне глаголе. По трајању радње се деле на свршене и несвршене. Глаголи имају различите облике за различита лица и број. Основним облицима глагола се сматрају основа првог лица једнине презента и основа инфинитива. Прости глаголски облици се граде додавањем наставака на основе глагола. То су: инфинитив, презент, императив, глаголски придев садашњи, трпни придев, радни придев, аорист, имперфекат и глаголски прилог прошли. Врсте промена глагола се одређују по завршецима презентске и инфинитивне основе. Помоћни глаголи се мењају на посебан начин. Сложени глаголски облици се граде од простих глаголских облика комбинованих са одговарајућим облицима помоћних глагола. Од сложених облика, глаголи имају перфекат, плусквамперфекат, футур 1, футур 2 и потенцијал. 1836У непроменљиве врсте речи спадају, као што је већ речено, прилози, предлози, везници, речце и узвици. Оне углавном имају само један облик и као такве се и складиште, мада постоје прилози који се компарирају (брзо, брже, најбрже). 1837Иако постоје правила за промену променљивих речи, проблем настаје због тога што свако од ових правила има изузетно велик број изузетака (и до неколико десетина). Ова чињеница доводи до тога да би, и поред укључивања генеративних правила за грађење речи, било потребно на други начин забележити изузетке. Овај дуализам би знатно отежао имплементацију речника који садржи речи српског језика. Са друге стране, често није јасно одређено шта је заиста корен речи, то јест, постоје случајеви у којима се и корен речи мења. 1838Из претходне анализе уочава се потреба да се јасно одреди шта ће бити основни елемент складиштења у речнику и колико ће облика речи тај елемент садржати. Такође, потребно је донети одлуку о томе да ли ће бити коришћена морфолошка правила или ће се речи складиштити по неком другом принципу. 1839Такође, потребно је одредити шта ће репрезентовати одређену реч и њене облике. Морфолошки, то је основни облик речи. Питање је, међутим, да ли је тај основни облик речи најпогоднији за рачунарску обраду и решавање задатака провере текста и генерисања скупа сличних речи задатој речи. 1840Међутим, проблем настаје због тога што свако од ових правила има изузетно велик број изузетака, тако да је крајње непрактично покушавати систематизовање ових правила. Такође, није јасно одређено шта је корен речи, то јест, постоје случајеви у којима се и корен речи мења. 1841У својој дисертацији [Витас 93], која се бави математичким моделом морфологије српског језика и то искључиво именском флексијом, Витас закључује да је конструкција електронског речника сложен подухват јер захтева да се традиционална знања о језику уобличе на строг и формалан начин. У овом раду, аутор се бави представљањем речи механизмима коначних аутомата, што због великог броја изузетака у нашем језику доводи до веома комплексног модела. Свакако је да је ово истраживање веома значајно за изграђивање апарата за истраживање језика, међутим, овакав модел је исувише компликован да би се користио у применама које првенствено захтевају што бржи одзив. 1842Са друге стране, мора се напоменути да морфолошке особине језика представљају посебан проблем у рачунарској обради текста. Наиме, без узимања у обзир специфичности морфологије језика, обрада текста се своди на пуко манипулисање појединим симболима, без могућности за даљу обраду. Зато је од критичне важности развити модел морфолошких карактеристика језика. Као полазна тачка за моделирање морфолошких особина може се узети објектни приступ. У следећем одељку дат је пример дизајн спецификације за именице српског језика. 18437.3. Дизајн спецификација именица српског језика 1844Покушај моделирања морфологије ког природног језика је повезан са великим тешкоћама, због великог броја правила и изузетака који карактеришу морфологију већине језика. 1845Слика 23 даје предлог класа модела именице у српском језику. Именица (Imenica) има свој основни облик (OsnovniOblik), који може, у случају сложене именице имати припадајући суфикс (Prefix) и/или префикс (Sufix). Свака именица је одређена тачно једним граматичким родом (Rod). Такође, уз сваку именицу се могу везати одређене граматичке и друге особине (Osobine). Особине, између осталих информација, садрже податке о томе да ли именица означава нешто живо или неживо. Свака именица се мења на тачно један начин, користећи правила промене (Promena). Ови елементи модела су заједнички за све врсте језика. 1846Слика 23 - Дијаграм класа модела именице 1847Елементи карактеристични за српски језик су везани уз начин промене речи, односно за инстанцу класе Promena. Ова класа дефинише правила промене променљивих речи, правила за одређивање припадности именице једној од група, као и изузетке који се јављају за одређене речи. Како морфологија српског језика по промени дели именице на три врсте (деклинације), то се класа Promena специјализује на три врсте промена4. Ове класе дефинишу правила која се користе да би се одређена именица променила. Свака именица има четрнаест облика, који се називају падежима, по седам за једнину и за множину. Стога се класа за промену састоји од четрнаест падежа. Класа Padez има атрибут којим означава да ли се одређени наставак односи на једнину или множину. Она се даље специјализује у падеже српског језика (номинатив, генитив, датив, акузатив, вокатив, инструментал и локатив) који садрже наставке који се додају на корен речи. Уз сваки падеж је везано и правило на какву именицу се који наставак примењује. Горе споменути основни облик представља номинатив једнине за одређену именицу. Одређени облик именице се добија када се на основни облик примени неки падеж. Међутим, одређене именице имају додатне промене које зависе од симбола које садрже и на њима се обављају додатне интервенције које су дефинисане као гласовне промене (GlasovnePromene). Гласовне промене су такође везане за падеже и имају информације о томе на ком месту у речи се догађају и које услове именица мора да задовољава да би се одређена гласовна промена применила. 1848Класе из пакета падежа се састоје од услова који одређују за какву врсту речи важи одређено правило. Ови услови се односе на завршетак именице (одређени симбол, вокал, консонант и сл.), наставак у номинативу (без наставка или вокал), граматички род (мушки, женски, средњи), да ли се именица односи на шта живо или неживо, да ли је именица страног порекла и на сличне особине. Класе такође садрже наставке који важе за реч која задовољава наведене услове. 1849Класе гласовних промена су такође везане за услове које испуњава нека именица - углавном завршетак одређеним симболом. Правила промена дефинишу мењање одређеног симбола или групе симбола у други симбол или групу симбола. 1850Пример: скуп правила за именице прве врсте: 1851Imenice prve vrste 1852Gen SG = -a 1853Pravila pripadnosti: 18541. Nom Sg = (, osnovnioblik.kraj ( KONSONANTI, rod = muski 18552. Nom Sg = -o, osnovnioblik.kraj ( KONSONANTI, rod = muski 18563. Nom Sg ( {-o, -e}, strana = true 18574. Nom Sg = (, osnovnioblik.kraj ( {o,e,i,u} 18585. Nom Sg ( {-o, -e}, rod = srednji 1859Padezi: 1860SINGULAR 18611. Gen Sg - : -a 18622. Dat Sg - : -u 18633. Aku Sg 1864 a- zivo=true, rod=muski:-a (Gen Sg) 1865 b- zivo=false, rod=muski:( (Nom Sg) 1866 c- osnovnioblik.kraj(konsonant.nepalatalni, rod=srednji:-o (Nom Sg) 1867 d- osnovnioblik.kraj(konsonant.palatalni, rod=srednji:-e (Nom Sg) 18684. Vok Sg 1869 a- strana=true, ime=true, osnovnioblik.kraj(konsonant:( 1870 b- osnovnioblik.kraj=r, rod=muski:-e/-u 1871 c- osnovnioblik.kraj({j,č,ć,đ,lj,nj,š,ž}, rod=muski: -u 1872 d- rod=muski: -e 1873 e- osnovnioblik.kraj(konsonant.nepalatalni, rod=srednji:-o(Nom Sg) 1874 f- osnovnioblik.kraj(konsonant.palatalni, rod=srednji:-e(Nom Sg) 18755. Ins Sg 1876 a- osnovnioblik.brslogova<=2, {e}(osnovnioblik, 1877 osnovnioblik.kraj({j,ć,đ,lj,nj,č,ž,š}, rod=muski:-om 1878 b- osnovnioblik.kraj=r, zivo=false, rod=muski:-om 1879 c- osnovnioblik.kraj=r, zivo=true, rod=muski:-om 1880 d- osnovnioblik.kraj({č,ž,š}, rod=muski:-em 1881 e- osnovnioblik.kraj({j,ć,đ,lj,nj}, rod=muski:-em 1882 f- rod=muski: -om 1883 g- osnovnioblik.kraj(konsonant.nepalatalni, rod=srednji:-om(Nom Sg) 1884 h- osnovnioblik.kraj(konsonant.palatalni, rod=srednji:-em(Nom Sg) 18856. Lok Sg - : -u 1886PLURAL 1887Infix: 1888 a-nepostojano "a",osnovnioblik.brojslogova=2,rod=muski:-ov 1889 b-osnovnioblik.kraj({c,z,s},osnovnioblik.brojslogova=1,rod=muski:-ev 1890 c-osnovnioblik.kraj({j,č,dž,đ,lj,nj,š,ž}, 1891 osnovnioblik.brojslogova=1,rod=muski:-ev 1892 d-osnovnioblik.brojslogova=1,rod=muski:-ov 1893 e-:( 18947. Nom Pl 1895 a-rod=muski:Infix-i 1896 b-rod=srednji:-a 18978. Gen Pl -:Infix-a 18989. Dat Pl -:Infix-ima 189910. Aku Pl 1900 a-rod=muski:Infix-e 1901 b-rod=srednji:-a 190211. Vok Pl 1903 a-rod=muski:Infix-i 1904 b-rod=srednji:-a 190512. Ins Pl -:Infix-ima 190613. Lok Pl -:Infix-ima 1907Glasovne promene: 19081. Vok Sg -rod=muski,padez= -e,osnovnioblik.kraj({k,c} => č 19092. Vok Sg -rod=muski,padez= -e,osnovnioblik.kraj=g => ž 19103. Vok Sg -rod=muski,padez= -e,osnovnioblik.kraj=h => š 19114. Nom,Vok,Dat,Ins,Lok Pl -rod=muski, padez({-i,-ima}, osnovnioblik.kraj=k => c 19125. Nom,Vok,Dat,Ins,Lok Pl -rod=muski, padez({-i,-ima}, osnovnioblik.kraj=g => z 19136. Nom,Vok,Dat,Ins,Lok Pl -rod=muski, padez({-i,-ima}, osnovnioblik.kraj=h: => s 19147. Gen,Dat,Aku,Vok,Ins,Lok Sg, Nom,Dat,Aku,Vok,Ins,Lok Pl -rod=muski,osnovnioblik.kraj=lac: la => o 19158. Svi osim Nom Sg - osnovnioblik.kraj=ao, rod=muski: o => l 1916Из претходне анализе се може извести закључак да је неопходно установити механизам за записивање правила и промена који је довољно флексибилан да подржи референцирање на разне особине речи, као и лако додавање и мењање правила. Ова анализа се не може сматрати до краја потпуном, зато што се у граматикама често срећу неодређене квалификације типа "неке", "уобичајено" што отежава формирање потпуног скупа правила, као и неки специјални случајеви (човек => људи) са којима се треба посебно бавити. Даље, за задатке код којих није битна класификација именица, као што је исправљање текста, можда је повољније одлучити се за једноставнији начин складиштења речи, без коришћења граматичких правила. 1917Пример: промена неких именица по дефинисаним правилима. 1918а) osnovnioblik = ученик, Nom Sg = ( 1919 rod=muski, zivo=true, strana=false, pr_rod=muski, 1920ime=false 1921Gen Sg (P 1)= -а => ученика 1922Dat Sg (P 2)= -у => ученику 1923Aku Sg (P 3a)= -а => ученика 1924Vok Sg (P 4d)= -е, (GP 1) к>ч => учениче 1925Ins Sg (P 5f)= -ом => учеником 1926Lok Sg (P 6)= -у => ученику 1927Infix = ( 1928Nom Pl (P 7a)= -и, (GP 4) к>ц => ученици 1929Gen Pl (P 8)= -а => ученика 1930Dat Pl (P 9)= -има, (GP 4) к>ц => ученицима 1931Aku Pl (P 10a)= -е => ученике 1932Vok Pl (P 11a)= -и, (GP 4) к>ц => ученици 1933Ins Pl (P 12)= - има, (GP 4) к>ц => ученицима 1934Lok Pl (P 13)= - има, (GP 4) к>ц => ученицима 1935б) osnovnioblik = сел, Nom Sg = -о 1936 rod=srednji, zivo=false, strana=false, pr_rod=n/a, 1937ime=false 1938Gen Sg (P 1)= -а => села 1939Dat Sg (P 2)= -у => селу 1940Aku Sg (P 3c)= -а => села 1941Vok Sg (P 4е)= -o => село 1942Ins Sg (P 5g)= -ом => селом 1943Lok Sg (P 6)= -у => селу 1944Infix = ( 1945Nom Pl (P 7b)= -а => села 1946Gen Pl (P 8)= -а => села 1947Dat Pl (P 9)= -има => селима 1948Aku Pl (P 10b)= -а => села 1949Vok Pl (P 11b)= -а => села 1950Ins Pl (P 12)= - има => селима 1951Lok Pl (P 13)= - има => селима 19527.4. Организација речника речи српског језика 1953У поглављу број 4 је дат преглед структура података које могу послужити за складиштење речника. Овај одељак покушава да одреди структуру која би била погодна за складиштење речи српског језика. 1954Основни проблем који се јавља у овом случају је чињеница да постоји незанемарљив број речи које имају више облика, то јест променљивих врста речи. Као што је раније наведено, ове речи се граде додавањем наставака на корен речи, уз изузетак сложених облика, који се граде од више речи и самим тим не утичу на систем који посматра изоловане речи. 1955Логично решење је да структура података не складишти у потпуном облику све облике једне речи, већ да посебно складишти корен речи, посебно наставке. Међутим, пошто морфолошки корен речи не може увек да послужи за грађење свих облика речи (долази до промене у корену речи за неке облике), није добро чувати морфолошки корен речи, већ корен који се добија тако што се утврди заједнички почетни подстринг за све облике речи. Наставак за сваки облик се одређује као остатак речи којој је одузет корен. У овом поступку је могуће да дође до ситуације у којој више од једне речи има исти корен (ова ситуација је могућа и у граматици). 1956Ово решење за последицу има потребу да се организује нешто компликованија структура података од основних облика који су приказани у четвртом поглављу. 1957Потребно је направити разлику између променљивих и непроменљивих врста речи. Непроменљиве врсте речи се складиште у свом основном и једином облику и као таквима им се и приступа. Међутим, променљиве речи имају корен и скуп наставака. Дакле, у структури података свака променљива реч мора имати додатну структуру података која чува наставке речи. 1958Овај приступ намеће потребу да се и коришћење техника за детекцију и корекцију прилагоди оваквој структури. Наиме, при претраживању речника, прво се мора пронаћи корен речи, а потом проверити да ли таква реч са одговарајућим кореном садржи и тражени облик. 1959Процес проналажења кандидата се такође мора изводити у два нивоа. У првом пролазу се прави шири избор кандидата на основу корена речи. Потом се приступа анализи облика речи које су у ширем избору и добија се листа кандидата која ће бити понуђена кориснику - ужи избор. 1960Са друге стране, могуће је искористити комплекснији модел морфологије језика, што је омогућено објектним приступом дизајну. Тада се речи само организују по идентификатору, а претраживање се своди на издавање упита речима. Унутрашња структура речи се састоји од основног облика и од правила за генерисање облика речи, што омогућава претраживање у једном пролазу. 19618. ЗАКЉУЧАК 1962Овај рад се бави проблемима детекције и корекције грешака у тексту. Посебна пажња је обраћена на примену детекција у случају да је текст писан на српском језику. 1963Рад садржи класификацију и преглед извора грешака у тексту, као и анализу разних утицаја на појаву грешака у тексту. Такође, описују се и технике корекције грешака у тексту, као и начини организовања података у проблему корекције грешака у тексту. 1964У даљем тексту, излаже се дизајн спецификација система за проверу текста, коришћењем језика за моделирање система UML (Unified Modeling Language) кроз use-case дијаграм, дијаграм класа система и дијаграме секвенци за одабране процесе. 1965У раду се разматрају и релевантни детаљи имплементације којом се извршава провера претпоставки из спецификације, коришћењем програмског језика JAVA. Наведени су детаљи везани за структуру података речника, имплементацију процеса претраге речника, процеса генерисања сличних речи и провере текста. Такође, уочене су и истакнуте погодности JAVA окружења за коришћење у случају српског језика. 1966На крају, разматрају се морфолошке особине српског језика и њихов утицај на могућност примене предложених техника у детекцији и корекцији грешака. Илуструје се могућност објектног моделирања речи српског језика на примеру именица. Дата је UML спецификација модела именица, која је карактеристична по скупу правила којим се подржава генерисање различитих облика именица. 1967Главни научни допринос рада је спецификација система за детекцију и корекцију грешака на излованим речима у тексту. Спецификацијом су обухваћени сви битни елементи система и она је независна од језика на коме је текст писан. Такође, обухваћене су најбитније карактеристике српског језика предлогом методологије за моделирање морфолошких карактеристика речи српског језика. 1968Показало се да ни једна од понуђених техника, као ни једна од структура података не решавају у потпуности проблеме проналажења и исправљања грешака. Зато је потребно комбиновати неколико техника и неколико начина организације података за постизање задовољавајућих резултата. 1969Највећа потешкоћа која се јавља при оваквом приступу проблему проналажења и исправљања грешака у тексту је одсуство коришћења информације о контексту. Овај фактор ограничава проверу текста на полуаутоматски режим рада, уз интервенције корисника који мора да одабере одређеног кандидата за исправку грешке, пошто ни један алгоритам не може бити сигуран у то која је реч у питању, без консултовања информације о контексту. Овај проблем се не јавља због примене рачунара, зато што и људи имају исте проблеме у случају да им се одузме могућност сагледавања ширег контекста у коме се реч налази. 1970Такође, ваља напоменути да ни једна од техника које су поменуте у овој тези није у стању да региструје исправно написану, али погрешну реч. 1971Ови проблеми се могу, у извесној мери, ублажити коришћењем статистичких информација о фреквенцији појављивања речи у тексту. 1972Даље, већина разматраних техника се не може директно успешно применити на српски језик, због своје везаности за, углавном, статистистичке карактеристике језика за који се развија. Једина техника коју је могуће применити на било који језик без додатних модификација је техника ограниченог едит растојања, која је, нажалост, једна од рачунски најсложенијих техника. 1973Даља истраживања у овој области треба да теже интегрисању у речник информација о томе у ком контексту се поједине речи јављају, као и стварању базе статистичких података о српском језику. 1974КОРИШЋЕНА ЛИТЕРАТУРА: 1975[Angell 83] 1976Angell, R. C., Freund, G., E., and Willet, P., Automatic spelling correction using a trigram similarity measure, Inf. Process. Manage. 19, 255-261, 1983 1977[Arbib 87] 1978Arbib, A., M., Brains, Machines and Matematics, Second Edition, Springer-Verlag New York Inc, 1987 1979[Bickel 87] 1980Bickel, M. A., Automatic correction to misspelled names: a fourth-generation language approach, ACM Commun. 30, 3(Mar.), 224-228, 1987 1981[Bledsoe 59] 1982Bledsoe, W. W., and Browning, I., Pattern recognition and reading by machine, Proceedings of the Eastern Joint Computer Conference, vol. 16, 225-232, 1959 1983[Bocast 91] 1984Bocast, A. K., Method and apparatus for reconstructing a token from a Token Fragment, U.S. Patent 5, 008, 818, Design Services Group, Inc. McLean, Va., 1991 1985[Boivie 81] 1986Boivie, R. H., Directory assistance revisited, AT & T Bell Labs Tech. Mem. June 12, 1981, 1981 1987[Booch 97] 1988Booch, J., Rumbaugh, I., Jacobson, Unified Modeling Language, Version 1.0, Rational Software Corporation, January 1997, http://www.rational.com 1989[Burr 83] 1990Burr, D. J., Designing a handwriting reader, IEEE Trans. Patt. Anal. Machine Intell. PAMI-5, 5(Sept.), 554-559, 1983 1991[Burr 87] 1992Burr, D. J., Experiments with a connectionist text reader, IEEE International Conference on Neural Networks, San Diego, Calif., June. IEEE, New York, IV : 717-724, 1987 1993[Cherkassky 89a] 1994Cherkassky, V., and Vassilas, N., Backpropagation networks for spelling correction, Neural Net. 1, 3(July), 166-173, 1989a 1995[Cherkassky 89b] 1996Cherkassky, V., and Vassilas, N., Performance of back-propagation networks for associative database retrieval, Int. J. Comput. Neural Net., 1989b 1997[Cherkassky 92] 1998Cherkassky, V., Vassilas, N., Brodt, G., L., and Wechsler, H., Conventional and associative memory approaches to automatic spelling checking, Eng. Appl. Artif. Intell. 5, 3, 1992 1999[Church 91a] 2000Church, K. W., and Gale, W., A., Probability scoring for spelling correction, Stat. Comput. 1, 93-103, 1991a 2001[Church 91b] 2002Church, K. W., and Gale, W., A., Enhanced Good-Turing and cat-cal: Two new methods for estimating probabilities of English bigrams, Comput. Speech. Lang., 1991b 2003[Dahl 90] 2004Dahl, P., and Cherkassky, V., Combined encoding in associative spelling checkers, Univ of Minnespta EE Dept. Tech. Rep., 1990 2005[Damareu 64] 2006Damerau, F. J., A technique for computer detection and correction of spelling errors, ACM Commun. 7, 3(Mar.), 171-176, 1964 2007[Damerau 89] 2008Damerau, F. J., and Mays, E., An examination of undetected typing errors, Inf. Process. Manage. 25, 6, 659-664, 1989 2009[Davidson 62] 2010Davidson, L., Retrieval of misspelled names in an airline passenger record system, ACM Commun. 5, 169-171, 1962 2011[Deerwerster 90] 2012Deerwester, S., Dumais, S., T., Furnas, G., W., Landauer, T., K., and Harshman, R., Indexing by Latent Semantic Analysis, JASIS 41, 6, 391-407, 90 2013[Deffner 90a] 2014Deffner, R., Eder, K., and Geiger, H., Word recognition as a first step towards natural language processing with artificial neural nets, Proceedings of KONNAI-90, 1990a 2015[Deffner 90b] 2016Deffner, R., Geiger, H., Kahler, R., Krempl, T., and Brauer, W., Recognizing words with connectionist architectures, Proceedings of INNC-90-Paris, Paris, France, July, 196, 1990b 2017[DeHeer 82] 2018DeHeer, T., The application of the concept of homeosemy to natural language information, Inf. Process. Manage. 18, 229-236, 1982 2019[Dunlavey 81] 2020Dunlavey, M. R., On spelling correction and beyond, ACM Commun. 24, 9 (Sept.) 608, 1981 2021[Durham 83] 2022Durham, I., Lamb, D. A., and Saxe, J., B., Spelling correction in user interfaces, ACM Commun. 26, 10 (Oct.) 764-773, 1983 2023[Eckel 97] 2024Eckel, B., Thinking in JAVA, Prentice Hall PTR, 1998. 2025[Eriksson 98] 2026Eriksson, H., and Penker, M., UML Toolkit, Wiley computer publishing, John Wiley & sons, inc., 1998. 2027[Forney 73] 2028Forney, G. D., Jr, The Viterbi algorithm, IEEE Proc. 61, 3 (Mar.) 268-278, 1973 2029[Fredkin 60] 2030Fredkin, E., Trie memory, ACM Commun. 3, 9 (Sept.), 490-500, 1960 2031[Gentner 83] 2032Gentner, D., R., Grudin, J., Larochelle, S., Norman, D., A., and Rumelhart, D., E., Studies of typing from the LNR typing research group, Cognitive Aspects of Skilled Typewriting, W. E. Copper, Ed., Springer-Verlag, New York, 1983 2033[Gersho 90] 2034Gersho, M., and Reiter, R., Information retrieval using self-organizing and heteroassociative supervised neural networks, Proceedings of IJCNN, San Diego, Calif., June, 1990 2035[Goshtaby 88] 2036Goshtasby, A., and Enrich, R., W., Contextual word recognition using probabilistic relaxation labeling, Patt. Recog. 21, 5, 455-462, 1988 2037[Graham 92] 2038Graham, A. S., String Search, Technical Report TR-92-gas-01, School of Electronic Engineering Science, University College of North Wales, 1992 2039[Grudin 81] 2040Grudin, J., The organization of serial order in typing, The organization of serial order in typing. Ph.D. dissertation , Univ. of California, San Diego, 1981 2041[Grudin 83] 2042Grudin, J., Error patterns in skilled and novice transcription typing, Cognitive Aspects of Skilled Typewriting, W. E. Copper, Ed., Springer-Verlag, New York, 1983 2043[Hanson 76] 2044Hanson, A. R., Riseman, E., M., and Fisher, E., Context in word recognition, Patt. Recog. 8, 35-45, 1976 2045[Henseler 87] 2046Henseler, J., Scholtes, J., C., and Verdoest, C., R., J., The design of a parallel knowledge-based optical character recognition system, Master of Science Thesis. Dept of Mathematics and Informatics, Delft Univ. of Technology, 1987 2047[Hull 82] 2048Hull, J. J., and Srihari, S., N., Experiments in text recognition with binary n-gram and Viterbi algorithms, IEEE Trans. Patt. Anal. Machine Intell. PAMI-4, 5 (Sept.) 520-530, 1982 2049[Jones 91] 2050Jones, M. A., Story, G., A., and Ballard, B., W., Integrating multiple knowledge sources in a Bayesian OCR post-processor, Proceedings of IDCAR-91, St. Malo, France, 925-933, 1991 2051[Kahan 87] 2052Kahan, S., Pavlidis, T., and Baird, H., S., On the recognition of characters of any font size, IEEE Trans. Patt. Anal. Machine Intell. PAMI-9, 9, 274-287, 1987 2053[Kashyap 84] 2054Kashyap, R. L., and Oommen, B., J., Spelling correction using probabilistic methods, Patt. Recog. Lett. 2, 3(Mar.), 147-154, 1984 2055[Keeler 92] 2056Keeler, J., and Rumelhart, D., E., A self organizing integrated segmentation and recognition neural net, Advances in Neural Information Processing Systems, vol. 4, Morgan Kaufmann, San Mateo, Calif., 496-503, 1992 2057[Kernighan 90] 2058Kernighan, M. D., Church, K., W., and Gale, W., A., A spelling correction program based on a noisy channel model, Proceedings of COLING-90, The 13th International Conference on Computational Linguistics, vol 2., Helsinki, Finland, 205-210, 1990 2059[Kernighan 91] 2060Kernighan, M. D., Specialized spelling correction for a TDD system, AT & T Bell Labs Tech. Mem. August 30, 1991 2061[Knuth 73] 2062Knuth, D., The Art of Computer Programming, Volume 3, Sorting and Searching, Addison - Wesley, Reading, Mass., 1973 2063[Kohonen 80] 2064Kohonen, T., Content Addressable Memories, Springer-Verlag, New York, 1980 2065[Kohonen 88] 2066Kohonen, T., Self-Organization and Associative Memory, Springer-Verlag, New York, 1988 2067[Kucera 67] 2068Kucera, H., and Francis, W., N., Computational analysis of Present-Day American English, Brown Uiversity Press, Providence, R.I., 1967 2069[Kukich 88a] 2070Kukich, K., Variations on a back-propagation name recognition net, Proceedings of the Advanced Technology Converence, vol. 2, May 3-5, U.S. Postal Service, Washington, D.C., 722-735, 1988a 2071[Kukich 88b] 2072Kukich, K., Back-propagation topologies for sequence generation, Proceedings of the IEEE International Conference on Neural Networks, vol. 1, San Diego, Calif., July 24-27, IEEE, New York, 301-308, 1988b 2073[Kukich 90] 2074Kukich, K. , A comparison of some novel and traditional lexical distance metrics for spelling correction, Proceedings of INNC-90-Paris, Paris, France, July, 309-313, 1990 2075[Kukich 92a] 2076Kukich, K., Techniques for Automatically Correcting Words in Text, ACM Computing Surveys, Vol. 24, No. 4, December 1992a 2077[Kukich 92b] 2078Kukich, K., Spelling Correction for the Telecommunications Network for the Deaf, ACM Commun. 35, 5(May), 80-90, 1992b 2079[Landauer 73] 2080Landauer, T. K., and Streeter, L., A., Structural differences between common and rare words, J. Verbal Learn. Verbal Behav. 12, 119-131, 1973 2081[Levenshtein 66] 2082Levenshtein, V. I., Binary codes capable of correcting deletions, insertions and reversals, Sov. Phys. Dokl. 10, (Feb), 707-710, 1966 2083[Matan 92] 2084Matan, O., Burges, C., J., C., LeCun, Y., and Denker, J., S., Multi-digit recognition using a space displacement neural network, Advances in Neural Information Processing Systems, vol. 4, Morgan Kaufmann, San Mateo, Calif, 488-495, 1992 2085[Means 88] 2086Means, L. G., Cn yur cmputr raed ths, Proceedings of the 2nd Applied Natural Language Processing Conference, Austin, Tex, Feb., ACL, 93-100, 1988 2087[Mitton 87] 2088Mitton, R., Spelling checkers, spelling correctors and the misspellings of poor spellers, Inf. Process. Manage. 23, 5, 495-505, 1987 2089[Muth 77] 2090Muth, F. E., Jr, Correcting human error in alphanumeric terminal input, Inf. Process. Manage. 13, 329-337, 1977 2091[Nielsen 92] 2092Nielsen, J., Retrieving imperfectly recognized handwritten notes, Behav. Inf. Tech., 1992 2093[Odell 18] 2094Odell, M. K., US Patent 1, 261, 167 (1918) & 1, 435, 663 (1922), U.S. Patent Office, Washington D.C., 1918 2095[Okuda 76] 2096Okuda, T., A method of correction of garbled words based on the Levenshtein metric, IEEE Trans. Comput. 25, 172-177, 1976 2097[ORACLE 97a] 2098Oracle8 ConText Cartridge Administrator's Guide, Oracle8 Server Documentation, Oracle Corporation 1997 2099[ORACLE 97b] 2100Oracle8 ConText Cartridge Application Developer's Guide, Oracle8 Server Documentation, Oracle Corporation 1997 2101[Oshika 88] 2102Oshika, T., Proceedings of the 2nd Annual Applied Natural Language Conference, Austin, Tex., Feb., ACL, 203-210, 1988 2103[Peterson 80] 2104Peterson, J., Computer Programs for Spelling Correction: An Experiment in Program Design, Lecture Notes in Computer Science 2105[Peterson 86] 2106Peterson, J. L., A note on undetected typing errors, ACM Commun. 29, 7 (July) 633-637, 1986 2107[Pollock 83] 2108Pollock, J. J., Collection and characterization of spelling errors in scientific and scholarly text, J. Amer. Soc. Inf. Sci. 34, 1, 51-58, 1983 2109[Pollock 84] 2110Pollock, J. J., Automatic spelling correction in scientific and scholarly text, ACM Commun. 27, 4 (Apr.) 358-368, 1984 2111[Riseman 74] 2112Riseman, E. M., A contextual postprocessing system for error correction using binary n-grams, IEEE Trans. Comput. C-23, (May) 480-493, 1974 2113[Rosenfeld 76] 2114Rosenfeld, A., Scene labeling by relaxation operations, IEEE Trans. Syst. Man Cybernet. SMC-6, 6, 420-433, 1976 2115[Rumelhart 86] 2116Rumelhart, D. E. Hinton, An interactive activation model of context effects in letter perception, Parallel Distributed Processing: Explorations in the Microstructure of Cognition, Bradford Books, MIT Press, 1986 2117[Santos 92] 2118Santos, P. J., On handwriting recognition system performance: Some experimental results, Proceedings of the Human Factors Society 36th Annual Meeting, Atlanta, Ga., Oct 12-16, Human Factors Society, 1992 2119[Sheil 78] 2120Sheil, B. A., Median Split Trees: A Fast Lookup Technique for Frequently Occuring Keys, ACM Commun. 21, 11(Nov.) 947-958, 1978 2121[Shingal 79a] 2122Shingal, R., and Toussaint, G., T., Experiments in text recognition with the modified Viterbi algorithm, IEEE Trans. Patt. Anal. Machine Intell. PAMI-1, 4(Apr.), 184-193, 1979a 2123[Shingal 79b] 2124Shingal, R., and Toussaint, G., T., A bottom-up and top-down approach to using context in text recognition, Int. J. Man-Machine Stud. 11, 201-212, 1979b 2125[Sinha 88] 2126Sinha, R. M., K., and Prasada, B., Visual text recognition through contextual processing, Patt. Recog. 21, 5, 463-479, 1988 2127[Srihari 83] 2128Srihari, S., N., Hull, J., J., and Choudhari, R., Integrating diverse knowledge sources in text recognition, ACM Trans. Office Inf. Syst. 1, 1 (Jan.) 68-87, 1983 2129[Sun 97a] 2130JAVAServer Documentation, Sun Microsystems, http://java.sun.com 2131[Sun 97b] 2132The JAVA Language Specification, Sun Microsystems, http://java.sun.com 2133[Taylor 81] 2134Taylor, W. D., GROPE - A spelling error correction tool, AT & T Bell Labs Tech. Mem., 1981 2135[Tenczar 72] 2136Tenczar, P., and Golden, W., CERL Report X-35. Computer-Based Education Research Lab., Univ. of Illinois, Urbana, Ill., 1972 2137[Toussaint 78] 2138Toussaint, G. T., The use of context in pattern recognition, Patt. Recog. 10, 189-204, 1978 2139[Troy 90] 2140Troy, P. L., Combining probabilistic sources with lexical distance measures for spelling correction, Bellcore Tech. Memo., Bellcore, Morristown, N. J., 1990 2141[Tsao 90] 2142Tsao, Y. C., A lexical study of sentences typed by hearing-impaired TDD users, Proceedings of the 13th International Symposium on Human Factors in Telecommunications, Turin, Italy, Sept., 197-201, 1990 2143[Ullman 77] 2144Ullman, J. R., A binary n-gram technique for automatic correction of substitution, deletion, isertion and reversal errors in words, Comput. J. 20, 141-147, 1977 2145[UNIMARC 94] 2146UNIMARC Manual: bibliographic format / International Federation of Library Association and Institutions, IFLA Universal Bibliographic Control and International MARC Programme, New Providence, London, 1994. 2147[VanBerkel 88] 2148Van Berkel, B., and DeSmedt, K., Triphone analysis: A combined method for the correction of orthographical and typographical errors, Proceedings of the 2nd Applied Natural Language Processing Conference, Austin, Tex., Feb., Association for Computational Linguistics (ACL), 1988 2149[Veronis 88a] 2150Veronis, J., Computerized correction of phonographic errors, Comput. Hum. 22, 43-56, 1988a 2151[Veronis 88b] 2152Veronis, J., Morphosyntatic correction in natural language interfaces, Proceedings of the 12th International Conference on Computational Linguistics, Budapest, Hungary, 708-713, 1988b 2153[Wagner 74] 2154Wagner, R. A., and Fischer, M., J., The String-To-String Correction Problem, ACM J. 21, 1 (Jan.), 168-178, 1974b 2155[Walker 86] 2156Walker, D. E., and Amsler, R., A., The use of machine-readable dictionaries in sublanguage analysis, Analyzing Language in Restricted Domains: Sublanguage Description and Processing, Lawrence Erlbaum, Hillsdale, N. J., 69-83, 1986 2157[Wing 80] 2158Wing, A. M., and Baddeley, A., D., Spelling errors in handwriting: A corpus and distributional analysis, Cognitive Processes in Spelling, Academic Press, London, 1980 2159[Yannakoudakis 83] 2160Yannakoudakis, E. J., and Fawthrop, D., An intelligent spelling corrector, Inf. Process. Manage. 19, 12, 101-108, 1983a 2161[Yannakoudakis 83b] 2162Yannakoudakis, E. J., and Fawthrop, D., The rules of spelling errors, Inf. Process. Manage. 19, 2, 87-99, 1983b 2163[Zipf 35] 2164Zipf, G. K., The Psycho-Biology of Language, The Psycho-Biology of Language, Houghton Mifflin, Boston, 1935 2165[Витас 93] 2166Витас, Д., Математички модел морфологије српскохрватског језика (именска флексија), Докторска дисертација, Београд, 1993. 2167[Јовичић 97] 2168Јовичић, В., Коњовић, З., "Organization of dictionaries for string correction problem", The First Workshop on Soft and Intelligent Computing in Control Engineering, SICCE '97, Суботица 1997. 2169[Милосављевић 98] 2170Милосављевић, Б., Текст сервер Oracle окружења, Испитни рад, Факултет техничких наука, Институт за рачунарство, аутоматику и мерања, Катедра за рачунарске науке и информатику, Нови Сад, 1998 2171[Мразовић 90] 2172Мразовић, П., Вукадиновић, З., Граматика српскохрватског језика за странце, Издавачка књижарница Зорана Стојановића, Сремски Карловци, Добра вест, Нови Сад, 1990. 2173[Стевановић 81] 2174Стевановић, Д., Савремени српскохрватски језик I, Научна Књига, Београд, 1981. 2175БИОГРАФИЈА 2176Vladimir Weinstein је рођен у Новом Саду 03. маја 1970. године. На Факултет техничких наука Универзитета у Новом Саду одсек електротехника и рачунарство, смер рачунарство и управљање системима, усмерење рачунарство уписао се 1989/90. године. Положио све испите прописане наставним планом и програмом у периоду 1989-1994. године, са просечном оценом 8.74 (осам и 74/100). Дипломски рад је одбранио 28.09.1994. године са оценом 10 (десет). 2177Одмах по дипломирању започео је рад на Факултету техничких наука као стипендиста Министарства за науку и технологију. Радни однос је засновао 1995. године на Институту за рачунарство, аутоматику и мерења, Факултета техничких наука у Новом Саду. 2178На последипломске студије, смер рачунарски системи се уписао 1994/95. године на Факултету техничких наука у Новом Саду. До 1998. године положио све планом предвиђене испите. Има 4 интернационална и више домаћих научних радова. Од страних језика говори енглески језик и служи се руским језиком. 2179УНИВЕРЗИТЕТ У НОВОМ САДУ 2180ФАКУЛТЕТ ТЕХНИЧКИХ НАУКА 2181КЉУЧНА ДОКУМЕНТАЦИЈСКА ИНФОРМАЦИЈА 2182Редни број: 2183РБР 2184Идентификациони број: 2185ИБР 2186Тип документације: 2187ТД 2188Монографска документација 2189Тип записа: 2190ТЗ 2191Текстуални штампани текст 2192Врста рада: 2193БР 2194Магистарска теза 2195Аутор: 2196АУ 2197Vladimir Weinstein 2198Ментор: 2199МН 2200др Зора Коњовић, ванр. професор 2201Наслов рада: 2202НР 2203Објектно оријентисана спецификација и имплементaција система за детекцију и корекцију грeшака у тексту на српском језику 2204Језик публикације: 2205ЈП 2206српски (ћирилица) 2207Језик извода: 2208ЈИ 2209српски/енглески 2210Земља публиковања: 2211ЗП 2212СР Југославија 2213Уже географско подручје: 2214УГП 2215Војводина 2216Година: 2217ГО 22181999. 2219Издавач: 2220ИЗ 2221Ауторски репринт 2222Место и адреса: 2223МА 2224Нови Сад, Факултет техичких наука, Институт за рачунарство, аутоматику и мерења, 2225Трг Доситеја Обрадовића 6 2226Физички опис рада: 2227ФО 22288/134/23/2/97/0/0 2229Научна област: 2230НО 2231Рачунарске науке 2232Ужа научна област: 2233НД 2234Предметна одредница/кључне речи 2235ПО 2236УДК: 2237Чува се: 2238ЧУ 2239Библиотека факултета техничких наука, Трг Доситеја Обрадовића 6, Нови Сад 2240Важна напомена: 2241ВН 2242Нема 2243Извод: 2244ИЗ 2245Теза се бави проблемом проналажења и исправљања погрешно написаних речи у тексту. Дати су прегледи врста грешака које се јављају приликом уношења текста, техника за проналажење и исправку грешака у тексту, као и структура података које се могу употребити у решавању овог проблема. Размотрена су особине које карактеришу могућности примене ових техника у случају да је текст писан на српском језику. Дата је дизајн спецификација у UML језику дистрибуираног система за детекцију и корекцију грешака, као и имплементација таквог система у JAVA програмском језику, као и дизајн спецификација система за идексирање и претраживање докумената. 2246Датум прихватања теме од стране Наставно-научног већа: 2247ДП 2248Датум одбране: 2249ДО 2250Чланови комисије: 2251КО: 2252Председник: 2253др Данило Обрадовић, ред. проф. 2254члан: 2255др Душан Сурла, ред. проф. 2256члан: 2257др Љиљана Суботић, ванр. проф. 2258члан: 2259др Зора Коњовић, ванр. проф., ментор 2260UNIVERSITY OF NOVI SAD 2261FACULTY OF ENGINEERING 2262KEY WORD DOCUMENTATION 2263Accession number: 2264ANO 2265Identification number: 2266INO 2267Document type: 2268DT 2269Monograph documentation 2270Type of record: 2271TR 2272Textual printed documentation 2273Contents code: 2274CC 2275Master's thesis 2276Author: 2277AU 2278Vladimir Weinstein 2279Mentor: 2280MN 2281Ph. D Zora Konjović, associate prof. 2282Title: 2283TI 2284Object oriented specification and implementation of a system for detection and correction of errors in text written in serbian language 2285Language of text: 2286LT 2287Serbian (Cyrillic) 2288Language of abstract: 2289LA 2290English 2291Country of publication: 2292CP 2293Yugoslavia 2294Locality of publication: 2295LP 2296Vojvodina 2297Publication year: 2298PY 22991998. 2300Publisher: 2301PU 2302Author's reprint 2303Publ. place: 2304PP 2305Novi Sad, Faculty of Engineering, Computer, Control and Measurements institute, Trg Dositeja Obradovića 6 2306Physical description: 2307PD 23088/134/23/2/97/0/0 2309Scientific field: 2310SF 2311Computer science 2312Scientific discipline: 2313SD 2314Subject/Key words: 2315SKW 2316UC: 2317Holding data: 2318HD 2319Library of Faculty of Engineering, Trg Dositeja Obradovića 6 2320Note: 2321N 2322None 2323Abstract: 2324AB 2325Thesis deals with the problem of detection and correction of spelling errors. Reviews are given of spelling errors, techniques for detection and correction of spelling errors and data structures usable for solving of this problem. Also, thesis explores possible usage of these techniques in case of text written in serbian language. An UML language design specification of distributed system for spelling error detection and correction is given, together with one possible implementation of such a system, written in JAVA programming language, as well as a design specification of a system for indexing and searching a database of documents. 2326Accepted by Scientific Board on: 2327ASB 2328Defended: 2329DB 2330Thesis defend board: 2331President: 2332Ph. D Danilo Obradović, prof. 2333Member: 2334Ph. D Dušan Surla, prof. 2335Member: 2336Ph. D Ljiljana Subotić, associate prof. 2337Member: 2338Ph. D Zora Konjović, associate prof., mentor 23391 Матрица конфузије је квадратна матрица чије су врсте и колоне означене симболима са тастатуре и чији елемент на позицији ij садржи број пута када је симбол i погрешно био откуцан уместо симбола j. 23402 Графема је низ симбола који одговара фонеми. На пример, that укључује графеме th, a, i t. 23413 McCulloch - Pitts-ов неурон (или логичка јединица са прагом окидања) је елемент са m улаза x1, ...xm (m(1) и једним излазом у. Карактеризован је са m+1 бројева: прагом окидања ( и тежинским факторима w1, ...wm, где је wi асоциран са xi. За брзину реаговања се узима јединица времена и каже се да неурон ради на временској скали n=1, 2, 3, 4, .... Окидање неурона у моменту n+1 се одређује окидањем његових улаза у времену n по следећем правилу: неурон окида импулс по свом излазу у моменту n+1 ако и само збир његових улаза превазилази праг окидања. [McCulloch 43] 23424 Ова подела се разликује од аутора до аутора. На пример [Мразовић 90] деклинацију именица дели на три групе, док [Стевановић 81] даје четири различите деклинације. Ипак, ова разлика не утиче битно на модел. 2343ii 2344i 2345116 234699 2347109 2348