9. Introduction à la recherche d’information

Supports complémentaires:

S1: les principes

Qu’est ce que la recherche d’information

La Recherche d’Information (RI, Information Retrieval, IR en anglais) consiste à trouver des documents peu ou faiblement structurés, dans une grande collection, en fonction d’un besoin d’information. Le domaine d’application le plus connu est celui de la recherche “plein texte”. Etant donné une collection de documents constitués essentiellement de texte, comment trouver les plus pertinents en fonction d’un besoin exprimé par quelques mots-clés? La RI développe des modèles pour interpréter les documents, le besoin, et les rapprocher, des techniques pour calculer des réponses rapidement même en présence de collections très volumineuses, enfin des systèmes (“moteurs de recherches”) fournissant des solutions sophistiquées prêtes à l’emploi.

La RI a pris une très grande importance, en raison notamment de l’émergence de vaste sources de documents que l’on peut agréger et exploiter (le Web bien sûr, mais aussi les systèmes d’information d’entreprise). Les techniques utilisées ont également beaucoup progressé, avec des résultats spectaculaires. La RI est maintenant omniprésente dans beaucoup d’environnements informatiques, et notamment:

  • La recherche sur le Web, utilisée quotidiennement par des milliards d’utilisateurs.
  • La recherche de messages dans votre boîte mail.
  • La recherche de fichiers sur votre ordinateur (Spotlight).
  • La recherche de sources dans une base documentaire, publique ou privée.

Ce chapitre introduit ces différents aspects en se concentrant sur la recherche d’information appliquée à des collections de documents structurés, comprenant des parties textuelles importantes.

Précision et rappel

Comme le montre la définition assez imprécise donnée en préambule, la recherche d’information se donne un objectif à la fois ambitieux et relativement vague. Cela s’explique en partie par le contexte d’utilisation de ces systèmes. Là où, avec une base de données classique, on connaît le schéma des données, leur organisation générale, avec des contraintes qui garantissent qu’elles ont une certaine régularité, en RI les données (ou “documents”) sont souvent hétérogènes, de provenances diverses, présentent des irrégularités et des variations dues à l’absence de contrainte et de validation au moment de leur création. De plus, un système de RI est souvent utilisé par des utilisateurs non-experts. À la difficulté d’interpréter le contenu des documents et de le décrire s’ajoute celle de comprendre le “besoin”, exprimé souvent de manière très partielle.

D’une certaine manière, la RI vise essentiellement à prendre en compte ces difficultés pour proposer des réponses les plus pertinentes possibles. La notion de pertinence est centrale ici: Un document est pertinent s’il satisfait le besoin exprimé. Quand on utilise SQL, on considère que la réponse est toujours exacte car définie de manière mathématique en fonction de l’état de la base. En RI, on ne peut jamais considérer qu’un résultat, constitué d’un ensemble de documents, est exact, mais on mesure son degré de pertinence en distinguant:

  • Faux positifs: ce sont les documents non pertinents inclus dans le résultat; ils ont été sélectionnés à tort.
  • Faux négatifs: ce sont les documents pertinents qui ne sont pas inclus dans le résultat.

Deux indicateurs formels, basés sur ces notions, sont couramment employés pour mesurer la qualité d’un système de RI.

La précision

La précision mesure la fraction des vrais positifs dans le résultat r. Si on note respectivement \(P_r\) et \(FP_r\) le nombre de vrais et de faux positifs dans r, alors

\[\text{précision} = \frac{P_r}{P_r + FP_r} = frac{P_r}{|r|}\]

Une précision de 1 correspond à l’absence totale de faux positifs. Une précision nulle indique un résultat ne contenant auxcun document pertinent.

Le rappel

Le rappel mesure la fraction de faux négatifs. Si on note \(VP\) le nombre de vrais positifs dans la collection (supposé connu), alors le nombre de faux négatifs est \(VP - P_r\), et le rappel est:

\[\frac{P_r}{VP}\]

Ces deux indicateurs sont très difficiles à optimiser simultanément. Pour augmenter le rappel, il suffit d’ajouter plus de documents dans le résultat, au détriment de la précision. À l’extrême, un résultat qui contient toute la collection interrogée a un rappel de 1, et une précision qui tend vers 0. Inversement, si on fait le choix de ne garder dans le résultat que les documents dont on est sûr de la pertinence, la précision s’améliore mais on augmente le risque de faux négatifs, et donc d’un rappel dégradé.

L’évaluation d’un système de RI est un tâche complexe et fragile car elle repose sur des enquêtes impliquant des utilisateurs. Reportez-vous à la référence citée au début du chapitre pour en savoir plus.

La recherche plein texte

