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. |
Struktura danych | Tablice znaków |
---|---|
Złożoność | |
Czasowa |
|
Pamięciowa | lub |
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
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 – 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
- Implementacja w PostgreSQL (ang.)
- Implementacja w MySQL (ang.)