Back

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




                                     

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

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

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

                                     

1. Формална дефиниција и особине

За дате две ниске a {\displaystyle a} и b {\displaystyle b} на азбуци Σ {\displaystyle \Sigma } нпр. скуп ASCII карактера, растојање d a, b {\displaystyle da,b} уређивања ниски је најкраћи низ операција које трансформишу a {\displaystyle a} у b {\displaystyle b}. Један од најједноставнијих скупова операција уређивања је дефинисан од стране Левенштајна 1966. године:

Убацивање једног симбола. Ако је a = u v {\displaystyle a=uv}, онда убацивањем симбола x {\displaystyle x} добијамо низ u x v {\displaystyle uxv}. Ово се такође може представити као ε → x {\displaystyle \varepsilon \rightarrow x}, користећи ε {\displaystyle \varepsilon } као ознаку за празну ниску. Брисање једног симбола мења u x v {\displaystyle uxv} у u v {\displaystyle uv} x → ε {\displaystyle x\rightarrow \varepsilon }. Замена једног симбола x {\displaystyle x} за симбол y ≠ x {\displaystyle y\neq x} мења u x v {\displaystyle uxv} у u y v {\displaystyle uyv} x → y {\displaystyle x\rightarrow y}.

У Левенштајновој оригиналној дефиницији, свака од ових операција има јединичну ценуосим замене карактера са самим собом што нема цену, тако да Левенштајнова је удаљеност једнака минималном броју операција потребних да се a {\displaystyle a} трансформише у b {\displaystyle b}.

Додатне примитивне операције су предлагане. Честа грешка приликом куцања текста је транспозиција два суседна карактера, формално карактерисана као операција која мења u x y z {\displaystyle uxyz} у u y x z {\displaystyle uyxz} где x, y ∈ Σ {\displaystyle x,y\in \Sigma }. Као задатак корекције ОЦР излаза, операције повезивање и раздвајање се користе за замену једног карактера у два и обрнуто.

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

                                     

1.1. Формална дефиниција и особине Пример

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

  • kitt e n → {\displaystyle \rightarrow } sitt i n"e" замењено са "i"
  • kitten → {\displaystyle \rightarrow } sitten g додато "g"
  • k itten → {\displaystyle \rightarrow } s itten"k" замењено са "s"

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

  • sitt e n → {\displaystyle \rightarrow } sittn обрисано "e" са четврте позиције
  • sittin → {\displaystyle \rightarrow } sittin g додато на "g" шесту позицију
  • sittn → {\displaystyle \rightarrow } sitt i n додато на "i" четврту позицију
  • k itten → {\displaystyle \rightarrow } itten обрисано "k" са нулте позиције
  • itten → {\displaystyle \rightarrow } s itten додато "s" на нулту позицију
                                     

1.2. Формална дефиниција и особине Особине

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

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

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

d a, a = 0 {\displaystyle da,a=0}, пошто сваки стринг може тривијално да се трансформише у самог себе користећи тачно нула операција. d a, b > 0 {\displaystyle da,b> 0}, када a ≠ b {\displaystyle a\neq b}, пошто је неопходно извршити макар једну операцију чија цена није 0. d a, b = d b, a {\displaystyle da,b=db,a} по једнакости цена сваке од операција и њиховог инверза. Неједнакост троугла: d a, c ≤ d a, b + d b, c {\displaystyle da,c\leq da,b+db,c}.

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

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

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

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

  • Када a {\displaystyle a} и b {\displaystyle b} деле заједнички префикс, овај префикс не утиче на растојање. Формално, када a = u v {\displaystyle a=uv} и b = u w {\displaystyle b=uw}, онда d a, b = d v, w {\displaystyle da,b=dv,w}. Ово омогућава побољшање времена извршавања рачуна везаних за растојање уређивања јер се чести префикси и суфикси могу прескочити у линеарном времену.


                                     

2.1. Рачунање Општи алгоритам

Коришћењем Левенштајнових оригиналних операција, растојање уређивања између a = a 1 … a n {\displaystyle a=a1\ldots an} i b = b 1 … b m {\displaystyle b=b1\ldots bm} је дат као d m n {\displaystyle d_{mn}}, дефинисано рекурзивно:

