Comment mettre en œuvre un « Vouliez-vous dire » ?[dupliquer]

https://stackoverflow.com/questions/41424

09-06-2019
|

Question

Doublon possible :
Comment le Google "vouliez-vous dire?" Le fonctionnement de l'algorithme?

Supposons que vous disposiez déjà d’un système de recherche sur votre site Web.Comment pouvez-vous implémenter le « Voulez-vous dire :<spell_checked_word>" comme le fait Google dans certains Requêtes de recherche?

La solution

En fait, ce que fait Google est tout à fait non trivial et, à première vue, contre-intuitif.Ils ne font rien comme vérifier par rapport à un dictionnaire, mais utilisent plutôt des statistiques pour identifier les requêtes "similaires" qui ont renvoyé plus de résultats que votre requête, l'algorithme exact n'est bien sûr pas connu.

Il y a différents sous-problèmes à résoudre ici, comme base fondamentale pour toutes les statistiques liées au traitement du langage naturel, il existe un livre indispensable : Fondements du traitement statistique du langage naturel.

Concrètement, pour résoudre le problème de similarité mot/requête, j'ai obtenu de bons résultats en utilisant Modifier la distance, une mesure mathématique de la similarité des chaînes qui fonctionne étonnamment bien.J'avais l'habitude d'utiliser Levenshtein mais les autres valent peut-être la peine d'être étudiés.

Soundex - d'après mon expérience - est de la merde.

En fait, stocker et rechercher efficacement un grand dictionnaire de mots mal orthographiés et avoir une récupération en moins d'une seconde n'est pas encore trivial, le mieux est d'utiliser les moteurs d'indexation et de récupération de texte intégral existants (c'est-à-direpas celle de votre base de données), dont Lucène est actuellement l'un des meilleurs et, par coïncidence, porté sur de nombreuses plates-formes.

Autres conseils

Le Dr Norvig de Google a expliqué comment cela fonctionne ;il donne même une implémentation Python de 20 lignes :

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

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

Le Dr Norvig discute également du « Vouliez-vous dire » dans cet excellent discours.Le Dr Norvig est chef de la recherche chez Google - lorsqu'on lui demande comment «voulez-vous dire» est implémenté, sa réponse est faisant autorité.

Il s'agit donc d'une vérification orthographique, probablement avec un dictionnaire dynamique construit à partir d'autres recherches ou même de phrases Internet réelles et autres.Mais c'est quand même vérification orthographique.

SOUNDEX et d’autres suppositions n’y jettent pas un coup d’œil, les amis !

Vérifier ce article sur wikipedia sur la distance de Levenshtein.Assurez-vous de bien examiner les améliorations possibles.

J'ai été agréablement surpris que quelqu'un ait demandé comment créer un système de suggestion orthographique de pointe pour les moteurs de recherche.Je travaille sur ce sujet depuis plus d'un an pour une société de moteurs de recherche et je peux citer des informations du domaine public sur le sujet.

Comme cela a été mentionné dans un article précédent, Google (ainsi que Microsoft et Yahoo !) n'utilisent aucun dictionnaire prédéfini et n'emploient pas non plus des hordes de linguistes qui réfléchissent aux éventuelles fautes d'orthographe des requêtes.Cela serait impossible en raison de l’ampleur du problème, mais aussi parce qu’il n’est pas sûr que les gens puissent réellement identifier correctement quand et si une requête est mal orthographiée.

Il existe en revanche un principe simple et plutôt efficace, valable également pour toutes les langues européennes.Obtenez toutes les requêtes uniques sur vos journaux de recherche, calculez la distance d'édition entre toutes les paires de requêtes, en supposant que la requête de référence est celle qui a le nombre le plus élevé.

Cet algorithme simple fonctionnera très bien pour de nombreux types de requêtes.Si vous souhaitez passer au niveau supérieur, je vous suggère de lire l'article de Microsoft Research sur ce sujet.Tu peux le trouver ici

Le document contient une excellente introduction, mais vous devrez ensuite connaître des concepts tels que le modèle de Markov caché.

Je suggérerais de regarder SOUNDEX pour trouver des mots similaires dans votre base de données.

Vous pouvez également accéder au propre dictionnaire de Google en utilisant le Demande de suggestion orthographique de l'API Google.

Vous voudrez peut-être regarder "Comment rédiger un correcteur orthographique" article.

Je pense que Google enregistre toutes les requêtes et identifie lorsque quelqu'un effectue une correction orthographique.Cette correction pourra alors être proposée lorsque d'autres fourniront la même première requête.Cela fonctionnera pour n'importe quelle langue, en fait n'importe quelle chaîne de caractères.

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

Je pense que cela dépend de la taille de votre site Web.Sur notre intranet local qui est utilisé par environ 500 membres du personnel, je regarde simplement les expressions de recherche qui n'ont renvoyé aucun résultat et je saisis cette expression de recherche avec la nouvelle expression de recherche suggérée dans une table SQL.

Je les appelle sur cette table si aucun résultat de recherche n'a été renvoyé. Cependant, cela ne fonctionne que si le site est relativement petit et je ne le fais que pour les expressions de recherche les plus courantes.

Vous voudrez peut-être également consulter ma réponse à une question similaire :

Des « messages similaires » comme des fonctionnalités utilisant MS SQL Server ?

Si vous disposez de traductions spécifiques à votre secteur d’activité, vous aurez probablement besoin d’un thésaurus.Par exemple, j'ai travaillé dans l'industrie de la bijouterie et nos descriptions contenaient des abréviations telles que kt - carat, rd - rond, cwt - poids en carats...Endeca (le moteur de recherche de ce poste) dispose d'un thésaurus qui traduira les fautes d'orthographe courantes, mais il nécessite une intervention manuelle.

je le fais avec Lucènec'est Correcteur orthographique.

Soundex est bon pour les correspondances phonétiques, mais fonctionne mieux avec les noms de personnes (il a été développé à l'origine pour les données de recensement)

Consultez également Full-Text-Indexing, la syntaxe est différente de la logique de Google, mais elle est très rapide et peut traiter des éléments de langage similaires.

Soundex et "Porter stemming" (soundex est trivial, je ne suis pas sûr de la racine porter).

Il y a quelque chose appelé aspell qui pourrait aider :http://blog.evanweaver.com/files/doc/fauna/raspell/classes/Aspell.html

Il y a un joyau rubis pour cela, mais je ne sais pas comment lui parler depuis pythonhttp://blog.evanweaver.com/files/doc/fauna/raspell/files/README.html

Voici une citation de l'implémentation de Ruby

Usage

Aspell vous permet de vérifier les mots et de suggérer des corrections.Par exemple:

  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

Cela produit :

Correction possible pour le cœur :Coeur Correction possible pour Wil:Volonté

Implémenter efficacement la correction orthographique pour les moteurs de recherche n'est pas anodin (vous ne pouvez pas simplement calculer la distance d'édition/levenshtein par rapport à chaque mot possible).Une solution basée sur les indices k-grammes est décrite dans Introduction à la recherche d'informations (texte intégral disponible en ligne).

Vous pourriez utiliser ngram pour la comparaison : http://en.wikipedia.org/wiki/N-gram

Utilisation du module 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]

Vous obtenez :

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

Pourquoi ne pas utiliser Google, vouliez-vous dire dans votre code. Pour savoir comment, voir icihttp://narenonit.blogspot.com/2012/08/trick-for-using-googles-did-you-mean.html

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow