Web: Le mystère des pages manquantes de Google résolu

[Version anglaise - English version]

---

Lire la suite

28 fév - MSN triche-t-il aussi ?
7 mar - Yahoo indexe plus de pages que Google
13 mar - Google ajuste ses comptes
23 mar - 5 milliards de "the" sont partis en fumée
25 mar - Un instantané sur la mise à jour

---

Dans de précédents articles, j'ai mis en évidence deux problèmes étranges affectant les comptes de Google (ici et ici). Des millions de pages semblent massivement disparaître :

• si l'on tape Chirac OR Sarkozy, on obtient la moitié des résultats obtenus pour Chirac tout seul, ce qui peut trouver une explication politique, mais constitue une curieuse approche de la logique booléenne ;
• si l'on cherche the dans les pages anglaises, on obtient 1% du nombre de résultats obtenus sur l'ensemble du Web, toutes langues confondues. Est-ce que ça veut dire que the est 99 fois plus fréquent dans les langues autres que l'anglais ? Bien sûr que non.

Où sont passées les pages manquantes ? C'est le problème que je me pose dans cet article. Un scenario possible est que l'index véritable de Google est considérablement plus petit que la taille officiellement annoncée. L'expérience détaillée que je rapporte ci-dessous donne une estimation de 60%, ce qui correspondrait à une taille d'index véritable d'environ 5 milliards de pages. Ce scénario est bien sûr entièrement hypothétique, mais il permet d'expliquer les différences dans les comptes de pages anglaises, et le comportement singulier des opérateurs booléens.

