Odległość Levenshteina
Z Wikipedii
Odległość Levenshteina (edycyjna) – miara odmienności napisów (skończonych ciągów znaków), zaproponowana w 1965 roku przez Vladimira Levenshteina.
Spis treści |
[edytuj] 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.
[edytuj] 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.
[edytuj] 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]
[edytuj] 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.
