Comment fonctionne un moteur de recherche ? (2ème partie : index inversé et duplicate content)

Mais, si on réfléchit à l’enjeu principal du moteur de recherche qui est de pouvoir répondre rapidement à la requête d’un utilisateur, on pressent qu’il y a un problème avec une telle structure. En effet, l’exemple de l’internaute cherchant la requête “moteur” met en exergue ce souci : récupérant la requête, le moteur de recherche doit trouver un ensemble de pages susceptibles d’intéresser l’internaute. Imaginons, pour simplifier les choses, que les bonnes pages sont celles qui contiennent le mot “moteur” (ce serait un processus d’analyse bien basique, et nous verrons en détails dans les prochains mois que c’est effectivement plus complexe que cela).

Fig. 1. Stockage « basique » en base de données.

Le moteur de recherche, pour trouver les pages adéquates dans son index, doit prendre chaque page une par une, puis regarder si dans le contenu associé, le mot “moteur” est présent… un index de 10 pages implique donc d’interroger 10 enregistrements de la base, tandis qu’un index de 30 mille milliards de pages implique d’interroger 30 mille milliards d’enregistrements. Même en supposant que récupérer un enregistrement ne nécessite qu’une fraction de seconde, on se rend bien compte que le retour vers l’utilisateur demanderait vraiment beaucoup - trop - de temps. Dès lors, le stockage des contenus textuels ne peut être fait uniquement de cette façon.

Comment rendre les choses plus rapides ?

Il faut donc avoir une structure qui permette une interrogation plus rapide, c’est-à-dire qui permette de consulter moins d’enregistrements pour obtenir la même réponse. Cette autre structure, c’est ce que l’on appelle l’index inversé.

Plutôt que d’avoir des pages qui contiennent des contenus, on décide que ce sont les mots qui envoient vers des pages. Le nombre de mots (toutes langues confondues ou non) étant assez limité par rapport au nombre total de pages sur le web, on réussit alors à obtenir des résultats bien plus rapidement.

Dans le cadre de l’exemple, chercher “moteur” implique seulement de trouver le mot parmi l’ensemble des mots que l’on connaît, et l’on obtient aussitôt une liste exhaustive de toutes les pages qui contiennent ce mot.

Fig. 2. Un stockage plus efficace en inversant l’index.

De la même façon, la liste des mots connus est sujette à caution. Par exemple, quand on sait que “the” et “off” en langue anglaise sont présents dans la quasi-totalité des contenus, ne peut-on pas simplement ne plus les prendre en compte, car ils ne permettent pas de faire de différence entre les pages ?

Comment inverser l’index ?

Créer l’index inversé est très coûteux (en termes de ressources informatiques, et donc, de fait en terme de coût pur), mais c’est une tâche besogneuse et systématique, qui peut être aisément parallélisée. Pour cela, on peut utiliser un procédé de calcul distribué, comme par exemple MapReduce. 

Voyons donc comment cela fonctionne. Map et Reduce sont des fonctions spécifiques que l’on retrouve dans de très nombreux langages (python, ocaml, etc.).

Map est une fonction qui prend en entrée une fonction de calcul (appelons la F) et une structure de données (la plupart du temps une liste d’éléments). Map va alors utiliser la fonction F sur chacun des éléments de la structure de données, de manière indépendante, et va renvoyer le résultat de la fonction sur chaque élément.

Par exemple, supposons que F soit une fonction qui calcule le carré d’un nombre, et que la structure de données soit la liste (1,2,3,4). Map(F,(1,2,3,4)) va calculer indépendamment (par exemple sur des processeurs séparés) les carrés et renvoyer (1,4,9,16).

