¿Cuáles son algunos algoritmos de corrección ortográfica que usan los motores de búsqueda? Por ejemplo, cuando utilicé Google para buscar “imágenes de Google”, me preguntó: “¿Quiso decir: imágenes de Google?”.

El blog de Peter Norvig ofrece una buena introducción a los algoritmos de corrección de hechizos ( http://norvig.com/spell-correct… .). Para la corrección ortográfica, los algoritmos de edición de distancia ( http://en.wikipedia.org/wiki/Edi …) son más populares. Puede usar proyectos SecondString ( http: //secondstring.sourceforge …) y simétricos ( http://sourceforge.net/projects/ …) si desea intentar editar algoritmos de distancia para la corrección de errores tipográficos. Lucene admite algoritmos de distancia de edición ( http://wiki.apache.org/solr/Func …). Aparte de eso, puede usar el índice de corrección ortográfica ngrams para la corrección ortográfica en lucene ( http://wiki.apache.org/lucene-ja …). Consulte también el tutorial de corrección ortográfica de lingpipe ( http://alias-i.com/lingpipe/demo …) y el wiki de solr para la corrección ortográfica ( http://wiki.apache.org/solr/Spel …) Lingpipe usa el modelo de lenguaje para corrección ortográfica.

Según Peter Norvig [1], Google usa un modelo de lenguaje para encontrar palabras clave probables y un modelo de error para encontrar errores probables, y los combina para sugerir la mejor alternativa. El ingrediente más importante son los datos para construir estos modelos, de los cuales Google tiene muchos.
Consulte las semanas 1 y 2 del gran curso de PNL de Stanford [2] para obtener una perspectiva más amplia sobre el corrector ortográfico.

[1] http://norvig.com/spell-correct… .
[2] https://class.coursera.org/nlp/l …

Parece que Lingpipe tiene una implementación agradable y cercana al corrector ortográfico de última generación ( http://alias-i.com/lingpipe/demo …).
Básicamente, utilizan modelos de lenguaje para medir qué tan probable es la cadena y el espacio de búsqueda para la búsqueda en la modificación más probable (errores) de la cadena original (modelo de probabilidad de error).
Así que, básicamente, cambiar z a s en “mouze” es más probable que z a p debido a la distancia del teclado y la probabilidad del mouse mucho más grande que “mouze” ya que ocurre en copra con mucha frecuencia.

En realidad, hay dos enfoques que conozco:
1. Modificación de palabra a palabra, es el corrector ortográfico predeterminado SOLR / LUCENE. No puede solucionar el problema de tokenización y los errores dependientes del contexto.
2. Modificación de cadena a cadena, es lo que se utiliza en los principales motores de búsqueda.

He estado experimentando con diferentes enfoques para resolver este problema. Al final, implementó dos sistemas diferentes. Uno se basa en este documento (Página en ronnblom.net) (El documento tiene varios problemas, tanto en pseudocódigo como en otros lugares, solo un aviso para que no pierdas mucho tiempo tratando de descubrir por qué no no funciona como se explica), y otro basado en la idea central de Norvig.

El primero se basa en un índice que se construye de manera que puede usar operaciones simples de conteo de bits (pop) en máscaras combinadas con XOR para determinar la posible distancia entre dos valores y los niveles de ramificación a ohter del árbol respectivamente. Las máscaras de bits en sí mismas se basan en características, y las características se extraen de cadenas de entrada basadas en el código ASCII de caracteres y el recuento de ocurrencias. Es bastante trivial. Larga historia corta, esto funciona extremadamente bien. En la práctica, se omite el 95-98% de los nodos del árbol, pero aún puede ser mucho si necesita ejecutar, por ejemplo, docenas o cientos de consultas para la reescritura de consultas. Para un índice de aproximadamente 5 millones de cadenas (secuencias de ngram lo que sea), toma aproximadamente 0.2s para una distancia de edición máxima = 2. También toma alrededor de 10 segundos construir dicho índice. No está nada mal, especialmente si desea usarlo, por ejemplo, para búsquedas en el diccionario, etc. Pero para reescrituras de consultas, donde potencialmente necesita ejecutar cientos de consultas para determinar una elección casi óptima de secuencias de ngram, necesita hacerlo mejor que eso.

El otro tipo de índice se basa en la idea de ediciones de Norvig, donde el índice fuera de línea se construye calculando todos los tokens posibles dentro de una distancia de edición máxima eliminando solo caracteres (similar a la idea de FAROO). Funciona con hashes, sin palabras. Por cada error ortográfico posible, emite (hash (error ortográfico), id de secuencia de ngram). El índice es bastante grande (exponencialmente más grande a medida que avanza la distancia máxima = 2, aunque en la práctica 2 es lo suficientemente bueno), y toma aproximadamente 8 veces más tiempo que el algoritmo de árbol mencionado anteriormente para construir. Sin embargo, una vez que se construye, toma de 20 a 120 microsegundos / consulta, según la distancia máxima de edición, para el mismo índice. Vea aquí cómo funciona. Desde la cadena de entrada, identifique todas las cadenas dentro de una distancia de edición específica de ella, basándose solo en eliminaciones. (así es como la cadena de consulta se expande aún más). Requiere filtros de floración, listas de omisión y otras estructuras de datos de soporte para evitar búsquedas de memoria / disco, pero funciona muy bien.
Esto hace posible construir un sistema de reescritura de consultas, incluso si necesita 500-800 consultas y su presupuesto es de 0.1 segundos.

Hay muchos documentos sobre el tema, pero la mayoría de ellos realmente no hablan de detalles (aunque uno de algunos Googlers se aventura en el tema aquí y allá).

Otro algoritmo útil que se puede usar para este propósito es el “Autómata de estado finito acíclico mínimo” o MA-FSA que se describe aquí: Construcción incremental de autómatas de estado finito acíclico mínimo

Tiene implementaciones en
Ir: smartystreets / mafsa
y Java: zunama / MA-FSA

Tiene la ventaja de ser almacenable en su forma minimizada, una vez que se construye la estructura de árbol.

No sé sobre Algoritmo, pero podemos resolver este problema usando un paquete de Python con el nombre TextBlob TextBlob: procesamiento de texto simplificado

Este código simple es suficiente para convertir las palabras mal escritas en palabras correctas.
Guión:
desde textblob import TextBlob

# Función para obtener la ortografía correcta
def spell_check (texto):
b = TextBlob (texto)
return b.correct ()

text = “¡Tengo una buena ortografía!”
print spell_check (texto)

Salida:
Tengo buena ortografía!

Un mejor enfoque para la corrección ortográfica (o inferir la intención del usuario) es rastrear todas las consultas en una sesión y relacionar las consultas con las consultas pasadas (temporalmente).

Por ejemplo, si entro:
koara
qora
koara, y finalmente
quora

entonces el motor de búsqueda puede inferir que los primeros 3 son errores ortográficos de “quora”.

Además, consulte BK-Trees para obtener un enfoque diferente y razonablemente rápido para corregir la ortografía, así como también devolver variantes cercanas de palabras clave