Comment fonctionne l'algorithme Google "Did you mean ? Algorithme fonctionne-t-il ?

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. J'ai été très impressionné par la capacité de certains moteurs de recherche à répondre très rapidement aux requêtes par "Vouliez-vous dire : xxxx".

Je dois être capable de prendre intelligemment une requête d'un utilisateur et de répondre non seulement avec des résultats de recherche bruts, mais aussi avec une réponse "Vous voulez dire ?" lorsqu'il existe une réponse alternative très probable, etc.

[Je développe dans ASP.NET (VB - ne m'en voulez pas ! )]

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

• Générer des coquilles pour chaque terme "connu" ou "correct" et effectuer des recherches ?
• Une autre méthode plus élégante ?

Answer 1

Voici l'explication directement de la source ( presque )

Recherche 101 !

à min 22:03

Ça vaut le coup de regarder !

En gros, 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 cherchez ( ne cliquez sur aucun résultat )

3) Vous vous rendez compte que vous avez mal orthographié le mot et vous le réécrivez dans le champ de recherche.

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

Ce schéma, multiplié des millions de fois, montre quelles sont les fautes d'orthographe les plus fréquentes et quelles sont les corrections les plus "courantes".

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 "nuit" comme "nigth", Google proposera ce mot à la place.

EDIT

@ThomasRutter : Douglas le décrit comme "l'apprentissage statistique des machines".

Ils savent qui a corrigé la requête, car ils savent quelle requête provient de quel utilisateur (en utilisant les cookies).

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

Ils peuvent également savoir s'il s'agit de requêtes "connexes" ou de deux requêtes différentes, car ils disposent d'informations sur tous les liens qu'ils affichent.

De plus, ils incluent désormais le contexte dans le correcteur orthographique, de sorte qu'ils peuvent même suggérer des mots différents en fonction du contexte.

Voir ceci démo de google wave ( @ 44m 06s ) qui montre comment le contexte est pris en compte pour corriger automatiquement l'orthographe.

Aquí il est expliqué comment fonctionne ce traitement du langage naturel.

Enfin, voici une démonstration impressionnante de ce que l'on peut faire en ajoutant des fonctions automatiques. traduction automatique ( @ 1h 12m 47s ) au mélange.

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

Answer 2

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 sur le thème de la "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. facilement à d'autres langues.

Vous trouverez ci-dessous une brève description de l'algorithme. L'algorithme se compose de deux étapes, la préparation et la vérification des mots.

Étape 1 : Préparation - mise en place de la base de données de mots

Le mieux est d'utiliser des mots de recherche réels et leur occurrence. Si vous n'avez pas cela, vous pouvez utiliser un grand ensemble de textes. Comptez l'occurrence (popularité) de chaque mot.

Étape 2. Vérification des mots - recherche de mots similaires à ceux qui ont été vérifiés.

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/échanges nécessaires pour transformer un mot en un autre.

Choisissez le mot le plus populaire de l'étape précédente et proposez-le comme correction (si ce n'est pas le mot lui-même).

Answer 3

Pour la théorie de l'algorithme "did you mean", vous pouvez vous référer au chapitre 3 de Introduction to Information Retrieval. Il est disponible en ligne gratuitement. Section 3.3 (page 52) répond exactement à votre question. Et pour répondre précisément à votre mise à jour, il suffit d'un dictionnaire de mots et rien d'autre (y compris des millions d'utilisateurs).

Answer 4

Hmm... Je pensais que google utilisait son vaste corpus de données (l'internet) pour faire un sérieux NLP (Natural Language Processing).

Par exemple, ils disposent d'une telle quantité de données provenant de l'ensemble de l'internet qu'ils peuvent compter le nombre de fois qu'une séquence de trois mots se produit (connue sous le nom de trigramme ). Donc s'ils voient une phrase comme : "concert de pink frugr", ils pourraient voir qu'elle a peu d'occurrences, puis trouver le "concert de pink *" le plus probable dans leur corpus.

Apparemment, ils ne font qu'une variation de ce que Davide Gualano disait, alors lisez bien ce lien. Google utilise bien sûr toutes les pages web qu'il connaît comme corpus, ce qui rend son algorithme particulièrement efficace.

Answer 5

Je pense qu'ils utilisent une combinaison d'une distance de Levenshtein l'algorithme et les masses de données qu'ils collectent concernant les recherches qui sont effectuées. Ils pourraient extraire un ensemble de recherches dont la distance de Levenshtein est la plus courte par rapport à la chaîne de recherche saisie, puis choisir celle qui donne le plus de résultats.