Les algorithmes des moteurs de recherche

Internet regroupe de nombreux outils dont la toile (de l’anglais Web) qui comporte de nombreuses pages publiées librement par des millions d’internautes. Du fait de la forte croissance du réseau et du nombre grandissant de documents mis en ligne le besoin s’est fait ressentir de trouver une information sans avoir à tout parcourir.

La recherche d’information sur Internet est un domaine d’application qui a beaucoup évolué ces dernières années. On est passé d’annuaires répertoriant des liens à des moteurs de recherche basiques pour en arriver aujourd’hui à des moteurs utilisant des algorithmes d’indexation et de recherche puissants. Les algorithmes des moteurs de recherche sont tous basés sur des théories différentes mais leurs objectifs est le même : indexer toute la toile, et l’indexer rapidement pour donner un résultat pertinent à l’utilisateur.

Afin de comprendre l’évolution de ces moteurs de recherche et des algorithmes qu’ils utilisent je vais dans une première partie introduire la recherche d’information pour mieux comprendre l’architecture de la toile ainsi que la manière dont on peut l’indexer. Dans une seconde partie je vais présenter les différents algorithmes des moteurs de recherche et plus particulièrement l’algorithme PageRank de Google. Dans une troisième partie je vais montrer vers quels moteurs de recherche nous évoluons aujourd’hui en m’intéressant aux fonctions lexicales et au Web sémantique.

a.      Définition

Le web sémantique est une partie d’Internet qui se dirige vers un réseau dans lequel on peut consulter et publier des documents automatiquement. Ces documents sont formalisés, ils ne contiennent pas des textes en langage naturel mais les informations y sont classées de manière ordonnée. En effet la sémantique ne se base pas sur l’orthographe d’un mot mais sur les caractéristiques polysémes des mots et donc sur le sens d’un mot ou la signification d’un texte.

Des logiciels de traitement du web sémantique ont pour objectifs de :

      générer des documents sémantiques à partir des données saisies par l’utilisateur,

      modifier les données sémantiques afin d’être publiées ou traitées,

      publier des données sémantiques avec une mise en forme personnalisée ou spécialisée

      échanger automatiquement des données en fonction de leurs relations sémantiques,

      générer des données sémantiques automatiquement à partir de règles d’inférences.

Le web sémantique utilise les protocoles et langages standards du web, il ne remet pas en cause le fonctionnement actuel de la toile mais il apporte un outil qui aide à ordonner, classer, et retrouver les documents. Le protocole utilisé est donc le HTTP, XML[1] est le langage utilisé de base pour coder les pages mais d’autres modèles ou langages s’appuyant sur le XML sont venus s’ajouter à ce dernier : le RDF [2]ou le OWL[3].

Le web sémantique est réuni sous un consortium appelé le W3C[4], c’est le consortium de la toile d’araignée mondiale (de l’anglais World Wide Web Consortium).

Le Web sémantique est un consortium récent (2001) qui se met en place peu à peu grâce à la volonté de beaucoup personnes de travailler sur un réseau bien ordonné. En effet Internet regroupe de nombreux surfeurs, professionnels, développeurs de tous les pays, il est devenu difficile d’interpréter tout ce qui s’y passe dans chaque langue. Le fait de travailler sur le sens des mots, la signification des textes ou sur des thématiques amène les moteurs de recherche à s’intéresser de plus prés au web sémantique. Ne plus orienter son indexation et sa recherche sur l’orthographe mais sur la sémantique est un pari que quelques moteurs de recherche ont relevé.

b.      Les moteurs de recherche sémantiques

L’utilisation de la sémantique dans les moteurs de recherche est un fait très récent mais il est déjà possible de faire un constat :

      les utilisateurs des moteurs de recherche ne sont pas habitués au format du résultat des requêtes,

      par contre l’ordonnancement des résultats offre à l’utilisateur la possibilité de se diriger vers un domaine précis.

Les derniers moteurs de recherche sémantiques sont apparus récemment sur Internet, leur part de marché est encore faible comparée à celle de Google, Yahoo ou MSN mais deux d’entre eux  proposent des fonctionnalités de recherche et d’affichage des résultats intéressants : Kartoo (www.kartoo.com) et Exalead (www.exalead.fr).

1)           Kartoo

Kartoo est un éditeur de logiciels et de technologies innovantes, il propose des logiciels de recherche d’informations, de visualisation graphique de l’information, de gestions de connaissances ou encore de cartographie. C’est une société française qui depuis 1997 multiplie les expériences dans le monde de la recherche d‘information, après le lancement en 2001 du moteur www.kartoo.com, elle a mis en ligne en 2004 un nouveau moteur de recherche www.ujiko.com. Le deuxième moteur de recherche utilise la base de connaissance de kartoo, mais fournit en plus une interface pour personnaliser les résultats.

L’avantage et l’innovation de ces deux moteurs, et principalement de kartoo, sont caractérisés par la présentation des résultats sous forme de fenêtres en formes de dossiers qui regroupent différents thèmes. En sélectionnant un thème le moteur de recherche nous propose une nouvelle division en sous thèmes, ceci jusqu’au niveau des pages individuelles.

