¿Estructura de datos para diccionario y corrector ortográfico?

¿Qué estructura de datos se puede utilizar para crear de forma eficaz un diccionario de palabras y un corrector ortográfico ?

La respuesta depende de los funcionalistas requeridos en el corrector ortográfico y la disponibilidad de memoria. Por ejemplo, las siguientes son algunas posibilidades.

Hashing es una opción simple para esto. Podemos poner todas las palabras en una tabla hash. Consulte este documento que compara el hashing con los árboles de búsqueda binarios autoequilibrados y la lista de omisión, y muestra que el hashing funciona mejor.

Hashing no admite operaciones como la búsqueda de prefijos. La búsqueda de prefijos es algo en lo que un usuario escribe un prefijo y su diccionario muestra todas las palabras que comienzan con ese prefijo. Hashing tampoco admite la impresión eficiente de todas las palabras en el diccionario en orden alfabético y la búsqueda del vecino más cercano.

Si queremos ambas operaciones, buscar y buscar prefijos, Trie es adecuado. Con Trie, podemos admitir todas las operaciones como insertar, buscar, eliminar en tiempo O(n), donde n es la longitud de la palabra que se procesará. Otra ventaja de Trie es que podemos imprimir todas las palabras en orden alfabético, lo que no es posible con hash.

La desventaja de Trie es que requiere mucho espacio. Si el espacio es una preocupación, entonces se puede preferir el Árbol de búsqueda ternario . En el árbol de búsqueda ternario, la complejidad temporal de la operación de búsqueda es O(h), donde h es la altura del árbol. Los árboles de búsqueda ternarios también admiten otras operaciones compatibles con Trie, como la búsqueda de prefijos, la impresión por orden alfabético y la búsqueda del vecino más cercano.

Si queremos admitir sugerencias, como Google muestra » ¿Quiso decir …», entonces necesitamos encontrar la palabra más cercana en el diccionario. La palabra más cercana se puede definir como la palabra que se puede obtener con un número mínimo de transformaciones de caracteres (agregar, eliminar, reemplazar). Una forma ingenua es tomar la palabra dada y generar todas las palabras que están a 1 distancia (1 editar o 1 eliminar o 1 reemplazar) y buscarlas una por una en el diccionario. Si no encuentra nada, busque todas las palabras que estén a 2 de distancia y así sucesivamente. Hay muchos algoritmos complejos para esto. Según la página wiki , el algoritmo más exitoso hasta la fecha es el algoritmo de corrección ortográfica basado en Windows de Andrew Golding y Dan Roth.

Vea esto para una implementación simple del corrector ortográfico.

Este artículo ha sido compilado por Piyush . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.