¿Cómo se implementan los algoritmos de autocorrección o sugerencia de escritura?

Hay varias posibilidades, pero la más común es comparar la palabra escrita con un diccionario grande, y si la palabra no se encuentra allí, encontrar las palabras más cercanas a la palabra escrita para mostrarlas como “sugerencias” – y posiblemente usar el más cercano de todos para “autocorregir”.

Esta idea de cuán “cercanas” están dos palabras entre sí es complicada. Hay toda una rama de la informática dedicada a encontrar buenas maneras de hacer esto.

¡Mira la métrica de cadena – Wikipedia – que tiene enlaces a dieciocho formas conocidas de hacer esto!

Parte del problema es que los humanos cometen errores por una variedad de razones:

• Al escribir, es fácil intercambiar dos letras, por lo que “alfabeto” podría escribirse como “alhpabet”.
• También es fácil perder una carta o agregar una extra: “alpabet” o “allphabet”.
• También puede presionar la tecla junto a la que pretendía presionar: “alohabet”.
• Es posible que la persona no sepa cómo se escribe correctamente la palabra y obtenga: “alfabet”.
• A veces una palabra está mal escrita intencionalmente (como mis errores ortográficos deliberados de “alfabeto”, arriba).
• Hay palabras como “Quora” que son válidas en contexto, pero no son palabras normales en absoluto.
• Lo peor de todo es que alguien podría usar un homónimo de la palabra que pretendía, usando “dos” en lugar de “también”, por ejemplo.
• Errores de capitalización: “Donald Trump tuvo una idea” versus “Esto triunfa sobre mi idea”.
• Incluso podrían haber deletreado la palabra 100% correctamente, pero usaron la versión incorrecta, completamente la palabra incorrecta, debido al contexto gramatical circundante. “Susan era una mujer agradable, pero solía ser malo en gramática” … usando “él” en lugar de “ella”.

Algunos correctores ortográficos tienen un diccionario pequeño, pero tienen reglas incorporadas sobre cosas como formar plurales y conjugar verbos comunes. Otros simplemente tienen un diccionario de “fuerza bruta” que tiene todas esas cosas como palabras separadas.

Todos estos errores pueden explicarse, pero no con un solo algoritmo. En los sistemas avanzados, es posible buscar rápidamente un gran cuerpo de texto para encontrar una oración completa como la que se escribió para que incluso se puedan encontrar errores gramaticales o contextuales.

Es por eso que los correctores ortográficos y gramaticales son tan falibles.

Comenzaré nuevamente, este fue mi proyecto de año prefinal y la razón para elegirlo porque estaba ansioso por conocer el funcionamiento de la predicción durante los mensajes de texto. Como mi proyecto estaba en Java, utilicé Netbean para ello.
Parte de la GUI : 3 bloques para salida y un cuadro de entrada, implementado a través del swing aquí está la imagen.

Parte lógica : el corrector ortográfico necesita algunas restricciones (3 en mi caso) para una predicción efectiva de la palabra. La clasificación de las palabras ordenadas se basa en estas restricciones.
1. Distancia de Levenshtein , longitud de la palabra correcta más cercana
2. Fonética : palabras que suenan similares pero deletrean de manera diferente.
3. diccionario propio del usuario puede consistir en palabras nativas.

Estructura de datos utilizada :
1. KMP algo para buscar, pero los resultados fueron bastante pobres, tomó 25 segundos para dar una predicción única 🙁 de la búsqueda en un diccionario de 20,000 palabras (formato .txt)
2. El mapa de hash (a diferencia del hashTable ‘value’ de ‘key’ puede ser nulo) fue mucho mejor, el resultado de búsqueda se redujo a 1 segundo por predicción :).
3. Otro concepto de Trie (árbol digital) también podría aplicarse. La implementación fue bastante compleja, por eso elegí el hashmap, pero el tiempo de búsqueda podría demorar menos de 1 segundo.

El tiempo total fue de 3 segundos para tres salidas diferentes, así que implementé Multithreading sobre ellas, no sé si hizo algún refinamiento.
Si alguien necesita su código fuente para un mayor desarrollo, envíeme un mensaje: {.

PD: desde que se adquirió el código , no puedo darle la última versión del código, pero la versión anterior sigue funcionando bien .

Se puede implementar un algoritmo simple para sugerencias de ortografía o autocompletar encontrando cadenas que estén “a un paso” de la cadena actual. Para hacerlo, simplemente busque todas las cadenas que se pueden crear 1. Sustituyendo cada carácter con cada letra del alfabeto, 2. Insertando cada letra del alfabeto en cada posición de la cadena, y 3. Eliminando cada carácter del palabra.

Una vez hecho esto, verifica las cadenas resultantes en una lista que contiene palabras válidas para el idioma que está utilizando y suelta las que no coinciden. Luego puede agregar estas palabras válidas a una cola y repetir los pasos tantas veces como sea necesario (normalmente hasta que se haya encontrado un número predeterminado de sugerencias o se haya alcanzado un umbral del número de cadenas para buscar).

Este es un algoritmo ingenuo, pero es la premisa en la que se basa la funcionalidad de sugerencia de ortografía.

Editar: no pude leer la nota debajo de la pregunta que mencionaba la funcionalidad predictiva. Eso va más allá del alcance de mi respuesta, pero lo dejaré aquí en caso de que ayude a alguien.

Mi primera idea de tal algoritmo sería usar estadísticas de ngram en palabras. Al conocer sus pocas palabras anteriores, se sabe estadística cuáles podrían ser sus próximas palabras y la distancia entre letras de lo que escribió.