Voici un exemple de recherche : « président France »

Figure III.3.a : Réponse à une requête sur kartoo : « président France »

On aperçoit au centre de l’écran plusieurs dossiers représentant plusieurs thèmes liés au terme président France, la grosseur du dossier est liée à la pertinence de la réponse. En passant la souris sur les dossiers on voit qu’il y a des liaisons entre les dossiers et donc entre les thèmes et un aperçu de la page est disponible sur la partie gauche de la fenêtre.

Figure III.3.b : Aperçu d’une page en passant la souris sur un dossier

En cliquant sur le thème « Jacques Chirac » dans la fenêtre de gauche une nouvelle fenêtre de kartoo nous présente une division plus précise des nouveaux thèmes trouvés en rapport avec Jacques Chirac et notamment dans la partie centrale différents liens vers des pages HTML.

Figure III.3.c : Précision de la requête en sélectionnant le thème Jacques Chirac

Ce moteur de recherche innovant, purement graphique est un outil manifestement très différent des outils de recherche actuels. Si l’on s’intéresse aux avantages et inconvénients de Kartoo, on va retrouver en points positifs :

     les fonctionnalités nouvelles qui apportent de l’aide par rapport aux autres moteurs,

et en points négatifs

     le temps de recherche nettement alourdi. En effet d’une part le temps de réponse du moteur est beaucoup plus long qu’un moteur de recherche classique et d’autre part le temps nécessaire pour parcourir les différents thèmes est lui aussi rallongé

Kartoo se montre donc efficace et novateur pour réaliser des recherches complexes mais assez lent et rebutant pour une recherche simple.

2)           Exalead

Exalead est à mi chemin entre les moteurs traditionnels tel que Google, Yahoo ou MSN et le moteur de recherche sémantique qu’est kartoo. En effet tout comme kartoo, exalead possède une classification de ces résultats par thèmes et c’est en ce sens qu’il fait parti de la nouvelle génération de moteurs de recherche dits sémantiques. Mais contrairement à kartoo, exalead ne veut pas trop jouer sur le changement et possède donc un affichage des résultats qui rappelle les moteurs traditionnels. Traditionnel oui mais avec des nouvelles fonctionnalités quand même. Voici donc les caractéristiques du moteur de recherche exalead :

      la fenêtre centrale regroupe les résultats de la recherche, ils sont classés par pertinence comme tout moteur classique,

      à droite de chaque résultat un aperçu présente l’aspect de la page correspondante,

      la colonne de gauche montre le coté sémantique et innovateur du moteur, il est composé de plusieurs parties, à savoir les termes associés, les rubriques associées, la localisation géographique, les langues des documents et les types de document.

Voici donc la réponse à la requête « président France » :

Figure III.3.d : Réponse à une requête sur exalead : « président France »

L’arrivée sur le marché de moteurs de recherche tels que Kartoo et Exalead explique le fait que les leaders actuels (Google, Yahoo, MSN) se tournent vers les fonctions lexicales et les outils sémantiques pour indexer le web. Ces nouvelles fonctionnalités sont toutes récentes mais elles marquent un tournant dans la course à la séduction des utilisateurs pour les moteurs de recherche.

[1] XML, Langage de balise extensible (Extensible Markup Language) est un standard qui sert à créer des langages de balisages, il définit des règles formalisées pour construire un document.

[2] RDF, Modèle de description des ressources (de l’anglais Resource Description Framewrok) est un modèle de graphe associé au langage XML, il sert à traiter automatiquement les métadonnées.

[3] OWL, Langage d’Ontologie du Web (de l’anglais Ontology Web Language), c’est un langage de modélisation des ontologies.

[4] W3C, http://www.w3.org/, site regroupant de nombreux membres professionnels ou amateurs de ce consortium.

L’étude des fonctions lexicales existe dans le domaine informatique dans le domaine du traitement automatique du langage naturel (TALN). C’est un domaine de recherche d’actualité depuis quelques années, en effet des applications informatiques récentes telles que dictionnaires de synonyme, traducteurs multilingues mais aussi les moteurs de recherche ont un réel besoin d’automatisation. Les utilisateurs sont de plus en plus exigeants sur la qualité attendue dans les nouvelles technologies de l’information.

Les fonctions lexicales sont utilisées dans le traitement d’un texte afin de désambiguïser le contenu du texte, c'est-à-dire trouver le sens de chaque mot. Dans toutes les langues chaque mot du dictionnaire peut avoir un ou plusieurs sens, la moyenne dans la langue française est d’environ 5 sens par mot, ces mots sont dits polysémiques.

Voici des exemples de fonctions lexicales :

      la synonymie,

      l’antonymie,

      l’hyperonymie,

      l’hyponymie.