Reduce est une fonction qui va également agir sur une structure, mais sur l’intégralité de cette dernière et non pas sur chaque élément séparément. Ainsi, on peut utiliser Map et Reduce pour, par exemple, calculer la somme des carrées de la liste (1,2,3,4). Pour cela, on fait Reduce(+,Map(^2,(1,2,3,4)) pour obtenir très rapidement le résultat 30.

La figure 3 est une illustration intuitive du concept de Map Reduce : pour colorier une grande image, on colorie des petits bouts indépendamment, et on les rassemble après avoir bien fait attention de choisir des couleurs compatibles en communiquant entre travailleurs “indépendants”.

Fig. 3. Schéma de principe du MapReduce.

Au final, MapReduce n’est ni plus ni moins qu’un framework pour faire du calcul distribué sur de très grands ensembles de données. Imaginons que l’on se consacre à travailler sur un crawl du web dans son intégralité et qu’on veut réaliser rapidement une tâche coûteuse, comme par exemple inverser un index.

La première étape est de couper l’index en petits blocs qui peuvent être traités par une machine de calcul raisonnable.
Puis chaque machine de calcul inverse sa partie d’index : c’est l’étape de mapping. Une fois que c’est fait, chaque machine envoie le résultat de son inversion locale à une seule machine, le maître, et ce dernier va faire l’étape de réduction. Pour cela, il va recombiner les différents index inversés, en faisant une gestion correcte des recoupements. Pour l’inversion d’index, on effectuera de nombreux recoupements puisqu’un même mot peut se trouver dans plusieurs index inversés.

Utiliser MapReduce est nécessaire, et a beaucoup d’avantages : calcul plus rapide, mais aussi robustesse aux crashs de machine (si une machine de calcul tombe en panne, on refait une petite inversion, tandis que si on inverse tout d’un coup il faut refaire un calcul très complexe depuis le début). En revanche, tous les problèmes ne peuvent pas être résolus par une approche de type MapReduce (notamment les problèmes qui nécessitent de nombreuses communications entre machines de calcul).

Dernier point pour préciser que l’approche MapReduce a été nommée ainsi par Google, mais que ce n’est rien de plus qu’une variation de la notion de squelettes algorithmiques mise au point par Murray Cole et son équipe au début des années 90.

Comment est stockée la structure impulsée par les liens

Lorsque l’on parle de l’indexation, on pense d’abord aux contenus des pages, mais on oublie un peu vite que le moteur de recherche a également besoin de stocker les liens entre les pages. Ces liens seront utilisés deux fois. Une première fois pour réaliser un crawl extensif. Et la liste des liens sortants de chaque page sera également indexée pour nourrir ce que l’on appelle la frontière des URL et donc créer l’ensemble des pages connues mais restant à crawler.

La deuxième utilisation des liens par le moteur est critique : il s’agit de s’en servir pour le calcul de plusieurs quantités qui permettent de mieux classer les pages. Nous évoquerons par exemple dans un prochain article de la lettre d’Abondance les notions de PageRank et d’indice de confiance. Il existe d’autres quantités importantes, comme par exemple le nombre de liens entrants vers une page, qui peut être utilisé dans le cadre de la détection de fermes de liens (structures typiques des opérations de netlinking « agressif » pour ne pas dire spammy).

Pour toutes ces tâches, il faut créer des structures de données spécifiques car stocker brutalement la liste des liens page par page n’est pas une solution techniquement satisfaisante.

Pour rentrer un peu dans la technique, il existe trois possibilités pour stocker le graphe sous-jacent au web (car le web est un graphe : des noeuds reliés par des arcs).

• Matrice d’adjacence
C’est la structure la plus simple, qui prend beaucoup de place en mémoire et qu’on veut donc éviter, même si elle permet de travailler sur le graphe d’origine directement. Une matrice d’adjacence est tout simplement un tableau qui a autant de lignes et de colonnes qu’il y a de pages dans l’index (oui, un tableau avec des milliards de lignes et colonnes pour un moteur moderne).
Chaque case du tableau contient un 1 s’il y a un lien sortant de la page correspondant à la ligne vers la page correspondant à la colonne.

• Liste d’adjacence
Les liens sortants de chaque page sont stockés sous forme de listes dans un tableau qui a autant de lignes qu’il n’y a de pages dans l’index. La première ligne du tableau va donc, par exemple, contenir la liste des pages qui ont un backlink depuis la première page.

• Double liste ou matrice d’adjacence non orientée
Il s’agit de modifications des structures précédentes pour pouvoir “remonter” les liens, ce qui est indispensable pour certains algorithmes de filtrage du webspam. Par exemple, si on part du principe qu’il faut pénaliser les pages qui pointent vers des pages de spam, il faut pour réaliser cette pénalisation être capable de remonter à la source des liens qui pointent vers une page de spam bien choisie. Sans une structure ad-hoc, il faut parcourir tout l’index pour réaliser le filtre, ce qui n’est pas raisonnable en termes de coût.

Analyser les pages au moment de l’indexation

La grande qualité d’un moteur de recherche, c’est d’avoir un bon index. En effet, si un moteur de recherche dispose d’algorithmes incroyables pour répondre avec pertinence aux demandes des internautes qui font des recherches, mais ne possède pas un bon index, il ne sera pas en mesure de renvoyer de bonnes pages.

L’exemple est ici facile : prenons un index de millions de pages, mais ne contenant aucune page traitant de réparation de voiture. Un internaute soucieux de réparer lui-même son automobile ne pourra jamais trouver son bonheur... Quel que soit le traitement opéré par le moteur sur son index.

Indexer les bonnes pages et éviter les pièges lors de l’indexation est donc une problématique essentielle, même si elle n’est pas suffisante, pour un moteur de recherche.

Le bon index et le biais

Pendant longtemps, on ne se préoccupait que d’une chose dans la création d’un index : qu’il soit le plus exhaustif possible. Mais désormais, les moteurs essayent d’avoir une attitude plus responsable envers la qualité de l’information et veulent notamment éviter les biais. Pour cela, un bon index doit être équitable, c’est-à-dire que toutes les informations doivent avoir la même probabilité de chance d’être intégrée à l’index. Il est important de noter que cette notion d’index équitable reste un vœux pieux à l’heure actuelle, les algorithmes de parcours du Web pour le crawl n’étant pas encore assez matures pour réaliser ce type d’index (mais les moteurs y travaillent).

Pour être exhaustif, un bon index doit couvrir le plus de sites web possibles, et pour cela, les politique de parcours lors du crawl vont favoriser la réalisation d’une multitude de sauts d’un site à un autre pour maximiser le nombre de sites visités et éviter de tomber dans un “spider trap”, c’est-à-dire un site sur lequel le robot d’indexation va rester très longtemps et va prendre des millions de pages. Cette stratégie est coûteuse puisqu’elle implique de garder en mémoire une frontière des URL très larges, ce qui est peu efficace en termes de gestion des infrastructures.

Trouver les pages candidates à l’indexation

Afin de repérer les pages à insérer dans l’index, le moteur de recherche se base avant tout sur un crawl du Web. Il part d’une liste d’URL connues et, en suivant les liens, récupère éventuellement de nouveaux contenus, comme on a pu le voir le mois dernier. Il est cependant complexe de crawler à grande échelle : il faut explorer intensivement vu les volumes en jeu sur le Web, tout en faisant attention à ne pas mettre en difficulté les serveurs web, tout en évitant les pièges ou les erreurs techniques et tout en respectant les bonnes pratiques.

Enfin, certains contenus ne sont pas indexables, du fait de leur non prise en charge par les moteurs de recherche, tandis que d’autres sont des contenus de faibles qualités, vides, ou vus partout ailleurs sur le Web, ou qu’il faut mettre à jour pour rester pertinent… il y a beaucoup à faire pour ce qu’on appelle l’indexation et qui se mêle étroitement au crawl.

Le problème des contenus non indexables

La principale problématique que peut rencontrer un robot d’indexation est de se retrouver face à un contenu dont il ne sait quoi faire. Par exemple, Google lit parfaitement bien les pages html, ou encore les PDF. Mais qu’en est-il des contenus insérés via du Javascript ? (réponse : en ce moment, il semble plutôt disposé à les prendre en compte) ou encore des contenus en Flash (réponse : ça existe de moins en moins), des images ? (réponse : c’est le texte contextuel - l'attribut ALT et le texte dans la page - qui semble avant tout permettre de comprendre les images au niveau de l’indexation du Web).

On l’aura compris, le Web, c’est avant tout du texte, et même si les avancées en détection d’éléments dans les vidéos et les images sont grandioses, elles ne semblent pas encore assez avancées pour être utilisées au niveau global.

Ensuite, il existe des contenus que le moteur aimerait récupérer. Mais la présence d’instructions explicites de non indexation l’empêche de le faire. On parle ici de balises ou de headers, ou de fichier robots.txt mis en place par le webmaster d’un site.
C’est une problématique assez importante pour Google, par exemple, puisqu’il est recommandé de ne pas indexer certains types de pages (résultats de moteurs de recherche internes par exemple) tandis que la syntaxe d’un fichier robots.txt prête encore à confusion chez beaucoup, la faute à une apparente simplicité mais en réalité une complexité dans les comportements du robot.

Le moteur a pour idée de pousser les webmasters à ne pas limiter l’indexation, sauf pour les pages qui de toute façon n’auraient pas d’intérêt pour lui.

Le problème de la mise à jour des contenus

Chaque jour, des millions de pages apparaissent sur le Web. Dès lors, le moteur de recherche, afin de rester pertinent et dans l’actualité, doit être capable d’ajouter de nouveaux contenus rapidement dans son index, voire même mettre à jour un contenu déjà présent. C’est une tâche difficile car elle implique de devoir revenir souvent sur les mêmes pages afin d’y détecter l’apparition de nouveaux liens. Par exemple, la page d’accueil d’un site de journal en ligne un peu populaire est crawlée des centaines de fois par jour.

Cela implique qu’un nouveau contenu qui ne serait pas efficacement lié par une page déjà connue par le moteur de recherche risque de ne jamais être vue, ou à retardement.

De même, le moteur doit tenir à jour son index afin d’être capable de détecter si les pages qu’il va renvoyer à l’internaute peuvent avoir des problèmes d’accessibilité, temporaires ou non.

On le sait, Wikipedia est un site très visible dans Google. Des millions d’internautes se voient proposer chaque jour des pages de Wikipedia dans leurs résultats de recherches. Si Wikipedia tombe en panne, les internautes vont subir une mauvaise expérience utilisateur, ce qu’il faut, pour le moteur de recherche, éviter à tout prix. Le moteur doit ainsi être capable de rapidement mettre de côté les pages injoignables, et être tout aussi prompt à les ramener dans ses résultats une fois l’anomalie corrigée.

C’est un enjeu particulièrement déterminant qui permet d’éviter une mauvaise perception par le public, même si l’indisponibilité des pages n’est nullement la faute du moteur de recherche.

Le problème des pages sans contenus ou dupliquées

Un autre type de contenus problématiques, est le contenu qui n’en est pas. C’est-à-dire des pages qui n’ont aucun intérêt pour l’internaute, voire même des pages qui sont complètement vides. Par exemple, les pages de moteurs de recherche internes ne présentent pas de valeur ajoutée du point de vue du moteur de recherche, et c’est même de la pollution : indexer des pages qui présentent des résultats déjà classés, quoi de pire !?

De la même façon, les pages de listings, de plan de site, etc. n’ont que peu de valeur pour un moteur de recherche : elles sont très importantes pour découvrir de nouvelles pages, pouvoir crawler l’entièreté d’un site, mais elles sont superflues en tant que résultats à afficher à l’internaute. Qui voudrait cliquer sur un résultat du moteur de recherche pour se voir proposer à nouveau un choix plutôt que directement le bon contenu ?

Détecter les pages de listing, les pages de résultats de moteur de recherche interne, etc. est plutôt aisé : elles répondent généralement à une typologie particulière où l’on rencontre beaucoup de liens et peu de contenu en volume, ou du contenu haché (10 résultats = 10 URL et 10 petites phrases, le tout bien structuré).

Cependant, si c’est assez facile à détecter, on ne peut s’affranchir de les crawler au départ, puis de lancer une analyse particulière. Ainsi, Google, par exemple, propose des balises spécifiques pour que le webmaster puisse indiquer si l’on est sur une page de ce type, ce qui évite une surcouche algorithmique à appliquer de suite.

Les pages vides, elles, sont encore plus faciles à détecter. Ce sont des pages où il n’y a que la navigation, les sidebars, mais pas de réel contenu. Il existe des algorithmes tout à fait capables de détecter l’absence d’un contenu, mais surtout, sur un même site, plusieurs pages qui ont un contenu central trop pauvre vont se trouver être en situation de contenu presque dupliqué.

Comment détecter le contenu dupliqué ?

Etre capable de détecter rapidement les copies multiples d’un même contenu est une tâche cruciale pour un moteur de recherche, qui peut ainsi éviter d’indexer du contenu (c’est une économie financière) qui n’apporte pas d’amélioration à la qualité perçue (car le contenu en question est déjà indexé via d’autres pages).

Nous nous intéressons ici au contenu en quasi-duplication, ce qu’en anglais on appelle « near-duplicate ». Il existe de très nombreuses méthodes pour déterminer si un contenu est une version quasi-dupliquée d’un autre contenu. Mais revenons d’abord sur la méthode des shingles de Broder, Glassman, Manasse et Zweig (1997).

La méthode des shingles a pour objectif d’approximer la distance d’édition avec mouvements. La distance d’édition avec mouvements (EDM pour Edit Distance with Moves) entre deux textes correspond au nombre minimum de mots qu’il faut supprimer, ajouter ou inverser pour passer d’un texte à l’autre.
Par exemple, la distance entre :
Olivier Andrieu est fan d’Astérix
et
Olivier Andrieu est fan d’Astérix et Obélix
a une valeur de 2 car il suffit de rajouter les mots “et” et “Obélix” pour obtenir la deuxième phrase à partir de la première.

Comme trop souvent pour des problèmes en apparence simple, le calcul n’est pas faisable sur un volume de données du niveau d’un index web.

Il faut donc trouver un autre moyen de caractériser la distance entre les textes. Pour travailler sur un ensemble de données plus petit, on va utiliser une représentation simplifiée des textes. Pour être exact, on va utiliser une représentation des textes sous forme de shingles. Shingles et n-gram, c’est la même chose. Il s’agit donc d’un ensemble de n mots consécutifs d’un texte. Tous les shingles d’un texte couvrent complètement le texte, et ils se recouvrent entre eux.

Par exemple, le texte suivant :
Olivier Andrieu est fan d’astérix
a pour shingles de taille 3 : « Olivier Andrieu est  »,  « Andrieu est fan » et « est fan d’astérix ».  Quand on veut travailler sur des textes, on va donc fixer arbitrairement la taille des shingles qu’on considère.

Une fois qu’on a construit pour chaque texte son ensemble de shingles, on va pouvoir définir une distance entre les textes en calculant l’intersection et l’union des ensembles de shingles. Reprenons l’exemple d’Olivier, Astérix et Obélix.

Soit A l’ensemble de shingles de la première phrase, et B celui de la deuxième phrase. On a :
A = {Olivier Andrieu est ; Andrieu est fan ; est fan d’astérix}
B = {Olivier Andrieu est ; Andrieu est fan ; est fan d’astérix ; fan d’astérix et ; d’astérix et obélix}

L’intersection entre A et B est {Olivier Andrieu est ; Andrieu est fan ; est fan d’astérix}, elle contient 3 shingles. L’union entre A et B est {Olivier Andrieu est ; Andrieu est fan ; est fan d’astérix ; fan d’astérix et ; d’astérix et obélix}, elle contient 5 shingles.
On va ensuite pouvoir calculer le coefficient de Jaccard entre les deux ensembles.
A ∩ B est l’intersection entre A et B. A ⋃ B est l’union entre les deux ensembles. Ici le coefficient de Jaccard vaut donc 3/5.
Plus le coefficient de Jaccard est haut (c’est-à-dire proche de 1), plus les textes sont en duplication.

Même si le calcul des shingles est simple, il reste encore un peu trop coûteux pour un moteur de recherche, et c’est pour cela que des méthodes encore plus rapides ont été mises au point. Abordons maintenant une telle méthode.

Détecter le contenu dupliqué grâce au simhash

Afin de pouvoir comparer efficacement une page nouvellement crawlée à celles déjà dans l’index, le moteur va avoir recours à des méthodes de comparaisons approchées qui sont nettement plus rapides. L’une de ces méthodes à été développée par Moses S. Charikar et s’appelle simhash. Le grand principe derrière cette méthode est de ne pas comparer les objets directement (ici les pages web) mais de petites “empreintes” de ceux-ci. L’idée étant que si les empreintes sont proches, alors les documents doivent l’être aussi.

Les empreintes sont calculées à partir de l’ensemble des shingles d’un document sur lequel on va appliquer un ensemble de fonctions de hachage pour obtenir une empreinte de quelques dizaines de bits. Comparer les empreintes est ensuite un processus extrêmement rapide qui peut être effectué efficacement par un moteur de recherche.

Tout la difficulté de cette opération consiste à trouver une famille de fonctions de hachage qui permettent de “conserver” la distance entre les documents, i.e. les empreintes doivent être similaires si les documents le sont aussi et elles doivent être réellement différentes si les documents n’ont pas grand-chose à voir.

Fort heureusement, il existe des familles de fonction connues qui remplissent parfaitement ce rôle.

L’utilisation d’un algorithme comme simhash permet au moteur de détecter les contenus très proches lors du crawl ce qui lui évite d’encombrer inutilement son index avec de l’information qu’il possède déjà.

Conclusion

Dans cette deuxième partie du dossier consacré au fonctionnement d’un moteur de recherche moderne, c’est la notion d’index et d’analyse succincte des pages qui nous a intéressée. Comment un moteur décide-t-il qu’une page doit être indexée, comment juge-t-il, au premier coup d’oeil, de sa qualité (même minimale) ? Comment le moteur stocke-t-il la “carte du web” ?

On a pu voir qu’à un moment situé entre le passage du robot et l’indexation d’une page - son insertion dans une base de données - le moteur est tout à fait capable de qualifier la page selon des analyses rapides à effectuer : le contenu est-il pauvre ? Est-il dupliqué ?

Maintenant que le moteur possède de son côté une copie structurée du Web qu’il a décidé de considérer, il va devoir lancer des traitements plus importants, plus poussés d’un point de vue algorithmique, afin de pouvoir, assez rapidement, associer des pages à des requêtes faites par un utilisateur avec une notion forte de pertinence, c’est-à-dire d’intérêt pour l’utilisateur.

Le mois prochain, c’est la notion du calcul de la popularité des pages par rapport à la carte du Web qui sera analysée en profondeur ici. Nous aborderons ainsi le fameux algorithme du PageRank dont tout le monde parle, que certains pensent désuet, et qui est pourtant toujours au coeur des algorithmes du moteur de recherche.

Cette étape, véritable facteur révolutionnaire chez Google - nous en reparlerons en détail -, sera suivie les mois suivants par l’analyse des requêtes des utilisateurs et par l’analyse des contenus textuels. Nous n'avons pas fini de vous parler de moteurs de recherche... 😉