¿Cómo quiere decir Google & # 8220; quiso decir? & # 8221; Algoritmo de trabajo?

https://stackoverflow.com/questions/307291

08-07-2019
|

Pregunta

He estado desarrollando un sitio web interno para una herramienta de gestión de cartera. Hay muchos datos de texto, nombres de compañías, etc. Me ha impresionado mucho la capacidad de algunos motores de búsqueda para responder rápidamente a las consultas con "Quiso decir: xxxx".

Necesito poder tomar de manera inteligente una consulta del usuario y responder no solo con resultados de búsqueda sin procesar, sino también con un "¿Quiso decir?" respuesta cuando hay una respuesta alternativa muy probable, etc.

[Estoy desarrollando en ASP.NET (VB - no esperes contra mí!)]

ACTUALIZACIÓN: OK, ¿cómo puedo imitar esto sin los millones de 'usuarios no remunerados'?

¿Genera errores tipográficos para cada término 'conocido' o 'correcto' y realiza búsquedas?
¿Algún otro método más elegante?

Solución

Aquí está la explicación directamente de la fuente (casi)

¡Busca 101!

a las 22:03 min

¡Vale la pena verlo!

Básicamente y de acuerdo con Douglas Merrill, ex CTO de Google, es así:

1) Escribe una palabra (mal escrita) en google

2) No encuentras lo que buscabas (no hagas clic en ningún resultado)

3) Te das cuenta de que escribiste mal la palabra y reescribes la palabra en el cuadro de búsqueda.

4) Encuentra lo que buscas (haces clic en los primeros enlaces)

Este patrón multiplicado millones de veces, muestra cuáles son los errores ortográficos más comunes y cuáles son los más comunes. correcciones

De esta forma, Google puede casi instantáneamente ofrecer corrección ortográfica en todos los idiomas.

También esto significa que si de la noche a la mañana todos comienzan a deletrear la noche como "noche" Google sugeriría esa palabra en su lugar.

EDIT

@ThomasRutter: Douglas lo describe como "aprendizaje automático de estadística".

Saben quién corrige la consulta, porque saben qué consulta proviene de qué usuario (usando cookies)

Si los usuarios realizan una consulta, y solo el 10% de los usuarios hacen clic en un resultado y el 90% regresa y escribe otra consulta (con la palabra corregida) y esta vez ese 90% hace clic en un resultado, entonces saben Han encontrado una corrección.

También pueden saber si están "relacionados" consultas de dos diferentes, porque tienen información de todos los enlaces que muestran.

Además, ahora están incluyendo el contexto en el corrector ortográfico, por lo que incluso pueden sugerir palabras diferentes según el contexto.

Vea esta demostración de google wave (@ 44m 06s) que muestra cómo se tiene en cuenta el contexto para corregir automáticamente la ortografía.

Aquí se explica cómo funciona el procesamiento del lenguaje natural.

Y finalmente, aquí hay una demostración impresionante de lo que se puede hacer agregando traducción automática (@ 1h 12m 47s) a la mezcla.

_{Agregué anclas de minutos y segundos a los videos para saltar directamente al contenido; si no funcionan, intente volver a cargar la página o desplazarse manualmente hasta la marca.}

Otros consejos

Encontré este artículo hace algún tiempo: Cómo escribir un corrector ortográfico , escrito por Peter Norvig (Director de Investigación de Google Inc.).

Es una lectura interesante sobre la " corrección ortográfica " tema. Los ejemplos están en Python pero es claro y simple de entender, y creo que el algoritmo puede ser fácilmente traducido a otros idiomas.

A continuación sigue una breve descripción del algoritmo. El algoritmo consta de dos pasos, preparación y verificación de palabras.

Paso 1: Preparación: configuración de la base de datos de palabras

Lo mejor es si puede usar palabras de búsqueda reales y su aparición. Si no tiene eso, puede usar un gran conjunto de texto en su lugar. Cuente la aparición (popularidad) de cada palabra.

Paso 2. Verificación de palabras: encontrar palabras similares a las marcadas

Similar significa que la distancia de edición es baja (generalmente 0-1 o 0-2). La distancia de edición es el número mínimo de inserciones / eliminaciones / cambios / intercambios necesarios para transformar una palabra en otra.