Commençons par étudier une méthode simple de recherche pour trouver des documents répondant à une recherche dite “plein texte” constituée d’un ensemble de mots-clés. On va donner à cette recherche une définition assez restrictive pour l’instant: il s’agit de trouver tous les documents contenant tous les mots-clés. Prenons pour exemple l’ensemble (modeste) de documents ci-dessous.

  • \(d_1\): Le loup est dans la bergerie.
  • \(d_2\): Le loup et le trois petits cochons
  • \(d_3\): Les moutons sont dans la bergerie.
  • \(d_4\): Spider Cochon, Spider Cochon, il peut marcher au plafond.
  • \(d_5\): Un loup a mangé un mouton, les autres loups sont restés dans la bergerie.
  • \(d_6\): Il y a trois moutons dans le pré, et un mouton dans la gueule du loup.
  • \(d_7\): Le cochon est à 12 le Kg, le mouton à  10 E/Kg
  • \(d_8\): Les trois petits loups et le grand méchant cochon

Et ainsi de suite. Supposons que l’on recherche tous les documents parlant de loups, de moutons mais pas de bergerie (c’est le besoin). Une solution simple consiste à parcourir tous les documents et à tester la présence des mots-clés. Ce n’est pas très satisfaisant car:

  • c’est potentiellement long, pas sur notre exemple bien sûr, mais en présence d’un ensemble volumineux de documents;
  • le critère “pas de bergerie” n’est pas facile à traiter;
  • les autres types de recherche (“le mot ‘loup’ doit être près du mot ‘mouton’”) sont difficiles;
  • quid si je veux classer par pertinence les documents trouvés?

On peut faire mieux en créant une structure compacte sur laquelle peuvent s’effectuer les opérations de recherche. Les données sont organisés dans une matrice (dite d’incidence) qui représente l’occurrence (ou non) de chaque mot dans chaque document. On peut, au choix, représenter les mots en colonnes et les documents en ligne, ou l’inverse. La première solution semble plus naturelle (chaque fois que j’insère un nouveau document, j’ajoute une ligne dans la matrice). La seconde, souvent qualifiée de matrice inversée est en fait beaucoup plus appropriée pour une recherche efficace.

Important

nous utilisons progressivement la notion de terme (token en anglais) qui est un peu différente de celle de “mot”. Le vocabulaire, parfois appelé dictionnaire, est l’ensemble des termes sur lesquels on peut poser une requête. Ces notions seront développées plus loin.

Commençons par montrer une matrice d’incidence avec les documents en ligne. On se limite au vocabulaire suivant: {“loup”, “mouton”, “cochon”, “bergerie”, “pré”, “gueule”}.

Tableau 9.1 La matrice d’incidence
  loup mouton cochon bergerie pré gueule
\(d_1\) 1 0 0 1 0 0
\(d_2\) 1 0 1 0 0 0
\(d_3\) 0 1 0 1 0 0
\(d_4\) 0 0 1 0 0 0
\(d_5\) 1 1 0 1 0 0
\(d_6\) 1 1 0 0 1 1
\(d_7\) 0 1 1 0 0 0
\(d_8\) 1 0 1 0 0 0

Cette structure est parfois utilisée dans les bases de données sous le nom d’index bitmap. Elle permet de répondre à la recherche de la manière suivante. On prend les vecteurs d’incidence de chaque terme contenu dans la requête, soit les colonnes dans notre représentation.

  • Loup: 11001101
  • Mouton: 00101110
  • Bergerie: 01010011

On fait un et (logique) sur les vecteurs de Loup et Mouton et on obtient 00001100. Puis on fait un et du résultat avec le complément du vecteur de Bergerie (01010111) et on obtient 00000100, d’où on déduit que la réponse est limitée au document \(d_6\).

Si on imagine maintenant des données à grande échelle, on s’aperçoit que cette approche un peu naïve soulève quelques problèmes. Posons par exemple les hypothèses suivantes:

  • Un million de documents, mille mots chacun en moyenne.
  • Disons 6 octets par mot, soit 6 GO (pas très gros en fait!)
  • Disons 500000 termes distincts

La matrice a \(500 \times 10^9\) bits, soit 62 GO. Elle ne tient pas en mémoire, ce qui va beaucoup compliquer les choses.... Comment faire mieux?

Une première remarque est que nous avons besoin des vecteurs pour les termes (mots) pour effectuer des opérations logiques (and, or, not) et il est donc préférable d’inverser la matrice pour disposer les termes en ligne (la représentation est une question de convention: ce qui est important c’est qu’au niveau de la structure de données, le vecteur d’incidence associé à un terme soit stocké contigument et donc accessible simplement et rapidement). On obtient la structure de la figure Inversion de la matrice pour notre petit ensemble de documents.

