Odległość edycyjna (odległość Levenshteina)
Wpisz recieve, a telefon podpowie receive. Wie, że byłeś blisko, bo oba słowa dzieli tylko kilka operacji. Mierzenie tej bliskości, czyli odległości edycyjnej, to klasyczne zadanie dla programowania dynamicznego.
Problem
Operacja zmienia słowo o jedną literę: wstawia literę, usuwa literę albo zamienia jedną literę na inną. Odległość edycyjna dwóch słów to najmniejsza liczba operacji, które zmieniają jedno w drugie. Między cat a cut odległość wynosi 1, między cat a cast też 1, a między cat a act 2. Nazywa się ją też odległością Levenshteina, od nazwiska radzieckiego matematyka: Vladimir Levenshtein badał ją w 1965 roku.
Tabela
Niech d[i][j] oznacza odległość edycyjną między pierwszymi i literami jednego słowa a pierwszymi j literami drugiego. Zamiana słowa w nic wymaga jednego usunięcia na literę, więc d[i][0] = i, a zbudowanie słowa od zera wymaga jednego wstawienia na literę, więc d[0][j] = j. Jeśli litera i jest równa literze j, to d[i][j] = d[i − 1][j − 1]. W przeciwnym razie d[i][j] = 1 + najmniejsza z wartości d[i − 1][j − 1] (zamiana), d[i − 1][j] (usunięcie) i d[i][j − 1] (wstawienie).
Przykład
Dla kitten i sitting tabela ma 7 wierszy i 8 kolumn. Prawa dolna komórka ma wartość 3, a odczyt wstecz od niej daje: zamień k na s, zachowaj i, t i t, zamień e na i, zachowaj n i wstaw g. Z kitten przez sitten i sittin do sitting: trzy operacje, a tabela dowodzi, że krótsza lista nie istnieje.
Odczytywanie operacji wstecz
Zacznij od prawej dolnej komórki i zapytaj, od którego sąsiada pochodzi jej wartość. Jeśli litery są zgodne, a komórka jest równa lewemu górnemu sąsiadowi, litera została zachowana: przejdź po przekątnej. Jeśli jest o jeden większa od lewego górnego sąsiada, była to zamiana; o jeden większa od komórki powyżej – usunięcie; o jeden większa od komórki po lewej – wstawienie. Kilka ścieżek może dawać ten sam wynik, a każda z nich daje najkrótszą listę operacji.
Historia i zastosowania
Levenshtein wprowadził tę odległość w 1965 roku, pracując nad kodami korygującymi błędy. Metodę tabeli opublikowało kilka osób, najbardziej znani są Robert Wagner i Michael Fischer w 1974 roku, dlatego często nazywa się ją algorytmem Wagner–Fischer. Dziś odległości edycyjne porządkują podpowiedzi pisowni, znajdują w bazach danych nazwiska z literówkami, porównują sekwencje DNA i białek oraz oceniają rozpoznawanie mowy.
Wypróbuj
Otwórz aplikację i naciśnij Krok. Dwie porównywane litery podświetlają się w nagłówkach; równe litery kopiują niebieską komórkę w lewo w górę, a różne odczytują wszystkich trzech niebieskich sąsiadów i dodają jeden do najmniejszego. Na końcu pomarańczowa ścieżka biegnie wstecz od rogu, a operacje pojawiają się pod tabelą.
Często zadawane pytania
Czy odległość edycyjna jest metryką?
Tak. Nigdy nie jest ujemna, wynosi 0 tylko dla równych słów, jest taka sama w obu kierunkach, a przejście przez trzecie słowo nigdy jej nie skróci: d(a, c) ≤ d(a, b) + d(b, c). Dzięki temu przydaje się do szukania bliskich dopasowań.
Czym jest odległość Damerau–Levenshteina?
To odległość edycyjna z jedną dodatkową operacją: zamianą miejscami dwóch sąsiednich liter. Frederick Damerau ustalił w 1964 roku, że wstawienie, usunięcie, zamiana i przestawienie razem obejmują ponad 80% błędów pisowni. Z przestawieniami odległość między recieve a receive wynosi 1 zamiast 2.
Czy odległość edycyjną można obliczyć szybciej niż w O(m·n)?
Niewiele. W 2015 roku Arturs Backurs i Piotr Indyk pokazali, że metoda działająca w czasie O(n^(2 − ε)) dla pewnego ε > 0 obaliłaby silną hipotezę czasu wykładniczego, w którą wierzy większość badaczy. Dla słów, które są do siebie podobne, wystarczy jednak wąski pas wokół przekątnej tabeli.
Jak odległość edycyjna pomaga porównywać DNA?
Biolodzy używają tej samej tabeli z punktacją zamiast liczenia: zgodności dają punkty, a zamiany i przerwy kosztują punkty zależne od liter. To algorytm Needleman–Wunsch z 1970 roku dla całych sekwencji i algorytm Smith–Waterman z 1981 roku dla najlepiej pasujących fragmentów.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Wypróbuj odległość edycyjną