Możliwe ulepszenie Damerau-Levenshtein?

9

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?

James Jensen
źródło
Postanowiłem napisać post na blogu szczegółowo wyjaśniający DL: scarcitycomputing.blogspot.com/2013/04/…
James Jensen

Odpowiedzi:

3

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.

Steve
źródło
Hmm, rozumiem co masz na myśli. DL pozwala na transpozycje przed dodaniem lub po usunięciu. Jeśli oba wystąpiły, tak naprawdę nie jest to transpozycja sąsiednia, więc koszt gwałtownie wzrośnie i koszt transpozycji nie zostanie wybrany jako nowy koszt. Wyglądało na to, że radzi sobie z obydwoma, ponieważ unika ich dzięki efektowi ubocznemu minimalizacji kosztów.
James Jensen,