_images/inverted-index-bool.png

Fig. 9.1 Inversion de la matrice

Seconde remarque: la matrice d’incidence est creuse: dans l’ensemble de la matrice, il n’y a que \(10^9\) positions avec des 1, soit un sur 500. Il est donc tout à fait inutile de représenter les cellules avec des 0. On obtient une structure appelée index inversé qui est essentiellement l’ensemble des lignes de la matrice d’incidence, dans laquelle on ne représente que les cellules correspondant à au moins une occurrence du terme (en ligne) dans le document (en colonne).

Important

Comme on ne représente plus l’ensemble des colonnes pour chaque ligne, il faut indiquer, pour chaque cellule, à quelle colonne elle correspond. Pour cela, on place dans les cellules l’identifiant du document (docId). De plus chaque liste est triée sur l’identifiant du document.

La figure Un index inversé montre un exemple d’index inversé pour trois termes, pour une collection importante de documents consacrés à nos animaux familiers. À chaque terme est associé une liste inverse.

_images/inverted-index.png

Fig. 9.2 Un index inversé

On parle donc de cochon dans les documents 2, 31, 54 et 101 (notez que les documents sont ordonnées - très important). Il est clair que la taille des listes inverses varie en fonction de la fréquence d’un terme dans la collection.

La structure d’index inversé est utilisée dans tous les moteurs de recherche. Elle présente d’excellentes propriétés pour une recherche efficace, avec en particulier des possibilités importantes de compression des listes associées à chaque terme.

Vocabulaire

Le dictionnaire (dictionary) est l’ensemble des termes de l’index inversé; le répertoire est la structure qui associe chaque terme à l’adresse de la liste inversée (posting list) associée au terme. Enfin on ne parle plus de cellule (la matrice a disparu) mais d’entrée pour désigner un élément d’une liste inverse.

En principe, le répertoire est toujours en mémoire, ce qui permet de trouver très rapidement les listes impliquées dans la recherche. Les listes inverses sont, autant que possible, en mémoire, sinon elles sont compressées et stockées dans des fichiers (contigus) sur le disque.

Opérations de recherche

Etant donné cette structure, recherchons les documents parlant de loup et de mouton. On ne peut plus faire un et sur des tableaux de bits de taille fixe puisque nous avons maintenant des listes de taille variable. L’algorithme employé est une fusion (“merge”) de liste triées. C’est une technique très efficace qui consiste à parcourir en parallèle et séquentiellement des listes, en une seule fois. Le parcours unique est permis par le tri des listes sur un même critère (l’identifiant du document).

La figure Parcours linéaire pour la fusion de listes triées montre comment on traite la requête loup et mouton. On maintient deux curseurs, positionnés au départ au début de chaque liste. L’algorithme compare les valeurs des docId contenues dans les cellules pointées par les deux curseurs. On compare ces deux valeurs, puis:

  • (choix A) si elles sont égales, on a trouvé un document: on place son identifiant dans le résultat, à gauche; on avance les deux curseurs d’un cran
  • (choix B) sinon, on avance le curseur pointant sur la cellule dont la valeur est la plus petite, jusqu’à atteindre ou dépasser la valeur la plus grande.
_images/loup-et-mouton-full.png

Fig. 9.3 Parcours linéaire pour la fusion de listes triées

La figure Parcours linéaire pour la fusion de listes triées se lit de gauche à droite, de haut en bas. On applique tout d’abord deux fois le choix A: les documents 1 et 2 parlent de loup et de mouton. À la troisième étape, le curseur du haut (loup) pointe sur le document 3, le pointeur du bas (mouton) sur le document 4. On applique le choix B en déplaçant le curseur du haut jusqu’à la valeur 4.

Et ainsi de suite. Il est clair qu’un seul parcours suffit. La recherche est linéaire, et l’efficacité est garantie par un parcours séquentiel d’une structure (la liste) très compacte. De plus, il n’est pas nécessaire d’attendre la fin du parcours de toutes les listes pour commencer à obtenir le résultat. l’algorithme est résumé ci-dessous.

// Fusion de deux listes l1 et l2
function Intersect($l1, $l2)
{
  $résultat = [];
  // Début de la fusion des listes
  while ($l1 != null and $l2 != null) {
    if ($l1.docId == $l2.docId) {
      // On a trouvé un document contenant les deux termes
      $résultat += $l1.docId;
      // Avançons sur les deux listes
      $l1 = $l1.next; $l2 = $l2.next;
    }
    else if ($l1.docId < $l2.docId) {
      // Avançons sur l1
      $l1 = $l1.next;
    }
    else {
       // Avançons sur l2
      $l2 = $l2.next;
    }
  }
}

