Odległość Levenshteina – miara różnicy między dwoma napisami lub, szerzej, skończonymi ciągami symboli. Jest równa najmniejszej liczbie operacji wstawienia, usunięcia i zamiany pojedynczego symbolu potrzebnych do przekształcenia jednego ciągu w drugi. W klasycznej definicji każda z tych operacji ma koszt równy 1V. I. Levenshtein, „Binary codes capable of correcting deletions, insertions, and reversals”, Doklady Akademii Nauk SSSR, t. 163, nr 4, 1965, s. 845–848; przekład angielski: Soviet Physics Doklady, t. 10, nr 8, 1966, s. 707–710. Math-Net..
Nazwa pochodzi od nazwiska radzieckiego matematyka Władimira Lewensztejna, który wprowadził tę miarę w 1965 roku w kontekście kodów korygujących błędy. Odległość Levenshteina jest jednym z podstawowych rodzajów odległości edycyjnej. Określenie „odległość edycyjna” bywa używane także szerzej, dla modeli, w których zmienia się zbiór dopuszczalnych operacji lub ich kosztyGonzalo Navarro, „A guided tour to approximate string matching”, ACM Computing Surveys, t. 33, nr 1, 2001, s. 31–88, doi:10.1145/375360.375365..
Definicja Niech
oraz
będą dwoma ciągami. Przez oznaczmy odległość Levenshteina między prefiksem a prefiksem .
Dla ciągu pustego zachodzą warunki brzegowe
Dla i :
gdzie
Trzy składniki odpowiadają odpowiednio usunięciu symbolu z ciągu źródłowego, wstawieniu symbolu z ciągu docelowego oraz pozostawieniu symbolu bez zmiany albo jego zamianieRobert A. Wagner, Michael J. Fischer, „The String-to-String Correction Problem”, Journal of the ACM, t. 21, nr 1, 1974, s. 168–173, doi:10.1145/321796.321811.. Szukana odległość dwóch pełnych ciągów jest równa .
Przykłady Odległość Levenshteina między identycznymi napisami, np. „pies” i „pies”, wynosi 0.
Dla napisów „granat” i „granit” odległość wynosi 1, ponieważ wystarcza zamiana litery „a” na „i”.
Dla klasycznego przykładu „kitten” i „sitting” odległość wynosi 3. Jedna z optymalnych sekwencji operacji to:
kitten → sitten – zamiana k na s; sitten → sittin – zamiana e na i; sittin → sitting – wstawienie g.
Własności i ograniczenia Przy jednostkowych kosztach wstawienia, usunięcia i zamiany odległość Levenshteina jest metryką: jest nieujemna, wynosi 0 wtedy i tylko wtedy, gdy oba ciągi są identyczne, jest symetryczna i spełnia nierówność trójkąta.
Dla ciągów o długościach i :
Dolne ograniczenie wynika z tego, że pojedyncze wstawienie lub usunięcie zmienia długość ciągu tylko o 1. Górne ograniczenie można osiągnąć przez zamianę symboli w części o wspólnej długości, a następnie wstawienie lub usunięcie pozostałych symboli.
Jeżeli oba ciągi mają tę samą długość, odległość Hamminga jest górnym ograniczeniem odległości Levenshteina:
Odległość Hamminga dopuszcza wyłącznie zamiany i jest bezpośrednio definiowana dla ciągów tej samej długości.
Jeżeli nie dopuszcza się zamian, a jedynie wstawienia i usunięcia, to minimalna liczba operacji dla ciągów długości i wynosi
gdzie jest długością najdłuższego wspólnego podciągu. Zależność ta nie przechodzi wprost na klasyczną odległość Levenshteina, ponieważ zamiana kosztuje w niej 1, a nie 2 jak usunięcie połączone z wstawieniem.
Obliczanie Programowanie dynamiczne
Standardowy algorytm wykorzystuje programowanie dynamiczne. W tablicy o wymiarach przechowywane są odległości między wszystkimi parami prefiksów.
function LevenshteinDistance(s[1..m], t[1..n]): utwórz d[0..m, 0..n]
for i = 0..m: d[i,0] = i
for j = 0..n: d[0,j] = j
for i = 1..m: for j = 1..n: if s[i] = t[j]: koszt = 0 else: koszt = 1
d[i,j] = minimum( d[i-1,j] + 1, // usunięcie s[i] d[i,j-1] + 1, // wstawienie t[j] d[i-1,j-1] + koszt // zgodność albo zamiana )
return d[m,n]
Algorytm wypełniający całą tablicę ma złożoność czasową i pamięciową .
Jeżeli potrzebna jest tylko wartość odległości, wystarczy przechowywać bieżący i poprzedni wiersz (albo kolumnę). Po wybraniu krótszego ciągu jako wymiaru przechowywanego pamięć roboczą można ograniczyć do Esko Ukkonen, „Algorithms for approximate string matching”, Information and Control, t. 64, nr 1–3, 1985, s. 100–118, doi:10.1016/S0019-9958(85)80046-2..
Odtwarzanie operacji Jeżeli zachowana jest pełna tablica, można od komórki przechodzić wstecz do komórek poprzedzających i w ten sposób odtworzyć optymalny ciąg operacji. Dla jednej pary napisów może istnieć więcej niż jedna optymalna sekwencja edycji o tym samym koszcie.
Algorytmy zależne od odległości Gdy rzeczywista odległość jest niewielka w porównaniu z długościami napisów, nie zawsze trzeba obliczać całą tablicę. Ukkonen przedstawił algorytmy dokładne, których koszt zależy od ; jeden z wyników z 1985 roku osiąga czas . W tym kontekście określenie „przybliżone dopasowanie napisów” oznacza dopasowanie dopuszczające błędy, a nie przybliżanie samej wartości odległości.
Metody bitowe Gene Myers zaproponował w 1999 roku algorytm bit-wektorowy dla przybliżonego dopasowania wzorca. Wiele stanów programowania dynamicznego reprezentuje się w bitach słowa maszynowego i aktualizuje równolegle za pomocą operacji bitowychGene Myers, „A fast bit-vector algorithm for approximate string matching based on dynamic programming”, Journal of the ACM, t. 46, nr 3, 1999, s. 395–415, doi:10.1145/316542.316550..
Złożoność problemu Dla ciągów jednakowej długości Backurs i Indyk wykazali w 2015 roku, że istnienie dokładnego algorytmu działającego w czasie dla dowolnej stałej przeczyłoby hipotezie SETH (Strong Exponential Time Hypothesis)Arturs Backurs, Piotr Indyk, „Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)”, Proceedings of the 47th Annual ACM Symposium on Theory of Computing, 2015, s. 51–58, doi:10.1145/2746539.2746612.. Jest to zatem dolne ograniczenie warunkowe, a nie bezwarunkowy dowód konieczności czasu kwadratowego we wszystkich modelach obliczeń.
Warianty i odległości pokrewne W ważonej odległości edycyjnej poszczególne operacje mogą mieć różne koszty, a koszt zamiany może zależeć od pary symboli. Dowolnie dobrane koszty nie muszą zachowywać wszystkich własności metryki; na przykład koszty asymetryczne mogą naruszyć symetrię.
Odległość Damerau-Levenshteina rozszerza zestaw podstawowych operacji o zamianę miejscami dwóch sąsiednich symboli.
Odległość Hamminga stanowi przypadek ograniczony do zamian i do ciągów równej długości. Z kolei wariant dopuszczający tylko wstawienia i usunięcia jest ściśle związany z najdłuższym wspólnym podciągiem.
Zastosowania Korekta pisowni w języku polskim
Odległość Levenshteina jest wykorzystywana w systemach sprawdzania pisowni do wyszukiwania kandydatów podobnych do błędnie zapisanego słowa. W przypadku języka polskiego samo zastosowanie rozwiązania zaprojektowanego dla języka angielskiego nie musi być optymalne ze względu na fleksję i cechy polskiej ortografii. Krzysztof Dorosz opisał adaptację metody opartej na odległości Levenshteina do korekty tekstów polskich, uwzględniającą m.in. wykorzystanie słownika fleksyjnego i właściwości języka polskiegoKrzysztof Dorosz, „Automatyczne sprawdzanie poprawności pisowni w języku polskim oparte na odległości Levenshteina”, Automatyka, t. 12, z. 1, 2008, s. 29–40. BaDAP AGH..
Polskie teksty historyczne i OCR W przetwarzaniu historycznej polszczyzny odległość Levenshteina może służyć do wyszukiwania dawnych wariantów pisowni. Filip Graliński i Krzysztof Jassem zastosowali ją wraz z podobieństwem wektorowym Word2Vec do wykrywania wariantów pisowni w korpusie współczesnych i historycznych tekstów polskich. Autorzy pokazali również analogiczne wykorzystanie metody do znajdowania wariantów powstałych wskutek błędów OCRFilip Graliński, Krzysztof Jassem, „Mining historical texts for diachronic spelling variants”, Poznań Studies in Contemporary Linguistics, t. 56, nr 4, 2020, s. 629–650, doi:10.1515/psicl-2020-0021..
Wyszukiwanie przybliżone i dopasowywanie danych W wyszukiwaniu przybliżonym odległość edycyjna umożliwia znalezienie napisów różniących się literówkami, brakującymi znakami lub dodatkowymi znakami. Dla dużych zbiorów danych obliczenie pełnej odległości dla każdego możliwego kandydata bywa łączone z filtrowaniem, indeksowaniem lub innymi metodami ograniczającymi liczbę szczegółowych porównań.
Rozpoznawanie mowy W automatycznym rozpoznawaniu mowy wynik systemu porównuje się z transkrypcją referencyjną m.in. za pomocą współczynnika Word Error Rate (WER). Liczby zamian, usunięć i wstawień słów wyznacza się z optymalnego dopasowania edycyjnego, a następnie oblicza
gdzie , i oznaczają liczbę zamian, usunięć i wstawień, a – liczbę słów w transkrypcji referencyjnej. WER jest stosowany również w badaniach nad rozpoznawaniem mowy polskiejArtur Zygadło, Artur Janicki, Przemysław Dąbek, „System rozpoznawania mowy polskiej dla robota społecznego”, Pomiary Automatyka Robotyka, t. 20, nr 4, 2016, s. 27–36, doi:10.14313/PAR_222/27..
Bioinformatyka W bioinformatyce odległość edycyjna i problem dopasowania sekwencji są ściśle związane. Wstawienia, usunięcia i zamiany tworzą prosty model różnic między sekwencjami DNA lub białek, jednak praktyczne algorytmy dopasowania biologicznego często stosują bardziej złożone macierze substytucji oraz kary za przerwy niż jednostkowa odległość LevenshteinaBonnie Berger, Michael S. Waterman, Yun William Yu, „Levenshtein Distance, Sequence Comparison and Biological Database Search”, IEEE Transactions on Information Theory, t. 67, nr 6, 2021, s. 3287–3294, doi:10.1109/TIT.2020.2996543..
Unicode i jednostka porównania Definicja matematyczna dotyczy ciągów symboli i sama nie określa, czym w implementacji ma być pojedynczy „znak”. W tekście zapisanym w Unicode porównywać można m.in. bajty, jednostki kodowe, punkty kodowe lub klastry grafemów. Wybór jednostki może prowadzić do różnych wartości odległości.
Ma to praktyczne znaczenie również dla polskiego tekstu. Przykładowo litera „ą” może być zapisana jako pojedynczy punkt kodowy U+0105 albo jako sekwencja litery „a” U+0061 i łączącego ogonka U+0328; Unicode traktuje te reprezentacje jako kanonicznie równoważneUnicode, Latin Extended-A – Names List.. Bez normalizacji porównanie na poziomie punktów kodowych może więc dać niezerową odległość dla tekstów wyglądających tak samo.
Unicode Standard Annex #15 definiuje formy normalizacji, m.in. NFC i NFDUnicode Consortium, „Unicode Standard Annex #15: Unicode Normalization Forms”. Unicode Consortium., a Unicode Standard Annex #29 opisuje rozszerzone klastry grafemów jako algorytmiczne przybliżenie znaków postrzeganych przez użytkownikaUnicode Consortium, „Unicode Standard Annex #29: Unicode Text Segmentation”. Unicode Consortium.. Z tego powodu implementacja pracująca z tekstem Unicode powinna określać zarówno jednostkę porównania, jak i ewentualną normalizację wykonywaną przed obliczeniem odległości.
Historia Lewensztejn opublikował podstawową pracę w 1965 roku w czasopiśmie Doklady Akademii Nauk SSSR; angielski przekład ukazał się w 1966 roku. Praca powstała w ramach teorii kodowania i dotyczyła kodów zdolnych do korygowania błędów związanych z usuwaniem, wstawianiem i zmianą symboli.
W 1974 roku Wagner i Fischer przedstawili algorytm programowania dynamicznego dla ogólnego problemu przekształcania jednego ciągu w drugi, działający w czasie proporcjonalnym do iloczynu długości ciągów. Późniejsze prace rozwijały m.in. algorytmy zależne od rzeczywistej odległości, metody bitowe oraz techniki stosowane w przybliżonym dopasowywaniu napisów.
Przypisy
Bibliografia Dan Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997, . Gonzalo Navarro, „A guided tour to approximate string matching”, ACM Computing Surveys, t. 33, nr 1, 2001, s. 31–88. Krzysztof Dorosz, „Automatyczne sprawdzanie poprawności pisowni w języku polskim oparte na odległości Levenshteina”, Automatyka, t. 12, z. 1, 2008, s. 29–40.