Comment fonctionne l'algorithme Google "Voulez-vous dire?"

https://stackoverflow.com/questions/307291

08-07-2019
|

Question

J'ai développé un site Web interne pour un outil de gestion de portefeuille. Il y a beaucoup de données textuelles, de noms de sociétés, etc. Les moteurs de recherche ont été très impressionnés par la capacité de répondre très rapidement aux requêtes en indiquant "Voulez-vous dire: xxxx"?

Je dois pouvoir prendre en compte intelligemment une requête utilisateur et y répondre non seulement avec des résultats de recherche bruts, mais également avec un "Voulez-vous dire?" réponse quand il y a une réponse alternative très probable, etc.

[Je développe dans ASP.NET (VB, ne tenez pas contre moi!)]

UPDATE: OK, comment puis-je imiter cela sans les millions d’utilisateurs non rémunérés?

Générez des fautes de frappe pour chaque terme "connu" ou "correct" et effectuez des recherches?
Une autre méthode plus élégante?

La solution

Voici l'explication directement de la source (presque)

Recherchez 101! h2>
à min 22h03

À voir!

Fondamentalement, selon Douglas Merrill, ancien directeur technique de Google, il se présente comme suit:

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, vous devez donc l'écrire de nouveau dans le champ de recherche.

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

Ce modèle, multiplié par des millions de fois, indique quels sont les fautes d’orthographe les plus courantes et les plus communes. corrections.

Ainsi, Google peut presque instantanément proposer une correction orthographique dans toutes les langues.

Cela signifie également que si tout au long de la nuit, tout le monde commence à épeler nuit comme suit: "nuit". Google suggère ce mot à la place.

MODIFIER

@ThomasRutter: Douglas le décrit comme un "apprentissage statistique en machine".

