¿Cuál es un buen algoritmo para atravesar un Trie para verificar las sugerencias de ortografía?

Question

Suponiendo que se construye una Trie general de palabras del diccionario, ¿cuál sería el mejor método para verificar los 4 casos de errores de ortografía: sustitución, eliminación, transposición e inserción durante el recorrido?

Un método es averiguar todas las palabras dentro de n editar las distancias de una palabra dada y luego buscarlas en el Trie. Esta no es una mala opción, pero una mejor intuición aquí parece ser el uso de un método de programación dinámica (o un equivalente recursivo) para determinar los mejores sub-intentos después de haber modificado las palabras durante el recorrido.

¡Cualquier idea sería bienvenida!

PD, agradecería las entradas reales en lugar de solo enlaces en las respuestas.

Answer 1

De hecho, me escribió algo de código para hacer esto el otro día:

https://bitbucket.org/teoryn/spell-checker/src/tip/spell_checker.py

Se basa en el código de Peter Norvig (http://norvig.com/spell-correct.html), pero almacena el diccionario en un trie de búsqueda de palabras dentro de una edición determinada distancia más rápido.

El algoritmo recorre el trie recursivamente aplicando las ediciones posibles (o no) en cada paso del camino, consumiendo letras de la palabra de entrada. Un parámetro para la llamada recursiva indica cuántas ediciones más se pueden realizar. El trie ayuda a reducir el espacio de búsqueda al verificar qué letras se pueden alcanzar realmente desde nuestro prefijo dado. Por ejemplo, al insertar un carácter, en lugar de agregar cada letra en el alfabeto, solo agregamos las letras que son accesibles desde el nodo actual. No hacer una edición equivale a tomar la rama del nodo actual en el trie junto con la letra actual de la palabra de entrada. Si esa rama no está allí, podemos retroceder y evitar buscar un espacio posiblemente grande donde no se encuentren palabras reales.

Answer 2

Eche un vistazo al cálculo de Levenshtein distance que proporciona una solución de programación dinámica para encontrar la distancia entre dos secuencias.

Answer 3

Creo que puede hacer esto con una simple búsqueda de amplitud en el árbol: elija un umbral del número de errores que está buscando, simplemente ejecute las letras de la palabra que se emparejarán de a una por vez, generar un conjunto de (prefijo, subtrie) pares alcanzados hasta el momento que coincide con el prefijo, y mientras esté por debajo de su umbral de error, añadir a su conjunto de los siguientes sub-objetivos:

1. No hay error en este lugar personaje: agregue el subobjetivo del trie en el siguiente carácter de la palabra
2. Un carácter insertado, eliminado o sustituido en este lugar: encuentre el trie apropiado allí e incremente el recuento de errores;
3. No es un objetivo adicional, pero tenga en cuenta que las transposiciones son una inserción o eliminación que coincide con una eliminación o inserción anterior: si esta prueba se mantiene, no incremente el recuento de errores.

Esto parece bastante ingenuo: ¿hay algún problema con esto que lo lleve a pensar en la programación dinámica?

Answer 4

Suponer que cada carácter sucesivo en su palabra representa un nivel en su árbol, entonces tiene cinco casos para verificar en cada carácter (una coincidencia, eliminación, inserción, sustitución y transposición). Supongo que las transposiciones son dos caracteres adyacentes.

Necesitará una función (CheckNode) que acepte un nodo de árbol y un carácter para verificar. Tendrá que devolver un conjunto de nodos (hijo/nieto) que representan coincidencias.

Necesitará una función (CheckWord) que acepte una palabra. Comprueba cada carácter a su vez contra un conjunto de nodos. Devolverá un conjunto de nodos (hoja) que representan palabras coincidentes.

La idea es que cada nivel en el árbol (niño, nieto, etc.), coincida con la posición del personaje en la palabra. Si llama al nodo de árbol de nivel superior, nivel 0, tendrá el nivel 1, el nivel 2, etc.

Claramente para una palabra sin errores, hay una coincidencia uno a uno entre la posición del personaje y el nivel en el árbol.

Para eliminar, debe omitir un nivel en el árbol.

Para las inserciones, debe omitir un carácter en la palabra.

Para las sustituciones, debe omitir tanto un nivel como un carácter.

Para las transposiciones, debe (temporalmente) intercambiar los caracteres de la palabra.