vendredi 1 février 2008

Chapitre 1- Définitions (2)

1.4. Comment fonctionne un moteur de recherche ?
Avant d’y référencer votre site, savez-vous ce que l’outil de recherche que vous utilisez au quotidien a “dans le ventre” ? Pas si simple, car si des moteurs comme Google, Yahoo! ou MSN Search semblent simplissimes à l’utilisation, sous leur capot sommeille souvent un tigre redoutable. Nous vous proposons dans ce chapitre une analyse globale du fonctionnement des moteurs et des processus qui sont mis en oeuvre pour traiter les documents, stocker les informations les concernant et restituer des résultats aux requêtes des utilisateurs. En effet, bien maîtriser le fonctionnement d’un moteur permet de bien mieux appréhender le référencement et l’optimisation de son site.
Un moteur de recherche est donc un ensemble de logiciels parcourant le Web puis indexant automatiquement les pages visitées. Trois étapes sont indispensables à son fonctionnement :
- La collecte d’information (ou crawl) grâce à des robots (ou spiders ou crawlers).
- L’indexation des données collectées et la constitution d’une base de données de documents nommée “index”.
- Le traitement des requêtes, avec en particulier un système d’interrogation de l’index
et de classement des résultats en fonction de critères de pertinence suite à la saisie de mots clés par l’utilisateur de l’outil.
Deux principaux types de contenus sont actuellement affichés par les moteurs dans leurs pages de résultats, comme nous l’avons vu dans les pages précédentes :
- les liens “organiques” ou “naturels”, obtenus grâce au “crawl” du Web.
- les liens sponsorisés.
Nous allons nous concentrer ici en priorité sur les techniques utilisées par les moteurs pour indexer et retrouver des liens “naturels” et nous n’aborderons pas le traitement spécifique des liens sponsorisés (liens commerciaux, traités au chapitre 7 de cet ouvrage).
1.4.1. Technologies utilisées par les principaux portails de recherche
En dehors des trois leaders du marché (Google, Yahoo et MSN), de nombreux moteurs n’utilisent pas leurs propres technologies de recherche mais ils sous-traitent cette partie auprès de grands moteurs. En fait il n’existe que peu de “fournisseurs de technologie” sur le marché : Google, Yahoo!, MSN, Teoma, Wisenut et Gigablast aux Etats-Unis, comme sur le plan mondial, sont les principaux. Exalead,
Mirago et Voila sont les acteurs majeurs en France, à côté d’autres moins connus comme Antidot, Deepindex, Seekport, Misterbot ou Dir.com (mais il en existe d’autres).
1.4.2. Principe de fonctionnement d’un moteur de recherche
Pour leur fonctionnement, les moteurs de recherche suivent plusieurs étapes : des robots (ou spiders ou crawlers) explorent dans un premier temps le Web de lien en lien et récupèrent des informations (phase dite de “crawl”). Ces informations sont ensuite indexées par des moteurs d’indexation, les termes répertoriés enrichissant un index régulièrement mis à jour (une base de données des mots contenus dans les pages). Une interface de recherche permet enfin de restituer des résultats aux utilisateurs en les priorisant en fonction de leur pertinence (phase de “ranking”).
1.4.2.1. Les crawlers ou spiders
Les spiders (également appelés agents, crawlers, robots ou bots) sont des programmes de navigation visitant les pages Web et leurs liens de manière continue en vue d’indexer leurs contenus. Ils parcourent les liens hypertextes entre les pages et reviennent périodiquement visiter les pages retenues pour prendre en compte les éventuelles modifications.
Un spider est donc un logiciel très simple mais redoutablement efficace. Il ne sait faire que deux choses :
- Lire des pages web et stocker leur contenu (leur code HTML) sur les disques durs du moteur.
- Détecter les liens dans ces pages et les suivre pour identifier de nouvelles pages web.
Le processus est immuable : le spider trouve une page, la sauvegarde, détecte les liens qu’elle contient, se rend aux pages de destination de ces liens, les sauvegarde, y détecte les liens, etc. Et cela 24 heures sur 24... L’outil parcourt donc le Web inlassablement pour y détecter des pages web en suivant des liens... Une image assez communément répandue pour un spider serait celle d’un “internaute fou” qui lirait et mémoriserait toutes les pages web qui lui sont proposées et qui cliquerait sur tous les liens qu’elles contiennent pour aller sur d’autres documents, etc. Parmi les spiders connus, citons notamment le spider “Googlebot” de Google,“Yahoo! Slurp” de Yahoo, “Henri Le Robot Mirago” du moteur Mirago ou encore le plus récent “MSNBot” de MSN.
Mais parcourir le Web ne suffit pas. En effet, lorsqu’un spider arrive sur une page, il va vérifier s’il ne la connaît pas déjà. Si c’est le cas, il va regarder si la version découverte est plus récente que celle qu’il a déjà à sa disposition... En cas de réponse positive, il va “jeter” l’ancienne version et la remplacer par la nouvelle. L’index se met ainsi à jour de façon automatique... Il y a quelques années de cela, les mises à jour des index des moteurs étaient mensuelles.Chaque mois, le moteur mettait à jour ses données en supprimant un “ancien” index pour le remplacer par un “nouveau”, mis à jour pendant 30 jours par ses robots, scrutant le Web à la recherche de nouveaux documents ou de versions plus récentes de pages déjà en sa possession. Cette période avait notamment été appelée chez Google la “Google Dance”. Elle fut d’ailleurs, pour l’anecdote, longtemps indexée (c’est le cas de le dire) sur les phases de pleine lune... On savait, à cette époque, que lorsque la pleine lune approchait, un nouvel index était en préparation chez Google... Nous verrons plus tard dans ce livre que le terme de “Google Dance” désigne tout autre chose actuellement. Ce système de mise à jour mensuelle des index n’a plus court aujourd’hui. La plupart des moteurs gère le crawling de manière “différenciée” et non “linéaire”. Ils visitent plus fréquemment les pages à fort taux de renouvellement des contenus (très souvent mises à jour) et se rendent moins souvent sur les pages “statiques”. Ainsi, une page qui est mise à jour quotidiennement (par exemple, un site d’actualité) sera visitée chaque jour ou tous les deux jours par le robot tandis qu’une page rarement modifiée sera “crawlée” toutes les quatre semaines en moyenne. De plus, la disponibilité du document dans l’index du moteur est quasi immédiate. Ainsi, une page souvent mise à jour sera le plus souvent accessible à la recherche sur le moteur un ou deux jours plus tard. Ces pages récemment crawlées sont par exemple identifiables sur Google car la date de crawling est affichée. Le résultat proposé ci-dessus montre bien que la page proposée a été “crawlée” (sauvegardée par les spiders) deux jours auparavant et qu’elle a été immédiatement traitée et disponible dans les résultats de recherche. On pourra noter que la technique de suivi par les spiders des liens hypertextes peuvent poser plusieurs problèmes pour :
- L’indexation des pages qui ne sont liées à aucune autre et ne peuvent donc pas être répérées par les crawlers qui n’ont aucun lien à “se mettre sous la dent” (si tant est que les robots aient des dents...). Il en est ainsi des sites qui viennent d’être créés et qui n’ont pas encore de “backlinks” (liens entrants) qui pointent vers eux.
- L’indexation des pages “dynamiques” de périodiques ou de bases de données (ces pages étant moins facilement prises en compte, nous y reviendrons au chapitre 4...).
- Les pages pointées par des documents proposant des liens non pris en compte par les moteurs de recherche, comme beaucoup de ceux écrits en langage JavaScript. Là aussi, nous y reviendrons (chapitre 4).
Le passage des spiders sur les sites peut être vérifié par les webmasters en analysant les fichiers “logs” sur les serveurs (ces fichiers indiquent l’historique des connexions, dont celles des spiders, qui ont eu lieu sur le site). La plupart des outils statistiques comprennent dans leurs graphiques ou données une partie “visites des robots”. Attention cependant : ces outils doivent le plus souvent être spécifiquement configurés pour prendre en compte tous les robots émanant de moteurs français.Les outils statistiques, notamment d’origine américaine, ne prennent pas toujours en compte ces spiders “régionaux”...
1.4.2.2. Le moteur d’indexation
Une fois les pages du Web “crawlées”, le spider envoie au moteur d’indexation les informations collectées. Historiquement, plusieurs systèmes d’indexation des données ont été utilisés :
- Indexation uniquement des balises meta (meta-tags) insérées par les webmasters dans le code source des pages html, balises qui comprennent entre autres le résumé et les mots-clés attribués par l’auteur à la page. Très peu de moteurs fonctionnent ainsi aujourd’hui.
- Indexation des titres seulement ou de quelques lignes des documents. Là aussi, ce mode de fonctionnement est devenu très rare.
- Indexation en texte intégral (c’est de loin le cas le plus fréquent). Tous les mots d’une page, et plus globalement son code HTML, sont alors indexés. Le plus souvent donc, les systèmes d’indexation se chargent d’identifier en “plein texte” l’ensemble des mots des textes contenus dans les pages ainsi que leur position.Certains moteurs peuvent cependant limiter leur capacité d’indexation. Ainsi, pendant de longues années, Google s’est limité aux 101 premiers kilo-octets des pages (ce qui représentait cependant une taille assez conséquente). Cette limite ne
semble aujourd’hui plus d’actualité. MSN Search, pour sa part, semblait se limiter aux 150 premiers kilo-octets des pages au moment où ces lignes étaient écrites.
D’autres moteurs peuvent effectuer une sélection en fonction des formats de document (Excel, Powerpoint, PDF…). Cependant, comme pour les logiciels documentaires et les bases de données, une liste de mots “vides” (par exemple, “le”, “la”, “les”, “et”…) appelés “stop words” en anglais, est le plus souvent automatiquement exclue (pour économiser de l’espace de stockage) ou ces mots sont systématiquement éliminés à l’occasion d’une requête (pour améliorer la rapidité des recherches).
1.4.2.3. L’index inversé
Au fur et à mesure de l’indexation et de l’analyse du contenu des pages web, un index des mots rencontrés est automatiquement enrichi. Cet index est constitué :
- D’un index principal ou maître, contenant l’ensemble du corpus de données capturé par le spider (URL et/ou document…).
- De fichiers inverses ou index inversés, créés autour de l’index principal et contenant tous les termes d’accès (mots clés) associés aux URL exactes des documents contenant ces termes sur le Web.
L’objectif des fichiers inverses est simple. Il s’agit d’espaces où sont répertoriés les différents termes rencontrés, chaque terme étant associé à toutes les pages où il figure. La recherche des documents dans lesquels ils sont présents s’en trouve ainsi fortement accélérée.
Pour comprendre le fonctionnement d’un index inversé, prenons, par exemple, une page A (disponible à l’adresse http://www.sanglots.com/) comprenant la phrase “Les sanglots longs des violons de l’automne” et une page B (http://www.violons.com/) contenant les mots “Les violons virtuoses : les premiers violons du Philharmonique de Radio France”.
- L’index de documents, comprenant toutes les pages prises en compte par le moteur lors d’une recherche. C’est cette base de données que nous appelerons “index” dans cet ouvrage, par souci de concision.
- L’index inversé, qui comprend en fait les mots clés potentiels de recherche ainsi que leurs connexions avec l’index de documents. Il s’agit de la partie immérgée de l’iceberg, invisible pour l’utilisateur du moteur mais pourtant indispensable à son fonctionnement...
L’index doit être mis à jour régulièrement, en ajoutant, modifiant ou supprimant les différentes entrées. C’est en effet la fréquence de mise à jour d’un index qui fait en grande partie la qualité des résultats d’un moteur et sa valeur (pas de doublons ou de liens morts dans les résultats…), d’où des délais de rafraîchissement relativement courts.
1.4.2.4. Le système de ranking
Le ranking est un processus qui consiste pour le moteur à classer automatiquement les données de l’index, de façon à ce que, suite à une interrogation, les pages les plus pertinentes apparaissent en premier dans la liste de résultats. Le but du classement est d’afficher dans les 10 à 20 premières réponses les documents répondant le mieux à la question. Les moteurs élaborent pour cela en permanence de nouveaux algorithmes (des formules mathématiques utilisées pour classer les documents).
Ces algorithmes sont un véritable facteur différenciant. Ils ne sont donc que très rarement rendus publics et ils sont même dans certains cas protégés par des brevets et font parfois l’objet de “secrets défenses” voire de mythes comparables à celui du “7X” (principal composant du Coca-Cola)...Il existe plusieurs grandes méthodes de ranking des résultats et les moteurs utilisent pour la plupart un mélange de ces différentes techniques...
- Le tri par pertinence Les résultats d’une requête sont triés en fonction de six principaux facteurs appliqués aux termes de la question (toutes ces notions seront revues en détail au chapitre 3) :
- Localisation d’un mot dans le document (exemple : le poids est maximum si le mot apparaît dans le titre ou au début du texte) ou son adresse (url).
- Densité d’un mot, calculée en fonction de la fréquence d’occurrences du mot par rapport au nombre total de mots dans le document.
- Mise en exergue d’un mot : gras, titre (balise Hn), lien, etc.
- Poids d’un mot dans la base de données calculé en fonction de la fréquence d’occurrences du mot dans l’index (les mots peu fréquents sont alors favorisés).
- Correspondance d’expression basée sur la similarité entre l’expression de la question et l’expression correspondante dans un document (un document est privilégié lorsqu’il contient une expression similaire à celle de la question, notamment pour des requêtes à plusieurs mots clés).
- Relation de proximité entre les termes de la question et les termes utilisés dans le document (les termes proches l’un de l’autre sont favorisés).
- Le tri par popularité (indice de popularité)
Popularisé - mais pas inventé - par Google en 1998 (pour contrer entre autres les abus possibles des méthodes de tri par pertinence), le tri par popularité s’appuie sur une méthode basée sur la “citation”, l’analyse de l’interconnexion des pages web par l’intermédiaire des liens hypertexte, et il est a priori indépendant du contenu. Ainsi, Google classe les documents en fonction de leur “PageRank” (nombre et qualité des liens pointant vers ces documents, nous y reviendrons en profondeur au chapitre 3). Le moteur analyse alors les pages contenant les liens (les liens émanant de pages issues de sites considérés comme “importants” pèsent plus “lourd” que ceux de pages de certains forums ou de “pages perso” jugées secondaires par exemple). Plus une page est pointée par des liens émanant de pages “populaires”, plus sa popularité est grande est meilleur est son classement. Cette méthode de tri des résultats est aujourd’hui utilisée par de nombreux moteurs (pour ne pas dire tous les moteurs majeurs).
- Le tri par mesure d’audience (indice de clic)
Créée par la société DirectHit en 1998, cette méthode permet de trier les pages en fonction du nombre et de la “qualité” des visites qu’elles reçoivent. Le moteur analyse alors le comportement des internautes à chaque clic, chaque visite d’un lien depuis la page de résultats (et notament le fait qu’il revienne ou non sur le moteur et au bout de combien de temps) pour tenter de trouver les pages les plus “populaires” (au sens du clic) parmi les pages référencées et améliorer en conséquence leur classement dans les résultats. Plus une page sera cliquée et moins les internautes reviendront sur le moteur après l’avoir consultée (signifiant ainsi qu’ils ont trouvé “chaussure à leur pied”), et plus cette page sera considérée comme pertinente et sera donc mieux classée à la prochaine requête similaire... Cette méthode semble être tombée en désuétude depuis quelques temps.
- Le tri par catégories Lancé en 1997, Northernlight proposait le classement automatique des documents trouvés dans des dossiers ou sous-dossiers (clustering) constitués en fonction des
réponses. celles-ci, intégrées à chaque dossier, étaient également triées par pertinence. Cette technique de “clusterisation” thématique des résultats est aujourd’hui notamment utilisée, entre autres, par le français Exalead (http://www.exalead.com/) et les américains Vivisimo (http://www.vivisimo.com/) et Clusty (http://www.clusty.com/).
Les moteurs sont également amenés à ajuster en permanence leurs algorithmes afin de contrer le “spamdexing”, c’est-à-dire les techniques peu scrupuleuses de spam utilisés par certains webmasters pour “tromper” les moteurs de recherche et améliorer artificiellement le positionnement d’une page. Parmi les techniques les plus connues (et réprouvées par les moteurs), citons notamment le fait de multiplier les mots-clés dans les balises meta des pages
HTML, qui a certainement amené les moteurs à ne plus prendre en compte ce champ (voir chapitre 3), le fait d’intégrer un texte “invisible” sur une page (en blanc sur fond blanc, par exemple), la création de “sites miroirs” ou de liens fictifs ou invisibles pointant vers une page (ce qui permet de détourner l’indice de popularité), les pages satellites, la mise en place de faux portails contenant en fait des liens commerciaux ou le développement de “fermes de liens” (linkfarms), à savoir des listes de liens sans cohérence ayant pour unique objectif de gonfler la popularité des sites inscrits. Mais nous aurons l’occasion d’en reparler plus longuement dans cet ouvrage...
1.4.2.5. Le logiciel de recherche / moteur d’interrogation
Le moteur d’interrogation (searcher) est l’interface frontale (formulaire de recherche) proposée aux utilisateurs. Plusieurs niveaux de requête (interface de recherche simple ou avancée) sont en général offerts. A chaque question, par le biais d’un script CGI (Common Gateway Interface), une requête est générée dans la base de données
et une page Web dynamique restitue les résultats généralement sous forme de listes ou de cartes de résultats. L’interface CGI permet d’exécuter un programme sur un serveur et de renvoyer le résultat à un navigateur Internet.
1.4.2.6. Focus sur le fonctionnement de Google
Créé en 1998 par deux étudiants de l’université de Stanford, Sergey Brin et Larry Page, Google s’est rapidement imposé comme le leader mondial des moteurs de recherche.
Le stockage des données et la réponse aux requêtes sont effectués à partir de dizaines de milliers de PC traditionnels tournant sous Linux. Réunis en clusters (grappes), les ordinateurs sont interconnectés selon un système basé sur la répartition des charges entre ordinateurs (un ordinateur distribue les tâches au fur et à mesure vers les autres ordinateurs disponibles).
D’un coût moins élevé que celui des serveurs, les PC traditionnels offrent un avantage au moteur de recherche dans la mesure où il est possible d’agrandir relativement “facilement” le parc informatique à mesure que croissent le Web et la quantité de documents à indexer. L’index de Google est découpé en petits segments (des “shards”) afin qu’ils puissent
être répartis sur l’ensemble des machines distribuées dans des datacenters déployés dans le monde entier, cela afin de réduire au maximum les temps de réponse aux requêtes et les coûts en bande passante. Pour rester disponible en cas de défaillance d’un PC, chaque “shard” est dupliqué sur plusieurs machines. Plus le PageRank est élevé et plus le nombre de duplicata est élevé Dévoilée il y a sept ans (et probablement toujours similaire à l’heure actuelle, même si plusieurs projets, dont le célèbre “BigDaddy” l’ont dernièrement renouvellée) l’architecture de Google fait apparaître l’interconnexion de plusieurs composants séparés. Chaque composant a un rôle bien défini :
- Le serveur d’URL (URL server) envoie aux crawlers (Googlebot) toutes les adresses des pages devant être visitées (et notamment les liens soumis via le formulaire de soumission de Google, voir chapitre 5).
- Le store server compresse les pages extraites par les crawlers et les envoie au Repository où elles sont stockées.
- L’indexeur lit et décompresse le contenu du Repository. Il associe à chaque document un numéro identifiant docID et convertit chaque page en un ensemble d’occurrences de termes (chaque occurrence est appelé un “hit”), enregistrant les informations sur le “poids” du mot dans la page (position, mis en exergue…).
- L’indexeur distribue les occurrences dans un ensemble de “barrels” (organisés pardocID).
- L’Anchors stocke certaines informations générées par l’indexeur, à savoir les liens hypertextes et les ancres qui leurs sont associés (textes des liens).
- Le solveur d’URL (URL Resolver) récupère les informations fournies par l’Anchors
et convertit chaque adresse URL pointée par l’ancre en un docID (si cette adresse n’existe pas dans le Doc Index, alors il l’ajoute).
- Le Links contient des paires de docID (reçues du solveur d’URL). Il s’agit de paires de liens car chaque ancre appartient à une page et pointe vers une autre page.
- Le PageRank récupère les informations de cette base de données de liens pour calculer le PageRank de chaque document (indice de popularité).
- Le Sorter récupère les données stockées dans les “Barrels”, organisées par docID, et les réorganise en wordID (identités des mots). Cette opération permet de générer l’index inversé, stocké dans les mêmes “Barrels”.
- La liste des mots créée par le Sorter est comparée avec celle du Lexicon (lexique) et tout mot ne figurant pas dans le lexique y est ajouté.
- Enfin, le Searcher (interface de recherche) exécute les recherches pour répondre aux requêtes des utilisateurs. Il utilise pour cela le lexique (créé par l’indexeur), l’index inversé contenu dans les Barrels, les adresses URL associées aux mots de l’index
inversé (provenant du Doc Index) et toutes les informations du PageRank concernant la popularité des pages. A chaque requête, le serveur consulte l’index inversé et regroupe une liste de documents comprenant les termes de recherche (hit list). Il classe ensuite les pages en fonction d’indices de popularité et de pertinence.
En résumé
Un moteur de recherche est basé sur plusieurs “modules” indispensables :
- Des spiders qui parcourent le Web pour collecter les documents qui le constituent, en adaptant leurs fréquences de visites aux délais de mise à jour des pages.
- Un index des documents identifiés par les spiders.
- Un index inversé contenant les mots compris dans les documents.
Lors de la saisie d’une requête, l’algorithme de pertinence du moteur permet
de classer les pages web en fonction de la pertinence par rapport aux mots clés demandés.

Aucun commentaire: