Możliwe ulepszenie Damerau-Levenshtein?

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_roww 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 Pythona
• DB( last_match_col) przechowuje ostatnią kolumnę, w której litera jest bdopasowana do litery adla bieżącego wiersza
• i1( last_matching_row) to numer wiersza DAdla bieżącej litery wb
• j1jest tylko kopią wartości DB/ last_match_colprzed jej potencjalną aktualizacją; w moim kodzie właśnie przesunąłem, gdzie last_match_coljest aktualizowany i wyeliminowałem tę zmienną

Koszt transpozycji:

H[i1][j1] + (i-i1-1) + 1 + (j-j1-1)

oblicza koszt zamiany bieżącej postaci bna ostatnią bznaną 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ą + 1jest 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?

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.