Ils savent qui corrige la requête, car ils savent quelle requête provient de quel utilisateur (à l'aide de cookies)

Si les utilisateurs effectuent une requête et que seulement 10% d'entre eux cliquent sur un résultat et que 90% reviennent en arrière et tapent une autre requête (avec le mot corrigé), cette fois 90% cliquent sur un résultat, ils savent alors ils ont trouvé une correction.

Ils peuvent également savoir si ceux-ci sont "liés" " requêtes de deux différentes, car elles contiennent des informations sur tous les liens qu’elles affichent.

De plus, ils incluent maintenant le contexte dans la vérification orthographique, de sorte qu'ils peuvent même suggérer un mot différent en fonction du contexte.

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

Ici , nous expliquons comment fonctionne le traitement en langage naturel.

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

_{J'ai ajouté des ancres de minute et de seconde aux vidéos pour passer directement au contenu. Si elles ne fonctionnent pas, essayez de recharger la page ou de faire défiler à la main jusqu'à la marque.}

Autres conseils

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

C’est une lecture intéressante à propos de la "correction orthographique". sujet. 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 brève description de l’algorithme. L'algorithme comprend deux étapes, la préparation et la vérification des mots.

Étape 1: Préparation - Configuration de la base de données de mots

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

Étape 2. Vérification des mots: recherchez des mots similaires à celui sélectionné

Similaire signifie que la distance de montage est basse (généralement 0-1 ou 0-2). La distance de modification est le nombre minimal d'insertions / suppressions / modifications / permutations 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 une correction (si autre que le mot lui-même).

Pour la théorie de "voulez-vous dire"? algorithme, vous pouvez vous reporter au Chapitre 3 de Introduction à la recherche d’information. Il est disponible en ligne gratuitement. La section 3.3 (page 52) répond exactement à vos 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 de la PNL (traitement du langage naturel).

Par exemple, ils ont tellement de données sur Internet qu’ils peuvent compter le nombre de fois qu’une séquence de trois mots se produit (connu sous le nom de trigram ). Ainsi, s’ils voient une phrase du type "concert rose frugr", ils peuvent constater qu’il n’a que peu de hits, puis trouver le "concert rose" le plus probable. dans leur corpus.

Apparemment, ils ne font qu’une variante de ce que disait Davide Gualano, alors lisez ce lien avec une certitude. Bien entendu, Google utilise toutes les pages Web connues comme corpus, ce qui rend son algorithme particulièrement efficace.

Je suppose qu'ils utilisent une combinaison d'un algorithme distance de Levenshtein et des masses de données collectées concernant les recherches effectuées. Ils peuvent extraire un ensemble de recherches qui ont la distance de Levenshtein la plus courte de la chaîne de recherche entrée, puis choisir celle qui donne le plus grand nombre de résultats.

Normalement, un correcteur d’orthographe en production utilise plusieurs méthodologies pour fournir une suggestion orthographique. Certains sont:

Choisissez une méthode pour déterminer si une correction orthographique est requise. Ceux-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. Vous les trouverez facilement en ligne, dans des endroits tels que LingPipe . Ensuite, pour déterminer la meilleure suggestion, vous recherchez un mot qui correspond le mieux, en fonction de plusieurs mesures. Le plus intuitif est des personnages similaires. Les recherches et les expériences ont montré que les correspondances de séquences de deux ou trois caractères donnent de meilleurs résultats. (bigrammes et trigrammes). 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 en tant que trigrammes ou bigrammes. Ainsi, lorsque vous effectuez une recherche, vous convertissez-le en n-gramme et effectuez une recherche avec hashtable ou trie.
Utilisez des méthodes heuristiques liées aux erreurs de clavier potentielles en fonction de l'emplacement du caractère. Pour que " hwllo " devrait être " bonjour " parce que 'w' est proche de 'e'.
Utilisez une clé phonétique (Soundex, Metaphone) pour indexer les mots et rechercher les corrections possibles. En pratique, cela donne normalement des résultats pires que ceux utilisant l'indexation n-grammes, comme décrit ci-dessus.
Dans chaque cas, vous devez sélectionner la meilleure correction dans une liste. Cela peut être une métrique de distance telle que levenshtein, la métrique de clavier, etc.
Pour une phrase de plusieurs mots, un seul mot peut être mal orthographié. Dans ce cas, vous pouvez utiliser les mots restants comme contexte pour déterminer la meilleure correspondance.

Utilisez distance de Levenshtein , puis créez un arbre métrique (ou arbre mince) pour indexer les mots. Exécutez ensuite une requête sur le voisin le plus proche et vous obtenez le résultat.

Google suggère apparemment les requêtes avec les meilleurs résultats, pas avec celles qui sont épelées correctement. Mais dans ce cas, un correcteur orthographique serait probablement plus pratique. Bien sûr, vous pouvez stocker une valeur pour chaque requête, en fonction de la mesure des résultats obtenus.

Alors,

Vous avez besoin d'un dictionnaire (anglais ou basé sur vos données)
Générez un treillis de mots et calculez les probabilités des transitions à l'aide de votre dictionnaire.
Ajoutez un décodeur pour calculer la distance d'erreur minimale à l'aide de votre treillis. Bien sûr, vous devez prendre en compte les insertions et les suppressions lors du calcul des distances. Ce qui est amusant, c’est que le clavier QWERTY maximise la distance si vous appuyez sur des touches proches les unes des autres. (Ca tournerait en voiture, cay tournerait en chat)
Renvoie le mot qui a la distance minimale.
Vous pouvez ensuite comparer cela à votre base de données de requêtes et vérifier s'il existe de meilleurs résultats pour les autres correspondances.

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

Si vous souhaitez en savoir plus sur la théorie sous-jacente, vous pouvez consulter son chapitre de livre . .

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

Comme par hasard ... cela pourrait

recherche de mots
s'il ne le trouve pas, utilisez un algorithme pour essayer de "deviner" le mot.

Cela pourrait provenir d’intelligence artificielle telle que le réseau Hopfield ou le réseau de propagation arrière, ou de l’autre chose "d’identification d’empreintes digitales", de restauration de données erronées ou de corrections orthographiques comme Davide l’a déjà mentionné ...

J'ai vu quelque chose à ce sujet il y a quelques années. Cela a peut-être changé depuis, mais apparemment, ils ont commencé par analyser leurs journaux pour les mêmes utilisateurs qui soumettaient des requêtes très similaires dans un court laps de temps, et utilisaient l'apprentissage automatique basé sur la manière dont les utilisateurs se sont corrigés eux-mêmes.

Simple. Ils disposent de tonnes de données. Ils ont des statistiques pour chaque terme possible, en fonction de la fréquence à laquelle il est interrogé et des variations de celui-ci. Les utilisateurs cliquent dessus. Ainsi, lorsqu'ils vous voient saisir une faute de frappe fréquente pour un terme de recherche, ils proposent des options. la réponse plus habituelle.

En fait, si le mot mal orthographié est le terme recherché le plus fréquemment recherché, l’algorythme le prendra pour le bon.

en ce qui concerne votre question, comment imiter le comportement sans disposer de 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 & Did; Did you moyenne: " dans le HTML.

Je suppose que cela s'appelle mashup de nos jours: -)

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

Parallèlement, je travaille également sur un projet qui inclut la recherche de bases de données à l'aide de texte. Je suppose que cela résoudrait votre problème

C’est une vieille question et je suis surpris que personne n’ait suggéré que l’opérateur utilise Apache Solr.

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

Par défaut, les vérificateurs d’orthographe Lucene trient d’abord les suggestions par le score du calcul de la distance entre les cordes et seconde de la fréquence (si disponible) de la suggestion dans l'index.

Outre les réponses ci-dessus, si vous souhaitez mettre en œuvre rapidement quelque chose vous-même, voici une suggestion -

Algorithme

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

Créer une file d'attente prioritaire avec un comparateur.
Créez un arbre de recherche Ternay et insérez tous les mots anglais (du l'article de Norvig ) ainsi que leurs fréquences. .
Commencez par parcourir le TST et pour chaque mot rencontré dans le TST, calculez sa distance de Levenshtein ( LD ) à partir du mot_de_entrée
Si LD & # 8804; 3 puis placez-le dans une file d'attente prioritaire.
Enfin, extrayez 10 mots de la file d'attente prioritaire et affichez-les.

Il existe une structure de données spécifique - arbre de recherche ternaire - qui prend naturellement en charge les correspondances partielles et les correspondances proches.

La méthode la plus simple consiste à utiliser la programmation dynamique de Google.

C’est un algorithme emprunté à la recherche d’informations et qui est très utilisé dans la bioinformatique moderne pour voir la similitude de deux séquences de gènes.

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

Il s’agit d’un problème très résolu comportant de nombreuses solutions. Allez sur Google jusqu'à ce que vous trouviez du code open source.

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow