algorithm - para - ¿Qué algoritmo da sugerencias en un corrector ortográfico?
corrector ortográfico android (5)
Algoritmo
- Tome una palabra mal escrita como entrada.
- Guarde la lista de palabras en inglés junto con sus frecuencias en un archivo de texto.
- Inserte todas las palabras disponibles en inglés (almacenadas en el archivo de texto) junto con sus frecuencias (medida de la frecuencia con que se usa una palabra en inglés) en un árbol de búsqueda ternaria.
- Ahora recorra el árbol de búsqueda ternario -
- Para cada palabra encontrada en el árbol de búsqueda ternario, calcule su distancia Levensthein a partir de la palabra mal escrita.
- Si Levensthein Distance <= 3, almacene la palabra en una cola de prioridad.
- Si dos palabras tienen la misma distancia de edición, la que tiene una frecuencia más alta es más gruesa. Imprima los 10 elementos principales de Priority Queue.
Mejoramiento
- Puede eleminar las palabras en el subárbol del nodo actual si la distancia de edición de la subcadena de la palabra de entrada de la palabra actual es mayor que la 3. Puede encontrar la explicación más detallada y el código fuente en el proyecto github .
¿Qué algoritmo se usa típicamente al implementar un corrector ortográfico que se acompaña con sugerencias de palabras?
Al principio, pensé que podría tener sentido comprobar cada nueva palabra escrita (si no se encuentra en el diccionario) frente a su distancia de Levenshtein de cada otra palabra en el diccionario y devolver los mejores resultados. Sin embargo, parece que sería muy ineficiente, tener que evaluar todo el diccionario repetidamente.
¿Cómo se hace esto típicamente?
El corrector ortográfico es muy fácil de implementar, como en el programa de hechizos de Unix. El código fuente está disponible en público. La corrección puede estar involucrada, una técnica es hacer ediciones y verificar nuevamente si esta nueva palabra está en el diccionario. Estas nuevas ediciones se pueden agrupar y mostrar al usuario.
El sistema Unix usa un programa escrito por Mc IllRoy. Una forma alternativa es usar un Trie que puede ser útil en el caso de archivos de gran tamaño.
El enfoque de Unix necesita muy poco espacio para un gran diccionario, ya que utiliza el algoritmo hash de dispersión.
Hay un buen ensayo de Peter Norvig sobre cómo implementar un corrector ortográfico. Básicamente es un enfoque de fuerza bruta que intenta cadenas candidatas con una distancia de edición determinada. ( Here hay algunos consejos sobre cómo puede mejorar el rendimiento del corrector ortográfico usando un filtro Bloom y un hash de candidato más rápido ).
Los requisitos para un corrector ortográfico son más débiles. Solo tiene que descubrir que una palabra no está en el diccionario. Puede usar un Filtro Bloom para construir un corrector ortográfico que consuma menos memoria. Una versión antigua está descrita en Programming Pearls por Jon Bentley usando 64kb para un diccionario de inglés.
Un BK-Tree es un enfoque alternativo. Un buen artículo está here .
La distancia de Levenshstein no es exactamente la distancia de edición correcta para un corrector ortográfico. Solo conoce inserción, eliminación y sustitución. Falta la transposición y produce 2 para una transposición de 1 carácter (es 1 eliminación y 1 inserción). La distancia Damerau-Levenshtein es la distancia de edición correcta.
No necesita saber la distancia exacta de edición para cada palabra en el diccionario. Puede detener el algoritmo después de alcanzar un valor límite y excluir la palabra. Esto le ahorrará mucho tiempo de computación.
Un enfoque para generar sugerencias que he utilizado con éxito pero que nunca se ha descrito en ninguna parte es precomputar sugerencias (al compilar el diccionario) mediante el uso de funciones hash "incorrectas".
La idea es mirar los tipos de errores ortográficos que las personas hacen, y diseñar funciones hash que asignarían una ortografía incorrecta al mismo cubo que la ortografía correcta.
Por ejemplo, un error común es usar la vocal incorrecta, como definate en lugar de definite . Así que diseñas una función hash que trata todas las vocales como la misma letra. Una manera fácil de hacerlo es primero "normalizar" la palabra de entrada y luego colocar el resultado normalizado a través de una función hash regular. En este ejemplo, la función de normalización puede soltar todas las vocales, por lo que definite convierte en dfnt . La palabra "normalizada" se codifica con una función hash típica.
Inserta todas las palabras de tu diccionario en un índice auxiliar (tabla hash) usando esta función hash especial. Las cubetas de esta tabla tendrán listas de colisiones largas porque la función hash es "mala", pero esas listas de colisiones son esencialmente sugerencias precomputadas.
Ahora, cuando encuentra una palabra mal escrita, busca las listas de colisiones para el cubo al que se asigna el error ortográfico en los índices auxiliares. Ta da: ¡tienes una lista de sugerencias! Todo lo que tienes que hacer es clasificar las palabras en él.
En la práctica, necesitará algunos índices auxiliares con otras funciones hash para manejar otros tipos de errores, como letras transpuestas, letras simples o dobles e incluso una versión simplista de Soundex para detectar errores ortográficos fonéticos. En la práctica, encontré que los de pronunciación simplista iban un largo camino y esencialmente obsoletos algunos de los diseñados para encontrar errores tipográficos triviales.
Así que ahora busca errores ortográficos en cada uno de los índices auxiliares y concatenan las listas de colisiones antes de clasificarlos.
Recuerde que las listas de colisiones contienen solo palabras que están en el diccionario. Con los enfoques que intentan generar deletreos alternativos (como en el artículo de Peter Norvig), puede obtener (decenas) de miles de candidatos que primero tiene que filtrar en contra del diccionario. Con el enfoque precalculado, obtienes quizás un par de cientos de candidatos, y sabes que están escritos correctamente, así que puedes saltar directamente al ranking.
Actualización : desde entonces he encontrado una descripción de algoritmo que es similar a esto, la búsqueda distribuida de FAROO . Esta sigue siendo una búsqueda limitada de edición de distancia, pero es muy rápida porque el paso de cálculo previo funciona como mi idea de "malas funciones hash". FAROO solo usa un concepto limitado de una mala función hash.