d i 0 = ∑ k = 1 i w d e l b k, for 1 ≤ i ≤ m d 0 j = ∑ k = 1 j w i n s a k, for 1 ≤ j ≤ n d i j = { d i − 1, j − 1 for a j = b i min { d i − 1, j + w d e l b i d i, j − 1 + w i n s a j d i − 1, j − 1 + w s u b a j, b i for a j ≠ b i for 1 ≤ i ≤ m, 1 ≤ j ≤ n. {\displaystyle {\begin{aligned}d_{i0}&=\sum _{k=1}^{i}w_{\mathrm {del} }b_{k},&&\quad {\text{for}}\;1\leq i\leq m\\d_{0j}&=\sum _{k=1}^{j}w_{\mathrm {ins} }a_{k},&&\quad {\text{for}}\;1\leq j\leq n\\d_{ij}&={\begin{cases}d_{i-1,j-1}&{\text{for}}\;a_{j}=b_{i}\\\min {\begin{cases}d_{i-1,j}+w_{\mathrm {del} }b_{i}\\d_{i,j-1}+w_{\mathrm {ins} }a_{j}\\d_{i-1,j-1}+w_{\mathrm {sub} }a_{j},b_{i}\end{cases}}&{\text{for}}\;a_{j}\neq b_{i}\end{cases}}&&\quad {\text{for}}\;1\leq i\leq m,1\leq j\leq n.\end{aligned}}}

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

Једноставан, рекурзивни начин рачунања овог проблема је експоненцијалне временске сложености. Тако да се уобичајено рачуна помоћу алгоритма динамичког програмирања званог Вагнер-Фишер. Након завршетка Вагнер-Фишеровог алгоритма, минимални низ операција уређивања може да се прочита уназад пратећи операције коришћене током алгоритма, почевши од d m n {\displaystyle d_{mn}}.

Овај алгоритам је припада класи временске сложености Θ m n {\displaystyle \Theta mn}. Када се конструише потпуна табела, просторна сложеност је такође Θ m n {\displaystyle \Theta mn} ; ово може да се побољша на Θ m i n m, n) {\displaystyle \Theta minm,n)} услед чињенице да у било ком тренутку, алгоритму само требају 2 редаили две колоне у меморији. Имплементирањем ове оптимизације губи се могућност памћења самог низа операција уређивања. Решење линеарне просторне сложености је нуди Хиршбергов Алгоритам.

                                     

2.2. Рачунање Побољшани алгоритми

Уконен је описао неколико варијанти побољшања горенаведеног Вагнер-Фишер алгоритма, једна од којих узима две ниске и максимално растојање уређивања s {\displaystyle s}, и враћа m i n s, d {\displaystyle mins,d}. То успева рачунајући и складиштећи само део табеле у околини дијагонале. Овај алгоритам захтева Θ s ∗ m i n m, n) {\displaystyle \Theta s*minm,n)} време, где су m {\displaystyle m} и n {\displaystyle n} дужине ниски. Просторна сложеност је Θ s 2 {\displaystyle \Theta s^{2}} или Θ s {\displaystyle \Theta s}, у зависности од тога да ли низ операција треба да се прочита или не.

                                     

3. Примена

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

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

  • Левенштајнов аутомат је коначни аутомат који препознаје сет ниски унутар ограниченог растојања уређивања фиксне референтне ниске.
  • Хиршбергов алгоритам рачуна оптимално поравнање две ниске, где је оптималност дефинисана минимизовањем растојања уређивања.
  • Тражење приближне ниске може да се формулише у терминима растојања уређивања. Уконенов алгоритам из 1985. узима ниску p {\displaystyle p}, названу узорак, и константу k {\displaystyle k}. Онда прави детерминистички коначни аутомат који проналази, у произвољној ниски s {\displaystyle s}, подниску чије је растојање уређивања до p {\displaystyle p} највише k {\displaystyle k}. Сличан алгоритам за тражење приближне ниске је битап алгоритам, такође дефинисан у терминима растојања уређивања.

Users also searched:

...