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

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

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

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

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

Убацивање једног симбола. Ако је $a=uv$, онда убацивањем симбола $x$ добијамо низ $uxv$. Ово се такође може представити као $\varepsilon \rightarrow x$ , користећи $\varepsilon$ као ознаку за празну ниску.

Брисање једног симбола мења $uxv$ у $uv$ ($x\rightarrow \varepsilon$).

Замена једног симбола $x$ за симбол $y\neq x$ мења $uxv$ у $uyv$ ($x\rightarrow y$).

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

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

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

Пример

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

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

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

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

Особине

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

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

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

$d(a,a)=0$, пошто сваки стринг може тривијално да се трансформише у самог себе користећи тачно нула операција.

$d(a,b)>0$, када $a\neq b$, пошто је неопходно извршити макар једну операцију чија цена није 0.

$d(a,b)=d(b,a)$ по једнакости цена сваке од операција и њиховог инверза.

Неједнакост троугла: $d(a,c)\leq d(a,b)+d(b,c)$.

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

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

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

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

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

Рачунање

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

Општи алгоритам

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

${\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_{mn}$.

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

Побољшани алгоритми

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

Примена

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

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

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

Спољашње везе

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