Растојање уређивања

Из Википедије, слободне енциклопедије
Ed NL icon.png
Овај чланак је део пројекта семинарских радова на Математичком факултету у Београду.
Датум уноса: март—мај 2016.
Википедијанци: Ова група студената ће уређивати у ГИП-у и молимо вас да не пребацујете овај чланак у друге именске просторе Википедије.
Позивамо вас да помогнете студентима при уређивању и допринесете да њихови уноси буду што квалитетнији.

У теорији информација и рачунарству, растојање уређивања између две ниске је број операција потребних да се једна од њих трансформише у другу. Растојање уређивања налази примену у обради природних језика где се аутоматско исправљање правописних грешака врши избором једног од кандидата за исправку погрешно написане речи избором речи из речника које имају мало растојање уређивања у односу на задату реч. У биоинформатици, може да се користи за одређивање сличности ДНК секвенци, који могу да се гледају као ниска карактера А, Ц, Г и Т.

Различите дефиниције растојања уређивања користе различите скупове операција над нискама. Операције Левенштајновог растојања су брисање, убацивање, или замена карактера у ниски. Пошто је то најчешћа метрика, Левенштајновно растојање је уобичајено оно на шта се мисли под "Растојањем уређивања". [1]

Формална дефиниција и особине[уреди]

За дате две ниске и на азбуци (нпр. скуп ASCII карактера), растојање уређивања ниски је најкраћи низ операција које трансформишу у . Један од најједноставнијих скупова операција уређивања је дефинисан од стране Левенштајна 1966. године:[2]

Убацивање једног симбола. Ако је , онда убацивањем симбола добијамо низ . Ово се такође може представити као , користећи као ознаку за празну ниску.
Брисање једног симбола мења у ().
Замена једног симбола за симбол мења у ().

У Левенштајновој оригиналној дефиницији, свака од ових операција има јединичну цену(осим замене карактера са самим собом што нема цену), тако да Левенштајнова је удаљеност једнака минималном броју операција потребних да се трансформише у . [2]


Додатне примитивне операције су предлагане. Честа грешка приликом куцања текста је транспозиција два суседна карактера, формално карактерисана као операција која мења у где . [3][4]. Као задатак корекције ОЦР излаза, операције повезивање и раздвајање се користе за замену једног карактера у два и обрнуто.[4]

Друге варијанте растојања уређивања добијају се ограничавањем сета операција. Удаљеност најдуже заједничке подниске је удаљеност уређивања са убацивањем и брисањем као једине две операције, обе са јединичном ценом. Слично, допуштањем само замене(опет по јединичној цени), добија се Хамингово Растојање, које мора бити ограничено на ниске са истим бројем карактера. Џаро-Винклер растојање се добија као растојање уређивања у коме је само транспозиција дозвољена.

Пример[уреди]

Левенштајново растојање између речи "kitten" и "sitting" је 3.

  1. kitten sitten("k" замењено са "s")
  2. kitten sittin("e" замењено са "i")
  3. kitten sitteng(додато "g")

Најдужа заједничка подниска (дозвољена само убацивања и брисања) даје растојање од 5.

  1. kitten itten (обрисано "k" са нулте позиције)
  2. itten sitten (додато "s" на нулту позицију)
  3. sitten sittn (обрисано "e" са четврте позиције)
  4. sittn sittin (додато на "i" четврту позицију)
  5. sittin sitting (додато на "g" шесту позицију)

Особине[уреди]

Растојање уређивања са не-негативним ценама задовољава аксиоме метрике, правећи метрички простор ниски када су наредни услови задовољени:

  • Свака операција уређивања има позитивну цену;
  • за сваку операцију, постоји инверзна операција са истом ценом.

Са овим особинама метричке аксиоме су задовољене:

, пошто сваки стринг може тривијално да се трансформише у самог себе користећи тачно нула операција.
, када , пошто је неопходно извршити макар једну операцију чија цена није 0.
по једнакости цена сваке од операција и њиховог инверза.
Неједнакост троугла: .[5]

Левенштајново растојање и Најдужа заједничка подниска са јединичним ценама операција задовољавају горе наведене услове.

Друге корисне особине растојања удаљености јединичних цена су:

  • Најдужа заједничка подниска је горње ограничена сумом дужина пара ниски.[1]
  • Најдужа заједничка подниска је горње ограничење Левенштајновог растојања.
  • За ниске исте дужине, Хамингово растојање је горња граница Левенштајновог растојања.[1]

Без обзира на цену, наредна особина важи за сва растојања уређивања:

  • Када и деле заједнички префикс, овај префикс не утиче на растојање. Формално, када и , онда .[4] Ово омогућава побољшање времена извршавања рачуна везаних за растојање уређивања јер се чести префикси и суфикси могу прескочити у линеарном времену.

