Odległość Levenshteina

Ten artykuł od 2023-08 wymaga zweryfikowania podanych informacji. Należy podać wiarygodne źródła w formie przypisów bibliograficznych. Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte. Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary) Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

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

Definicja[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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 – odległość Damerau-Levenshteina.
• 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.

Linki zewnętrzne[edytuj | edytuj kod]

• Implementacja w PostgreSQL (ang.)
• Implementacja w MySQL (ang.)