¿Qué algoritmo da sugerencias en un corrector ortográfico?

114

¿Qué algoritmo se utiliza normalmente al implementar un corrector ortográfico que se acompaña de sugerencias de palabras?

Al principio pensé que podría tener sentido comparar cada nueva palabra escrita (si no se encuentra en el diccionario) con su distancia de Levenshtein de todas las demás palabras en el diccionario y devolver los mejores resultados. Sin embargo, esto parece ser muy ineficaz, tener que evaluar todo el diccionario repetidamente.

¿Cómo se hace esto normalmente?

Mitrax
fuente

Respuestas:

203

Hay un buen ensayo de Peter Norvig sobre cómo implementar un corrector ortográfico. Básicamente, es un enfoque de fuerza bruta que prueba cadenas candidatas con una distancia de edición determinada. (A continuación, se ofrecen algunos consejos sobre cómo mejorar el rendimiento del corrector ortográfico mediante un filtro Bloom y un hash candidato más rápido ).

Los requisitos para un corrector ortográfico son más débiles. Solo tienes que descubrir que una palabra no está en el diccionario. Puede utilizar un filtro Bloom para crear un corrector ortográfico que consuma menos memoria. Una versión antigua se describe 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á aquí .

La distancia de Levenshstein no es exactamente la distancia de edición correcta para un corrector ortográfico. Conoce solo la inserción, la eliminación y la 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.

Thomas Jung
fuente
2
+1 para la referencia BK-Tree relativamente desconocida. Así es como lo están haciendo empresas como Google, que trabajan con una cantidad de datos del mundo real [TM].
NoozNooz42
2
Hay una explicación mucho mejor de BK-Trees aquí .
Ian Boyd
17

Un enfoque para generar sugerencias que he usado con éxito pero que nunca he visto descrito en ninguna parte es calcular previamente las sugerencias (al construir el diccionario) usando funciones hash "malas".

La idea es observar los tipos de errores ortográficos que cometen las personas y diseñar funciones hash que asignarían una ortografía incorrecta al mismo grupo que su ortografía correcta.

Por ejemplo, un error común es usar la vocal incorrecta, como definir en lugar de definido . Así que diseña una función hash que trata todas las vocales como la misma letra. Una forma fácil de hacerlo es primero "normalizar" la palabra de entrada y luego poner el resultado normalizado a través de una función hash regular. En este ejemplo, la función de normalización podría eliminar todas las vocales, por lo que se definiteconvierte en dfnt. La palabra "normalizada" se codifica con una función hash típica.

Inserte todas las palabras del diccionario en un índice auxiliar (tabla hash) usando esta función hash especial. Los depósitos de esta tabla tendrán listas de colisiones más largas porque la función hash es "mala", pero esas listas de colisiones son esencialmente sugerencias precalculadas.

Ahora, cuando encuentre una palabra mal escrita, busque las listas de colisiones para el depósito 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 / dobles e incluso uno simplista similar a Soundex para detectar errores ortográficos fonéticos. En la práctica, encontré que la pronunciación simplista es muy útil y esencialmente obsoleta algunas de las diseñadas para encontrar errores tipográficos triviales.

Así que ahora busca errores ortográficos en cada uno de los índices auxiliares y concatena las listas de colisiones antes de clasificar.

Recuerde que las listas de colisiones contienen solo palabras que están en el diccionario. Con enfoques que intentan generar ortografías alternativas (como en el artículo de Peter Norvig), puede obtener (decenas de) miles de candidatos que primero debe filtrar en el diccionario. Con el enfoque precalculado, puede obtener tal vez un par de cientos de candidatos, y sabe que todos están escritos correctamente, por lo que puede pasar directamente a la clasificación.

Actualización : desde entonces encontré una descripción de algoritmo similar a esta, la búsqueda distribuida de FAROO . Esta sigue siendo una búsqueda limitada a la distancia de edición, pero es muy rápida porque el paso previo al cálculo funciona como mi idea de "funciones de hash incorrectas". FAROO solo usa un concepto limitado de una mala función hash.