Dans les moteurs de recherche les fonctions lexicales peuvent être utilisées à deux étapes très importantes que sont :

      L’indexation des pages, le moteur d’indexation doit être capable de classer les pages par domaine même si au sein d’un même domaine les mots utilisés sont différents. En utilisant la synonymie, l’hyperonymie ou l’hyponymie le moteur va être capable de reconnaître le sens de chaque mot polysème, l’indexation ainsi réalisée facilitera l’étape suivante.

      La réponse à une requête, ou plutôt la recherche d’informations similaires à al requête dans l’index du moteur de recherche. Tout comme pour l’étape d’indexation les fonctions lexicales vont donner des informations supplémentaires sur le sens recherché.

Google numéro un des moteurs de recherche ne peut pas passer à coté de ces nouvelles technologies de l’information. Encore une fois aucune information n’a été dévoilée mais depuis deux ans certains parlent déjà de l’algorithme PageRank sensible au contexte (de l’anglais topic sensitive PageRank).

a.      Le PageRank sensible au contexte

1)       Le constat

Le besoin pour Google de s’intéresser à la thématique d’une page découle d’un constat simple : Le PageRank classe par ordre d’importance des pages dont le contenu est identique mais il ne distingue pas de différence entre 2 mots identiques mais utilisés avec un sens différent. Ainsi des pages qui traitent de la voiture de marque Jaguar seront indexées avec des pages qui parlent des jaguars, animaux d’Afrique. L’ambiguïté existe pour de nombreux mots et ceci pour toutes les langues.

2)       Les PageRank thématiques

Pour désambiguïser ses index Google décide de doter son PageRank de thématiques de départ et de suivre par le biais des robots d’indexation les liens de s pages en restant dans un même domaine. Le résultat est un vecteur de PageRank général et 16 vecteurs de PageRank spécialisés dans un certain domaine. Chaque page possède désormais 17 PageRank au lieu d’un. La difficulté demeure ensuite dans la clarté et le décryptage de la requête. Si la requête est assez complète et possède des mots qui, mis ensemble, donnent un sens à la requête alors il sera facile au moteur de recherche de retrouver dans son index les pages correspondantes. Par contre si la requête est vague, l’index a beau être classé par thématique il est difficile de savoir quel sens donné à un mot seul. En reprenant l’exemple du jaguar on sait que l’index peut séparer les polysèmes et donc on aura une partie des pages indexées qui seront dans l’automobile et l’autre partie dans les animaux, mais si la requête comporte le seul mot « jaguar », aucune précision ne guide le moteur pour savoir quelle thématique donner en réponse.

3)       Une thématique pour chaque utilisateur

Les PageRank thématiques représentent une belle avancée dans la recherche de la pertinence mais Google, qui utilise déjà des robots localisés sur le PC de chaque utilisateur peut très bien utiliser des informations relatives à l’utilisateur et ses habitudes afin de mieux répondre à ses attentes.

Le moteur de recherche, en cas d’ambiguïté peut donc s’aider du contexte des recherches effectuées auparavant (répertoriées dans un historique) ou tout simplement des favoris ou de l’historique des pages Web visités par l’utilisateur. De plus l’utilisateur peut lui-même créer un profil dans lequel il renseigne ses centres d’intérêt qui pourront très certainement aider le moteur de recherche pour répondre à des requêtes.

      Ces outils paraissent très utiles et très robuste face aux problèmes rencontrés dans la désambiguïsation d’une requête mais elle se heurte à la protection des données de l’utilisateur. Certains soupçonnent déjà Google d’utiliser ce genre de robots sans en exploiter les informations récupérées, mais ceci sans l’accord préalable de l’internaute qui installe la barre d’outils Google ou l’utilitaire de bureau Google (Google Desktop[1]).

[1] Google Desktop : Utilitaire installé en local sur le PC de l’utilisateur qui indexe tous les fichiers des disques dur et qui accélèrent donc la recherche pour l’utilisateur : résultat de recherche présenté sur une page Google.

Les moteurs de recherche ont fait d’énormes progrès en une quinzaine d’année. Le gain apporté aux utilisateurs se situe sur la rapidité d’indexation des pages du Web, la rapidité de  réponse à une requête, la mise à l’écart des pages indésirables, et la plus grande diversité des formats de données proposées. La qualité des moteurs de recherche semble plafonner à son maximum, pourtant de nombreux chercheurs travaillent dans le sens de moteurs de recherches intelligents travaillant sur le coté linguistique des données, les fonctions lexicales.

D’un autre coté on voit aussi apparaître la volonté de certains développeurs de sites Web et de nombreux utilisateurs de mieux ordonner la toile afin de pouvoir trouver plus facilement une information et comprendre plus facilement le contenu d’une page, c’est le Web sémantique.

C’est donc ainsi que l’on a vu apparaître récemment des moteurs de recherche encore peu connus, peut-être du fait de leurs différences d’utilisation avec les moteurs plus conventionnels tel que Google, Yahoo et MSN.

