Odległość Levenshteina

Odległość Levenshteina (edycyjna) – miara odmienności napisów (skończonych ciągów znaków), zaproponowana w 1965 roku przez Vladimira Levenshteina.

Definicja

Formalnie jest to metryka w przestrzeni ciągów znaków, zdefiniowana następująco:

• działaniem prostym na napisie nazwiemy:
  • wstawienie nowego znaku do napisu
  • usunięcie znaku z napisu
  • zamianę znaku w napisie na inny znak
• odległością pomiędzy dwoma napisami jest najmniejsza liczba działań prostych, przeprowadzających jeden napis na drugi.

Miara ta znajduje zastosowanie w przetwarzaniu informacji, danych w postaci ciągów symboli: w maszynowym rozpoznawaniu mowy, analizie DNA, rozpoznawaniu plagiatów, korekcie pisowni (np. wyszukiwanie w spisie telefonicznym błędnie podanego nazwiska), itp.

Przykłady

Odległość Levenshteina pomiędzy napisami identycznymi, np.

pies
pies

jest zerowa – skoro są identyczne, to potrzeba zero działań, by jeden z nich przeprowadzić na drugi.

Odległość Levenshteina pomiędzy napisami:

granat
granit

wynosi 1, ponieważ do przeprowadzenia pierwszego na drugi wystarcza jedno działanie: zamiana litery a na i.

Odległość pomiędzy napisami:

orczyk
oracz

równa jest 3, ponieważ do przeprowadzenia pierwszego napisu na drugi potrzeba trzech działań: usunięcia liter y i k oraz wstawienia litery a.

Odległość pomiędzy napisami:

marka
ariada

wynosi 4, ponieważ potrzeba co najmniej czterech działań, np.: usunięcia litery m, zamiany k na i oraz dodania d i a.

Obliczanie odległości Levenshteina

Odległość Levenshteina można obliczyć używając programowania dynamicznego. Przykładowy algorytm w pseudokodzie:

int LevenshteinDistance(char s[1..m], char t[1..n])
   
   declare int d[0..m, 0..n] // niech d będzie tablicą o m+1 wierszach i n+1 kolumnach  
   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,       // usuwanie
                              d[i, j-1] + 1,       // wstawianie
                              d[i-1, j-1] + cost)  // zamiana
 
   return d[m, n]

Uogólnienia i przypadki szczególne

Odległość Levenshteina jest uogólnieniem odległości Hamminga; sama też ma swoje uogólnienia, oparte na rozszerzaniu zestawu działań uważanych za proste.

Podstawowym rozszerzeniem jest uznanie za działanie proste zamiany miejscami dwu sąsiednich znaków. Innym spotykanym jest dopuszczenie wstawiania, usuwania i zastępowania spójnych ciągów znaków (bloków, nieprzerwanych fragmentów napisu). Jest to szczególnie pożyteczne przy przetwarzaniu ciągów danych o wyróżnionych mniejszych fragmentach, jak wyrazy w zdaniu.

Tak zdefiniowane miary nazywa się odległością transformacyjną, jednak czasem są również nazywane odległościami edycyjnymi. Z tego powodu użycie określenia odległość edycyjna należy zawsze uściślić, podając na jakim zestawie działań opiera się używana miara.