Odległość Levenshteina
Odległość Levenshteina, wprowadzona przez Władimira Lewensztejna w 1965 roku, jest miarą różnicy między dwoma napisami. Definiuje się ją jako najmniejszą liczbę operacji, które trzeba wykonać, aby przekształcić jeden napis w drugi. Do operacji tych zalicza się: wstawienie znaku, usunięcie znaku oraz zamianę znaku na inny.
Zastosowania
Miara ta znajduje zastosowanie w różnych dziedzinach, takich jak:
- maszynowe rozpoznawanie mowy
- analiza DNA
- rozpoznawanie plagiatów
- korekta pisowni
Przykłady obliczeń
Odległość Levenshteina między napisami można zilustrować na kilku przykładach:
- między „pies” a „pies” wynosi 0, ponieważ napisy są identyczne.
- między „granat” a „granit” wynosi 1, wymagając zamiany litery a na i.
- między „orczyk” a „oracz” wynosi 3, co wymaga usunięcia liter y i k, oraz wstawienia a.
- między „marka” a „ariada” wynosi 4, co wymaga usunięcia m, zamiany k na i, oraz dodania d i a.
Obliczanie odległości
Odległość Levenshteina można obliczyć przy użyciu programowania dynamicznego. Poniżej przedstawiono uproszczony algorytm:
int LevenshteinDistance(char s[1..m], char t[1..n]) {
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]
}
Uogólnienia
Odległość Levenshteina jest uogólnieniem odległości Hamminga. Istnieją także inne rozszerzenia, takie jak:
- Odległość Damerau-Levenshteina, która dodatkowo uwzględnia zamianę miejscami sąsiednich znaków.
- Umożliwienie operacji na blokach ciągów znaków, co jest przydatne w przetwarzaniu tekstów.
Te warianty są często określane jako odległości transformacyjne lub edycyjne, co wymaga precyzyjnego określenia zestawu używanych operacji.
