Article on other languages:
- Levenshteinafstand
- Levenshtein-Distanz
- Levenshtein_distance
- Distancia_de_Levenshtein
- Levenšteinin_etäisyys
- Distance_de_Levenshtein
- Distanza_di_Levenshtein
- レーベンシュタイン距離
- Levenšteina_attālums
- Levenshteinafstand
- Levenshtein-distanse
- Odległość_Levenshteina
- Distância_Levenshtein
- Расстояние_Левенштейна
- Масофаи_Левенштейн
- Відстань_Левенштейна
- Khoảng_cách_Levenshtein
- 編輯距離
 |
del.icio.us |
 |
Digg |
 |
Furl |
 |
|
 |
Rojo |
| Add to OnlyWire |
У рачунарству, Левенштајново растојање је метрика за ниске, која је један од начина да се одреди растојање уређивања (енгл. edit distance) две ниске. Левенштајново растојање две ниске је одређено минималним бројем операција неопходним да се једна ниска трансформише у другу, а операције су уметање, брисање или замена једног карактера другим. Добило је име по Владимиру Левенштајну, који га је развио 1965.[1] Левенштајново растојање је корисно у одређивању сличности две ниске, на пример у софтверу за проналажење грешака у куцању.
На пример, Левенштајново растојање речи "kitten" и "sitting" је 3, јер су потребне најмање три едит операције да се једна реч трансформише у другу:
- kitten → sitten (замена 's' са 'k')
- sitten → sittin (замена 'i' са 'e')
- 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]
Дата су два примера матрица које се добијају (оптимални кораци су подвучени):
|
|
Инваријанта која се одржава кроз цео алгоритам је да умемо да трансформишемо почетни део 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је доња граница.
Види још
- Дамерау-Левенштајново растојање
- Џаро-Винклер растојање
- Проблем најдужег заједничког подниза
- Метрички простор
- Нидлман-Вуншов алгоритам
- Смит-Вотерманов алгоритам
Напомене
- ^ В.И. Левенштейн (1965) Двоичные коды с исправлением выпадений, вставок и замещений символов. Доклады Академий Наук СССР 163.4:845–848.
