¿Cómo funciona Google? “¿Quiso decir?” ¿Algoritmo funciona?

He estado desarrollando un sitio web interno para una herramienta de administración de carteras. Hay una gran cantidad de datos de texto, nombres de empresas, etc. He quedado realmente impresionado con la capacidad de algunos motores de búsqueda para responder rápidamente a las consultas con “¿Quiso decir: xxxx”?

Necesito poder tomar inteligentemente una consulta de usuario y responder no solo con resultados de búsqueda sin formato sino también con un “¿Querías decir?” respuesta cuando hay una respuesta alternativa muy probable, etc.

[Estoy desarrollando en ASP.NET (VB – ¡No lo hagas contra mí!)]

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

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

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

¡Busca 101!

a lo min 22:03

¡Vale la pena ver!

Básicamente, y según Douglas Merrill, antiguo CTO de Google, es así:

1) Escribes una palabra (mal escrita) en google

2) No encuentra lo que quería (no haga clic en ningún resultado)

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

4) Usted encuentra lo que quiere (hace clic en los primeros enlaces)

Este patrón se multiplicó millones de veces, muestra cuáles son los errores ortográficos más comunes y cuáles son las correcciones más “comunes”.

De esta forma, Google puede ofrecer casi instantáneamente 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.

EDITAR

@ThomasRutter: Douglas lo describe como “aprendizaje automático estadístico”.

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 que el 90% hace clic en un resultado, entonces saben que han encontrado una corrección

También pueden saber si esas son consultas “relacionadas” 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 impresionante demostración de lo que se puede hacer añadiendo la traducción automática (@ 1h 12m 47s) a la mezcla.

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

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

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

A continuación sigue una breve descripción del algoritmo. El algoritmo consiste en 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 ocurrencia. Si no tiene eso, puede usar un gran conjunto de texto en su lugar. Cuente la ocurrencia (popularidad) de cada palabra.

Paso 2. Verificación de palabras: encontrar palabras que son similares a la marcada

Similar significa que la distancia de edición es baja (típicamente 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 del algoritmo “quisiste decir”, puedes consultar el Capítulo 3 de Introducción a la recuperación de información. Está disponible en línea de forma gratuita. La 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 un poco de PNL (procesamiento de lenguaje natural).

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

Sin embargo, aparentemente solo hacen una variación de lo que decía Davide Gualano, así que definitivamente lea ese enlace. Google, por supuesto, usa todas las páginas web que conoce como corpus, por lo que su algoritmo es particularmente efectivo.

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

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

  • Decidir sobre una forma de determinar si se requiere corrección ortográfica. Estos pueden incluir resultados insuficientes, resultados que no son específicos o suficientemente precisos (de acuerdo con alguna medida), etc. Luego:

  • Use una gran cantidad 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 más cercana en función de varias medidas. El más intuitivo es personajes similares. Lo que se ha demostrado a través de la investigación y la experimentación es que dos o tres coincidencias secuencia de caracteres funcionan mejor. (bigtwigs y trigtwigs). Para mejorar aún más los resultados, pondere una puntuación más alta en un partido al principio o al final de la palabra. Por motivos de rendimiento, indexe todas estas palabras como trigtwigs o bigtwigs, de modo que cuando esté realizando una búsqueda, convierta a n-gram y busque mediante hashtable o trie.

  • Utilice heurísticas relacionadas con posibles errores de teclado en función de la ubicación del personaje. Entonces, “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 resultados peores que el uso de indexación de n-gtwigs, como se describió anteriormente.

  • En cada caso, debe seleccionar la mejor corrección de una lista. Puede ser una medida 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 la mejor coincidencia.

Usa la distancia de Levenshtein , luego crea un árbol de métricas (o un árbol delgado) para indexar palabras. Luego ejecute una consulta de 1-Nearest Neighbour, y obtendrá el resultado.

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

Asi que,

  1. Necesitas un diccionario (inglés o basado en tus datos)

  2. Genere una palabra enrejada y calcule las probabilidades para las transiciones usando su diccionario.

  3. Agregue un decodificador para calcular la distancia mínima de error usando su enrejado. Por supuesto, debe tener en cuenta las inserciones y eliminaciones al calcular las distancias. Lo divertido es que el teclado QWERTY maximiza la distancia si presionas las teclas una cerca de la otra. (Cae giraría el auto, cay se convertiría en un gato)

  4. Devuelve la palabra que tiene la distancia mínima.

  5. Luego, puede comparar eso con su base de datos de consultas y verificar si hay mejores resultados para otras coincidencias cercanas.

Esta es la mejor respuesta que encontré , el 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.

con respecto a su pregunta sobre cómo imitar el comportamiento sin tener toneladas de datos, ¿por qué no utilizar montones de datos recostackdos por google? Descargue los resultados de google sarch para la palabra mal escrita y busque “¿Quiso decir:” en el HTML?

Creo que eso se llama mashup hoy en día 🙂

Como una conjetura … podría

  1. buscar palabras
  2. si no se encuentra, use algún algoritmo para tratar de “adivinar” la palabra.

Podría ser algo de IA como la red Hopfield o la red de propagación de retorno, o alguna otra cosa que “identifique huellas dactilares”, restaurando datos rotos o correcciones ortográficas como Davide ya mencionó …

Vi algo sobre esto hace algunos años, puede haber cambiado desde entonces, pero al parecer lo iniciaron al analizar sus registros para los mismos usuarios que enviaron consultas similares en un corto espacio de tiempo, y utilizaron el aprendizaje automático basado en cómo los usuarios habían corregido sí mismos.

Sencillo. Tienen toneladas de datos. Tienen estadísticas para cada término posible, en función de la frecuencia con la que se consultan, y de las variaciones que generalmente arrojan resultados en los que los usuarios hacen clic … por lo tanto, cuando lo ven tipeado un error ortográfico frecuente para un término de búsqueda, continúan y proponen la respuesta más usual.

En realidad, si el error ortográfico es en efecto el término buscado más frecuente, el algoritmo lo tomará por el correcto.

¿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. Ver este enlace

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

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 .

  • Crea una cola de prioridad 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 para cada palabra encontrada en TST, calcule su Distancia de Levenshtein ( LD ) desde input_word
  • Si LD ≤ 3, colóquelo en una cola de prioridad.
  • Al final extrae 10 palabras de la cola de prioridad y la pantalla.

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

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

La solución óptima usa progtwigción dinámica y recursión.

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

Existe una estructura de datos específica – árbol de búsqueda ternaria – que naturalmente admite coincidencias parciales y coincidencias de vecinos cercanos.

Esta es una vieja pregunta, y me sorprende que nadie sugiriera OP utilizando Apache Solr.

Apache Solr es un motor de búsqueda de texto completo que, además de muchas otras funcionalidades, también proporciona revisión ortográfica o sugerencias de consultas. De la documentación :

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