Les moteurs de recherche

Dans cet article, nous allons expliquer le principe de fonctionnement d’un moteur de recherche. Pour la plupart des internautes, « moteur de recherche » est synonyme de Google ou Bing. En fait, je les appellerais plutôt « sites de recherche ». Un moteur de recherche est en fait un outil ou ensemble d’outils permettant de construire par exemple ces « sites de recherche », mais également d’ajouter des fonctionnalités de recherche à divers types d’applications (CRM, messagerie, …).

Avant de pouvoir offrir une page de recherche et des résultats, il est nécessaire de réaliser certaines tâches comme par exemple la création d’un index des données. En simplifiant, les étapes de la mise en place d’une solution de recherche sont :

• accéder aux données à indexer : système de fichiers, sites web (crawler), base de données, messagerie, …
• parser les données à indexer afin d’en extraire le texte, diverses propriétés (titre, auteur, date de publication, … ) et pour un site web les liens vers d’autres pages
• supporter différents jeux de caractères et différentes langues (et éventuellement être capable de détecter la langue du document)
• créer l’index proprement dit qui est la plus part du temps constitué d’un ensemble de fichiers et de structures de données de type B-trees.
• paramétrer la solution au moyen de listes de mots vides, de dictionnaire de synonymes, de thésaurus, …
• Mettre en place la sécurité : authentification et droits d’accès
• administrer la solution au moyen d’outils de manipulation des index (création, suppression, optimisation, sauvegarde, réindexation, …)
• créer une interface de recherche Web ou embarquée dans une application non Web
• mettre en place des fonctionnalités facilitant l’accès à la bonne information : alertes, filtres, entités nommées

Lors de l’apparition des premières solutions commerciales à la fin des années 80 (avec BRS/Search ou Lotus magellan par exemple), les moteurs de recherche permettent d’indexer uniquement des fichiers de format simple (texte) localisés dans un système de fichiers. Avec le temps, ils ont appris à accéder à des sources d’informations variées, à traiter un très grand nombre de formats de fichiers, à tenir compte des droits d’accès aux données et bien d’autres choses encore.

Les moteurs de recherches sont très connus au travers des solutions WEB telles que Google ou Bing mais ils sont également présents dans des outils d’entreprise (Gestion de contenu, CRM, Gestion documentaire, Outils de veille) et des outils grands publics tel que la messagerie ou le « Desktop search » (Google Desktop, Copernic, …).

Fonctionnement d’un moteur de recherche

L’index

La brique de base d’un moteur de recherche c’est l’index. Il s’agit d’une structure de données organisée afin de permettre au moteur de retrouver très rapidement les documents correspondants a une requête de l’utilisateur. Il s’agit dans la plupart des cas d’un ensemble de fichiers. Ces fichiers ont pour rôle de mémoriser l’emplacement de TOUS LES MOTS présents dans l’ensemble des données indexées (soit plusieurs milliers à plusieurs millions d’occurrences de mots). Un index ne contient pas une entrée par document avec la liste des mots du document, mais il contient une entrée par mot avec la liste des documents ou se trouve ce mot ET pour chaque occurrence d’un mot, sa position exacte dans les documents.

Imaginons par exemple un tous petit corpus de 4 documents contenant seulement une phrase chacun.

On constate que certains mots sont présents plusieurs fois. En considérant les mots « l », « que », « je », « est », « bien », « suis », « sur », « mon », « m », « a »  et « de » comme vides, et en utilisant la notation « identifiant document / position » pour décrire les positions des mots, ceci donnerait dans l’index :

On constate tout d’abord que l’utilisation de mots vides permet de réduire considérablement la taille d’un index et donc d’optimiser les temps d’indexation puis de recherche. On comprend également que lorsque le nombre de documents va augmenter, le nombre de mots nouveaux va avoir tendance à se stabiliser car les mots des documents ajoutés seront souvent déjà présents dans l’index. La taille de l’index va croître moins vite car pour les mots déjà présents dans l’index, seules la référence des documents et la position des mots sont à ajouter au fichier d’index.

Dans un index, les mots ne sont pas classés alphabétiquement comme dans mon exemple, mais placés dans une structure de données de type B-Tree. Ajouter, trouver et supprimer un élément dans une telle structure est infiniment plus rapide que dans une liste ordonnée.

Un moteur de recherche peut gérer simultanément plusieurs index (pour des données distinctes d’une même application, pour des applications différentes d’une même société, pour séparer des données dans des langues différentes, …).

Les requêtes

Fort de cet index, le moteur de recherche est à même de répondre aux requêtes des utilisateurs. Il existe deux types de requête : les requêtes booléennes et les requêtes en « langage naturel ».

