Comment fonctionne l’algorithme Google «Vouliez-vous dire?

J’ai développé un site Web interne pour un outil de gestion de portefeuille. Il y a beaucoup de données texte, de noms de sociétés, etc. J’ai été vraiment impressionné par la capacité de certains moteurs de recherche à répondre très rapidement aux requêtes avec “Voulez-vous dire: xxxx”.

Je dois être capable de prendre intelligemment une requête utilisateur et de répondre avec non seulement des résultats de recherche bruts, mais aussi avec “Vouliez-vous dire?” réponse quand il y a une réponse alternative très probable, etc.

[Je développe en ASP.NET (VB – ne m’en prenez pas!)]

MISE À JOUR: OK, comment puis-je l’imiter sans les millions d’utilisateurs non rémunérés?

  • Générer des fautes de frappe pour chaque terme «connu» ou «correct» et effectuer des recherches?
  • Une autre méthode plus élégante?

Voici l’explication directement de la source (presque)

Rechercher 101!

à min 22:03

La peine de regarder!

Fondamentalement et selon Douglas Merrill, ancien directeur technique de Google, c’est comme ça:

1) Vous écrivez un mot (mal orthographié) dans Google

2) Vous ne trouvez pas ce que vous vouliez (ne cliquez sur aucun résultat)

3) Vous réalisez que vous avez mal orthographié le mot afin de réécrire le mot dans le champ de recherche.

4) Vous trouvez ce que vous voulez (vous cliquez dans les premiers liens)

Ce modèle multiplié par des millions de fois, montre quels sont les erreurs les plus communes et quelles sont les corrections les plus “communes”.

De cette façon, Google peut presque instantanément proposer une correction orthographique dans toutes les langues.

Cela signifie également que si, du jour au lendemain, tout le monde commence à épeler la nuit, Google suggèrera ce mot à la place.

MODIFIER

@ ThomasRutter: Douglas le décrit comme “apprentissage automatique statistique”.

Ils savent qui corrige la requête, car ils savent quelle requête provient de quel utilisateur (en utilisant des cookies)

Si les utilisateurs effectuent une requête et que seuls 10% des utilisateurs cliquent sur un résultat et que 90% retournent et tapent une autre requête (avec le mot corrigé) et que cette fois-ci 90% cliquent sur un résultat, ils savent qu’ils ont trouvé une correction

Ils peuvent également savoir si ce sont des requêtes “liées” de deux types différents, car ils ont des informations sur tous les liens qu’ils affichent.

De plus, ils incluent maintenant le contexte dans la vérification orthographique, ils peuvent même suggérer des mots différents selon le contexte.

Voir cette démo de Google Wave (@ 44m 06s) qui montre comment le contexte est pris en compte pour corriger automatiquement l’orthographe.

Ici, il est expliqué comment fonctionne le traitement du langage naturel.

Et enfin, voici une démonstration impressionnante de ce qui peut être fait en ajoutant une traduction automatique (@ 1h 12m 47s) au mixage.

J’ai ajouté des ancres de minutes et de secondes aux vidéos pour accéder directement au contenu. Si elles ne fonctionnent pas, essayez de recharger la page ou de la faire défiler manuellement jusqu’à la marque.

J’ai trouvé cet article il y a quelque temps: Comment écrire un correcteur orthographique , écrit par Peter Norvig (directeur de la recherche chez Google Inc.).

C’est une lecture intéressante sur le sujet “correction orthographique”. Les exemples sont en Python mais c’est clair et simple à comprendre, et je pense que l’algorithme peut être facilement traduit dans d’autres langues.

Ci-dessous une courte description de l’algorithme. L’algorithme comprend deux étapes, la préparation et la vérification des mots.

Étape 1: Préparation – mise en place de la firebase database de mots

Le mieux est si vous pouvez utiliser des mots de recherche réels et leur occurrence. Si vous ne l’avez pas, un grand ensemble de texte peut être utilisé à la place. Comptez l’occurrence (popularité) de chaque mot.

Etape 2. Vérification des mots – trouver des mots similaires à celui coché

Similaire signifie que la distance d’édition est faible (généralement 0-1 ou 0-2). La distance d’édition est le nombre minimum d’insertions / suppressions / modifications / swaps nécessaires pour transformer un mot en un autre.

Choisissez le mot le plus populaire de l’étape précédente et suggérez-le comme correction (s’il ne s’agit pas du mot lui-même).

Pour la théorie de l’algorithme “avez-vous voulu dire”, vous pouvez vous reporter au chapitre 3 de l’introduction à la recherche d’informations. Il est disponible en ligne gratuitement. La section 3.3 (page 52) répond exactement à votre question. Et pour répondre spécifiquement à votre mise à jour, vous n’avez besoin que d’un dictionnaire de mots et de rien d’autre (y compris des millions d’utilisateurs).

Hmm … Je pensais que Google utilisait son vaste corpus de données (Internet) pour faire du NLP (Natural Language Processing).

Par exemple, ils disposent de tellement de données provenant d’Internet entier qu’ils peuvent compter le nombre de fois qu’une séquence de trois mots se produit (appelée sortinggramme ). Donc, s’ils voient une phrase comme: “concert rose frugr”, ils pourraient voir qu’il a peu de succès, puis trouver le plus probable “concert rose” dans leur corpus.

Ils font apparemment juste une variation de ce que disait Davide Gualano, alors lisez ce lien. Google utilise bien entendu toutes les pages Web connues comme corpus, ce qui rend son algorithme particulièrement efficace.

J’imagine qu’ils utilisent une combinaison d’un algorithme de distance Levenshtein et des masses de données qu’ils collectent concernant les recherches effectuées. Ils peuvent extraire une série de recherches ayant la distance Levenshtein la plus courte de la chaîne de recherche saisie, puis choisir celle qui donne le plus de résultats.

Normalement, un correcteur orthographique de production utilise plusieurs méthodes pour fournir une suggestion orthographique. Certains sont:

  • Déterminez un moyen de déterminer si une correction orthographique est requirejse. Celles-ci peuvent inclure des résultats insuffisants, des résultats qui ne sont pas spécifiques ou suffisamment précis (selon certaines mesures), etc. Ensuite:

  • Utilisez un grand corps de texte ou un dictionnaire, où tous ou la plupart sont connus pour être correctement orthographiés. Ceux-ci se trouvent facilement en ligne, dans des endroits tels que LingPipe . Ensuite, pour déterminer la meilleure suggestion, vous recherchez un mot qui correspond le mieux à plusieurs mesures. La plus intuitive est des caractères similaires. Ce qui a été démontré par la recherche et l’expérimentation, c’est que les correspondances entre deux ou trois caractères fonctionnent mieux. (bigrammes et sortinggrammes). Pour améliorer encore les résultats, pesez un score plus élevé lors d’une correspondance au début ou à la fin du mot. Pour des raisons de performances, indexez tous ces mots sous forme de sortinggrammes ou de bigrammes, de sorte que lorsque vous effectuez une recherche, vous convertissez en n-gram et recherchez via la table de hachage ou le sortinge.

  • Utilisez des heuristiques liées aux erreurs de clavier potentielles en fonction de l’emplacement du personnage. Donc, “hwllo” devrait être “hello” parce que “w” est proche de “e”.

  • Utilisez une clé phonétique (Soundex, Metaphone) pour indexer les mots et rechercher les corrections possibles. Dans la pratique, cela produit normalement des résultats moins bons que l’utilisation de l’indexation en n-grammes, comme décrit ci-dessus.

  • Dans chaque cas, vous devez sélectionner la meilleure correction dans une liste. Cela peut être une mesure de distance telle que levenshtein, la mésortingque du clavier, etc.

  • Pour une phrase à plusieurs mots, un seul mot peut être mal orthographié, auquel cas vous pouvez utiliser les mots restants comme contexte pour déterminer la meilleure correspondance.

Utilisez la distance Levenshtein , puis créez un arbre mésortingque (ou un arbre mince) pour indexer les mots. Exécutez ensuite une requête 1-Nearest Neighbor et vous obtenez le résultat.

Google suggère apparemment des requêtes avec les meilleurs résultats, pas avec ceux qui sont orthographiés correctement. Mais dans ce cas, un correcteur orthographique serait probablement plus faisable. Bien sûr, vous pourriez stocker des valeurs pour chaque requête, en fonction de mesures indiquant les résultats obtenus.