Citons deux exemples :

      Exalead (http://www.exalead.fr/search)

      Kartoo (http://www.kartoo.com/flash04.php3)

Les nouveaux moteurs de recherche s’éloigne du coté algorithmique au sens mathématique pour se rapprocher du coté de l’étude du langage humain via des fonctions lexicales et de la signification des mots. C’est en cherchant à palier à leur plus gros défaut que les moteurs de recherche font ce choix, c'est-à-dire en essayant d’être plus pertinent sur les résultats.

Dans un point de vue général on peut parler de sémantique linguistique qui peut se définir comme l’étude du sens des mots d’une langue. On ne cherche plus un mot ou une expression précise mais on cherche un sens (une idée) et on souhaite avoir en réponse à une requête toutes les pages traitant du même domaine.

C’est à travers ces deux domaines que sont les fonctions lexicales et le web sémantique que ce chapitre va traiter des évolutions récentes et à venir dans les moteurs de recherche.

Google est une société fondée en 1998 par Larry Page et Sergei Brin en Californie. Mais Google est avant tout un moteur de recherche créé en 1996 par les deux cofondateurs de la société alors qu’ils étaient encore étudiants à l’université de Stanford. Le projet Google traite d’un moteur de recherche dont le fondement est basé sur le principe d’une analyse des relations entre les sites Web.

a.      Le fonctionnement du moteur de recherche Google

Le moteur de recherche tel qu’il est apparu en

1998 a

Depuis le printemps 2003 le moteur de recherche fonctionne comme suit :

      Tout d’abord l’indexation, elle est réalisée par le Google bot[1], c’est un spider bot[2] qui est chargé de ré indexer les pages contenues dans l’index actuel mais aussi d’indexer les nouvelles pages. La période d’indexation s’adapte aux besoins de rafraîchissement des différentes pages, que ce soit des pages personnelles (mises à jour à une fréquence aléatoire) ou des pages d’actualité (avec des fréquences de mises à jour plus importantes). C’est une nouveauté de Google car dans sa première version le moteur de recherche effectuait ses trois fonctions via l’utilisation de plusieurs robots. Le Google bot est capable de suivre tout type de lien et il est donc capable d’indexer la totalité du Web.

En plus du Google bot, il existe deux autres robots d’indexation qui ont des fonctions bien particulières, elles sont liées aux nouveautés que proposent Google :

. Un robot qui se charge d’indexer les pages affichées ensuite dans Google News,

. Un robot qui se charge d’indexer les pages commerciales qui seront affichées dans le bandeau de droite d’une réponse à une requête quelconque, c’est le robot de Google AdSense.

      La seconde étape durant laquelle le calcul des notes des pages en fonction du contenu et des liens.

b.     Le PageRank

Pendant que de nombreux chercheurs ont passé beaucoup de temps à imaginer des algorithmes capables d’indexer tout le Web ou de l’indexer le plus rapidement possible Larry Page et Sergei Brin se sont penchés sur le classement des résultats d’une recherche. Ils ont imaginé une méthode pour déterminer l’importance d’une page Web. Contrairement à d’autres algorithmes le pageRank ne se base pas sur le contenu total d’une page Web mais plutôt sur ses liens sortants mais aussi entrants.

En français PageRank signifie rang de la page, on retrouve dans cette dénomination la volonté de classer les pages par importance et de leur donner un rang pour les distinguer les unes des autres lors d’une requête sur le moteur de recherche.

Définition de l’algorithme du pageRank telle qu’énoncée dans la publication de Google :

Le PageRank peut être calculé en utilisant un simple algorithme itératif, et correspond au vecteur propre principal de la matrice normalisée des liens du Web.

1)     Le concept de base de l’algorithme :

Un lien d’une page A vers une page B est traduit par le fait que le webmestre de la page A estime que la page B est de bonne qualité et, de plus, il y a de fortes chances pour que le domaine des informations contenues dans la page B ait un lien avec le domaine des informations de la page A. En possédant un lien vers la page B, A affecte donc un vote à B.

On comprend donc aisément que plus la page B reçoit de votes (possède des liens entrants) d’autres pages du Web plus elle est considérée comme importante par Google et plus elle aura de chances de se retrouver bien placée en réponse à une requête dans le domaine dont elle traite.

Remarques :

-          L’importance de la page B émettrice du lien vers la page B n’est pas négligeable pour déterminer l’importance de la page B. En effet une page possédant une multitude de liens entrants de la part de sites persos n’obtiendra le même classement qu’une page qui possède quelques liens entrants de la part de sites reconnus et mondialement connus.

-          Comme pour l’indexation incrémentale, et comme son nom l’indique l’algorithme pageRank n’attribue pas un classement pour un site complet mais pour chaque page qui le constitue. Aucune extrapolation (moyenne des pages d’un site ou autre) n’a été réalisée afin de noter le site plutôt que ses pages.

-          L’algorithme pageRank ne scrute pas le contenu d’une page afin d’y déceler les méta données ou autres informations qui pourraient aider le moteur d’indexation à donner une note pertinente en rapport avec tel ou tel sujet. L’algorithme pageRank est basé sur le principe des liens et donc le fait qu’une page est un fort pageRank ne signifie pas que son contenu est très intéressant ni que les informations sont vraies, une page a un fort pageRank si de nombreuses pages pointent vers elle.

2)     La barre d’outils de Google[3]