Elija la palabra más popular del paso anterior y sugiérala como una corrección (si no es la palabra misma).

Para la teoría de "quiso decir" algoritmo puede consultar el Capítulo 3 de Introducción a la recuperación de información. Está disponible en línea de forma gratuita. Sección 3.3 (página 52) responde exactamente su pregunta. Y para responder específicamente a su actualización, solo necesita un diccionario de palabras y nada más (incluidos millones de usuarios).

Hmm ... pensé que Google usaba su vasto corpus de datos (Internet) para hacer algunos PNL (procesamiento del lenguaje natural) serios.

Por ejemplo, tienen tantos datos de toda Internet que pueden contar la cantidad de veces que ocurre una secuencia de tres palabras (conocida como trigrama ). Entonces, si ven una oración como: "concierto de frugr rosa", podrían ver que tiene pocos éxitos, entonces encontrarán el concierto de rosa * más probable ". en su corpus.

Sin embargo, aparentemente solo hacen una variación de lo que Davide Gualano estaba diciendo, así que definitivamente lean ese enlace. Por supuesto, Google utiliza todas las páginas web que conoce como un corpus, por lo que su algoritmo es particularmente efectivo.

Supongo que usan una combinación de un algoritmo distancia de Levenshtein y las masas de datos que recopilan sobre las búsquedas que se ejecutan. Podrían extraer un conjunto de búsquedas que tengan la distancia de Levenshtein más corta desde la cadena de búsqueda ingresada, luego elegir la que tenga más resultados.

Normalmente, un corrector ortográfico de producción utiliza varias metodologías para proporcionar una sugerencia ortográfica. Algunos son:

Decidir una forma de determinar si se requiere corrección ortográfica. Estos pueden incluir resultados insuficientes, resultados que no son lo suficientemente específicos o precisos (según alguna medida), etc. Luego:
Utilice un gran cuerpo de texto o un diccionario, donde se sabe que todos o la mayoría están escritos correctamente. Estos se encuentran fácilmente en línea, en lugares como LingPipe . Luego, para determinar la mejor sugerencia, busque una palabra que sea la coincidencia más cercana en función de varias medidas. El más intuitivo son los personajes similares. Lo que se ha demostrado a través de la investigación y la experimentación es que las coincidencias de secuencia de dos o tres caracteres funcionan mejor. (bigrams y trigrams). Para mejorar aún más los resultados, evalúe una puntuación más alta en un partido al principio o al final de la palabra. Por razones de rendimiento, indexe todas estas palabras como trigramas o bigramas, de modo que cuando realice una búsqueda, se convierta a n-gram y busque a través de tabla hash o trie.
Utilice la heurística relacionada con posibles errores del teclado en función de la ubicación de los caracteres. De modo que "hwllo" debería ser "hola" porque 'w' está cerca de 'e'.
Use una tecla fonética (Soundex, Metaphone) para indexar las palabras y buscar posibles correcciones. En la práctica, esto normalmente arroja peores resultados que el uso de la indexación de n-gramas, como se describió anteriormente.
En cada caso, debe seleccionar la mejor corrección de una lista. Esta puede ser una métrica de distancia, como levenshtein, la métrica del teclado, etc.
Para una frase de varias palabras, solo una palabra puede estar mal escrita, en cuyo caso puede usar las palabras restantes como contexto para determinar una mejor coincidencia.

Utilice Distancia de Levenshtein , luego cree un árbol métrico (o árbol delgado) para indexar palabras. Luego ejecute una consulta de 1 vecino más cercano y obtendrá el resultado.

Google aparentemente sugiere consultas con mejores resultados, no con las que están escritas correctamente. Pero en este caso, probablemente un corrector ortográfico sería más factible. Por supuesto, podría almacenar algún valor para cada consulta, en función de alguna métrica de los buenos resultados que devuelve.

Entonces,