C’est l’algorithme de base de la recherche d’information. Dans la version présentée ici, on satisfait des requêtes dites booléennes: l’appartenance d’un document au résultat est binaire, et il n’y a aucun classement par pertinence.

À partir de cette technique élémentaire, on peut commencer à raffiner, pour aboutir aux techniques sophistiquées visant à capturer au mieux le besoin de l’utilisateur, à trouver les documents qui satisfont ce besoin et à les classer par pertinence. Pour en arriver là, tout un ensemble d’étapes que nous avons ignorées dans la présentation abrégée qui précède sont nécessaires. Nous les reprenons dans ce qui suit.

Exercices

Exercice Ex-S1-1: précision et rappel, calculons

Voici une matrice donnant les faux positifs et faux négatifs, vrais positifs et vrais négatifs pour une recherche.

Tableau 9.2 Table de contingence
  Pertinent Non pertinent
Ramené 50 10
Non ramené 30 120

Quelques questions:

  • Donnez la précision et le rappel.
  • Quelle méthode stupide donne toujours un rappel maximal?
  • Quelle méthode stupide donne une précision infinie?

Correction

  • Précision: 50 / 60
  • Rappel: 50 / 80
  • Ramener tous les documents
  • Ne ramener aucun document

Exercice Ex-S1-2: précision et rappel, réfléchissons.

Soit un système qui affiche systématiquement 20 documents, ni plus ni moins, pour toutes les recherches. Indiquez quel est la précision et le rappel dans les cas suivants:

  • Je cherche un document unique, il est affiché parmi les 20.
  • Ma base contient 100 documents, je veux tous les obtenir, le système m’en renvoie 20.
  • Je fais une recherche dont je sais qu’elle devrait me ramener 30 documents. Parmi les 20 que renvoie le système, je n’en retrouve que 10 parmi ceux attendus.

Correction

  • p = 1/20, r = 1/1 = 1
  • p = 20/20 = 1 ; r = 20/100 = 0.2
  • p = 10/20 = 0.5 ; r = 10/30 = 1/3

Exercice Ex-S1-3: proposons une autre mesure

Voici une autre mesure de qualité, que nous appellerons exactitude comme traduction de accuracy (exactitude). Elle se définit comme la fraction du résultat qui est correcte (en comptant les vrais positifs et vrais négatifs comme corrects). Donc,

\[accuracy = \frac{t_n + t_p}{t_n + t_p + f_n + f_p}.\]

p et n désignent les négatifs et positifs, t et f les vrais et faux, respectivement.

Cette mesure ne convient pas en recherche d’information. Pourquoi? Imaginez un système où seule une infime partie des documents sont pertinents, quelle que soit la recherche.

  • Quelle serait l’exactitude dans ce cas?
  • Quelle méthode simple et stupide donnerait une exactitude proche de la perfection?

Correction

  • L’exactitude tend vers 1
  • Il suffit de renvoyer un résultat vide, quelle que soit la requête.

Exercice Ex-S1-4: matrice d’incidence

Faire un fichier Excel (ou l’équivalent) qui calcule la taille d’une collection, la taille de la matrice d’incidence, et la densité de 1 dans cette matrice, en fonction des paramètres suivants :

  • n, le nombre de documents,
  • d, le nombre de termes distincts,
  • m, le nombre moyen de mots dans un document,
  • w, la taille moyenne d’un mot (en octets).

Exercice Ex-S1-5: algorithme de négation

On sait faire une fusion pour une recherche de type ET. La recherche de type OU est évidente (?). Montrer qu’un algorithme similaire existe pour une recherche de type NOT (“les documents qui parlent de loup mais pas de mouton”).

S2: la pratique: MongoDB/ElasticSearch

Passons au concret avec l’installation d’un moteur de recherche, et l’indexation de l’une de nos bases (en l’occurrence MongoDB, mais vous pouvez faire la même chose avec CouchDB ou BaseX, cf. exercices). Nous allons utiliser ici Elastic Search, un moteur de recherche qui s’installe et s’initialise très facilement.

Nous allons ici nous appuyer entièrement sur les choix par défaut d’ElasticSearch pour nous concentrer sur son utilisation. La construction d’un moteur de recherche en production demande un peu plus de soin: nous reprendrons les différentes étapes pas à pas, cette fois avec Solr, l’autre système étudié dans ce cours.

Mise en place d’ElasticSearch

Commençons par l’installation avec Docker. Voici une commande qui devrait fonctionner sous tous les systèmes et mettre ElasticSearch en attente sur le port 9200.

