Duplicar posible:
How does the Google “Did you mean?” Algorithm work?¿Cómo implementas un "Did you mean"?
Suponga que tiene un sistema de búsqueda que ya están en su sitio web. ¿Cómo se puede implementar el "¿Quería decir: <spell_checked_word>", como Google lo hace en algunos search queries?
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 sub-problemas para resolver, como una base fundamental para todas las estadísticas de procesamiento de lenguaje natural relacionadas hay un libro que debe tener: Foundation of Statistical Natural Language Processing.
Concretamente para resolver el problema de la similitud entre palabras y consultas, he obtenido buenos resultados con el uso de Edit Distance, una medida matemática de la 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 porquería.
En realidad almacenar de manera eficiente y buscando un gran diccionario de palabras mal escritas y que tiene segundos de recuperación secundaria es de nuevo no trivial, lo mejor es hacer uso de los motores de indización y recuperación de texto completo existentes (es decir, no uno de su base de datos), de que Lucene es actualmente uno de los mejores y coincidentemente portado a muchas plataformas.
Sugeriría mirar SOUNDEX para encontrar palabras similares en su base de datos.
También puede acceder al diccionario propio de google utilizando el Google API spelling suggestion request.
+1 para el enlace a la API de Google que parece ser exactamente lo que el solicitante estaba buscando, incluso si la respuesta elegida es más profunda y responde el "por qué" y el "cómo" de la implementación de Google. – dimo414
Soundex es bueno para los partidos fonéticos, pero funciona mejor con los nombres de las personas (que fue desarrollado originalmente para los datos del censo)
También puedes ver texto completo de indización, la sintaxis es diferente de la lógica de Google, pero es muy rápido y puede tratar con elementos de lenguaje similares.
una de las cosas malas de soundex es que está demasiado centrado en el inglés – Javier
Fue desarrollado para angliseñar los nombres, por lo que se supone que Smith y Schmidt coinciden. Metaphone es mejor pero tiene un problema similar. Cualquier algoritmo fonético va a depender del idioma. – Keith
Soundex y "Porter stemming" (soundex es trivial, no estoy seguro acerca de porter stemming).
La información (incluidas las implementaciones en 19 idiomas de codificación diferentes) sobre la derivación de Porter se puede encontrar en http://tartarus.org/~martin/PorterStemmer/index.html – msanders
¿Podría ampliar esto, en caso de que su enlace muera de link-rot o Delegationism desenfrenado? El ancla ya está muerta ... –
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.
Creo que esto depende de qué tan grande sea su 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.
los llamo en esa tabla si se ha devuelto sin resultados de búsqueda, sin embargo, esto sólo funciona si el sitio es relativamente pequeño y sólo lo haga por frases de búsqueda que son los más comunes.
También puede ser que desee mirar a mi respuesta a una pregunta similar:
Es posible que desee ver en el artículo de Peter Norvig "How to Write a Spelling Corrector".
perfecto, gracias! –
creo que Google registra todas las consultas e identifica cuando alguien hace 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.
Lo hacen de hecho. Esto les ayuda a aprender nuevas palabras fácilmente, tienen la ayuda de millones. –
Sí, esta es en realidad la respuesta correcta. Según el libro "In the Plex", Google busca casos en los que alguien busca algo, obtiene resultados y luego ajusta un poco sus términos de búsqueda. –
de Google Dr. Norvig ha esbozado cómo funciona; Incluso se da una línea de 20 Ish aplicación Python:
http://googlesystem.blogspot.com/2007/04/simplified-version-of-googles-spell.html
http://www.norvig.com/spell-correct.html
Dr. Norvig también discute el "Quiso decir" en this excellent talk. El Dr. Norvig es jefe de investigación en Google: cuando se le pregunta cómo se implementó "quiso decir", su respuesta es autoritiva.
Por lo que su corrección ortográfica, presumiblemente con un diccionario dinámico construir a partir de otras búsquedas de Internet o incluso frases reales y tal. Pero eso sigue siendo deletreo ortográfico.
SOUNDEX y otras conjeturas no obtienen un vistazo, la gente!
El Dr. Norvig proporcionó un ejemplo de juguete del concepto; no es lo suficientemente preciso como para proporcionar '¿quiso decir?' para la web.Por ejemplo: "barak" no produce una sugerencia; "barak obama" (dado que saben que "barack" ocurre a menudo con obama, y pueden inferir la corrección probable – SquareCog
no es difícil pasar de su corrector ortográfico de juguete a algo que maneje su ejemplo y que funcione bien. Lo que hay que recordar es que está mostrando un corrector ortográfico que es sutil pero significativamente diferente de un sugerente de consulta. Entrenarlo con consultas previas en lugar de texto en inglés es un buen lugar para comenzar. – jshen
Definitivamente hay algo más que solo la corrección ortográfica. Por un lado, he visto casos en los que ni lo que escribí ni el reemplazo sugerido son "palabras del diccionario". –
Hay algo que se llama aspell que podría ayudar: http://blog.evanweaver.com/files/doc/fauna/raspell/classes/Aspell.html
Hay una gema de rubíes por ella, pero no saben cómo hablar a la misma desde pitón http://blog.evanweaver.com/files/doc/fauna/raspell/files/README.html
He aquí una cita del rubí aplicación
Uso
Aspell le permite comprobar palabras y sugerir corre ctions. 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
Este salidas:
corrección posible para haert: corazón corrección posible para Wil: Will
La implementación de 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 Introduction to Information Retrieval (texto completo disponible en línea).
Lo hago con Lucene 's Spell Checker.
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 su lugar, existe un principio simple y bastante eficaz 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á muy bien para muchos tipos de consultas. Si desea llevarlo al siguiente nivel, le sugiero que lea el documento de Microsoft Research sobre ese tema. Usted puede encontrarlo here
El documento tiene una gran introducción, pero después de eso tendrá que estar bien informado con conceptos tales como el Modelo Hidden Markov.
T podría utilizar n-gramas para el comparisment: http://en.wikipedia.org/wiki/N-gram
Usando el modulo pitón n-gramas: 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]
U obtener:
>>>
String Similarity
0.76 "iis7 configure ftp 7.5"
0.24 "mac configure ftp"
0.19 "ubunto configre 8.5"
Por qué no usar Google de quisiste decir en su código . Por cómo ver aquí http://narenonit.blogspot.com/2012/08/trick-for-using-googles-did-you-mean.html
La página ya no se encuentra ...: '( –
@pek: Hace un tiempo tuve el mismo pensamiento ... ¿Has pensado en utilizar un scruber HTML y usar Google como fuente de las correcciones? –
Ver http://stackoverflow.com/questions/3763640/where-can-i-learn-more-about-the-google-search-did-you-mean-algorithm – John