Рачунање[уреди]

Први алгоритам за рачунање минималног растојања уређивања две ниске је објавио Дамарау 1964. године.[6]

Општи алгоритам[уреди]

Коришћењем Левенштајнових оригиналних операција, растојање уређивања између i је дат као , дефинисано рекурзивно:[2]

Овај алгоритам може да се уопшти како би подржавао транспозиције додавањем додатног члана у рекурзивној клаузи за минимизацију.[3]

Једноставан, рекурзивни начин рачунања овог проблема је експоненцијалне временске сложености. Тако да се уобичајено рачуна помоћу алгоритма динамичког програмирања званог Вагнер-Фишер.[7] Након завршетка Вагнер-Фишеровог алгоритма, минимални низ операција уређивања може да се прочита уназад пратећи операције коришћене током алгоритма, почевши од .

Овај алгоритам је припада класи временске сложености . Када се конструише потпуна табела, просторна сложеност је такође ; ово може да се побољша на услед чињенице да у било ком тренутку, алгоритму само требају 2 реда(или две колоне) у меморији. Имплементирањем ове оптимизације губи се могућност памћења самог низа операција уређивања. Решење линеарне просторне сложености је нуди Хиршбергов Алгоритам.

Побољшани алгоритми[уреди]

Уконен је описао неколико варијанти побољшања горе наведеног Вагнер-Фишер алгоритма, једна од којих узима две ниске и максимално растојање уређивања , и враћа .[8] То успева рачунајући и складиштећи само део табеле у околини дијагонале. Овај алгоритам захтева време, где су и дужине ниски. Просторна сложеност је или , у зависности од тога да ли низ операција треба да се прочита или не.

Примена[уреди]

Растојање уређивања налази примену у рачунској биологији и обради природних језика, нпр. исправљању правописних или ОЦР грешака и тражењем приближног поклапања ниски, где је циљ наћи поклапања за кратке ниске у много дужим текстовима, у ситуацијама када се мали број разлика очекује.

Разни алгоритми постоје за решавање сличних типова проблема.

  • Хиршбергов алгоритам рачуна оптимално поравнање две ниске, где је оптималност дефинисана минимизовањем растојања уређивања.
  • Тражење приближне ниске може да се формулише у терминима растојања уређивања. Уконенов алгоритам из 1985. узима ниску , названу узорак, и константу . Онда прави детерминистички коначни аутомат који проналази, у произвољној ниски , подниску чије је растојање уређивања до највише .[9] Сличан алгоритам за тражење приближне ниске је битап алгоритам, такође дефинисан у терминима растојања уређивања.
  • Левенштајнов аутомат је коначни аутомат који препознаје сет ниски унутар ограниченог растојања уређивања фиксне референтне ниске. [4]

References[уреди]

  1. 1,0 1,1 1,2 Navarro, Gonzalo (1. 03. 2001). „A guided tour to approximate string matching” (PDF). ACM Computing Surveys. 33 (1): 31—88. doi:10.1145/375360.375365. Приступљено 19. 03. 2015. 
  2. 2,0 2,1 2,2 Daniel Jurafsky; James H. Martin. Speech and Language Processing. Pearson Education International. стр. 107—111. 
  3. 3,0 3,1 Esko Ukkonen (1983). On approximate string matching. Foundations of Computation Theory. Springer. стр. 487—495. 
  4. 4,0 4,1 4,2 4,3 Schulz, Klaus U.; Mihov, Stoyan (2002). „Fast string correction with Levenshtein automata”. International Journal of Document Analysis and Recognition. 5 (1): 67—85. doi:10.1007/s10032-002-0082-8. CiteSeerX: 10.1.1.16.652. 
  5. Lei Chen; Raymond Ng (2004). On the marriage of Lₚ-norms and edit distance. Proc. 30th Int'l Conf. on Very Large Databases (VLDB). 
  6. Kukich, Karen (1992). „Techniques for Automatically Correcting Words in Text” (PDF). ACM Computing Surveys. 24 (4): 377—439. doi:10.1145/146370.146380. 
  7. R. Wagner; M. Fischer (1974). „The string-to-string correction problem”. J. ACM. 21: 168—178. doi:10.1145/321796.321811. 
  8. „Algorithms for approximate string matching” (PDF). Information and Control. 64 (1–3): 100—118. 1985. doi:10.1016/S0019-9958(85)80046-2. 
  9. Esko Ukkonen (1985). „Finding approximate patterns in strings”. J. Algorithms. 6: 132—137. doi:10.1016/0196-6774(85)90023-9. 

Спољашње везе[уреди]

  • Text::WagnerFischer, Perl имплементација Вагнер-Фишер растојања уређивања