Obliczanie odległości Levenshteina szybko

Biorąc pod uwagę ogromną bazę dozwolonych słów (posortowane alfabetycznie) i słowo, znajdź słowo z bazy danych, która jest najbliższa podanemu słowu pod względem odległości Levenshteina.

Naiwnym podejściem jest oczywiście po prostu obliczenie odległości levenshteina między danym słowem a wszystkimi słowami w słowniku (możemy przeprowadzić wyszukiwanie binarne w bazie danych przed obliczeniem odległości).

Zastanawiam się, czy istnieje bardziej wydajne rozwiązanie tego problemu. Może jakaś heurystyka, która pozwala nam zmniejszyć liczbę słów do wyszukania lub optymalizację algorytmu odległości Levenshteina.

Linki do artykułów na ten temat są mile widziane.

To, o co pytasz, to problem wyszukiwania w sąsiedztwie pod odległością edycji. Nie wspomniałeś, czy interesują Cię wyniki teoretyczne, czy heurystyka, więc odpowiem na to pierwsze.

Odległość edycji jest nieco nieprzyjemna w przypadku budowania struktur wyszukiwania w sąsiedztwie. Główny problem polega na tym, że jako metryka zachowuje się (podobnie) jak inne dobrze znane złe metryki, takie jak w celu zmniejszenia wymiarów i przybliżenia. Jest dużo pracy do przeczytania na ten temat, a twoim najlepszym źródłem jest zestaw artykułów Alexa Andoniego : podążając za wskazówkami do tyłu (na przykład z jego artykułu z FOCS 2010) otrzymasz dobry zestaw źródeł.$\ell_1$

Automaty Levenshtein: http://en.wikipedia.org/wiki/Levenshtein_automaton

Drzewa BK: http://en.wikipedia.org/wiki/BK-tree

Jeśli masz niewielką liczbę błędnych edycji, które będziesz tolerować, możesz spróbować użyć drzewa kropek . Oświadczenie: Napisałem ten papier, ale rozwiązuje to, czego chcesz: ma wysoki koszt miejsca na dysku, ale zapytania są naprawdę szybkie.

Ogólnie rzecz biorąc, lepiej spojrzeć na to odwrotnie: masz indeks wszystkich słów w słowniku. Teraz, jeśli słowo wejściowe w znajduje się w słowniku, przestań. W przeciwnym razie wygeneruj wszystkie warianty w odległości 1 i poszukaj ich. Jeśli ich tam nie ma, poszukaj odmian w odległości 2 itd.

Istnieje kilka ulepszeń tego podstawowego pomysłu.

$O(m^{k+1} \cdot \sigma^{k})$$m$$\sigma$$k$

Odpowiedziałem na bardzo podobne pytanie na cs.stackexchange.com ( /cs//a/2096/1490 ), a potem znalazłem to pytanie. Istnieje odpowiedź na przybliżone wyszukiwanie w sąsiedztwie w odległości edycji (tj. Algorytm generuje ciąg znaków, który jest w przybliżeniu tak blisko ciągu zapytania, jak najbliższy sąsiad ciągu zapytania). Piszę tutaj, ponieważ nie znajduję żadnego z odniesień, które tam podałem w podanych tutaj odpowiedziach.

Myślę, że to, czego chcesz, to algorytm Wagnera-Fischera: https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorytm Kluczową sprawą jest to, że skoro słownik, przez który przechodzisz, jest posortowany, dwa kolejne słowa bardzo często mają długi prefiks, więc nie trzeba aktualizować całej macierzy dla każdego obliczenia odległości.

Możesz użyć Czy miałeś na myśli?

Następnie znajdź odległość Levenshteina między odpowiedzią zwróconą przez „Czy miałeś na myśli” a ciągiem wejściowym za pomocą programowania dynamicznego.

Jednym ze sposobów jest szkolenie modelu uczenia maszynowego do mapowania słów na wektory i mapowania odległości lewenshteina do odległości euklidesowej. Następnie możesz zbudować KDTree z wektorów dla słownika, którego chcesz użyć. Utworzyłem notatnik jupyter, który robi to tutaj: https://gist.github.com/MichaelSnowden/9b8b1e662c98c514d571f4d5c20c3a03

Zgodnie z komentarzami DW:

1. procedura treningowa = opadanie gradientu stochastycznego z gradientami adaptacyjnymi
2. funkcja straty = średni błąd kwadratu między prawdziwą odległością edycji a odległością euklidesową
3. dane treningowe = losowe ciągi o długości od 1 do 32 znaków (można poprawić o dane, które pasują do rzeczywistego rozkładu typowych literówek)
4. wyniki ilościowe: po treningu dla około 150 epok z rozmiarem partii 2048 (czas na ścianie = około jednej minuty), przy użyciu osadzania słów o 512 wymiarach, z jedną ukrytą warstwą, średni błąd bezwzględny między rzeczywistą odległością edycji a przewidywaną odległością edycji wynosi około 0,75, co oznacza, że ​​przewidywany dystans edycji wynosi mniej więcej jeden znak

Podsumowanie struktury modelu:

1. Utwórz wyuczone osadzanie dla każdego znaku, w tym znaku zerowego (używanego później do wpisywania tekstu po prawej stronie poniżej limitu znaków)
2. Wypełnij prawą stronę tekstu znakiem null, aż osiągnie limit znaków (32)
3. Połącz te osadzenia
4. Przeprowadź osadzanie przez sieć neuronową ze sprzężeniem zwrotnym, aby utworzyć osadzanie słów niższego wymiaru (512-wymiarowe)
5. Zrób to dla obu słów
6. Znajdź odległość euklidesową między wektorami
7. Ustaw stratę jako średni błąd kwadratu między prawdziwą odległością Levenshteina a odległością euklidesową

Moje dane treningowe to tylko losowe ciągi, ale myślę, że wyniki mogłyby się naprawdę poprawić, gdyby dane treningowe były parami (literówka / poprawne słowo). Skończyło się na tym, że używałem, /usr/share/dict/wordsponieważ jest powszechnie dostępny.