Les requêtes booléennes ont toujours existé dans les moteurs de recherche. Elles permettent de décrire les documents désirés au moyen d’opérateurs tels que : ET, OU, SAUF, PROCHE, PHRASE EXACTE, TRONCATURE, …

Voici quelques exemples de requêtes et de résultats basés sur notre index

Ce type de requête utilise uniquement des éléments statistiques fournis par l’index : présence, position et occurrences des mots. Le gros inconvénient de ce type de requête est la nécessitée pour l’utilisateur de connaître la syntaxe booléenne propre à l’outil utilisé ou pour les concepteurs de fournir des écrans de recherche complexes guidant l’utilisateur (comme par exemple la recherche avancée de Google)

Les requêtes en langage naturel sont apparues plus tard. Le premier but est de permettre à l’utilisateur d’interroger le système à l’aide d’expressions ou de phrases plus ou moins précises mais surtout de ne pas être obliger l’utilisateur à connaître une syntaxe booléenne complexe et rébarbative.

Par exemple, l’utilisateur qui s’intéresse à la dégustation des avocats saisit la requête « Comment déguster un avocat ? ». Bien que « comment » et « déguster » ne soient présents dans aucun document, le moteur va sans doute trouver des résultats. En effet, les moteurs retirent les mots vides de la question et aussi les mots ou expressions typiques d’une question : « comment », « pourquoi », « je cherche … ». Exit donc le mot « comment ». Ensuite, si aucun document ne correspond exactement, le moteur doit fournir les documents les plus proches possible de la requête et doit utiliser tous les mots de la requête pour orienter le résultat. Dans cet exemple, « déguster » doit orienter vers un avocat qui se mange et donc retourner les documents 1 et 2. Bien sur cela impose un index plus complexe qui contienne une information complémentaire sur la nature des avocats. Ce qui donne par exemple l’index suivant :

Pour ce type de requête, le moteur utilise les éléments statistiques de l’index, mais également des informations sémantiques (sens des mots), morphologiques (forme des mots) et syntaxique (mots composés et expressions) après analyse du texte indexé et de la requête.

Pertinence des résultats

Une fois obtenue la liste des documents correspondants à une requête, ce que l’on demande à un moteur est de nous fournir les résultats classés par « pertinence ». Il s’agit de retourner en premier les documents qui répondent le mieux à la requête et là encore, le moteur s’appuie sur son index pour calculer la pertinence. Selon les moteurs, il existe plusieurs algorithmes de calcul de pertinence. Par exemple, l’algorithme qui privilégie les documents qui contiennent le plus de mots de la requête. Dans ce cas, pour la requête « avocat OU pourri », le moteur va retourner le document 2 en premier.

Deux autres indicateurs majeurs de pertinence sont la proximité et le bon ordonnacement des mots de la requête dans le document.

Les algorithmes peuvent être très variés. Par exemple, le très célèbre « Page Rank » de Google n’est pas basé que sur la fréquence d’apparition des mots recherchés au sein des documents trouvés, mais grandement sur la popularité du site hébergeant le document en tenant compte du nombre des autres sites pointant sur lui.

Certains moteurs savent également, par des algorithmes d’analyse grammaticale dépendants de la langue, déterminer si l’expression recherchée (dégustation d’avocat, par exemple) est un sujet central dans le document ou bien traitée en aparté. Dans le premier cas, le document sera considéré comme plus pertinent.

Les propriété associées aux documents (metadonnées)

Aux documents indexés sont généralement associées un minimum de métadonnées : titre, auteur, mots-clés, date de publication, …. Ces métadonnées sont gérées dans une application métier (messagerie, CRM) et saisies par des utilisateurs. Une partie d’entre elles sont indexées par le moteur et donc elles peuvent être utilisées comme critère de recherche ou de tri des résultats (par exemple, pour rechercher tous les documents sur les avocats et publiés après une certaine date) et affichées dans la liste de résultats.

Il existe par exemple un schéma de metadonnées normalisé (ISO 15836) appelé Dublin Core. Le Dublin Core permet de décrire des ressources numériques ou physiques et d’établir des relations avec d’autres ressources. Il comprend officiellement 15 éléments de description formels (titre, créateur, éditeur), intellectuels (sujet, description, langue, …) et relatifs à la propriété intellectuelle.

Faut-il choisir un moteur « statistique » ou « sémantique » ?

Comme cela a été dit précédemment, tous les moteurs sont statistiques à la base. La question doit donc être « Faut-il choisir un moteur avec des fonctionnalités sémantiques ? ». Plusieurs paramètres sont à prendre en considération afin de répondre à cette question.

Quelle est la nature des données (spécifique à un métier, généraliste) ?

Les moteurs sémantiques mettent en oeuvre des algorithmes d’analyse du texte qui nécessitent des dictionnaires. Le rôle de ces dictionnaires est de fournir des informations sur les mots : nature (nom, adjectif), synonymes, …. Si le ou les domaines couverts par les documents indexés sont multiples, vastes et évolutifs, ces dictionnaires seront plus longs (donc coûteux) à élaborer et à maintenir.