Adrian McCarthy
fuente
Gracias por hacer referencia al algoritmo SymSpell de Faroos. Si bien ambos algoritmos calculan previamente posibles errores tipográficos y utilizan una tabla hash para una búsqueda rápida, la principal diferencia es que SymSpell garantiza la detección de todos los posibles errores ortográficos hasta una cierta distancia de edición (en este sentido, SymSpell es equivalente al algoritmo de Peter Norvig, simplemente 3..6 órdenes de magnitud más rápido), mientras que su algoritmo utiliza un enfoque heurístico que detectará solo un subconjunto limitado de todos los errores ortográficos teóricamente posibles (por lo tanto, su costo de cálculo previo podría ser menor).
Wolf Garbe
El algoritmo SymSpell precalcula y almacena explícitamente posibles errores tipográficos, pero mi esquema de "hash incorrecto" no lo hace. Para el inglés, es trivial agregar solo un hash fonético simplista que cubra mucho terreno (por ejemplo, "terradacktle" -> "pterodactyl", que tiene una distancia de edición de 6). Por supuesto, si necesita búsquedas en varios idiomas, entonces podría ser mucho más difícil.
Adrian McCarthy
Absolutamente, al explotar el conocimiento empírico sobre posibles errores tipográficos (y restringirlos), ahorra tiempo y espacio antes del cálculo. Pero para cubrir todos los posibles errores de ortografía, SymSpell necesita calcular previamente solo una pequeña fracción de ellos. Una palabra de 5 letras tiene alrededor de 3 millones de posibles errores de ortografía dentro de una distancia máxima de edición de 3, pero con SymSpell necesita calcular previamente y almacenar solo 25 eliminaciones. Esto es importante para la búsqueda de similitudes / borrosas más allá de la corrección ortográfica donde no existe ningún conocimiento empírico.
Wolf Garbe
7

Algoritmo

  1. Tome una palabra mal escrita como entrada.
  2. Guarde la lista de palabras en inglés junto con sus frecuencias en un archivo de texto.
  3. Inserte todas las palabras en inglés disponibles (almacenadas en el archivo de texto) junto con sus frecuencias (medida de la frecuencia con la que se usa una palabra en el idioma inglés) en un árbol de búsqueda ternario.
  4. Ahora recorre el árbol de búsqueda ternario:
    • Para cada palabra encontrada en el árbol de búsqueda ternaria, calcule su distancia de Levensthein de la palabra mal escrita.
    • Si Levensthein Distance <= 3, almacena la palabra en una cola de prioridad.
    • Si dos palabras tienen la misma distancia de edición, la que tiene mayor frecuencia es mayor. Imprima los 10 elementos principales de Priority Queue.

Mejoramiento

  1. Puede eliminar las palabras en el subárbol del nodo actual si la distancia de edición de la subcadena de la palabra de entrada desde la palabra actual es mayor que 3.
    Puede encontrar la explicación más detallada y el código fuente en el proyecto github .
amarjeetAnand
fuente
Hmm, la distancia de Levenshtein de 'rallador' a 'mayor' en este caso no sería suficiente, ya que 'rallador' también es una palabra del diccionario. ;-)
Tony Brasunas
1
@TonyBrasunas, sí, tienes razón. Pero el programa en realidad devolverá una lista de 10 palabras en el caso de "rallador" como entrada y sugerirá "rallador" con una distancia de edición de 0 y también "mayor" con una distancia de edición de 1. Lo que podría ser de ayuda. ;)
amarjeetAnand
Si un candidato tiene una distancia de 2, pero es extremadamente frecuente, y otro candidato tiene una distancia de 1 pero es extremadamente raro, ¿cómo clasifica a los dos? En el enfoque anterior, el artículo raro siempre ganaría, ¿es este el resultado correcto?
Speedplane
@speedplane Sí. el raro ganará. Y creo que es el resultado correcto. Porque lo que esperamos es la palabra más cercana, según la ortografía de la palabra de entrada. Si todavía tiene dudas, piense de esta manera: suponga que hay una palabra rara que el usuario ha escrito correctamente. Ahora su distancia es 0 pero la frecuencia es muy baja. Ahora, en sugerencias, deberíamos enumerar esta palabra rara (con distancia 0) en la parte superior (porque la distancia de edición mínima gana) y otras palabras con distancia 1-2-3, a continuación.
amarjeetAnand
3

No es necesario que sepa la distancia de edición exacta 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 informático.

Petr Peller
fuente
1

El corrector ortográfico es muy fácil de implementar como en el programa de ortografía Unix. El código fuente está disponible en público. La corrección puede estar involucrada, una técnica es hacer ediciones y nuevamente verificar 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 grandes.

El método Unix necesita menos espacio para un diccionario enorme, ya que utiliza un algoritmo de dispersión hash.

Harisankar Krishna Swamy
fuente