docker run -d --name es1  -p 9200:9200 -p 9300:9300 elasticsearch:2.4 \
       -Des.index.number_of_shards=1 \
       -Des.index.number_of_replicas=0

Quelques remarques:

  • ElasticSearch évolue rapidement. Pour éviter que les instructions qui suivent ne deviennent rapidement obsolète, j’indique le numéro de version dans l’installation avec Docker (ici, la 2.4).
  • L’option -d lance le serveur ElasticSearch en tâche de fond.
  • Les serveurs ElasticSearch prennent par défaut des noms tirés du catalogue des héros Marvel.
  • L’option -D permet de configurer le serveur en affectant des valeurs à certains paramètres.

Ici, le nombre de fragments de l’index est fixé à 1, et le degré de réplication à 0. Cela revient à demander à ElasticSearch de s’exécuter en mode local, sans distribution. Tout cela sera revu plus tard.

Pour une inspection confortable du serveur et des index ElasticSearch, une interface Web est disponible sous forme de plugin. Vous avez entre autres possibilités, Kopf et HQ. Voici la commande d’installation du premier (rappel: l’identifiant du conteneur s’obtient avec docker ps).

docker exec <containerId> plugin install lmenezes/elasticsearch-kopf

Et celle du second:

docker exec <containerId> plugin install  royrusso/elasticsearch-HQ

Vous pouvez directement vous adresser au serveur REST en écoute sur le port 9200. Un accès avec votre navigateur (ou avec cUrl) à http://<conteneurIP>:9200 devrait renvoyer un document JSON semblable à celui-ci:

{
  "status" : 200,
  "name" : "Crimson",
  "cluster_name" : "elasticsearch",
  "version" : {
    "number" : "2.4.2",
    "...": "...",
   "lucene_version" : "5.10.2"
  } ,
 "tagline" : "You Know, for Search"
}

Il est plus pratique d’utiliser l’interface Web offerte par l’un des plugins recommandés précédemment. En accédant avec votre navigateur à http://<conteneurIP>:9200/_plugin/hq par exemple vous devriez obtenir l’affichage de la Fig. 9.4 montrant le serveur et proposant tout un ensemble d’actions. Remplacez hq par kopf dans l’URL pour obtenir l’autre interface.

_images/es-webui.png

Fig. 9.4 L’interface Web (plugin HQ) de ElasticSearch

Toutes les interactions avec un serveur ElasticSearch passent par une interface REST basée sur JSON. ElasticSearch organise les données selon trois niveaux:

  • l’index regroupe des chemins d’accès à un collection de documents;
  • le type désigne le format du document indexé;
  • l’identifiant sert de clé d’accès à un document;
  • enfin chaque document a un numéro de version.

Pour indexer un de nos films dans l’index nfe204, avec le type movies, on exécute la commande suivante:

curl -X PUT http://<containerIP>:9200/nfe204/movies/movie:1 --data-binary @movie_1.json

Note

Les versions récentes d’ElasticSearch n’acceptent pas d’attribut nommé _id dans le document JSON. Retirez-le avant d’effectuer l’insertion.

Le PUT crée une “ressource” (au sens Web/REST du terme, cf. chapitre Interrogation de bases NoSQL) à l’URL indiquée. Attention à bien spécifier comme identifiant de la ressource la même valeur que celle du champ _id du document JSON. Si vous avez pratiqué un peu l’interface REST de CouchDB, vous remarquerez que l’on retrouve exactement les mêmes principes.

La réponse devrait être:

{"_index":"nfe204","_type":"movies","_id":"movie:1","_version":1,"created":true}

Si nous rafraichissons l’interface web, nous obtenons l’affichage de la figure Apparition d’un nouvel index, avec un nouvel index nfe204.

_images/es-insert.png

Fig. 9.5 Apparition d’un nouvel index

Bien entendu, la ressource étant créée, un GET permet de la ramener.

curl -X GET http://<containerIP>:9200/nfe204/movies/movie:1

On peut insérer les documents un par un, mais on peut aussi faire mieux (et beaucoup plus robuste) en synchronisant l’index ElasticSearch avec une base documentaire. C’est ce que nous allons maintenant faire avec notre base MongoDB.

Synchronisation avec MongoDB

Note

Cette section est obsolète avec la suppression des rivers par les versions de MongoDB postérieures à la 2.0. Pour l’instant, insérez directement le fichier http://b3d.bdpedia.fr/files/movies_elastic.json avec la commande suivante:

curl -s -XPOST http://<conteneurIP>:9200/_bulk/ --data-binary @movies_elastic.json

(Début de section obsolète)

