Eu tenho um dicionário de 50K a 100K strings (pode ter até 50+ caracteres) e estou tentando descobrir se uma determinada string está no dicionário com alguma tolerância de "editar" distância. (Levenshtein por exemplo). Estou bem pré-computando qualquer tipo de estrutura de dados antes de fazer a pesquisa.

Meu objetivo é executar milhares de strings contra esse dicionário o mais rápido possível e retornar o vizinho mais próximo. Eu estaria bem apenas pegando um booleano que diga se um dado está no dicionário ou não se houvesse um algoritmo significativamente mais rápido para fazer isso

Para isso, eu primeiro tentei calcular todas as distâncias de Levenshtein e pegar o mínimo e foi obviamente terrivelmente lento. Então eu tentei implementar um Levenshtein Trie baseado neste artigohttp://stevehanov.ca/blog/index.php?id=114

Veja minha essência aqui para reproduzir o benchmark:https://gist.github.com/nicolasmeunier/7493947

Aqui estão alguns benchmarks que eu tenho na minha máquina:

Edite a distância de 0 (correspondência perfeita)

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> 

*Edite a distância de 2, torna-se muito mais lento *

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>

E desce a partir daí e torna-se extremamente lento para editar distâncias maiores que 2. (1+ segundo em média por string testada).

Eu gostaria de saber como / se eu poderia acelerar isso significativamente. Se já existem soluções já implementadas em Ruby / Gems, também não quero reinventar a roda ...

EDIT 1: No meu caso, eu espero que a maioria das cordas que eu estou combinando com o dicionário não esteja lá. Portanto, se houver algum algoritmo para descartar rapidamente uma string, isso pode realmente ajudar.

Obrigado Nicolas