Mam słownik ciągów od 50K do 100K (może mieć maksymalnie 50 znaków) i próbuję znaleźć, czy dany ciąg jest w słowniku z pewną tolerancją odległości „edytuj”. (Na przykład Levenshtein). Dobrze wykonuję wstępne obliczanie dowolnej struktury danych przed rozpoczęciem wyszukiwania.

Moim celem jest jak najszybsze uruchomienie tysięcy ciągów w stosunku do tego słownika i zwrócenie najbliższego sąsiada. Byłbym w porządku, gdybyśmy otrzymali boolean, który mówi, czy dany podany jest w słowniku, czy nie, jeśli istnieje znacznie szybszy algorytm, aby to zrobić

W tym celu po raz pierwszy próbowałem obliczyć wszystkie odległości Levenshteina i wziąć minimum i było to oczywiście strasznie powolne. Próbowałem więc wdrożyć Levenshtein Trie na podstawie tego artykułuhttp://stevehanov.ca/blog/index.php?id=114

Zobacz moją istotę tutaj, aby odtworzyć benchmark:https://gist.github.com/nicolasmeunier/7493947

Oto kilka testów porównawczych na moim komputerze:

Edytuj odległość 0 (idealne dopasowanie)

Benchmark.measure { 10.times { dictionary.search(random_word, 0) } }
<Benchmark::Tms:0x007fa59bad8908 @label="", @real=0.010889, @cstime=0.0, @cutime=0.0, @stime=0.0, @utime=0.00999999999999801, @total=0.00999999999999801> 

*Edytuj odległość 2, staje się dużo wolniejsza *

Benchmark.measure { 10.times { dictionary.search(random_word, 2) } }
<Benchmark::Tms:0x007fa58c9ca778 @label="", @real=3.404604, @cstime=0.0, @cutime=0.0, @stime=0.020000000000000018, @utime=3.3900000000000006, @total=3.4100000000000006>

Stamtąd spada i staje się niezwykle powolny dla odległości edycji większej niż 2. (średnio 1+ sekund na testowany ciąg).

Chciałbym wiedzieć, jak / jeśli mogę to znacznie przyspieszyć. Jeśli istnieją już rozwiązania już zaimplementowane w ruby ​​/ gems, nie chcę też wymyślać nowego koła ...

EDYCJA 1: W moim przypadku oczekuję, że większość ciągów, które dopasowuję do słownika NIE będzie tam. Jeśli więc istnieje jakikolwiek algorytm umożliwiający szybkie odrzucenie ciągu, może to naprawdę pomóc.

Dzięki, Nicolas