¿Cómo implementas un “Did you mean”?

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

Supongamos que ya tiene un sistema de búsqueda en su sitio web. ¿Cómo se puede implementar el “¿Quiso decir: ” como lo hace Google en algunas consultas de búsqueda ?

En realidad, lo que Google hace no es muy trivial y, al principio, contra-intuitivo. No hacen nada como verificar contra un diccionario, sino que utilizan las estadísticas para identificar consultas “similares” que arrojaron más resultados que su consulta; por supuesto, el algoritmo exacto no se conoce.

Aquí hay diferentes subproblemas que resolver, como base fundamental para todas las estadísticas de Procesamiento del Lenguaje Natural relacionadas hay un libro que debe tener: Fundación del Procesamiento del Lenguaje Natural Estadístico .

Concretamente para resolver el problema de la similitud entre palabras y consultas, he obtenido buenos resultados al utilizar Edit Distance , una medida matemática de similitud de cadenas que funciona sorprendentemente bien. Solía ​​usar Levenshtein, pero los otros valdrían la pena investigar.

Soundex – en mi experiencia – es una mierda.

En realidad, almacenar y buscar de manera eficiente un gran diccionario de palabras mal escritas y tener una recuperación secundaria no es trivial, su mejor opción es hacer uso de los motores existentes de indexación y recuperación (es decir, no de su base de datos), de los cuales Lucene es actualmente uno de los mejores y coincidentemente portado a muchas plataformas.

El Dr. Norvig de Google ha explicado cómo funciona; incluso le da una implementación de Python en línea de 20 años:

http://googlesystem.blogspot.com/2007/04/simplified-version-of-googles-spell.html

http://www.norvig.com/spell-correct.html

El Dr. Norvig también discute el “¿quisiste decir?” En esta excelente charla . El Dr. Norvig es el jefe de investigación en Google: cuando se le pregunta cómo se implementó “quise decir”, su respuesta es autoritaria .

Por lo tanto, su revisión ortográfica, presumiblemente con una comstackción dinámica del diccionario a partir de otras búsquedas o incluso frases de Internet reales y cosas por el estilo. Pero eso sigue siendo la revisión ortográfica .

¡SOUNDEX y otras conjeturas no miran, gente!

Consulte este artículo en la wikipedia sobre la distancia Levenshtein. Asegúrese de echar un buen vistazo a posibles mejoras.

Me sorprendió gratamente que alguien me haya preguntado cómo crear un sistema de sugerencia de ortografía de última generación para los motores de búsqueda. He estado trabajando en este tema durante más de un año para una empresa de motores de búsqueda y puedo señalar información sobre el dominio público sobre el tema.

Como se mencionó en una publicación anterior, Google (y Microsoft y Yahoo!) no usan ningún diccionario predefinido ni emplean hordas de lingüistas que reflexionan sobre los posibles errores ortográficos de las consultas. Eso sería imposible debido a la escala del problema, pero también porque no está claro que las personas puedan identificar correctamente cuándo y cuándo una consulta está mal escrita.

En cambio, existe un principio simple y bastante efectivo que también es válido para todos los idiomas europeos. Obtenga todas las consultas únicas en sus registros de búsqueda, calcule la distancia de edición entre todos los pares de consultas, suponiendo que la consulta de referencia es la que tiene el recuento más alto.

Este algoritmo simple funcionará de maravilla para muchos tipos de consultas. Si desea llevarlo al siguiente nivel, le sugiero que lea el documento de Microsoft Research sobre ese tema. Puedes encontrarlo aquí

El documento tiene una gran introducción, pero luego deberá conocer conceptos como Hidden Markov Model.

Sugeriría mirar SOUNDEX para encontrar palabras similares en su base de datos.

También puede acceder al diccionario propio de google utilizando la solicitud de sugerencia ortográfica de la API de Google .

Es posible que desee consultar el artículo ” Cómo escribir un corrector ortográfico ” de Peter Norvig.

Creo que Google registra todas las consultas e identifica cuándo alguien realiza una corrección ortográfica. Esta corrección puede ser sugerida cuando otros proveen la misma primera consulta. Esto funcionará para cualquier idioma, de hecho, cualquier cadena de caracteres.

Creo que esto depende de cuán grande sea tu sitio web. En nuestra Intranet local que es utilizada por aproximadamente 500 miembros del personal, simplemente miro las frases de búsqueda que arrojaron cero resultados e ingresé esa frase de búsqueda con la nueva frase de búsqueda sugerida en una tabla SQL.

Yo invoco esa tabla si no se han devuelto resultados de búsqueda, sin embargo, esto solo funciona si el sitio es relativamente pequeño y solo lo hago para frases de búsqueda que son las más comunes.

También es posible que desee ver mi respuesta a una pregunta similar:

  • “Publicaciones similares” como funcionalidad usando MS SQL Server?

Si tiene traducciones específicas de la industria, es probable que necesite un diccionario de sinónimos. Por ejemplo, trabajé en la industria de la joyería y había abreviaturas en nuestras descripciones como kt – karat, rd – round, cwt – quilate weight … Endeca (el motor de búsqueda en ese trabajo) tiene un tesauro que se traducirá de común errores ortográficos, pero requiere una intervención manual.

Lo hago con el corrector ortográfico de Lucene .

Soundex es bueno para las coincidencias fonéticas, pero funciona mejor con los nombres de las personas (fue desarrollado originalmente para los datos del censo)

También consulte Indización de texto completo, la syntax es diferente de la lógica de Google, pero es muy rápida y puede tratar con elementos de lenguaje similares.

Soundex y “Porter stemming” (soundex es trivial, no estoy seguro acerca de porter stemming).

Hay algo llamado aspell que podría ayudar: http://blog.evanweaver.com/files/doc/fauna/raspell/classes/Aspell.html

Hay una joya de Ruby, pero no sé cómo hablar con ella desde python http://blog.evanweaver.com/files/doc/fauna/raspell/files/README.html

Aquí hay una cita de la implementación de ruby

Uso

Aspell te permite consultar palabras y sugerir correcciones. Por ejemplo:

  string = "my haert wil go on" string.gsub(/[\w\']+/) do |word| if !speller.check(word) # word is wrong puts "Possible correction for #{word}:" puts speller.suggest(word).first end end 

Esto produce:

Posible corrección para Haert: heart Posible corrección para wil: Will

Implementar la corrección ortográfica para los motores de búsqueda de una manera efectiva no es trivial (no se puede calcular la distancia de edición / levenshtein a cada palabra posible). Una solución basada en índices de k-gram se describe en Introducción a la recuperación de información (texto completo disponible en línea).

U podría usar ngram para la comparación: http://en.wikipedia.org/wiki/N-gram

Usando el módulo python ngram: http://packages.python.org/ngram/index.html

 import ngram G2 = ngram.NGram([ "iis7 configure ftp 7.5", "ubunto configre 8.5", "mac configure ftp"]) print "String", "\t", "Similarity" for i in G2.search("iis7 configurftp 7.5", threshold=0.1): print i[1], "\t", i[0] 

Obtienes:

 >>> String Similarity 0.76 "iis7 configure ftp 7.5" 0.24 "mac configure ftp" 0.19 "ubunto configre 8.5" 

¿Por qué no utilizar google? ¿Qué quieres decir con tu código? Por cómo ver aquí http://narenonit.blogspot.com/2012/08/trick-for-using-googles-did-you-mean.html