Les moteurs sémantiques sont donc plus adaptés à des moteurs spécialisés qu’à des moteurs généralistes. Il est toutefois possible de mettre en oeuvre une « couche sémantique » généraliste et légères qui ne demande pas trop de maintenance des dictionnaires. Mais, avec une couche sémantique légère, il ne faudra pas attendre de miracles avec des applications métiers (domaine médical, scientifique ou financier par exemple).

Quel est le volume des données ?

Sans doute pas le paramètre le plus important, mais il faut savoir que les étapes d’analyse sémantique des documents en phase d’indexation entraînent des temps de traitement plus long. C’est à prendre en compte donc si les temps d’indexation sont critiques et/ou les documents très nombreux.

Quel type de population va utiliser le moteur de recherche ?

Il faut savoir que les moteurs généralistes traitent 80% de requêtes constituées d’un seul mot. Contrairement à la requête « Comment déguster un avocat ? », la requête « avocat » ne fournira pas d’information sur la nature de l’avocat recherché. Ces requêtes sont par défaut de type booléen et la couche sémantique du moteur n’est dans ce cas d’aucune utilité.

Sur des sites spécialisés utilisés par des spécialistes, les requêtes seront globalement plus précises et là, la couche sémantique donnera sa pleine puissance.

Quel investissement matériel, logiciel et humain peut être alloué au projet ?

Bien sur, il faut tenir compte des coups de licences et de matériels imposés par la solution évaluée, mais il faut surtout bien évaluer les ressources humaines nécessaires à la mise en oeuvre de la solution. Un moteur sémantique nécessite souvent un travail important en amont du projet pour constituer ou enrichir les dictionnaires. En phase d’exploitation, il est aussi nécessaire de bien suivre l’utilisation faite du moteur afin de déterminer les ajustements à apporter dans les dictionnaires (quelles requêtes sont posées, quelles requêtes ne remontent pas de documents et pourquoi, …).

Quel est l’impact sur l’interface utilisateur et sa complexité d’utilisation ?

Plus haut je disais qu’un moteur sémantique permet de mettre en place une interface plus simple. C’est vrai pour la zone de saisie de la requête, mais d’autres éléments peuvent venir s’ajouter à la liste de résultats :

• des navigateurs (liste d’auteurs, liste de thèmes, listes de lieux) qui vont permettre à l’utilisateur d’affiner sa requête. Les données affichées par ces navigateurs sont relatives aux documents trouvés et peuvent soit provenir des métadonnées, soit avoir fait l’objet d’une détection par le moteur dans le flux textuel des documents. Cette détection d’entités nommées est automatique (par calcul statistique) et/ou basée sur des dictionnaires.
• une liste de questions proches et suggérées par le moteur.

A prioris, ces fonctions sont des plus, mais elles complexifient l’interface.

Choix et mise en oeuvre d’une solution

La mise en place d’une solution de recherche se fait en deux temps : la recherche et la sélection d’un moteur, puis sa mise en oeuvre. La seconde phase sera bien sur plus simple, plus rapide et avec moins de surprises si la première phase a été bien menée.

Le choix d’une solution passe par l’écriture d’un cahier des charges, la rencontre des éditeurs et après une première sélection la réalisation de un ou deux prototypes pour valider les fonctionnalités critiques.

En phase de définition et de validation du prototype, une personne connaissant parfaitement le corpus de données et le métier doit être impliquée. De même plus tard en phase d’exploitation de la solution cette personne aura pour rôle d’évaluer régulièrement le bon fonctionnement du système : documents trouvés à tort (bruit), documents non trouvés et requêtes sans réponse (silence), pertinence des réponses.

Dès la phase d’élaboration du cahier des charges, il est souhaitable de se faire assister pas un consultant spécialisé. Cette phase a également la vertu d’être pédagogique et donc permet de mieux conduire la sélection et la mise en oeuvre future.

Quelques paramètres à prendre en compte dans le choix d’une solution :

• fonctionnalités
• langages supportés
• volumétrie acceptée
• performance en indexation et en recherche (coût de la couche sémantique)
• ergonomie de l’interface de recherche
• pertinence des résultats
• ouverture de la solution (API) et extensions possibles (connexion à une source de données spécifique)
• gestion de la sécurité et confidentialité des données
• architecture préconisée (nombre de serveurs, mémoire, processeurs, espace disque), système d’exploitation, gestion de la monté en charge et autres pre-requis (matériels et logiciels)
• administration et paramétrage du produit (charge de travail devant être en adéquation aux ressources disponibles en phase d’exploitation)
• compétences à acquérir

Remerciements à Philippe et Eric.