Niedawno zaimplementowałem algorytm odległości Damerau-Levenshteina z pseudokodu na Wikipedii. Nie mogłem znaleźć żadnego wyjaśnienia dokładnie jak to działa i pseudokod używa nazwy zmiennych całkowicie uninformative jak DA
, DB
, i1
, i j1
że zostawiła mnie drapania moją głowę.
Oto moja implementacja w Pythonie: https://gist.github.com/badocelot/5327337
Implementacja Pythona pomogła mi przejść przez program i dowiedzieć się, co się dzieje, zmieniając nazwy zmiennych na bardziej pomocne nazwy. Byłem wystarczająco obeznany z podejściem Wagnera-Fischera do obliczania odległości Levenshteina, że miałem ramkę odniesienia.
Ryzykując, że będę zbyt długi, rozumiem Damerau-Levenshtein:
Tajemnicze zmienne:
DA
(last_row
w moim kodzie) jest rodzajem mapy zawierającej ostatni wiersz, w którym każdy element był widziany; w moim kodzie jest to prawdziwy słownik PythonaDB
(last_match_col
) przechowuje ostatnią kolumnę, w której litera jestb
dopasowana do literya
dla bieżącego wierszai1
(last_matching_row
) to numer wierszaDA
dla bieżącej litery wb
j1
jest tylko kopią wartościDB
/last_match_col
przed jej potencjalną aktualizacją; w moim kodzie właśnie przesunąłem, gdzielast_match_col
jest aktualizowany i wyeliminowałem tę zmienną
Koszt transpozycji:
H[i1][j1] + (i-i1-1) + 1 + (j-j1-1)
oblicza koszt zamiany bieżącej postaci b
na ostatnią b
znaną postać a
(ostatnie dopasowanie), traktując wszystkie postacie między nimi jako uzupełnienia lub usunięcia.
Składniki kosztu:
H[i1][j1]
cofa koszt podstawowy do punktu w obliczeniach przed transpozycją, ponieważ znalezienie transpozycji unieważnia poprzednie prace(i-i1-1)
to odległość między bieżącym wierszem a ostatnim wierszem pasująca do bieżącego znaku, czyli liczba wymaganych operacji usunięcia(j-j1-1)
to odległość między bieżącą kolumną a ostatnią kolumną z dopasowaniem, która jest liczbą dodatków- Dodatkową korzyścią
+ 1
jest sam koszt transpozycji
Jeśli ta analiza jest nieprawidłowa, chciałbym wiedzieć, gdzie popełniłem błąd. Jak już mówiłem, nie mogłem znaleźć żadnego szczegółowe wyjaśnienie, w jaki sposób algorytm działa w Internecie.
Poprawiona wersja?
Po ustaleniu tego, uderzyło mnie, że obliczanie kosztów zarówno dodawania, jak i usuwania między transponowanymi literami wydawało się wadliwe: jedno dodanie i jedno usunięcie jest równoważne zamianie, której to nie sprawdza.
Jeśli wszystko jest w porządku, rozwiązanie powinno być trywialne: koszt liter między transponowanymi literami powinien być wyższy z dodań i usunięć: zamień jak najwięcej na podstawienia i dodaj wszelkie pozostałe uzupełnienia lub usunięcia.
Koszt byłby więc:
H[i1][j1] + max((i-i1-1), (j-j1-1)) + 1
Oto mój kod dla tej wersji: https://gist.github.com/badocelot/5327427
Z kilku prostych testów wydaje się to poprawne. Na przykład „abcdef” -> „abcfad” daje odległość edycji 2 (transpozycja „d” i „f”, zmiana „e” na „a”), podczas gdy oryginalny algorytm podaje odległość 3 (albo trzy ostatnie litery to podstawienia lub 1 transpozycja + 1 dodatek + 1 usunięcie).
Nie mogę być pierwszą osobą, która o tym pomyślała. Dlaczego więc nie natknąłem się na to? Czy po prostu nie szukałem wystarczająco długo? A może jest jakaś subtelna wada, która uniemożliwia to działanie?
źródło
Odpowiedzi:
Musiałem sprawdzić odległość Damerau-Levenshtein na wikipedii, więc wybacz mi, jeśli to źle. Wygląda jednak na to, że pozwala jedynie na transpozycję sąsiednich liter, a nie dowolnych liter. Twój przykład „abcdef” -> „abcfad” z transpozycją d i f nie działa. Wydaje mi się, że zmodyfikowałeś definicję algorytmu i nie obliczasz już odległości Damerau-Levenshtein.
źródło