Tengo un diccionario de cadenas de 50K a 100K (puede tener hasta más de 50 caracteres) y estoy tratando de encontrar si una cadena dada está en el diccionario con alguna tolerancia de distancia de "edición". (Levenshtein por ejemplo). Estoy bien pre-computando cualquier tipo de estructura de datos antes de hacer la búsqueda.

Mi objetivo es correr miles de cadenas contra ese diccionario lo más rápido posible y devolver al vecino más cercano. Estaría bien simplemente obteniendo un booleano que diga si un determinado está en el diccionario o no si hubiera un algoritmo significativamente más rápido para hacerlo

Para esto, primero intenté calcular todas las distancias de Levenshtein y tomar el mínimo y obviamente fue terriblemente lento. Así que traté de implementar un Levenshtein Trie basado en este artículohttp://stevehanov.ca/blog/index.php?id=114

Vea mi esencia aquí para reproducir el punto de referencia:https://gist.github.com/nicolasmeunier/7493947

Aquí hay algunos puntos de referencia que obtuve en mi máquina:

Editar distancia de 0 (coincidencia perfecta)

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> 

*Editar la distancia de 2, se vuelve mucho más 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>

Y va cuesta abajo desde allí y se vuelve extremadamente lento para una distancia de edición mayor que 2. (1+ segundo en promedio por cadena probada).

Me gustaría saber cómo / si podría acelerar esto significativamente. Si ya existen soluciones ya implementadas en ruby ​​/ gems, tampoco quiero reinventar la rueda ...

EDITAR 1: En mi caso, espero que la mayoría de las cadenas que estoy comparando con el diccionario NO estén allí. Entonces, si hay algún algoritmo para descartar rápidamente una cadena, eso realmente podría ayudar.

Gracias nicolas