Une river dans ElasticSearch désigne un mécanisme de surveillance d’une source de données (une base MongoDB par exemple, ou MySQL, ou une API REST Twitter, etc.) qui détecte toute modification de cette source et synchronise un index ElasticSearch. C’est un dispositif très appréciable car on a la garantie que l’index est en phase avec la source de données, ce qui évite des surprises désagréables comme:

  • un document présent dans la source mais pas dans l’index, et donc non trouvé lors d’une recherche;
  • un document présent dans l’index mais détruit dans la source, trouvé donc par une recherche alors qu’il n’existe pas.

Les rivers sont disponibles sous forme d’extensions nommées plugins. La river MongoDB est disponible ici.

Vous pouvez consulter cette page pour des informations sur les versions récentes ou pour consulter la documentation. L’installation se fait comme pour le plugin head (vérifiez le numéro de la version courante au préalable):

cd esdir;
bin/plugin --install com.github.richardwilly98.elasticsearch/elasticsearch-river-mongodb/2.0.7

Stoppez puis relancez le serveur ElasticSearch, vous devriez obtenir au démarrage un message confirmant la disponibilité du plugin:

[plugins] [Serveur d'index] loaded [mongodb-river], sites [head, river-mongodb]

Maintenant lancez votre serveur MongoDB. Une option spéciale est nécessaire pour assurer la synchronisation:

mongod --replSet rs0

Lancez également un client mongo et entrez la commande suivante:

> rs.initiate()

Voilà. Pour ceux qui se posent des questions: MongoDB est maintenant lancé en mode réplication, ce qui assure que des messages sont produits par le serveur mongod pour chaque mise à jour de la base, messages qui sont capturés par la river ElasticSearch. Il reste à déclarer cette “rivière”. Voici le document de configuration (minimal).

{
  "type": "mongodb",
  "mongodb": {
  "db": "nfe204",
  "collection": "movies"
  },
  "index": {
   "name": "nfe204",
   "type": "movies"
  }
}

Important

Cela suppose bien entendu l’existence d’une collection movies dans la base nfe204. À adapter à votre environnement si vous avez choisi des noms différents: cf. les chapitres qui précèdent.

Cela suppose également que l’index n’existe pas au préalable. Si vous avez créé un index nfe204, détruisez le avant de définir la river.

Sauvegardez ce document dans le fichier mongo-river.json. La création de la rivière s’effectue avec une requête REST:

curl -X PUT http://localhost:9200/_river/mongodb/_meta -d @mongo-river.json

Et voilà. Jetez un œil du côté de la fenêtre où vous avez lancé le serveur ElasticSearch pour vérifier que vous avez bien un message sympathique comme celui-ci:

[org.elasticsearch.river.mongodb.MongoDBRiver] Started river mongodb

Bases documentaires et moteur de recherche

Un moteur de recherche comme ElasticSearch ou Solr est une application spécialisée dans la recherche, qui s’appuie sur un index (Lucene dans les deux cas cités). La question qui vient naturellement à l’esprit est alors: mais pourquoi ne pas utiliser directement le moteur de recherche comme gestionnaire des documents. En effet, pour s’embarasser de MongoDB alors qu’ElasticSearch permet des recherches puissantes, efficaces, ainsi que le stockage et l’accès aux documents.

La réponse qu’un système comme ElasticSearch est entièrement consacré à la recherche (donc à la lecture) la plus efficace possible de documents. il s’appuie pour cela sur des structures compactes, compressées, optimisées (les index inversés) dont nous avons donné un aperçu.

En revanche, ce n’est pas un très bon outil pour les autres fonctionnalités d’une base de données. Le stockage par exemple n’est ni aussi robuste ni aussi stable, et il faut parfois reconstruire l’index à partir de la base originale.

Un système comme ElasticSearch (ou Solr, ou un autre s’appuyant sur des index inversés) n’est pas non plus très bon pour des données souvent modifiées. Pour des raisons qui tiennent à la structure de ces index, les mises à jour sont difficiles et s’effectuent difficilement en temps réel.

L’utilisation la plus courante consiste donc à utiliser un système comme un complément d’un serveur de base de données (relationnelle ou documentaire) et à lui confier les tâches de recherche que le serveur BD ne sait pas accomplir (soit, en gros, les recherches non structurées). Dans le cas des bases NoSQL, l’absence fréquente de tout langage de requête fait du moteur de recherche associé un outil indispensable.

Note

Pour revenir sur l’inconvénient mentionné précédemment de dupliquer les documents de la base de données vers le moteur de recherche, il faut le modérer. C’est vrai quand on utilise une river sans aucune configuration. En pratique, on pourrait filtrer les documents de la base pour n’indexer que les champs soumis à des recherches plein texte comme le résumé du film. Voir le filtrage des rivers dans ElasticSearch.

Même en cas de présence d’un langage d’interrogation fourni par le système NoSQL, le moteur de recherche est un candidat tout à fait valide pour satisfaire les recherches plein texte et les recherches structurées. En résumé, à part les deux inconvénients (reconstruction depuis une source extérieure, support faible des mises à jour), les moteurs de recherche sont des composants puissants aptes à satisfaire efficacement les besoins d’un système documentaire.

_images/archi-ri.png

Fig. 9.6 Architecture d’une application avec moteur de recherche.

La figure Architecture d’une application avec moteur de recherche. montre une architecture typique, en prenant pour exemple une base de données MongoDB. Les documents (applicatifs) sont donc dans la base MongoDB qui fournit des fonctionnalités de recherche structurées. On peut indexer la collection des documents applicatifs en extrayant des “champs” formant dans documents (ElasticSearch, Solr), fournis à l’index qui se charge de les organiser pour satisfaire efficacement des requêtes. L’application peut alors soit s’adresser au serveur MongoDB, soit au moteur de recherche.

Un scénario typique est celui d’une recherche par mot-clé dans un site. Les données du site sont probablement gérées classiquement par, disons, MySQL. On extrait de la base MySQL tous les textes à indexer et on en fait des documents Solr que l’on confie à Solr. Ce dernier se charge alors de réponde à la fonctionnalité Search que l’on trouve couramment sur tous les types de site.

S3: la pratique: requêtes booléennes

Supports complémentaires:

ElasticSearch s’appuie sur le système d’indexation Lucene, dont le rôle est essentiellement de créer les index inversés, et d’implanter les algorithmes de parcours brièvement introduits dans la session précédente. Lucene propose un langage de recherche basé sur des combinaisons de mot-clés, langage étendu et raffiné par ElasticSearch.

Le langage de base

Une première méthode pour transmettre des recherches est de passer une expression en paramètre à l’URL http://localhost:9200//nfe204/movies/_search. La forme la plus simple d’expression est une liste de mots-clés. Voici quelques exemples:

curl http://localhost:9200//nfe204/movies/_search?q=alien
curl http://localhost:9200//nfe204/movies/_search?q=alien,coppola
curl http://localhost:9200//nfe204/movies/_search?q=alien,coppola,1994

Ce sont des requêtes essentiellement non structurées, très faciles à exprimer, mais donnant peu de contrôle et d’expressivité. Une seconde méthode est de transmettre un document JSON décrivant la recherche. Pour la tester, il est plus pratique d’utiliser l’interface Web. la figure L’interface avec recherches structurées montre la requête précédente placée dans un document JSON et exécutée avec l’interface.

_images/es-search.png

Fig. 9.7 L’interface avec recherches structurées

On voit clairement (mais partiellement) le résultat, produit sous la forme d’un document JSON énumérant les documents trouvés dans un tableau hits. Notez que le document indexé lui-même est présent, dans le champ _source. Ce qui implique que la collection MongoDB a été complètement dupliquée dans ElasticSearch: la question de l’utilisation de deux systèmes qui semblent partiellement redondants se pose. Nous revenons sur cette question plus loin.

Exprimer une recherche revient donc à envoyer à ElasticSearch (utiliser la méthode POST) un document-recherche comme celui-ci.

{
 "query": {
    "query_string" : {
       "query" : "alien,coppola,1994"
    }
  }
}

Le langage de recherche proposé par ElasticSearch, dit “DSL” pour Domain Specific Language, est très riche (voir la documentation en ligne pour tous les détails). Pour vous donner juste un exemple, voici comme on prend les 5 premiers documents d’une requête, en excluant la source du résultat.

{
 "from": 0,
 "size": 5,
 "_source": false,
 "query": {
    "query_string" : {
        "query" : "matrix,2000,jamais"
    }
  }
}

Nous allons nous contenter d’une variante du language, dite Query String, qui correspond, essentiellement, au langage de base de Lucene. Toutes les expressions données ci-dessous peuvent être entrées comme valeur du champ query dans le document-recherche donné

Termes

La notion de base est celle de terme. Un terme est soit un mot, soit une séquence de mots (une phrase) placée entre apostrophes. La recherche:

neo apprend

retourne tous les documents contenant soit “neo”, soit “apprend”. La recherche

"neo apprend"

ramène les documents contenant les deux mots côte à côte (vous devez utiliser \” pour intégrer une apostrophe double dans une requête). .

Par défaut, la recherche s’effectue toujours sur tous les champs d’un document indexé (ou , plus précisément, sur un champ _all dans lequel ElasticSearch concatène toutes les chaînes de caractères). La syntaxe complète pour associer le champ et le terme est:

champ:terme

Si on ne précise pas le champ, c’est celui par défaut qui est pris en compte. Les requêtes précédentes sont donc équivalentes à:

_all:"neo apprend"

Les valeurs des termes (dans la requête) et le texte indexé sont tous deux soumis à des transformations que nous étudierons plus tard. Une transformation simple est de tout transcrire en minuscules. La requête:

_all:"NEO APPREND"

devrait donc donner le même résultat, les majuscules étant converties en minuscules. La conception d’un index doit soigneusement indiquer les transformations à appliquer, car elles déterminent le résultat des recherches.

On peut spécifier un terme simple (pas une phrase) de manière incomplète

  • le ‘?’ indique un caractère inconnue: opti?al désigne optimal, optical, etc.
  • le ‘*’ indique n’importe quelle séquence de caractères (opti* pour toute chaîne commençant par opti).

La valeur d’un terme peut-être indiquée de manière approximative en ajoutant le suffixe ‘-‘, si l’on n’est pas sûr de l’orthographe par exemple. Essayez de rechercher optimal, puis optimal-. La proximité des termes est établie par une distance dite “distance d’édition” (nombre d’opérations d’éditions permettant de passer d’une valeur - optimal - à une autre - optical).

Des recherches par intervalle sont possibles. Les crochets [] expriment des intervalles bornes comprises, les accolades {} bornes non comprises. Voici comment on recherche tous les documents pour un prix compris entre 100 (inclus) et 300 (exclus):

year:[1990 TO 2005]

Connecteurs booléens

Les critères de recherche peuvent être combinés avec les connecteurs Booléens AND, OR et NOT. Quelques exemples.

year:[1990 TO 2005] OR title:M*
year:[1990 TO 2005] AND NOT title:M*

Important

Attention à bien utiliser des majuscules pour les connecteurs Booléens.

Par défaut, un OR est appliqué, de sorte qu’une recherche sur plusieurs critères ramène l’union des résultats sur chaque critère pris individuellement.

Venons-en maintenant à l’opérateur “+”. Utilisé comme préfixe d’un nom de champ, il indique que la valeur du champ doit être égale au terme. La recherche suivante:

+year:2000  title:matrix

recherche les documents dont l’année est 2000 (obligatoire) ou dont le titre est matrix ou n’importe quel titre.

Quelle est alors la différence avec +year:2000? La réponse tient dans le classement effectué par le moteur de recherche: les documents dont le titre est matrix seront mieux classés que les autres. C’est une illustration, parmi d’autres, de la différence entre “recherche d’information” et “interrogation de bases de données”. Dans le premier cas, on cherche les documents les plus “proches”, les plus “pertinents”, et on classe par pertinence.

Exercices

Exercice Ex-S3-1: recherches

Exprimez les recherches suivantes sur votre base de données

  • les films dans lesquels on parle d’un “meurtrier”;
  • même critère, mais en ajoutant le mot-clé “féroce”;
  • films avec Kate Winslett et Leonardo di Caprio;
  • films qui sont soit des drames, soit du fantastique;
  • films avec le mot-clé “France”; obtient-on les films produits en France? Sinon pourquoi? Que faudrait-il faire?
  • on recherche le film “Sleepy Hollow”; effectuez une recherche sur le titre (“Sleepy”, “Hollow”, “Sleepy Hollow”) puis sur le résumé.
  • films satisfaisant une combinaison de critères: parus entre 1990 et 2000 et aux USA, ou contenant les mots-clés “Michael” et “Sonny”;
  • etc.

Vous êtes invités à effectuer les recherches avec ou sans majuscules, à chercher des phrases comme “féroce et meurtrier”, à indiquer ou non des noms de champs, et à interpréter les résultats (ou l’absence de résultat) obtenus.

Exemple: cherchez le titre “Titanic”, puis “titanic”, puis effectuez une recherche sans précisez le nom du champ. Alors?

Exercice Ex-S3-2: le langage DSL d’ElasticSearch

Cet exercice est presque un sujet de projet: il s’agit d’étudier le langage complet de recherche DSL d’ElasticSearch. Cela vaut la peine d’effectuer ce travail, même partiellement, pour réaliser la puissance du moteur de recherche. On peut compléter avec les filtres et la percolation, à titre d’exemples.

Quiz

Répondez aux questions suivantes pour vérifier que vous avez bien compris le cours.

  • Quel est le rappel si la recherche ramène tous les documents?
  • Quelle est la précision si la recherche ne ne ramène acune document?
  • Et inversement...
  • La racinisation permet-elle d’augmenter ou de réduire le rappel?