Alors,

  1. Vous avez besoin d’un dictionnaire (anglais ou basé sur vos données)

  2. Générez un mot treillis et calculez les probabilités pour les transitions à l’aide de votre dictionnaire.

  3. Ajoutez un décodeur pour calculer la distance d’erreur minimale à l’aide de votre treillis. Bien sûr, vous devez vous occuper des insertions et des suppressions lors du calcul des distances. Ce qui est amusant, c’est que le clavier QWERTY maximise la distance si vous touchez des touches proches les unes des autres.

  4. Renvoie le mot qui a la distance minimale.

  5. Ensuite, vous pouvez comparer cela à votre firebase database de requêtes et vérifier s’il y a de meilleurs résultats pour d’autres correspondances proches.

Voici la meilleure réponse que j’ai trouvée , le correcteur d’orthographe implémenté et décrit par le directeur de la recherche de Google, Peter Norvig.

Si vous voulez en savoir plus sur la théorie derrière cela, vous pouvez lire son chapitre de livre .

L’idée de cet algorithme est basée sur l’apprentissage automatique statistique.

en ce qui concerne votre question sur la façon d’imiter le comportement sans avoir des tonnes de données – pourquoi ne pas utiliser des tonnes de données collectées par Google? Téléchargez les résultats Google Sarch pour le mot mal orthographié et recherchez «Vouliez-vous dire:» dans le code HTML.

Je suppose que ça s’appelle mashup de nos jours 🙂

Comme deviner … ça pourrait

  1. chercher des mots
  2. s’il n’est pas trouvé, utilisez un algorithme pour essayer de “deviner” le mot.

Peut-être quelque chose provenant de l’IA comme le réseau Hopfield ou le réseau de propagation arrière, ou autre chose “identifiant les empreintes digitales”, restaurant les données brisées, ou les corrections orthographiques mentionnées par Davide …

J’ai vu quelque chose à ce sujet il y a quelques années, donc peut-être a changé depuis, mais apparemment, ils ont commencé par parsingr leurs journaux pour que les mêmes utilisateurs soumettent des requêtes très similaires en peu de temps et se.

Simple. Ils ont des tonnes de données. Ils ont des statistiques pour tous les termes possibles, en fonction de la fréquence à laquelle ils sont interrogés et des variations qui en résultent généralement. Les utilisateurs cliquent alors sur une faute de frappe fréquente. la réponse la plus habituelle.

En fait, si la faute d’orthographe est en réalité le terme le plus fréquemment recherché, l’algorithme le prendra pour le bon.

Vous voulez dire correcteur orthographique? Si c’est un correcteur orthographique plutôt qu’une phrase entière, j’ai un lien sur la vérification orthographique où l’algorithme est développé en python. Vérifiez ce lien

Pendant ce temps, je travaille également sur un projet qui inclut la recherche de bases de données en utilisant du texte. Je suppose que cela résoudrait votre problème

Outre les réponses ci-dessus, au cas où vous souhaiteriez mettre en œuvre quelque chose rapidement, voici une suggestion –

Algorithme

Vous pouvez trouver la mise en œuvre et la documentation détaillée de cet algorithme sur GitHub .

  • Créez une queue prioritaire avec un comparateur.
  • Créez un arbre de recherche Ternay et insérez tous les mots anglais (du post de Norvig ) avec leurs fréquences.
  • Commencez à traverser le TST et pour chaque mot rencontré dans TST, calculez sa distance Levenshtein ( LD ) à partir de input_word
  • Si LD ≤ 3, alors placez-le dans une queue prioritaire.
  • À la dernière extraction 10 mots de la queue prioritaire et de l’affichage.

Le moyen le plus simple de le découvrir est la programmation dynamic de Google.

C’est un algorithme emprunté à Information Resortingeval et largement utilisé en bioinformatique moderne pour voir à quel sharepointux séquences de gènes sont similaires.

La solution optimale utilise la programmation dynamic et la récursivité.

C’est un problème très résolu avec beaucoup de solutions. Allez sur Google jusqu’à ce que vous trouviez un code source ouvert.

Il existe une structure de données spécifique – arbre de recherche ternaire – qui supporte naturellement les correspondances partielles et les correspondances proches.

C’est une vieille question, et je suis surpris que personne n’ait suggéré l’OP utilisant Apache Solr.

Apache Solr est un moteur de recherche en texte intégral qui, outre de nombreuses autres fonctionnalités, fournit également des suggestions de vérification orthographique ou de requête. De la documentation :

Par défaut, les correcteurs Lucene Spell sortingent les suggestions en fonction du score obtenu lors du calcul de la distance de chaîne et ensuite de la fréquence (si disponible) de la suggestion dans l’index.