Afin de mieux sensibiliser les utilisateurs du moteur de recherche, Google propose une barre d’outils qui s’insère sous menus du navigateur Web. Cette barre d’outil Google donne la possibilité d’effectuer une recherche à l’aide d’une barre de saisie de texte, la réponse à la requête est transcrite dans la fenêtre de recherche de Google habituelle. La nouvelle fonctionnalité qui la différencie par rapport aux autres barres d’outils des moteurs de recherche est l’affichage du pageRank de la page en cours.

Figure II.3.a :La barre d’outil de Google (

la Google

Toolbar

On voit ci-dessus, qu’en plus des outils habituels la barre d’outil de Google affiche sous la forme d’une progression verte sur fond blanc. Ici le pageRank est de 9/10, la page est www.cnn.com alors que la requête était « cnn ».

De nombreux articles traitent de l’algorithme pageRank depuis sa sortie en 1998. L’équipe de Google a volontairement gardé une part de secret dans cet algorithme en donnant seulement le principe de base qui pour une page donnée calcule le rang d’une page. De ce fait de nombreux mathématiciens ont émis des hypothèses pour retrouver l’algorithme exact. Avec la formule du pageRank ces derniers n’ont qu’à essayer avec plusieurs paramètres et plusieurs hypothèses pour se rapprocher des vrais résultats retournés actuellement par la « Google Toolbar ».

3)     La formule de l’algorithme pageRank

Même si tous les secrets de l’algorithme pageRank n’ont pas été testés la plupart des informations ont été données et cela suffit pour, dans un premier temps, s’intéresser à la formule mathématique qui a fait la gloire du moteur de recherche Google.

Les pages T1, T2, …, Tn possèdent des liens sortants vers la page A, le pageRank de la page A est le suivant :

PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

      PR(A) est le pageRank calculée pour une page A (idem pour T1, Tn…).

      d est un coefficient d’amortissement qui limite l’importance de la quantité des votes donnés à une page. Ce facteur peut être ajusté entre 0 et 1, il prend généralement la valeur 0.85.

      La notation (1-d) est la garantie que la moyenne des pageRank de l’ensemble des pages Web est égal à 1.

      T1 à Tn sont des pages qui émettent des liens vers la page A.

      C(Tn) est le nombre de liens émis par la page Tn. Cette partie de la formule nous met la puce à l’oreille sur le fait que si une page Y qui pointe vers la page possède de nombreux liens sortants l’importance de chaque lien (et donc de celui pointant vers A) va être minimisé proportionnellement au nombre de liens.

Le résultat de cette formule donne dans la théorie des valeurs fractionnaires, en effet on peut s’apercevoir que le pageRank d’une page peut varier de 0.15 jusqu’à une valeur très grande. Hors nous avons vu précédemment (cf 2) la barre d’outils de Google) que les pageRank affichés dans la pratique sont compris entre 0 et 10 et ce ne sont que des valeurs entières.

Google cache une partie de son algorithme, certains parlent d’une échelle logarithmique de base 10 qui, en effet, fait retomber sur les bonnes valeurs les rangs calculés par le pageRank.

Voici les 11 possibilités de valeurs de pageRank affiché sur la barre d’outils de Google :

Tableau II.3.b : PageRank affiché en fonction du pageRank calculé

Remarque :

L’échelle logarithmique de base 10 est reprise dans de nombreux articles traitant de l’algorithme pageRank de Google mais elle n’est en aucun cas énoncée explicitement par les fondateurs de l’algorithme. Cependant cette hypothèse offre des résultats qui se rapprochent du résultat retourné par la barre d’outil de Google et elle aide à la compréhension.

L’algorithme itératif

Si on s’intéresse de plus prés à la définition donnée dans la publication de Google on s’aperçoit que l’on parle d’un algorithme itératif et qui va donc de pages en pages pour calculer le pageRank de chacune d’elles, et ceci, en boucle. Une question se pose alors étant donnée la formule sur la valeur de pageRank de la première page visitée. Elle va influencer les valeurs des pageRank des pages vers qui elle a un lien sortant, et ainsi de suite. Il parait donc très important de connaître la valeur de pageRank de départ à donner ou à calculer et il faudrait pouvoir évaluer par la suite si la valeur choisie était la bonne.

→ En réalité le caractère itératif de l’algorithme fait que chaque itération fait converger les résultats vers une valeur de plus en plus précise. La valeur finale est retenue à chaque fin d’itération et est réinjectée dans l’itération suivante. On s’aperçoit alors que qu’elle que soit la valeur donnée en entrée l’itération fera toujours converger l’algorithme vers la même valeur. Pour accélérer le processus d’itération qui devrait boucler autant de fois que de pages visitées le facteur d’amortissement a été mis en place dans l’algorithme, il joue le rôle de modérateur et fait converger les valeurs rapidement. Le nombre d’itérations utilisé pour indexer le nombre impressionnant de pages Web existantes (quelques milliards) est d’environ 40.