Necesita un diccionario (inglés o basado en sus datos)
Genere una palabra enrejada y calcule las probabilidades para las transiciones usando su diccionario.
Agregue un decodificador para calcular la distancia mínima de error usando su enrejado. Por supuesto, debe tener cuidado con las inserciones y eliminaciones al calcular distancias. Lo divertido es que el teclado QWERTY maximiza la distancia si presionas las teclas cerca una de la otra (cae cae el auto, cay gira el gato)
Devuelve la palabra que tiene la distancia mínima.
Entonces podría compararlo con su base de datos de consultas y verificar si hay mejores resultados para otras coincidencias cercanas.

Aquí está la mejor respuesta que encontré , corrector ortográfico implementado y descrito por el Director de Investigación de Google Peter Norvig.

Si desea leer más sobre la teoría detrás de esto, puede leer el capítulo de su libro .

La idea de este algoritmo se basa en el aprendizaje automático estadístico.

Como una suposición ... podría

búsqueda de palabras
si no se encuentra, utilice algún algoritmo para intentar "adivinar" la palabra.

Podría ser algo de AI como la red Hopfield o la red de propagación hacia atrás, o algo más "identificar huellas dactilares", restaurar datos rotos o correcciones ortográficas como Davide ya mencionó ...

Vi algo sobre esto hace unos años, por lo que puede haber cambiado desde entonces, pero aparentemente lo comenzaron analizando sus registros para los mismos usuarios enviando consultas muy similares en un corto espacio de tiempo, y utilizaron el aprendizaje automático basado en cómo los usuarios se habían corregido a sí mismos.

Simple. Tienen toneladas de datos. Tienen estadísticas para cada término posible, en función de la frecuencia con la que se consulta, y qué variaciones de la misma generalmente producen resultados en los que los usuarios hacen clic ... así que, cuando ven que escribiste un error ortográfico frecuente para un término de búsqueda, continúan y proponen la respuesta más habitual.

En realidad, si la falta de ortografía es el término buscado más frecuente, el algoritmo lo tomará como el correcto.

con respecto a su pregunta sobre cómo imitar el comportamiento sin tener toneladas de datos, ¿por qué no usar toneladas de datos recopilados por google? Descargue los resultados de google sarch para la palabra mal escrita y busque " significa: " en el HTML.

Creo que hoy en día se llama mashup :-)

¿Quieres decir corrector ortográfico? Si se trata de un corrector ortográfico en lugar de una frase completa, entonces tengo un enlace sobre la revisión ortográfica donde se desarrolla el algoritmo en Python. Consulte este enlace

Mientras tanto, también estoy trabajando en un proyecto que incluye la búsqueda de bases de datos usando texto. Supongo que esto resolvería tu problema

Esta es una vieja pregunta, y me sorprende que nadie sugirió el OP usando Apache Solr.

Apache Solr es un motor de búsqueda de texto completo que, además de muchas otras funciones, también proporciona correcciones ortográficas o sugerencias de consulta. De la documentación :

Por defecto, los correctores ortográficos de Lucene ordenan las sugerencias primero por puntuación del cálculo de distancia de cuerda y segundo por la frecuencia (si está disponible) de la sugerencia en el índice.

Además de las respuestas anteriores, en caso de que desee implementar algo usted mismo rápidamente, aquí hay una sugerencia:

Algoritmo

Puede encontrar la implementación y la documentación detallada de este algoritmo en GitHub .

Crear una cola prioritaria con un comparador.
Cree un árbol de búsqueda de Ternay e inserte todas las palabras en inglés (de la publicación de Norvig ) junto con sus frecuencias .
Comience a recorrer el TST y, por cada palabra encontrada en el TST, calcule su distancia de Levenshtein ( LD ) desde input_word
Si LD & # 8804; 3 luego póngalo en una cola de prioridad.
Por fin extraer 10 palabras de la cola de prioridad y mostrar.

Existe una estructura de datos específica, árbol de búsqueda ternario , que naturalmente admite coincidencias parciales y coincidencias cercanas al vecino.

La forma más fácil de resolverlo es mediante la programación dinámica de Google.

Es un algoritmo que se ha tomado prestado de Recuperación de información y se usa mucho en la bioinformática moderna para ver cuán similares son dos secuencias de genes.

La solución óptima utiliza programación dinámica y recursividad.

Este es un problema muy resuelto con muchas soluciones. Simplemente busque en Google hasta que encuentre algún código fuente abierto.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow