Левенштајново растојање

У рачунарству, Левенштајново растојање је метрика за ниске, која је један од начина да се одреди растојање уређивања (енгл. edit distance) две ниске. Левенштајново растојање две ниске је одређено минималним бројем операција неопходним да се једна ниска трансформише у другу, а операције су уметање, брисање или замена једног карактера другим. Добило је име по Владимиру Левенштајну, који га је развио 1965. Левенштајново растојање је корисно у одређивању сличности две ниске, на пример у софтверу за проналажење грешака у куцању.

На пример, Левенштајново растојање речи "kitten" и "sitting" је 3, јер су потребне најмање три едит операције да се једна реч трансформише у другу:

1. kitten → sitten (замена 's' са 'k')
2. sitten → sittin (замена 'i' са 'e')
3. sittin → sitting (уметање 'g' на крај)

Ово растојање се може посматрати као уопштење Хаминговог растојања, које се користи да ниске исте дужине, и које подразумева искључиво замене карактера. Постоје и даље генерализације Левенштајновог растојања, на пример Дамерау-Левенштајново растојање које дозвољава операцију промене места карактеру (које се код Левенштајновог растојања посматра као две операције - брисање и потом уметање).

Алгоритам

Обично се за рачунање Левенштајновог растојања користи алгоритам динамичког програмирања, који подразумева употребу (n + 1) × (m + 1) матрице, где су n и m дужине ниски. Овај алгоритам се базира на Вангер-Фишеровом алгоритму за едит растојање. Следи псеудокод функције LevenstajnovoRastojanje која узима две ниске, s дужине m, и t дужине n, и рачуна Левенштајново растојање између њих:

int LevenstajnovoRastojanje(char s[1..m], char t[1..n])
   // d је табела са m+1 врста и n+1 колона
   declare int d[0..m, 0..n]
 
   for i from 0 to m
       d[i, 0] := i
   for j from 1 to n
       d[0, j] := j
 
   for i from 1 to m
       for j from 1 to n
           if s[i] = t[j] then cost := 0
                          else cost := 1
           d[i, j] := minimum(
                                d[i-1, j] + 1,     // брисање
                                d[i, j-1] + 1,     // уметање
                                d[i-1, j-1] + cost   // замена
                            )
 
   return d[m, n]

Дата су два примера матрица које се добијају (оптимални кораци су подвучени):

k i t t e n 0 1 2 3 4 5 6 s 1 1 2 3 4 5 6 i 2 2 1 2 3 4 5 t 3 3 2 1 2 3 4 t 4 4 3 2 1 2 3 i 5 5 4 3 2 2 3 n 6 6 5 4 3 3 2 g 7 7 6 5 4 4 3

S a t u r d a y 0 1 2 3 4 5 6 7 8 S 1 0 1 2 3 4 5 6 7 u 2 1 1 2 2 3 4 5 6 n 3 2 2 2 3 3 4 5 6 d 4 3 3 3 3 4 3 4 5 a 5 4 3 4 4 4 4 3 4 y 6 5 4 4 5 5 5 4 3

Инваријанта која се одржава кроз цео алгоритам је да умемо да трансформишемо почетни део s[1..i] у t[1..j] коришћењем најмање d[i,j] операција. На крају, доњи десни елемент низа даје коначан одговор.

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

Доказ коректности

Као што је претходно поменуто, инваријанта је да умемо да трансформишемо почетни сегмент s[1..i] у t[1..j] коришћењем минимума операција, d[i,j]. Ова инваријанта важи јер:

• У почетку је ово тачно за врсту и колону 0 јер се s[1..i] може трансформисати у празну ниску t[1..0] простим брисањем свих i карактера. Слично, можемо да трансформишемо s[1..0] у t[1..j] простим додавањем свих j карактера.
• Минимум се добија од три раздаљине, од које је свака изводљива:
  • Ако умемо да трансформишемо s[1..i] у t[1..j-1] са k операција, онда просто можемо да додамо t[j] након тога, и да добијемо t[1..j] са k+1 операција.
  • Ако умемо да трансформишемо s[1..i-1] у t[1..j] са k операција, онда можемо да спроведемо исте операције на s[1..i] а затим да уклонимо s[i] са краја, и да добијемо укупан број од k+1 операција.
  • Ако умемо да трансформишемо s[1..i-1] у t[1..j-1] са k операција, умемо да урадимо исто и са s[1..i] а затим да заменимо t[j] са s[i] на крају, уколико је неопходно, што захтева укупно k+cost операција.
• Број операција неопходних да се трансформише s[1..n] у t[1..m] је број операција потребних да се свако s трансформише у свако t, па тако d[n,m] важи за наш резултат.

Овај доказ не доказује да је број који се налази у матрици, d[i,j] заиста минималан; ово је теже показати, и неопходно је користити свођење на контрадикцију.

Могућа унапређења и варијације

Међу могућим унапређењима алгоритма су:

• Можемо да направимо варијацију алгоритма да захтева мање простора, O(m) уместо O(mn), јер је неопходно да памтимо само претходну и тренутну врсту матрице у сваком тренутку.
• Можемо да ускладиштимо број уметања, брисања и замена одвојено, или чак на позицијама на којима се јављају, што је увек j.
• Можемо да дајемо различите цене операцијама уметања, брисања и замене.
• Иницијализација d[i,0] се може преместити у главну спољашњу петљу.
• Овај алгоритам се лоше паралелизује, услед велике количине зависних података. Међутим, све cost вредности се могу израчунати паралелно.

Горње и доње границе

Левенштајново растојање има неколико једноставних горњих и доњих граница које су корисне у применама које рачунају много њих, и пореде их. Међу њима су:

• Растојање никад није мање од разлике у дужинама две ниске.
• Растојање није дуже од дужине дуже од ниски.
• Растојање је једнако нули ако и само ако су ниске идентичне.
• Ако су ниске једнаких дужина, Хамингово растојање је горња граница Левенштајновог растојања.
• Ако две ниске означимо са s и t, број карактера (искључујући дупликате) који се појављују у s али не и у t је доња граница.

Види још

• Дамерау-Левенштајново растојање
• Џаро-Винклер растојање
• Хамингово растојање
• Проблем најдужег заједничког подниза
• Метрички простор
• Нидлман-Вуншов алгоритам
• Смит-Вотерманов алгоритам

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

• Java, C++ и VB имплементације алгоритма
• NIST речник алгоритама и база података: Левенштајново растојање
• Визуализација Левенштајновог растојања