Ce qui a été présenté jusque ici est la partie de l’algorithme du moteur de recherche. L’algorithme est la base du moteur de recherche Google mais depuis sa mise en fonctionnement en 1998 le moteur de recherche a subi des modifications. D’une part les robots d’indexation ont été améliorés (cf a-Le fonctionnement du moteur de recherche Google) et d’autre part des modifications ont été effectuées au niveau du PageRank afin que les notes données aux pages soient bien objectives et pertinentes.

      En effet Google s’est intéressé de plus prés au contenu des pages et a mis en place un système pour évaluer si une page est bien en relation avec le texte du lien par lequel a est arrivé le robot d’indexation. Bien que Google ne dévoile rien sur les algorithmes utilisés sur de nombreux forums les administrateurs de sites parlent d’algorithme Hilltop et localrank.

      De plus le PageRank veut se protéger des systèmes qui ont pour but de faire apparaître des pages dans le début des listes de réponse, et ceci en jouant avec l’algorithme PageRank. Pour se protéger de ses pages indésirables Google utiliserait des filtres identiques à ceux utilisés pour filtrer nos mails.

Le domaine des algorithmes des moteurs de recherche se montre divers et varié mais ce qui le caractérise le plus c’est l’évolution qu’il subit du fait de la forte demande des utilisateurs qui souhaitent trouver avec facilité, rapidité et fiabilité une réponse à leur requête. Dans le lot des moteurs de recherche Google a su se positionner dans les premiers dés son arrivée en 1998 avec son algorithme PageRank. Alors que sa place de numéro un est difficile à détrôner Google ne souhaite pas en rester là et, en plus des fonctionnalités de plus en plus nombreuses qu’il propose, renforce son algorithme afin de gagner en rapidité et en pertinence. Les caractéristiques présentées ci-dessus ne sont que des théories et, alors que les premiers moteurs de recherche sémantiques montrent le bout de leur nez certaines théories apparaissent désormais sur le fait que Google, lui aussi, se tournerait vers des outils sémantiques.

[1] GoogleBot : Robot d’indexation de Google

[2] Spider Bot : De l’anglais Robot araignée c’est un robot d’indexation qui parcourt les pages du Web telle une araignée du fait de la similitude de la structure d’Internet à une toile d’araignée.

[3] La barre d’outils de Google = Google Toolbar

[4] PageRank calculé selon une hypothèse d’utilisation d’une échelle logarithmique, cela dit très proche de la réalité.

Tout comme pour les moteurs d’indexation traditionnels les objectifs restent les mêmes, c'est-à-dire qu’il faut indexer vite mais il faut tout indexer. Les méthodes qui vont suivre ne cherchent pas à savoir ce que l’auteur d’une page veut faire ressortir comme information en scrutant le contenu des balises META mais les moteurs d’indexation doivent récupérer tout le contenu des pages et les analyser rapidement.

Le contexte dans lequel sont apparus ces nouveaux moteurs ne laissait pas présager une certaine aisance, le nombre de pages est en perpétuelle augmentation, les capacités des supports de stockages augmentent en même temps que leurs prix baissent, ce qui encourage les développeurs à créer des pages Web avec de plus en plus d’information (texte, sons, vidéos…). C’est donc une mission difficile pour ces moteurs d’indexation qui envoient des robots pour récupérer le maximum d’information en un temps assez court afin que les données une fois indexées ne soient pas obsolètes.

En plus du soucis de la rapidité d’indexation les robots doivent passer partout et donc récupérer l’information de toutes nouvelles pages mises en ligne sur Internet.

a.      L’indexation par lot

L’indexation par lots (en anglais Batch Crawling) est une des premières méthodes utilisées dans l’analyse des liens. Ce type de moteur se soucie tout d’abord de l’indexation de la majorité des pages, c'est-à-dire essayer de ne rien oublier, ou du moins ne rien oublier d’important.

      La 1° étape de l’indexation par lots consiste à créer une liste de pages susceptibles d’être fortement connectées au reste du Web. Cette liste d’URL appelée Seed URL en anglais) représente le point de départ crucial pour le batch crawling.

      Lors de la 2° étape les robots envoyés par le moteur d’indexation vont aspirer les pages de la liste d’URL.

      Les pages aspirées sont analysées et plus particulièrement les liens qu’elles possèdent qui vont être ajoutées à la nouvelle liste d’URL. C’est cette 3° étape appelée le crawling qui crée des files d’attentes d’URL qui vont être traitées les unes après les autres.

      On repart ainsi à la 1° étape avec la nouvelle liste.

Lorsque les files d’attente ne contiennent plus de nouvelles URL le moteur d’indexation peut estimer que tout le Web a été visité et indexé, à condition évidemment que la liste de départ contient bien des pages fortement connectées au reste du Web.