Je préfère le dire clairement tout de suite, de façon à ne pas faire perdre leur temps aux commentateurs éventuels : ceci ne veux pas dire que Google soit un mauvais moteur (je l'ai d'ailleurs en page d'accueil de mon navigateur). Pour la plupart des utilisateurs, les comptes sont sans intérêt, et ce qui... compte pour eux, c'est de savoir s'ils obtiennent leur résultats rapidement et efficacement ou non. Les chiffres ne présentent un intérêt que pour les experts, et dans ce cas précis, ils ont des raisons de s'interroger.

Une expérience

Dans cette nouvelle expérience, je n'ai pas utilisé des mots fréquents comme the, car de tels mots ont toutes les chances de faire l'objet d'un traitement spécial dans tous les moteurs de recherches. Ils font probablement partie d'un antidictionnaire (stoplist), et leurs occurrences ne sont probablement pas pleinement indexées. J'ai plutôt utilisé 50 mots anglais tirés au hasard dans un corpus d'un million de mots (accumulated, alive, ancestor, bushes, etc.), en éliminant les mots pour lesquels je connaissait un homographe évident dans une autre langue (par exemple patio).

La figure ci-dessous donne une représentation des comptes fournis par Google pour une recherche de ces mots dans les pages en anglais par rapport à ceux qu'il fournit sur l'ensemble du Web (la partie qu'il en connaît, bien évidemment) [voir résultats complets ici -- toutes les valeurs ont été obtenues le 6 février] :

La pente de la droite de régression nous indique que les résultats en anglais représentent 56% des résultats pour l'ensemble du Web, sur les mêmes mots. Bien entendu, j'ai pu manquer quelques homographes interlingues, et certains des mots apparaissent probablement cités dans des pages non-anglaises, mais ces facteurs devraient être marginaux -- et de toutes façons différents pour chaque mot. Si quasiment la moitié des occurrences apparaissent dans des pages non-anglaises, on devrait oberver une dispersion considérable des résultats. Au lieu de cela, on observe une très forte corrélation entre les deux comptes, avec un coefficient de détermination R² égal à 0.96. Cette corrélation importante est statistiquement impossible, et un facteur systématique doit être présent pour l'expliquer. Une possiblité serait une performance très médiocre de l'algorithme de détection de langues utilisé par Google, mais c'est une explication très improbable, car on en verrait des traces dans près d'un résultat sur deux. Or, c'est loin d'être le cas : la détection des langues dans Google est très robuste, même si, évidemment, elle n'est pas parfaite.

Par ailleurs, si nous examinons les résultats de Yahoo pour la même liste de mots, nous obtenons un comportement bien plus conforme à nos attentes [voir résultats complets ici] :

La corrélation est également très forte (même plus forte, en fait), mais ceci est tout à fait normal, puisque les résultats sont presque identiques : les résultats anglais représentent 92% du total. Ce chiffre est bien plus en accord avec nos connaissances linguistiques.

Les résultats français sont tout à fait similaires. J'ai fabriqué une liste de mots français selon les mêmes principes, et je l'ai soumise à Google et Yahoo [voir résultats complets ici]. Google donne 58% des résultats situés dans des pages en français, avec, à nouveau, une corrélation importante -- légèrement plus faible (R² = 0.86), mais également incompatible avec la proportion importante de résultats qui seraient situés dans des pages non-françaises. Le comportement des mots individuels devrait amener une image globale beaucoup plus aléatoire.

Yahoo se comporte exactement comme pour l'anglais. La proportion des résultats situés dans des pages françaises est même légèrement supérieure (97%), ce qui est conforme aux attentes, puisque l'anglais, langue internationale, est plus susceptible que le français d'être cité dans de nombreux documents en langues étrangères.

Un scénario possible

De nombreux experts (voir par exemple ici) pensent que la base de données de Google est composée de deux parties (au moins). L'une des deux parties est un véritable index, tandis que l'autre ne contiendrait que des URLs de pages dont Google connaît la présence, mais qui n'ont pas été réellement indexées (à part peut-être les mots présents dans l'URL). Je n'ai bien entendu aucun moyen de savoir si cette hypothèse est correcte (bien que, jusqu'en 2002, Google l'ait admise publiquement), mais elle permet d'expliquer les comportements curieux dont je me suis fait l'écho ci-dessus.

Appelons ces parties hypothétiques A et B, composant à elles-deux la base de données D :

Nous pouvons dès lors écrire un scénario possible. Quand on interroge Google avec un mot X sans spécification d'une langue particulière, Google interroge son index (c'est-à-dire la partie A), qui lui fournit un nombre de résultats. Ce compte est extrapolé pour être en accord avec la taille de la base de données D (c'est-à-dire augmenté dans un rapport de 1/0.60 = 1.66). Par contre, lorsque la recherche est restreinte à une langue particulière, l'extrapolation n'est pas faite, car les pages dans la partie B ne sont pas indexées, et pas catégorisées du point de vue des langues. Seuls les résultats de A sont fournis. Bien sûr, il aurait été possible de projeter les proportions des différentes langues de A dans la base de données D, et de fournir une extrapolation réaliste malgré tout, mais les ingénieurs de chez Google n'y ont sans doute pas pensé, ou ont trouvé que c'était sans importance.

On peut calculer une estimation très précise de la taille relative des parties A et B, à partir de mes résultats précédents. Selon Yahoo (si on accepte de lui faire confiance), 92% des résultats concernant ma liste de mots anglais sont situés dans des pages en anglais. Si l'on applique la même proportion à Google, cela veut dire que l'index (c'est-à-dire la partie A) est de 0.52 / 0.92 = 60.9% de la taille de D. Il est assez intéressant de remarquer que si on applique les mêmes calculs au français, on obtient une estimation de 0.58 / 0.96 = 60.4%. Ces chiffres sont si proches qu'il serait surprenant qu'ils soient dus à une coincidence.

Selon le scénario esquissé ci-dessus la taille réelle de l'index Google est donc d'environ 60% de celle de la base de données complète, et les résultats fournis sont affectés d'un facteur d'inflation de 66% (1/0.60 - 1).

Il est difficile de rapporter ces proportions à des valeurs absolues, car personne ne sait exactement quelle est la taille de la base de données Google. En novembre 2004, Google a annoncé que le moteur cherchait dans 8 058 044 651 pages Web. Ce chiffre n'a pas changé depuis sur la page d'accueil, mais j'ai montré le 23 janvier que l'index s'était accru d'un facteur 1.13 depuis novembre (lire ici). Une estimation du 6 février me donne un facteur d'accroissement de 1.14. Ceci correspondarait à une base de données de 9.2 milliards de pages, c'est-à-dire un index véritable (partie A) d'environ 5.5. milliards. Certains obervateurs ont observé qu'en novembre, Google a affiché pour un court instant 10.8 milliards de résultats pour la requête the, ce qui indiquerait une base de données plus grande encore, à moins que cela signifie simplement qu'à un moment donné Google a envisagé un facteur d'inflation encore plus grand. Nous ne le saurons probablement jamais.

Un nouveau regard sur la logique Googléenne

Le scénario hypothétique esquissé ci-dessus fournit également une explication simple au problème de la logique Googléenne. Rappellons-nous que X OR Y renvoie moins de résultats que X tout seul (voir détails). Encore plus étrange, X OR X et X (AND) X renvoient aussi moins de résultats que X tout seul. J'ai interrogé Google avec X OR X et X (AND) X pour chaque mot de ma liste anglaise (avec l'option "tout le Web") . Les résultats sont dans les deux cas quasiment identiques pour la totalité des mots [voir résultats complets ici], et, ce qui est encore plus surprenant, ils correspondent quasi exactement aux résultats pour X sur les pages anglaises seulement (coefficient de détermination R² > 0.999 !

Il est probable que Google effectue ses calculs booléens (union et intersection de listes) sur la base de l'index véritable (partie A). Ceci expliquerait pourquoi X OR X et X (AND) X donnent les mêmes résultats qu'une recherche sur X en anglais. La même chose se produit avec les mots français [voir résultats complets ici]. Si ce phénomène surprenant n'a pas été relevé jusqu'ici c'est sans doute qu'il est brouillé lorsqu'on utilise des mots qui peuvent apparaître dans plusieurs langues (homographes comme patio ou noms propres comm Chirac ou Bush).

Selon toute probabilité, les ingénieurs Google ont oublié de connecter la routine d'extrapolation à la sortie du module de requêtes booléennes ! En conclusion, si vous voulez connaître le vrai compte des mots dans l'index Google, tapez-les deux fois :

Mot	Compte
Chirac	3 570 000
Chirac Chirac	2 170 000

La deuxième ligne fournit probablement le vrai compte...

---

Lire la suite

28 fév - MSN triche-t-il aussi ?
7 mar - Yahoo indexe plus de pages que Google
13 mar - Google ajuste ses comptes
23 mar - 5 milliards de "the" sont partis en fumée
25 mar - Un instantané sur la mise à jour

---