Comment fonctionne un moteur de recherche ? (1ère partie)

Maintenant que la définition de ce qu’est le Web a été faite, on peut parler de moteur de recherche. Un moteur de recherche est tout simplement un site web (ou une application sur smartphone, ou une API, etc.) dont l’objectif est de renvoyer des résultats pertinents pour la requête saisie par l’utilisateur (par exemple, si un internaute fait une recherche cherchant à trouver un appartement, le moteur de recherche aura certainement bien fait son travail si les résultats font apparaître des biens actuellement en vente).

C’est bien évidemment à ce moment-là que les choses se compliquent : qu’est ce qu’un résultat pertinent ? qu’est ce qu’une requête ?

En pratique, la requête est l’expression de ce que l’on appelle le besoin informationnel. Il s’agit de l’intention réelle qui est plus ou moins adroitement exprimée via une requête par l’internaute. Par exemple, l’internaute a peut-être pour besoin informationnel de savoir à quoi ressemble un jaguar (l’animal), mais il va inscrire la requête "jaguar" dans le moteur de recherche… Ce qui est ambigu puisqu’il est difficile de savoir s’il s’agit de l’animal ou de la célèbre marque de voitures de luxe. En effet, le besoin informationnel étant dissimulé dans le cerveau de l’internaute, le capter et donc le comprendre est difficile, d’autant plus que l’internaute fait certainement une recherche car il ne connaît pas quelque chose, et on peut donc s’estimer chanceux quand il est au moins capable de nommer cette chose (c’est l’histoire du client néophyte du référenceur qui dit "balise ALT" au lieu d’"attribut ALT" par exemple, en évoquant une modification du code html d'un image).

Si on résume, l’objectif pour le moteur de recherche est donc de comprendre le besoin informationnel de chaque utilisateur, puis de renvoyer une ou plusieurs pages web qui vont remplir ce besoin informationnel. Une fois le besoin compris, est-ce facile ? Bien évidemment non, pour plusieurs raisons que nous allons maintenant évoquer en détail.

1. Pour quasiment chaque requête, on peut trouver pléthore de pages pertinentes, mais le moteur ne doit en renvoyer que quelques-unes (par exemple une dizaine dans le cas de Google, puisque la première page, présentant généralement 10 résultats, est, de loin, la plus consultée par les internautes - quand ce n’est pas la seule). Il faut donc être capable de choisir les "meilleures des meilleures".
2. Comprendre le contenu d’une page est difficile : on peut exprimer de nombreuses idées différentes avec peu de mots, et comprendre les double-sens, l’ironie, les homonymies, etc. est très complexe.
3. Il faut répondre rapidement à l’internaute. Seriez-vous prêt à attendre dix minutes que le moteur sélectionne la meilleure page ? Non, vous auriez supprimé le moteur de recherche de votre barre de favoris en bien moins de temps que cela. Donc le moteur de recherche doit, et va, faire au mieux, mais dans un temps admissible pour ses visiteurs.
4. Il faut que le moteur génère des profits, fasse des bénéfices. Même si c’est dommage, il faut que le moteur soit rentable pour continuer ses opérations. Il n’est donc pas possible d’avoir des index de tailles invraisemblables et de faire des calculs trop coûteux. L’argent est un facteur limitant la qualité des résultats. Cela se voit d’ailleurs particulièrement lorsqu’on compare la qualité des résultats proposés par des nouveaux arrivants par rapport à ceux des moteurs importants (Google et Bing par exemple). Un moteur de recherche possédant des infrastructures techniques très performantes a réellement un avantage face à ses concurrents.
5. Les tricheurs existent. Eh oui, il existe des personnes qui essayent de manipuler les résultats des moteurs de recherche, afin de positionner dans les premières positions leurs propres sites (ou ceux de leurs clients). Oui, nous parlons bien des lecteurs de la lettre d’Abondance : les référenceurs web. Parfois le travail des référenceurs ne diminue pas la qualité des résultats (par exemple lorsqu’un travail conséquent sur la qualité de la rédaction est effectué), mais parfois ce n’est pas le cas (par exemple dans le cadre des opérations de netlinking). On parle d’ailleurs de "adversarial information retrieval" en anglais lorsqu’on désigne la recherche d’information sur le Web. C’est-à-dire qu’un moteur de recherche doit être capable de trier le bon grain de l’ivraie.

Schéma de principe d’un moteur de recherche

La figure 1 présente le schéma de principe d’un moteur de recherche. On y voit tous les grands blocs fonctionnels qui sont mis en branle pour répondre au besoin informationnel de l’internaute utilisateur du moteur. Il s’agit d’un schéma de principe, la réalité étant légèrement plus complexe. Par exemple, ce schéma laisse penser que le filtrage du spam n’est fait qu’en dernier recours, ce qui est inexact, les briques antispam sont actives dès le crawl du web par le robot du moteur. Pour comprendre les principes de base, ce schéma est cependant suffisant.

Fig. 1. Schéma de principe du fonctionnement d’un moteur de recherche

Nous allons passer en revue rapidement chacun de ses blocs, avant de rentrer dans les détails du premier. Les autres blocs seront abordés plus en détails au travers des articles des prochains mois.

Première étape : le crawl

La première tâche que doit remplir un moteur de recherche est le crawl du Web, c’est-à-dire le parcours de l’ensemble des pages que l’on peut trouver sur le Web. En effet, pour être capable de renvoyer des pages web pertinentes, il faut avoir vu et analysé le contenu d’une multitude de pages. C’est le robot d’indexation (ou crawler, ou bot, ou spider : Googlebot ou Bingbot pour les deux plus gros moteurs) qui remplit cette mission. Intuitivement, son fonctionnement est très simple : il va parcourir récursivement (l’un après l’autre) les liens hypertextes qu’il va trouver lors de son parcours, en partant d’un certain nombre de pages sources (seeds en anglais).

Si l’idée est simple, la réalisation est difficile, principalement car il y a un volume de données très grand à crawler, et que la structure dynamique du Web ne facilite pas le parcours du crawler sur le Web. En effet, un crawler "brutal" serait peu efficace car il passerait son temps à revenir sur les mêmes pages, ce qui n’est pas souhaitable en terme de dépense de bande passante. Pour un moteur, la stratégie de crawl et l’accélération de l’accès aux sites web est le nerf de la guerre. C’est par exemple pour cela que Google pousse sans cesse l’idée que le web doit proposer uniquement des sites rapides, c’est-à-dire qui répondent très rapidement. En effet, des sites rapides permettent à l’internaute d’avoir une expérience de navigation plaisante, mais cela permet également aux robots d’indexation de parcourir davantage de sites dans un même temps : plus les sites sont rapides, plus le crawl a un coût faible.

Deuxième étape : l’indexation

Nous avons choisi de séparer la présentation de l’indexation de celle du crawl, mais il s’agit bien évidemment de tâches qui sont réalisées conjointement. L’indexation, c’est l’insertion des données des pages crawlées au sein d’une structure de données globale : l’index du moteur. Cet index est l’actif principal du moteur de recherche, puisque c’est de cet index que seront extraites les réponses aux besoins informationnels des utilisateurs.

L’index contient essentiellement deux types d’information : une information structurelle qui décrit les liens entre les pages web (le graphe du Web, limité aux pages de l’index), et une information de contenu des pages. L’information de contenu utilisée est, de nos jours encore, principalement textuelle, même si de belles avancées ont été faites en matière de compréhension des images et des vidéos (notamment dans le domaine du deep learning, chez Google et Facebook, pour comprendre le contenu des images - voir [3] par exemple).

Troisième étape : l’analyse de l’importance

Si les moteurs de recherche stockent de manière différenciée l’information structurelle (les liens) et l’information de contenu (les textes des pages), c’est parce que la première va être traitée séparément et à l’avance, ce qui permet de répondre plus rapidement aux internautes lorsqu’ils saisissent une requête : inutile pour cette partie de faire des calculs à la volée. Vous l’aurez sans doute compris, ce que l’on appelle l’analyse de l’importance est essentiellement la création d’un classement des pages en fonction de leur popularité supposée, indépendamment de leur contenu. On parle ici de l’algorithme le plus connu de Google, le PageRank, qui est décrit dans l’article The PageRank citation ranking: bringing order to the web [4].

Quatrième étape : l’analyse de la requête

Avant de déterminer si une page est pertinente pour une requête, le moteur de recherche va travailler sur cette requête pour essayer de mieux la comprendre. Cette tâche passe par ce que l’on appelle une expansion de requête. Sachant qu’Amit Singhal, qui a été pendant très longtemps le responsable de l’équipe Qualité de Google (ce qui signifie qu’il était l’architecte principal du moteur), est à l’origine un chercheur spécialisé dans l’expansion de requête, on comprend ainsi bien pourquoi la requête à un rôle si central chez Google. C’est d’ailleurs avec la mise en place d’Hummingbird en 2013 que Google a explicitement annoncé faire un travail très poussé sur les requêtes pour mieux comprendre l’intention derrière les demandes de chacun de ses visiteurs.

Cinquième étape : l’analyse de la pertinence

Dans cette étape, le moteur va créer une représentation interne du contenu de chaque page qui va permettre de "comprendre" de quoi parle la page. En pratique, il n’y a pas vraiment de compréhension, mais plutôt la capacité à savoir quelles sont les pages qui abordent les mêmes sujets (ce que l’on va appeler un cluster thématique), et celles qui parlent de choses très différentes.

Sixième étape : le filtrage des comportements malicieux

Que ce soit en créant des backlinks de qualité douteuses, en générant du contenu au kilomètre avec des techniques de content spinning ou avec de la rédaction bas de gamme, en achetant des domaines expirés et en faisant des redirections 301, etc., chacun essaye à son niveau de manipuler le classement produit par Google. Mais le moteur riposte en continu, à tous les niveaux : dès le crawl et l’indexation, en repérant les contenus ne méritant même pas d’être indexés ;  au moment du calcul de l’importance pour diminuer l’impact de ce que l’on appelle des fermes de liens (sous forme de PBN pour Private Blog Networks chez les référenceurs web) ; lors de l’analyse de la pertinence (filtre Panda par exemple), ou enfin en filtrage lors de la création du classement. Le va-et-vient incessant entre l’attaque des uns et la défense des autres est d’ailleurs ce qui occupe quasiment à plein temps les discussions des référenceurs web, et qui permet à cette lettre d'exister (en partie)...

Septième étape : construction du classement final

Une fois que les pages ont été crawlées, indexées, analysées pour leur pertinence et leur popularité, le moteur peut finalement renvoyer des résultats de recherche. Lorsque l’internaute va saisir une requête, le moteur de recherche va choisir dans son index les pages les plus pertinentes, et il va les renvoyer dans l’ordre décroissant de popularité. Ainsi plus une page pertinente est populaire, plus elle a de chances de se retrouver dans les premiers résultats de la SERP pour les requêtes qui la concerne.

On notera que plusieurs filtres modulent le classement, par exemple pour personnaliser les résultats selon l’intention détectée (si le moteur voit une intention d’achat il favorise les sites commerçants) ou la localisation (pour proposer des commerces près de chez vous).

Bonus : le re-ranking

Enfin, une dernière brique - moins connue - utilisée par les moteurs de recherche est la prise en compte des informations de comportement et d’interaction des visiteurs au niveau du moteur. Nous l’avons déjà évoqué dans la lettre d’Abondance, mais par exemple le CTR (taux de clics), le click-skip (click sur les résultats 1 et 3 mais pas sur le 2 par exemple) et autres métriques, vont être utilisés par le moteur pour requalifier les résultats et les modifier finement (c’est-à-dire requête par requête).

Voilà, nous avons fini le panorama des tâches réalisées par un moteur de recherche, et nous allons maintenant pouvoir détailler chacune des briques.

Première étape : le crawl

Ce mois-ci nous allons nous contenter de parler de la première brique : le crawl. Même si elle est techniquement complexe, il s’agit de la brique qui est intellectuellement la plus simple, et c’est pour cela que nous l’abordons dès maintenant.

Techniquement, un crawler va partir d’un certain nombre d’URL et va visiter tout le Web en partant de ces URL de base. Pour cela il va parcourir les URL pointées par les liens des URL qu’il a  déjà parcouru pour enrichir sa base de pages à visiter, et en parallèle indexer les contenus et les informations structurelles.

Pour chaque URL à visiter, le robot d’indexation va effectuer un accès au registre DNS pour aller chercher la page correspondant à l’URL sur le serveur qui l’héberge. Cela parait anodin, mais c’est à ce moment-là qu’on trouve la première difficulté : l’accès au DNS induit une latence dans le crawl très grande, et c’est pour cela que les grands moteurs ont leur propre copie du DNS (qu’il propose à tous, via par exemple l’IP 8.8.8.8 pour Google). On notera que la fourniture du DNS par un moteur lui permet aussi de monitorer de façon très précise le comportement des internautes, mais il s’agit d’un sujet pour un autre article…

Une fois la page récupérée, le moteur va effectuer une analyse syntaxique et planifier une liste de traitements qui seront réalisés sur la page. Il y a parmi eux une notion très importante : le filtre à URL. Ce filtre à URL contient un ensemble de règles à appliquer selon certaines caractéristiques de la page qui est en cours d’analyse. On peut ainsi imaginer que les pages en .edu sont par défaut moins lourdement et profondément analysées que les pages en .biz, car le filtre à URL ne va pas mettre en place la même chaîne de traitement pour les .edu et les .biz, tout simplement car il y a plus de spam chez les uns que chez les autres..

Un autre point important est que l’analyse de duplication peut être effectuée par le moteur lors du crawl (en parallèle de l’indexation donc), pour éviter d’indexer des pages dont le contenu est déjà connu. Nous reviendrons sur ce point dans un prochain article, mais il est indispensable que toutes les pages offertes au crawl sur un site web contiennent assez de contenu unique pour passer la barre de l’indexation.

Lorsque le moteur aura crawlé les pages et que celles-ci sont suffisamment uniques, le contenu va être indexé (nous en reparlerons). Lors du crawl, une page de qualité, c’est une page qui sera indexée. Une page ne passant même pas cette étape a certainement d’énormes soucis à résoudre.

Pour en finir sur la notion de crawl, il faut savoir qu’il peut y avoir plus d’un type de crawler utilisé par chaque moteur. En effet, un crawler est défini par plusieurs variables :

1. Sa politesse : c’est le nombre de pages qu’un moteur a le droit de parcourir simultanément sur un même site web ou sur un même serveur. Ces limites permettent en pratique d’éviter de faire tomber des sites qui seraient hébergés sur des serveurs incapables d’accueillir un nombre important de visiteurs en même temps. Il est très aisé, même avec un simple ordinateur de bureau et une connexion correcte, de crawler un site web à raison d’une centaine de pages par secondes. Si le serveur en face n’est pas capable d’accepter ce flux, le site qui y est hébergé peut simplement se retrouver en panne.
2. Sa stratégie de crawl : est-ce que le moteur visite tout un site avant de passer au suivant, est-ce qu’il voit les pages en démarrant par la page d’accueil puis en prenant les liens dans l’ordre où il les croise, ou une page de chacun des sites qu’il connaît, ou seulement les pages récentes, etc. ? Par ailleurs, le moteur doit décider des pages qu’il se contente de traverser par rapport à celles qu’il va réellement analyser et éventuellement indexer.
3. Sa gestion de la fraîcheur des informations : les contenus des pages web sont parfois amenés à  évoluer, et le moteur doit donc revenir voir les sites périodiquement. Mais il doit revenir le moins souvent possible car chaque visite sans nouvelle information est une perte pour lui. Décider quand revenir est un problème difficile. Revenir trop souvent et c’est une perte sèche, revenir trop peu souvent et l’index voit sa qualité détériorée, surtout face aux requêtes liées à l’actualité.
4. Sa stratégie de coordination : bien évidemment il n’y a pas UN bot mais des milliards de bots qui oeuvrent en parallèle. Le moteur doit décider de la façon dont  il coordonne les bots entre eux, et de comment chacun peut mettre à jour les bases de données du moteur pour avoir une vision la plus exacte possible du Web. Le surcoût de cette coordination est bien sûr onéreux, mais largement compensé par le fait de pouvoir crawler de nombreuses pages du web à un même instant.

On le comprend, crawler le web est effectivement bien plus complexe que la simple théorie (suivre les liens de pages en pages) ne le laisse entendre !

Nous verrons dans le prochain article comment le moteur va créer son index, et comment il va analyser les pages qu’il aura choisi de rentrer dans son index.

 

Références

[1] Schütze, H., Raghavan, P., & Manning, C. (2009). An introduction to information retrieval.
http://nlp.stanford.edu/IR-book/

[2] Amini, M. R., & Gaussier, E. (2013). Recherche d'information: applications, modèles et algorithmes. Editions Eyrolles.

[3] https://research.googleblog.com/2016/03/train-your-own-image-classifier-with.html

[4] Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking: bringing order to the web.
http://ilpubs.stanford.edu:8090/422/1/1999-66.pdf