L’avantage majeur de ce procédé est l’indexation quasi-totale du Web en utilisant les liens récupérés à chaque passage dans une nouvelle page. L’inconvénient est le temps que cela prend pour indexer tout le Web et notamment le temps perdu à ré indexer les pages plusieurs fois. De cet inconvénient découle un autre problème qui est le fait que le temps d’indexer tout le Web de nombreuses pages sont obsolètes (environ un mois pour tout indexer). La solution à ce problème serait de posséder des robots intelligents qui seraient capables d’indexer les pages à une fréquence dépendante de la fréquence de mise à jour du site.

b.     Le crawler incrémental

Pour palier aux inconvénients du batch crawling plusieurs constats ont été posés afin de trouver des solutions.

Les constats

      Les informations indexables sur le Web représentent plusieurs téraoctets de données, la gestion d’une telle quantité de données est un défi gigantesque sur le plan technique.

      Les périodes d’indexation sont longues et en parties obsolètes une fois terminées.

      Toutes les pages disponibles sur la toile n’ont pas toute la même importance.

Les solutions proposées pour le crawler incrémental :

      La totalité de la masse d’information présente sur le Web n’est pas utile pour des utilisations classiques d’un moteur de recherche. Une solution est donc de limiter la taille de l’index à une portion de cet ensemble sans trop dégrader la pertinence des résultats. On souhaite travailler désormais sur un index de taille fixe et limitée dans le but de privilégier la fraîcheur et la qualité par rapport à l’exhaustivité.

      Contrairement à l’indexation par lot les robots d’indexation ne doivent jamais s’arrêter et n’obéissent plus à des cycles. Ces robots ont pour mission de déterminer l’obsolescence des pages et d’effectuer leurs mises à jour dans l’index.

      Il faut différencier les pages par leur importance, et leur attribuer une note d’importance qui jouera sur le classement lors d’une réponse à une recherche mais aussi qui modifiera la fréquence de mise à jour de son indexation.

Cette méthode évite d’indexer des pages non modifiées, elle est donc économique en ressources (ressources qui seront utilisées pour gagner du temps par ailleurs). Il est désormais possible d’adapter la périodicité du crawl à la fréquence de changement des pages, selon le site visité ou le domaine. Le cycle de crawl n’est donc plus uniforme.

En plus de la fréquence de mise à jour des pages le robot doit se préoccuper des nouvelles pages et de celles qui ont été supprimées. C’est ici que réapparaît la technique de l’indexation par lot qui va être exécutée pour collecter les informations fiables afin d’éviter une dérive de l’index.

Un exemple concret de Web incrémental est « Seeker ». Ce moteur d’indexation a été proposé par Jenny Edwards, une spécialiste australienne des robots d’indexation. Cette méthode d’indexation a été proposée pour un outil de recherche d’IBM nommé Webfountain.

La particularité d’IBM est que en son sein il est possible de posséder des stations de travail ultra puissantes avec une très bonne bande passante et avec des énormes capacités de stockage. C’est pourquoi le moteur d’indexation créé dans ce cas ne travaillait pas sur un index de taille fixe (index fermé) mais plutôt sur un index ouvert capable de suivre en quasi temps réel la croissance de la toile. En plus de mettre à jour les informations existantes des pages déjà présentes dans l’index ce moteur met à jour la structure des sites qui vont composer l’index.

Le Web incrémental tire son épingle du jeu en travaillant sur un index élaboré et maîtrisé (du fait d’une bonne méthode de limite de sa taille). De ce fait la rapidité pour indexer le Web devient plus importante mais les résultats en retour d’une recherche ont une pertinence toujours discutable. Le talon d’Achille de ces moteurs demeure donc dans la qualité de classification les résultats et donc dans la méthode utilisée pour noter les pages lors de leurs indexations.

Tout moteur de recherche qui indexe des pages Web doit obéir à certaines règles de base.

            → L’indexation doit être rapide : le Web évolue tous les jours, en effet on voit apparaître de nouvelles pages de plus en plus fréquemment mais en plus le contenu de ces pages est mis à jour de façon quotidienne ou même une fois par heure.

            → L’indexation doit être complète : hormis pour les composants déconnectés du Web un moteur d’indexation doit être capable de récupérer les informations pertinentes des pages.

            → L’indexation doit respecter les sites : certains sites contiennent des pages cachées ou des pages authentifiées, d’autres sites utilisent le fichier robot.txt qui indique au moteur d’indexation qu’il ne souhaite pas être référencé.

Pour se faire les moteurs d’indexation utilisent des robots qui parcourent le Web et qui relèvent les informations contenues dans les pages. Plusieurs méthodes sont utilisées, en essayant d’optimiser les trois caractéristiques citées ci-dessus.

Dans ces différents moteurs d’indexation on voit apparaître deux catégories :

-          une catégorie qui indexe chaque page visitée sur le Web, cette méthode a une vue du Web bas niveau,

-          une autre catégorie qui sépare le Web en plusieurs domaines qui contiennent eux-mêmes plusieurs pages, cette méthode a une vue du Web haut niveau.

Les balises META

Le langage HTML prévoit dans son codage une partie réservée aux moteurs de recherche. Les balises META[1] contiennent des informations relatives au contenu de la page Web (cf 1.3 La recherche d’information). Ces balises sont mal exploitées et souvent inefficaces pour les raisons suivantes :

