¿Cómo se implementa un "¿Quiso decir"?[duplicar]

Question

Posible duplicado:
¿Cómo se dice en Google "¿Quisiste decir?" ¿Funciona el algoritmo?

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

Answer 1

En realidad, lo que hace Google no es trivial y, al principio, también contraintuitivo.No hacen nada parecido a comparar con un diccionario, sino que utilizan estadísticas para identificar consultas "similares" que arrojaron más resultados que su consulta; por supuesto, se desconoce el algoritmo exacto.

Hay diferentes subproblemas que resolver aquí, como base fundamental para todas las estadísticas relacionadas con el procesamiento del lenguaje natural, hay un libro que debe tener: Fundación del procesamiento estadístico del lenguaje natural.

Concretamente para resolver el problema de similitud palabra/consulta he tenido buenos resultados con el uso Editar distancia, una medida matemática de similitud de cadenas que funciona sorprendentemente bien.Solía ​​​​usar Levenshtein, pero vale la pena investigar los demás.

Soundex, en mi experiencia, es una mierda.

En realidad, almacenar y buscar de manera eficiente en un gran diccionario de palabras mal escritas y tener una recuperación en menos de un segundo tampoco es trivial; su mejor opción es utilizar los motores de recuperación e indexación de texto completo existentes (es decir,no la de su base de datos), de los cuales Lucena Actualmente es uno de los mejores y, casualmente, está adaptado a muchas plataformas.

Answer 2

El Dr. Norvig de Google ha explicado cómo funciona;incluso ofrece una implementación de Python de 20 líneas:

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

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

El Dr. Norvig también analiza el "¿quiso decir?" en esta excelente charla.El Dr. Norvig es jefe de investigación en Google: cuando se le preguntó cómo se implementa "quiso decir", su respuesta es autoritario.

Entonces se trata de revisión ortográfica, presumiblemente con un diccionario dinámico creado a partir de otras búsquedas o incluso frases reales de Internet y demás.Pero eso es todavía corrección ortográfica.

¡SOUNDEX y otras conjeturas no entran, gente!

Answer 3

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

Answer 4

Me sorprendió gratamente que alguien me preguntara cómo crear un sistema de sugerencia ortográfica de última generación para 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 de dominio público sobre el tema.

Como se mencionó en una publicación anterior, Google (y Microsoft y Yahoo!) no utilizan 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 magnitud del problema, pero también porque no está claro que las personas puedan identificar correctamente cuándo y si una consulta está mal escrita.

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

Este sencillo algoritmo funcionará muy bien para muchos tipos de consultas.Si desea llevarlo al siguiente nivel, le sugiero que lea el artículo de Microsoft Research sobre ese tema.Puedes encontrarlo aquí

El documento tiene una excelente introducción, pero después deberá tener conocimientos de conceptos como el modelo oculto de Markov.

Answer 5

Yo sugeriría mirar SONIDO para encontrar palabras similares en su base de datos.

También puede acceder al diccionario propio de Google utilizando el Solicitud de sugerencia de ortografía de la API de Google.

Answer 6

Quizás quieras ver el libro de Peter Norvig "Cómo escribir un corrector ortográfico" artículo.

Answer 7

Creo que Google registra todas las consultas e identifica cuando alguien hace una corrección ortográfica.Esta corrección puede entonces sugerirse cuando otros hagan la misma primera consulta.Esto funcionará para cualquier idioma, de hecho, cualquier cadena de caracteres.

Answer 8

http://en.wikipedia.org/wiki/N-gram#Google_use_of_N-gram

Answer 9

Creo que esto depende del tamaño de su sitio web.En nuestra intranet local, que utilizan aproximadamente 500 miembros del personal, simplemente miro las frases de búsqueda que arrojaron cero resultados e ingreso esa frase de búsqueda con la nueva frase de búsqueda sugerida en una tabla SQL.

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

Quizás también quieras ver mi respuesta a una pregunta similar:

• ¿"Publicaciones similares" como funcionalidad usando MS SQL Server?

Answer 10

Si tiene traducciones específicas de la industria, probablemente necesitará un diccionario de sinónimos.Por ejemplo, trabajé en la industria de la joyería y había abreviaturas en nuestras descripciones, como kt - quilates, rd - redondo, cwt - peso en quilates...Endeca (el motor de búsqueda de ese trabajo) tiene un diccionario de sinónimos que traducirá los errores ortográficos comunes, pero requiere intervención manual.

Answer 11

lo hago con Lucena's Corrector ortográfico.

Answer 12

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

Consulte también la indexación de texto completo, la sintaxis es diferente de la lógica de Google, pero es muy rápida y puede manejar elementos de lenguaje similares.

Answer 13

Soundex y "Derivación de Porter" (soundex es trivial, no estoy seguro acerca de la derivación de Porter).

Answer 14

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

Hay una gema de rubí para ello, 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 comprobar 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:corazón Posible corrección para wil:Voluntad

Answer 15

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

Answer 16

Podrías usar ngram para la comparación: http://en.wikipedia.org/wiki/N-gram

Usando el módulo ngram de Python: 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"   

Answer 17

¿Por qué no utilizar el de Google que quiso decir en su código? Para saber cómo, consulte aquíhttp://narenonit.blogspot.com/2012/08/trick-for-using-googles-did-you-mean.html