Les techniques évoluées d’indexation dans les moteurs de recherche

Les techniques de crawl ont beaucoup évolué en quelques années. Et de nombreux moteurs ont adoptés des technologies nouvelles, pas forcément très connues des webmasters. Ceux qui consultent leurs logs régulièrement ont pu remarquer des changements subtils dans le comportement de certains robots (Googlebot notamment). Nous allons vous en dévoiler les raisons, et les nouveaux objectifs assignés à ces crawlers.

Indexer vite, indexer tout, mais indexer poliment

La taille de la toile ne cesse d’augmenter. Cette croissance touche à la fois le nombre de pages, mais aussi la taille moyenne de chaque page. Par ailleurs, la part des pages de texte diminuent au profit des pages contenant des images, des videos, des animations flash etc…

Dans le même temps, la bande passante disponible pour crawler le web est toujours limitée. Il est donc indispensable, et même stratégique, d’optimiser les crawlers pour qu’ils puissent indexer la Toile de manière efficace. [*]

Cette efficacité se mesure en fonction de trois facteurs :

1°) L’indexation doit être rapide : c’est la condition sine qua non pour qu’un robot puisse passer souvent et assurer que les pages figurant dans l’index aient une « fraîcheur suffisante »

2°) L’indexation doit être complète : on sait qu’elle ne peut pas être exhaustive, car certaines portions du web ne sont pas reliées entre elles par des liens. Mais le robot doit être capable d’indexer une portion significative de la Toile

3°) Dans le même temps, l’indexation doit respecter les sites visités : notamment, le robot doit tenir compte des instructions du fichier robots.txt, et ne pas aspirer des centaines de pages à la seconde… [**]

Les enjeux d’une indexation efficace

Pour développer un moteur de recherche encore plus pertinent, il convient d’améliorer les techniques d’indexation dans trois domaines différents.
* D’abord, savoir indexer toujours plus de formats de fichiers différents.
* Ensuite, indexer plus de pages, plus vite, et de manière opportune pour conserver la fraicheur de l’index.
* Enfin, savoir indexer plus de pages dynamiques.

Le problème de l’indexation des formats de fichiers non textuels ou exotiques, et celui des pages dynamiques ne seront pas abordés ici. Ils nécessitent chacun un développement complet.

La fraîcheur de l’index quant à elle représente un enjeu important. Il était mal géré par la plupart des moteurs de recherche grand public jusqu’à une époque récente : et encore aujourd’hui, il n’est pas rare de se voir renvoyer une erreur 404 en cliquant sur une page de résultats. Or les pages « d’actualité » se multiplient sur la Toile, et le rythme de changement des pages ne cesse d’augmenter.


Fréquence de changement des pages sur le web – extrait de [1]

Dans le même temps, le rythme de « mise à jour » varie dans des proportions extrêmes d’un site à l’autre, et même souvent entre les pages d’un même site. Imaginer des stratégies de crawl qui tiennent compte de ces facteurs constitue donc une nécessité si l’on ne veut pas, soit crawler souvent des pages qui ne changent pas, et consommer des ressources utiles, soit crawler de manière trop espacée et rater des changements intermédiaires…


Fréquence de changement des pages en fonction des domaines – extrait de [1]

Les méthodes traditionnelles de crawl : le batch crawling

La méthode de crawl la plus communément utilisée jusque là était l' »indexation par lot » (« batch crawling » en anglais.

Le batch crawling se déroule en trois étapes.

D’abord, on détermine une série d’urls de départ à crawler (les  » seed url « ). La taille de ce fichier d’urls et la manière de les choisir a d’ailleurs une influence certaine sur le résultat final. Il suffit de penser à ce qui peut se passer si l’on ne choisit que les adresses de site ne figurant que dans une seule catégorie DMOZ par exemple : l’index qui sera créé risque d’être sérieusement « coloré » par ce choix, et des pans entiers du web ne seront pas indexés.

Ensuite, on lance les robots d’indexation qui vont « aspirer » les pages, tout en récupérant les liens qu’elles contiennent vers d’autres pages.