• Les développeurs de pages Web ne fournissent que très rarement ces informations.
  
  
• Lorsque elles sont renseignées ces balises ne sont pas toujours significatives du réel contenu de la page.
  
  
• Les balises META[2] sont souvent utilisées à mauvais escient par les spammeurs qui souhaitent faire apparaître leurs sites en haut des listes des moteurs de recherche.
  
  
• Tous les moteurs de recherche n’utilisent pas ces balises META pour indexer le contenu d’une page.

Les balises META sont disponibles sur chaque page HTML (bien que rarement renseignées sur une autre page que la page d’accueil d’un site), cette méthode d’indexation est donc une méthode qui utilise la structure bas niveau du Web.

Bien que utilisée dans les premiers moteurs de recherche, aujourd’hui les moteurs d’indexation s’attachent plus au contenu réel des la page qu’aux méta données. C’est donc dans cette optique que nous pouvons nous intéresser aux différents algorithmes qui indexent les pages Web.

[1] META pour Méta données, En informatique, une méta donnée est une donnée contenue dans un fichier qui décrit son contenu.

[2] Le SPAM désigne les communications électroniques massives à des fins publicitaires ou malhonnêtes. En France les spammeurs sont aussi appelés polluposteurs.

La définition de l’expression « moteur de recherche » des années 90 n’est pas la même que celle d’aujourd’hui. En effet le moteur de recherche est, en 1994, un outil qui, à partir d’une requête établie par un utilisateur fournit une réponse en proposant une liste de pages HTML qui traitent du sujet recherché.

Bien que le fond n’ait pas changé, la forme de la réponse ainsi que la façon de l’acquérir a évolué. Aujourd’hui il est possible de rechercher toutes les informations disponibles sur le Web, des pages HTML, des images, des sons, des vidéos, des fichiers dont on peut préciser le format.

► On est passé en quelques années d’un moteur de recherche de pages HTML à un réel moteur de recherche de l’information, et plus précisément de toutes les informations.

Pour ce qui est de la forme, c'est-à-dire de la façon de stocker les informations récupérées et la façon de la restituer et de l’associer à une requête donnée c’est ce que nous allons voir dans ce chapitre en présentant plusieurs algorithmes qui ont été, ou qui sont toujours utilisés par des moteurs de recherche.

Ci-joint le rapport en cours d'avancement...

Rapport_14_04_2006.pdf

C’est dans le contexte présenté précédemment que le besoin se fait ressentir de trouver une information sans avoir à naviguer à travers tous les liens existants sur le Web. C’est ainsi que la notion de recherche d’information est née sur Internet. Bien que le nombre de pages disponibles sur la toile tend à stagner ces derniers temps il n’en reste pas moins fortement peuplé de plusieurs milliards dont le classement en sites plus ou moins intéressants et plus ou moins pertinents s’avère très difficile.

C’est donc dans le milieu des années 90 que l’on a vu apparaître les premiers moteurs de recherche, ou plutôt les premiers annuaires. En effet ces annuaires n’étaient pas des moteurs à parts entières car ils étaient gérés par des personnes qui naviguaient sur la toile et qui s’efforçaient de donner une importance et une catégorie à chaque site visité. Ce principe d’indexation des pages de la toile est resté utile pendant de nombreuses années. Une fois indexées les pages sont séparées en plusieurs catégories et disponibles en réponse à des requêtes réalisées à l’aide d’une interface. Bien que la pertinence des résultats soit bien souvent approximative, ces annuaires font tout de même le bonheur des premiers surfeurs du web qui sont à la recherche d’information. Le Web étant un outil totalement nouveau les utilisateurs sont bien souvent contents de la quantité d’information disponibles et ne se plaignent donc pas de la qualité des informations proposées par les moteurs de recherche.

En plus des ces premiers annuaires qui classent les pages visitées en catégories de façon manuelles on voit apparaître les moteurs de recherche qui utilisent les propriétés des pages HTML et notamment des balises META pour connaître le contenu d’une page Web. Il existe au sein d’un même page plusieurs balises méta définissant plusieurs caractéristiques des données.

Exemple de 3 balises META fréquemment utilisées :

<meta name = “Author “ content = “Arnaud ADELL“>

<meta name = “Description” content = “Guide du diagnostic de l’ostéoporose">

<meta name = “keywords” content = “Ostéoporose, maladie, os, fracture, rayons X">

-          La première balise comprend simplement le ou les noms des auteurs de la page.

-          La deuxième balise comprend une explication simple en quelques mots (sous forme de phrase) du contenu de la page.

-          La troisième balise comporte une liste de mots séparés par des virgules utiles pour certains moteurs de recherche qui vont s’en servir pour comparer cette liste à la requête du surfeur.

Le Web est désormais disponibles à de nombreux internautes dans le monde entier et le besoin de moteurs de recherche se fait ressentir. C’est pourquoi certaines personnes vont se pencher sur le sujet et proposer des moteurs à base d’algorithmes de plus en plus efficaces.