Calcular la distancia de Levenshtein rápidamente

Dada una enorme base de datos de palabras permitidas (ordenadas alfabéticamente) y una palabra, encuentre la palabra de la base de datos que esté más cerca de la palabra dada en términos de distancia de Levenshtein.

El enfoque ingenuo es, por supuesto, simplemente calcular la distancia levenshtein entre la palabra dada y todas las palabras en el diccionario (podemos hacer una búsqueda binaria en la base de datos antes de calcular las distancias).

Me pregunto si hay una solución más eficiente para este problema. Tal vez alguna heurística que nos permita reducir la cantidad de palabras a buscar, u optimizaciones al algoritmo de distancia levenshtein.

Enlaces a documentos sobre el tema de bienvenida.

Lo que está preguntando es el problema de la búsqueda de vecino bajo la distancia de edición. No mencionaste si te interesan los resultados teóricos o la heurística, por lo que responderé lo primero.

La distancia de edición es algo desagradable para tratar de construir estructuras de búsqueda cercanas. El principal problema es que, como métrica, se comporta (más o menos) como otras métricas conocidas como con el propósito de reducir y aproximar la dimensionalidad. Hay una gran cantidad de trabajo para leer sobre este tema, y ​​su mejor fuente es el conjunto de documentos de Alex Andoni : siguiendo los indicadores hacia atrás (por ejemplo, de su artículo de FOCS 2010) obtendrá un buen conjunto de fuentes.$\ell_1$

Autómatas de Levenshtein: http://en.wikipedia.org/wiki/Levenshtein_automaton

Árboles BK: http://en.wikipedia.org/wiki/BK-tree

Si tiene una pequeña cantidad de ediciones incorrectas que va a tolerar, puede intentar usar un árbol de sufijos punteado . Descargo de responsabilidad: escribí ese documento, pero resuelve lo que quiere: tiene un alto costo de espacio en disco, pero las consultas son realmente rápidas.

En general, es mejor mirarlo al revés: tiene un índice de todas las palabras en el diccionario. Ahora, para una palabra de entrada w, si está en el diccionario, deténgase. De lo contrario, genere todas las variaciones a la distancia 1 y búsquelas. Si no están allí, busque variaciones a la distancia 2, y así sucesivamente ...

Hay varias mejoras a esta idea básica.

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

Escribí una respuesta a una pregunta muy similar en cs.stackexchange.com ( /cs//a/2096/1490 ) y luego encontré esta pregunta. La respuesta allí es una búsqueda aproximada de vecino cercano en la distancia de edición (es decir, el algoritmo genera una cadena que está aproximadamente tan cerca de la cadena de consulta como el vecino más cercano de la cadena de consulta). Estoy publicando aquí ya que no encuentro ninguna de las referencias que di allí en las respuestas dadas aquí.

Creo que lo que quiere es el algoritmo de Wagner-Fischer: https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm La idea clave es que, dado que el diccionario que está atravesando está ordenado, dos palabras consecutivas es muy probable que comparta un prefijo largo, por lo que no necesita actualizar toda la matriz para cada cálculo de distancia.

Puedes usar ¿Quiso decir?

Y luego encuentre la distancia de Levenshtein entre la respuesta devuelta por "Quiso decir" y la cadena de entrada usando la Programación dinámica.

Una forma es entrenar un modelo de aprendizaje automático para mapear las palabras a vectores y mapear la distancia levenshtein a la distancia euclidiana. Luego puede construir un KDTree a partir de los vectores para el diccionario que desea usar. Creé un cuaderno jupyter que hace esto aquí: https://gist.github.com/MichaelSnowden/9b8b1e662c98c514d571f4d5c20c3a03

Según los comentarios de DW:

1. procedimiento de entrenamiento = descenso de gradiente estocástico con gradientes adaptativos
2. función de pérdida = error cuadrático medio entre la verdadera distancia de edición y la distancia euclidiana
3. datos de entrenamiento = cadenas aleatorias entre 1 y 32 caracteres de largo (podría mejorarse con datos que coincidan con una distribución real de errores tipográficos comunes)
4. Resultados cuantitativos: después de entrenar durante aproximadamente 150 épocas con un tamaño de lote de 2048 (tiempo de pared = aproximadamente un minuto), utilizando incrustaciones de palabras de 512 dimensiones, con una capa oculta, el error absoluto promedio entre la distancia de edición real y la distancia de edición prevista se encuentra alrededor de 0,75, lo que significa que la distancia de edición prevista es aproximadamente un carácter

Resumen de la estructura del modelo:

1. Cree una incrustación aprendida para cada carácter, incluido el carácter nulo (que se usa más adelante para rellenar con texto derecho debajo del límite de caracteres)
2. Rellene el lado derecho del texto con el carácter nulo hasta que esté en el límite de caracteres (32)
3. Concatenar estas incrustaciones
4. Ejecute las incrustaciones a través de una red neuronal de avance para producir una incrustación de palabras de menor dimensión (512 dimensiones)
5. Haz esto para ambas palabras
6. Encuentre la distancia euclidiana entre los vectores
7. Establezca la pérdida como el error cuadrático medio entre la verdadera distancia de Levenshtein y la distancia euclidiana

Mis datos de entrenamiento son solo cadenas aleatorias, pero creo que los resultados realmente podrían mejorar si los datos de entrenamiento fueran pares (error tipográfico / palabra correcta). Terminé usando /usr/share/dict/wordsporque está comúnmente disponible.