Dans la première partie, nous avons évoqué l’enjeu pour un moteur de recherche de disposer d’un index à jour. Et nous avons expliqué comment la technique traditionnelle du "batch crawling" représentait de ce point de vue un obstacle pour atteindre cet objectif :
Les techniques évoluées d’indexation dans les moteurs de recherche

Nous allons voir que de nouvelles techniques de crawl permettent de bien meilleurs résultats. Et que ces techniques sont d’ores et déjà utilisées par les principaux moteurs de recherche.

Une solution : indexer plus souvent les pages les plus importantes

C’est la piste proposée par Cho et Garcia-Molina [1][2]. Les deux chercheurs américains sont partis du principe que la Toile représente un volume global de données qui atteint (c’est une estimation indirecte, valable au moment de la publication de l’article) plusieurs téraoctets de données. Gérer une telle quantité d’information représente déjà un défi gigantesque sur le plan technique. Mais toute cette masse de données n’est pas forcément utile pour la plupart des utilisations classiques d’un moteur de recherche, il n’est donc pas absurde de "limiter" la taille de l’index, de manière arbitraire, à une portion de cet ensemble, sans dégrader gravement la pertinence des résultats.

Cho et Garcia Molina se sont donc attachés à améliorer la qualité d’un index de taille fixe et limitée. Cette approche convient notamment si l’on souhaite développer un moteur performant, mais avec des ressources limitées. Elle privilégie la fraîcheur et la qualité de l’index, par rapport à l’exhaustivité.

Le fondement de cette approche repose sur une évaluation de l’importance des pages. En effet, la qualité d’un index limité reposera sur la possibilité d’indexer toujours les pages "importantes", et jamais les pages "sans importance".

Le problème est de définir les bons critères pour évaluer l’importance d’une page...

La technique proposée par Garcia et Molina repose sur une combinaison des critères possibles suivants pour attribuer à chaque url une note d’importance :
1°) La similarité avec une requête donnée (évaluation sémantique)
2°) Le décompte des backlinks pointant vers cette page
3°) Le pagerank (dans ce cas, tous les backlinks n’ont pas la même valeur)
4°) Le décompte des forwardlinks
5°) La localisation des pages (note dépendant du TLD, de la position dans l’arborescence)

Une fois que l’on a défini une fonction d’évaluation de l’importance de la page, on peut s’en servir pour déterminer de manière plus intelligente l’ordre de crawl pour les pages, en indexant toujours de manière prioritaire les pages dotées de la meilleure note d’importance...

A noter que les travaux de Cho et Garcia-Molina ont montré que s’il ne fallait se baser que sur un seul de ces critères, le pagerank fournissait l’évaluation la plus efficace.

Le crawler incrémental

Par la suite, les deux chercheurs ont travaillé sur une application de cette fonction d’évaluation des pages à un crawler "incrémental". Un tel robot d’indexation, par opposition à la technique d’indexation par lot, ne s’arrête jamais. Il ne s’agit plus d’aspirer tout le web et de s’arrêter, pour recommencer à zéro plus tard. Un crawler incrémental a pour mission de déterminer quelles pages sont susceptibles d’être devenues obsolètes, et de les mettre à jour.

Cette approche incrémentale est beaucoup plus économique en ressources, car elle évite en théorie d’avoir à crawler des pages qui n’ont pas changé. Et il devient possible d’adapter la périodicité des crawls à la fréquence de changement des pages d’un site donné. Le cycle de crawl n’est plus uniforme : il varie d’un domaine à un autre. [*]

Une telle technique n’est utilisable que si l’on a pris soin d’évaluer préalablement la fréquence de changement des pages dans un site donné. Et il faut séparer ici deux évolutions différentes : la disparition de pages et l’apparition de nouvelles d’une part, et les changements de contenu dans une page donnée d’autre part. Un moteur de recherche qui décide de s’appuyer sur les techniques incrémentales a donc besoin, pour que l’indexation soit pertinente, d’ attendre un certain délai pour collecter des informations fiables sur la manière dont l’index évolue. Il convient par la suite de mettre à jour ces informations, et de lancer, périodiquement, un "batch crawling" général pour éviter une dérive de l’index.

L’ordre de crawl, dans le robot d’indexation proposé par Garcia-Molina et Cho, est donc finalement déterminé en fonction de deux groupes de critères différents :
l’importance des pages
et leur probabilité d’obsolescence...

Un crawler incrémental, sur une base ouverte (L’exemple de Webfountain)