Ces nouvelles url sont ajoutées à une « file d’attente » des liens qui restent à explorer. Lorsque cette file d’attente ne contient plus de nouvelles url, le processus s’arrête. Le crawl est terminé. Et l’on considère que la Toile entière a été indexée.

Les urls ainsi recueillies pendant le crawl serviront par ailleurs d’urls de départ au prochain cycle de crawl…

Ce processus de « batch crawling » décrit en fait ce que les webmasters observaient sur leur site lors des full crawls de Google jusqu’au printemps 2003. La version « deep crawl » de Googlebot était un « batch crawler » typique.

Les inconvénients du batch crawling

L’indexation par lots a de graves inconvénients, dès que l’on veut développer un moteur de recherche « grand public » comportant un très grand nombre de pages. D’abord les crawlers indexent l’ensemble des pages à chaque cycle, y compris celles qui ne changent jamais. Le processus est donc long, il dure dans la pratique plusieurs jours, jusqu’à une semaine complète. Or, c’est seulement à la fin du processus que l’on déclarera l’index « complet » et « bon pour le service ». Le problème, c’est que certaines des pages sont déjà obsolètes à la fin du processus. D’autres auront disparu. De nouvelles pages auront été mises en ligne, et ne figurent pas dans l’index.

Bref, ce n’est pas un moyen très efficace de gérer le problème de la fraîcheur des pages. Google, qui lançait un « full crawl » par mois, se retrouvait donc avec un index dont la fraîcheur posait problème. La solution adoptée pour compenser le problème consistait à lancer un robot différent « le fresh crawler » destiné à détecter de nouvelles pages apparues entre deux « full crawl ».

De nombreux chercheurs ont donc réfléchi à des solutions alternatives ou à des perfectionnements de la méthode. La plupart des travaux ont abouti à la création d’agents d’indexation spécialisés, extrêmement efficaces pour « aspirer » et « surveiller » des portions limitées du web. Parmi ces travaux, on peut citer les techniques de crawling ciblé (focused crawling) et de crawl intelligent (intelligent crawl), ou les techniques de crawl s’appuyant sur des algorithmes génétiques.

Mais la taille de la Toile dans son entier pose des problèmes particuliers, et les pistes efficaces pour résoudre le problème à cette dimension sont moins nombreuses.

Philippe YONNET

Suite de cet article : cliquez ci-dessous
Les techniques évoluées d’indexation dans les moteurs de recherche (2e partie)


[*] Est-il possible de crawler toutes les pages de la Toile ?

Si on remonte à deux ou trois ans seulement, il était communément admis que la croissance du WWW était exponentielle, et que face à cette explosion, indexer l’ensemble de la Toile était totalement illusoire. Aujourd’hui, les données ont un peu changé.
La puissance des machines d’indexation continue de croître selon la loi de Moore et la bande passante utilisable a également progressé dans des proportions notables. Surtout, la capacité des supports de stockage magnétique s’est développée de manière extraordinaire, et l’on peut faire tenir plusieurs dizaines de Teraoctets dans un volume de la taille d’une commode !
Dans le même temps, la vitesse de croissance du nombre des pages webs n’est plus du tout exponentielle ! Les dernières évaluations laissent penser que le rythme de cette croissance diminue.
Bref, il y’a encore un avenir pour les moteurs dont l’ambition est d’indexer toutes les pages de la Toile accessibles par les techniques de crawl actuelles ou futures… Reste à savoir si un moteur dont l’index est de la taille du web est forcément utile ou plus pertinent. Rien n’est moins sûr, et le débat n’est pas près d’être clos…

[**] Une solution classique à ce problème est celui du  » round robin logiciel  » : les urls à crawler ne sont pas choisies n’importe comment, un programme choisit un groupe de sites à crawler, et au lieu de visiter toujours le même site, change le site crawlé à chaque fois, pour espacer les visites.

[1] http://citeseer.nj.nec.com/cache/papers/cs/20215/http:zSzzSzwww-db.stanford.eduzSz~chozSzpaperszSzcho-incre.pdf/cho99evolution.pdf
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