texto ¿Cómo funcionan los correctores ortográficos?




word 2016 no corrige ortografia (5)

Necesito implementar un corrector ortográfico en C. Básicamente, necesito todas las operaciones estándar ... Necesito poder revisar la ortografía de un bloque de texto, hacer sugerencias de palabras y agregar dinámicamente nuevas palabras al índice.

Me gustaría escribir esto yo mismo, aunque realmente no sé por dónde empezar.


Dado que no sabes por dónde empezar, te sugiero usar una solución existente. Ver, por ejemplo, aspell (licencia GLPL). Si realmente tiene que implementarlo usted mismo, por favor díganos por qué.


Uno debe mirar prefijos y sufijos.

de repente = repentino + ly.

Al eliminar la de Ly, puede escaparse almacenando solo la palabra raíz.

Del mismo modo preasignar = pre + asignar.

Y cariñosamente = love + ing + ly se vuelve un poco más complejo, ya que las reglas inglesas para ing se invocan.

También existe la posibilidad de utilizar algún tipo de función hash para mapear una palabra raíz en un bit específico es un mapa de bits grande, como un método de tiempo constante para determinar si la palabra raíz está escrita correctamente.

Puede llegar a ser aún más complejo al tratar de proporcionar una lista alternativa de posibles deletreos correctos a una palabra mal escrita. Puede investigar el algoritmo soundex para obtener algunas ideas.

Aconsejaría crear prototipos con un pequeño conjunto de palabras. Haga muchas pruebas, luego amplíe. Es un problema educativo maravilloso.


El corrector ortográfico de Open Office Hunspell puede ser un buen punto de partida. Aquí está la página de inicio: Hunspell en Sourceforge


Lea sobre Tree Traversal . El concepto básico es el siguiente:

  1. Lea un archivo de diccionario en la memoria (este archivo contiene la lista completa de palabras escritas correctamente que son posibles / comunes para un idioma determinado). Puede descargar archivos de diccionarios gratuitos en línea. Un ejemplo es java.sun.com
  2. Analice este archivo de diccionario en un árbol de búsqueda para que la búsqueda de texto real sea lo más eficiente posible. No describiré todos los detalles sucios de este tipo de estructura de árbol, pero el árbol estará formado por nodos que tienen (hasta) 26 enlaces a nodos secundarios (uno para cada letra), más una bandera para indicar si o no, el nodo actual es el final de una palabra válida.
  3. Recorra todas las palabras de su documento y compruebe cada una en el árbol de búsqueda. Si llega a un nodo en el árbol donde la siguiente letra de la palabra no es un elemento secundario válido del nodo actual, la palabra no está en el diccionario. Además, si llega al final de su palabra, y el indicador de "fin de la palabra válida" no está establecido en ese nodo, la palabra no está en el diccionario.
  4. Si no se encuentra una palabra en el diccionario, informe al usuario. En esta etapa, también puede sugerir ortografías alternativas, pero eso se vuelve un poco más complicado. Tendrá que recorrer cada carácter de la palabra, sustituyendo caracteres alternativos y probando cada uno de ellos en el árbol de búsqueda. Probablemente haya algoritmos más eficientes para encontrar las palabras recomendadas, pero no sé cuáles son.

Un ejemplo realmente breve:

Diccionario:

apex apple design nombrado

Árbol: ( * indica el final de la palabra válido) actualización: Gracias a Curt Sampson por señalar que esta estructura de datos se llama Patricia Tree

A -> P -> E -> X*
\\-> P -> L -> E*
\\-> O -> I -> N -> T* -> E -> D*

Documento:

simio manzana appint

Resultados:

  • "apple" se encontrará en el árbol, por lo que se considera correcto.
  • "appint" se marcará como incorrecto. Atravesando el árbol, seguirá A -> P -> P , pero la segunda P no tiene un nodo hijo I , por lo que la búsqueda falla.
  • "mono" también fallará, ya que el nodo E en A -> P -> E no tiene el indicador de "fin de la palabra válido" establecido.

editar: para obtener más detalles sobre las sugerencias de ortografía, consulte Levenshtein Distance , que mide el menor número de cambios que se deben realizar para convertir una cadena en otra. Las mejores sugerencias serían las palabras del diccionario con la menor distancia de Levenshtein a la palabra mal escrita.


Dividir una palabra en raíz y sufijo es conocido como el "Algoritmo de Stemming de Porter". Es una buena forma de adaptar a un ditionary inglés a un memoria increíblemente pequeña.
También es útil para buscar, por lo que el "corrector ortográfico" también encontrará "revisión ortográfica" y "corrector ortográfico".





spell-checking