Jenny Edwards, une spécialiste australienne des robots d’indexation, a proposé une méthode similaire, mais capable de fonctionner non pas sur un index limité, mais sur un index ouvert, et de taille variable[3][4]. Ses travaux ont trouvé leur application dans le nouvel outil de recherche d’IBM : Webfountain, avec le crawler baptisé "Seeker".

Pourquoi un index ouvert ? Parce qu’au sein de "Big Blue", Jenny Edwards savait qu’elle pouvait disposer de stations de travail ultra-puissantes, d’une bande passante très importante, et de capacité de stockage sans équivalent. Travailler sur une solution flexible, capable de suivre la croissance de la Toile n’était plus une utopie avec de tels moyens.

Dans ce cas, l’adjectif "incrémental" prend une signification légèrement différente. Il ne s’agit plus de mettre à jour un index fixe, mais de mettre à jour les pages existantes de l’index.

Seeker ne tient pas compte de l’importance des pages, mais uniquement de leur rythme de changement. Sa particularité est de "séparer" le traitement des urls, en fonction de leur fréquence de mise à jour... Ce qui permet de traiter différemment les sites d’actualités, des sites qui ne disposent que de pages fixes rarement modifiées.

L’autre enjeu : crawler le web invisible

Un autre problème a toujours préoccupé les concepteurs de robots d’indexation : comment crawler certaines pages inaccessibles aux moteurs de recherche traditionnels ?
Les causes de cette inaccessibilité sont multiples :

informations illisibles par les robots (textes dans des images)

zones protégées par un robots.txt

code de pages non valides, ou liens en javascript, empêchant les robots de suivre ces liens [1]

pages protégées par des mots de passe

pages accessibles uniquement après avoir complété des formulaires

cloaking : les pages vues par les robots ne sont pas celles vues par les internautes
Tous ces cas de figure ont été détaillé dans un article de 2001 rédigé par Garcia Molina et Raghavan "Crawling the Hidden Web" [5], dans lesquels ils décrivent le fonctionnement d’un robot capable de crawler une partie du "Web Insivible" baptisé HiWE.
La figure ci-dessous synthétise ce que peuvent voir les robots traditionnels et le robot Hiwe.

On voit qu’une partie du Web reste toujours inaccessible... cela reste l’une des limites que nombre de chercheurs cherchent à repousser, notamment dans le cas d’applications de "veille technologique", un terme choisi pour parler en fait d’"espionnage".

Vers le niveau de fraîcheur optimal ?

Toutes ces techniques évoluées permettent d’améliorer le niveau de "fraîcheur" des index.

Si l’on considère la Toile dans son ensemble, disposer d’un index parfaitement à jour reste toutefois encore une utopie. Mais pour celui qui veut développer un moteur d’actualités, la démonstration est faite qu’il est parfaitement possible d’élaborer un crawler capable de maintenir son index à jour, même si elles s’avèrent changer plusieurs fois par heure.

Les techniques de crawl évoluées dotent les moteurs de recherche, jadis un peu myopes, de capacités d’indexation désormais très impressionnantes... C’est une avancée importante dans la problématique de la pertinence des résultats. Mais c’est dans l’amélioration de tous les autres maillons de la chaîne de production de ces résultats que se jouera l’avenir des moteurs de recherche ...

Philippe YONNET

BIBLIOGRAPHIE

[1]The Evolution of the Web and Implications for an Incremental Crawler
Junghoo Cho, Hector Garcia-Molina / Department of Computer Science Stanford, CA 94305
December 2, 1999

[2]Parallel Crawlers
Junghoo Cho / University of California, Los Angeles - Hector Garcia-Molina / Stanford University
2002

[3]Webfountain d’IBM : un moteur de recherche révolutionnaire
Philippe YONNET - Webmaster Hub
novembre 2003

[4]An Adaptive Model for Optimizing Performance of an Incremental Web Crawler
Jenny Edwards, Kevin McCurley, John Tomlin
25 février 2002

[5]Crawling the HiddenWeb
Sriram Raghavan Hector Garcia-Molina
Computer Science Department Stanford University
2001

[*] Le comportement d’un robot d’indexation incrémental décrit ici correspond trait pour trait à celui de Googlebot depuis quelques mois. Ce n’est probablement pas une coïncidence : le robot de Google semble fonctionner de manière incrémentale.

[1] ** à noter que Googlebot sait suivre depuis peu les liens en javascript, ainsi que ceux contenus dans des fichiers de type flash, ou pdf, sous certaines conditions

> Référencement et publicité