Systèmes de RI

Pr. Bouzid

Génie informatique – 5ème année

Année universitaire 2023- 2024

SRI & Big Data

 Plan
• Introduction:
• Définitions autour de la RI
• Domaines de la RI
• Historique
• Problématique de la RI
• L’indexation
• Les modèles de RI
• L’évaluation d’un SRI
• La RI sur le web

SRI & Big Data

 Introduction

SRI & Big Data

 Introduction
• Le domaine de la recherche d’information remonte au début
des années 1950 :
• explosion des informations après la seconde guerre mondiale
• Avènement de l’informatique (et de l’utilisation des ordinateurs)
• popularisation de l’internet
• Les pionniers de l’époque étaient enthousiastes à utiliser
l’ordinateur pour automatiser la recherche d’information,
dépassant la capacité humaine
• Les informations étaient principalement contenues dans des
documents textuels
• Problématique abordée: comment rechercher des
informations dans une base de documents volumineuse de
4
manière rapide et efficace

SRI & Big Data

 Définition - RI
• Définition de la RI:
• La recherche d’information (RI) est une branche de l’informatique
qui s’intéresse a l’acquisition, l’organisation, le stockage, la
recherche et la sélection d’information [salton, 1968]

• Terminologies utilisées:
• Recherche d’information (RI) - Information Retrieval (IR)
• Recherche de document – Document Retrieval

• Finalité:
• Sélectionner dans une collection (de documents) les informations
pertinentes répondant à un besoin précis
5

SRI & Big Data

 Définition - RI
• Trois notions clés se dégagent :
• Document (quels documents)
• Requête (comment correspondre la requête et les documents)
• Pertinence (comment évaluer le résultat)
• La notion de document en RI:
• Document textuel
• Page web (fichiers web , mail, …)
• Images, Vidéos
• Mélange de types (textes, images, …) dans un format précis
=> On appelle « document » dans la RI toute ressource
d’information qui peut constituer une réponse à une requête
d‘un utilisateur
6

SRI & Big Data

 Définition - RI
• Remarques:
• Dans la RI: l’information recherchée est textuelle, mais peut être
retrouvée dans différents formats de documents / fichiers
• Pour les images et les vidéos (ou tout autre fichier multimédia),
leurs métadonnées sont utilisées en premier
• Il existe une autre branche de la RI (recherche d’image - image
retrieval) qui se focalise sur la recherche d’image à partir d’une
requête sous forme d’image (comparaison d’images…). Il ne s’agit
pas d’une recherche textuelle (hors sujet de ce cours).

SRI & Big Data

 Domaines de la RI
• Domaines d’applications:
• GED (gestion électroniques de documents)
• Recherche sur le web
• Réseaux sociaux
• Bibliothèques numériques
• Monde de l’entreprise (toute activité métier produisant des
documents)
• Recherche scientifique
• Nos propres ordinateurs (bureautique et autre)
• …

SRI & Big Data

 Domaines de la RI
• Domaines d’application connexes :
• Classification / catégorisation (clustering)
• Web sémantique (semantic web)
• Systèmes de Questions-réponses (Query Answering)
• Systèmes de Recommandation (Recommendation systems)
• L’IA (intelligence artificielle)
• Fouille de textes (Text mining)
• Gestion des connaissances (knowledge management)
• …

SRI & Big Data

 Définition - SRI
• Un système de recherche d'information (SRI) est un système
qui permet de retrouver les « documents pertinents » à une
requête utilisateur (textuelle)

• Exemples de SRI:
• Moteur de recherche Web (google, bing, …)
• Systèmes de RI documentaires (tels que pour la recherche
d’articles scientifiques)
• Systèmes de RI dans les logiciels de GED
• Systèmes de RI spécifiques à une base de documents d’une
entreprise

10

SRI & Big Data

 Définition - SRI
• Remarque:
• Il ne faut pas confondre systèmes de bases de données et
systèmes de RI
• Les SRI se focalisent sur la recherche d’informations textuelles
dans des ressources telles que des documents
• La recherche (requêtage) dans des BD (relationnelles ou non
relationnelles) ne relève pas du domaine de la RI, car :
• ces BD contiennent des données (et pas des informations)
organisées suivant un certain schéma (modèle) de stockage (les
données ont un modèle de conception métier)
• le résultat renvoie des données (table, liste de données) et pas des
documents

11

SRI & Big Data

 Historique
• La RI date des années 1940, dès la naissance des ordinateurs.
• Le nom de « recherche d’information » (information retrieval)
fut donné par Calvin N. Mooers en 1948 [MOO 48] pour la
première fois quand il travaillait sur son mémoire de maîtrise
• Au début, la RI se concentrait sur les applications dans des
bibliothèques (on utilisait le nom "automatisation de
bibliothèques")
• Dans les années 1950, on commençait de petites
expérimentations en utilisant des petites collections de
documents (références bibliographiques). Le modèle utilisé
est le modèle booléen

12

SRI & Big Data

 Historique
• La première conférence dédiée au thème de la RI –
International Conference on Scientific Information - s’est
tenue en 1958 à Washington
• Les premiers problèmes qui intéressaient les chercheurs
portaient sur comment retrouver les documents (avec quels
mots, quels termes) => la notion d’index est devenue au
centre des recherche
• Dans les années 1960 et 1970, des expérimentations plus
larges ont été menées, et des méthodologie pour évaluer les
système de RI ont vue le jour. Des corpus de test (e.g. CACM)
ont été conçus pour évaluer des systèmes différents de RI. Ces
corpus de test ont beaucoup contribué à l'avancement de la RI
13

SRI & Big Data

 Historique
• Parmi les projets d’expérimentation menés sur la RI :
• Projet Cranfield (dirigé par Cyril Cleverdon, 1957-1967) [CLE 67]:
on visait à tester l’efficacité de différentes façons d’indexer et de
rechercher des documents. C’est dans ce projet que les mesures
précision et rappel (precision and recall) on été inventées. Ces
mesures sont encore utilisées aujourd’hui pour évaluer la
pertinence des résultats obtenus par rapport aux résultats
souhaités
• Projet MEDLARS – MEDical Literature Analysis and Retrieval
System (F. Wilfrid Lancaster, complete en 1968) [LAN 68]: il s’agit
d’expérimentation de RI dans le domaine biomédical. Les
documents sont indexés manuellement, avec un vocabulaire
contrôlé (choisi). Les résultats sont évalués en terme de précision
et de rappel. Les résultats de ce projet montrent que l’utilisation
d’un vocabulaire contrôlé avec l’indexation manuelle est efficace
mais restreint la pertinence des résultats. 14

SRI & Big Data

 Historique
• SMART (Gerard Salton, 1ière version 1961-1965) [SAL 71] : celui
qui a eu le plus d’impact sur la RI est le système SMART,
développé entre les années 1960 et début des années 1970. Les
travaux sur ce système ont été dirigés par G. Salton, professeur à
Cornell university (NY). De nouvelles techniques ont été
implémentées et expérimentées pour la première fois dans ce
système telles que: l’utilisation du modèle vectoriel, la technique
de « relevance feedback », le regroupement de documents /
clustering, …). Le système SMART fut réécrit dans les années 1970
et 1980 par E. Fox et C. Buckley. Ce système a été, et est encore
aujourd’hui, utilisé par de nombreux chercheurs pour des
expérimentations en RI.

15

SRI & Big Data

 Historique
• Les années 1980 ont été influencées par le développement de
l'intelligence artificielle. Ainsi, on tentait d'intégrer des
techniques de l'IA dans la RI (par exemple, système expert
pour la RI, etc).
• Les années 1990 (surtout à partir de 1995) sont les années de
l’avènement de l'Internet. Cela a eu pour effet de propulser la
RI en avant et sur sur le web (apparition des moteurs de
recherche web). La problématique de la RI a été élargie à
d’autres types de documents/fichiers tels que le multimédia
(et encore plus aujourd’hui avec les réseaux sociaux). Les
techniques de base utilisées dans les moteurs de recherche
web sont celles connues de la RI. Des améliorations et des
spécificités liées au web ont été apportées par la suite. 16

SRI & Big Data

 Problématique de la
RI
17

SRI & Big Data

 Problématique de la RI
Besoin
d’information

How?
Sources d’information
Input

Matching
Requête utilisateur
…
Documents textuels, images, vidéos, …

Output

18

SRI & Big Data

 Problématique de la RI
Besoin
d’information

Sources d’information
Input

Matching
Requête utilisateur
…
Documents textuels, images, vidéos, …

Output

19

SRI & Big Data

 Problématique de la RI
• Besoin d’information :
• Il s’agit d’une expression mentale de l’utilisateur
• Le même besoin peut être exprimé de différentes manières, selon
l’utilisateur…
• Requête utilisateur:
• Est une représentation possible du besoin de l’utilisateur
• Peut prendre les formes suivantes :
• Texte libre, texte avec operateurs (AND, OR, NOT,…)
• Liste de mots clés (vocabulaire contrôlé)
• Images, sons
• Par navigation dans une collection
• Hashtag (cas des réseaux sociaux)
• … 20

SRI & Big Data

 Problématique de la RI
• Problématique du besoin :
• Une requête idéale doit comporter toutes les informations que
l’utilisateur recherche, la similarité serait alors optimale (et
maximale)
• Or, l’utilisateur recherche une information qu’il ne connait pas a
priori, il ne peut donc pas l’exprimer (décrire) de maniere précise
(ideale)
• Le besoin est donc exprimé de manière approximative
• Le besoin est subjectif car dépend de l’utilisateur qui l’exprime

21

SRI & Big Data

 Problématique de la RI
Besoin
d’information

Sources d’information
Input

Matching
Requête utilisateur
…
Documents textuels, images, vidéos, …

Output

22

SRI & Big Data

 Problématique de la RI
• Sources d’information :
• Ressources d’information (documents / fichiers)
• Formes des ressources :
• Texte
• images, sons, vidéo, graphiques, etc.
• Propriétés des ressources :
• Non structurée : texte brut (plain text)
• Structurée ou semi structurée (XML, HTML, …)
• Hétérogénéité
• Langage (contenu multilingue)
• Format connu (documents, images, vidéos,…)
• Format spécifique (issue d’applications métier…)

23

SRI & Big Data

 Problématique de la RI
• Exemple semi-structuré: livre numérique (métadonnées + texte
brut):

24

SRI & Big Data

 Problématique de la RI
• Deux classes d’information:
• Méta-information, métadonnées (données/informations à
propos du document)
• Attributs : titre, auteur, date de création, etc.
• Structure (organisation du contenu) : structure logique, liens, ...
• Contenu :
• Contenu brut : texte du document
• Contenu sémantique : texte ayant du sens (information) extrait à
partir du contenu brut

25

SRI & Big Data

 Problématique de la RI
• Problématique des sources d’information :
• Beaucoup de formes et d’hétérogénéités dans les documents
• Quantité importante d’informations
• L’utilisateur ne connait pas les sources d’information à l’avance
(pas nécessairement). L’information recherchée est noyée dans
d’autres informations

=> Comment peut-on parcourir autant de sources d’information et

en sélectionner les plus pertinentes par rapport à un besoin
utilisateur ?

26

SRI & Big Data

 Problématique de la RI
Besoin
d’information

Sources d’information
Input

Matching
Requête utilisateur
…
Documents textuels, images, vidéos, …

Output

27

SRI & Big Data

 Problématique de la RI
• Matching (mise en correspondance) :
=> Deux approches possibles:
• Approche simple de la RI :
Correspondance mot à mot
Trouver les documents ayant
X Y Z les mêmes mots que la
requête

• La requête et les documents sont des listes de mots clés (texte)

• On parcourt séquentiellement les textes des documents en
recherchant les occurrences de chaque mot-clé de la requête
• On sélectionne les documents et classe les résultats : les documents
qui contiennent le plus de mots de la requête sont présentés en
premier 28

SRI & Big Data

 Problématique de la RI
• Critique de l’approche simple:
• Efficace pour des bases de textes de petite taille : le temps de
calcul est linéaire dans la taille de la base
• Pas de prétraitement de la requête ni des textes : caractères
(majuscules, accents, ...), mots de même famille => risque de
passer à côté de certains documents
• Problème de Vitesse: L'opération de recherche est très lente.
Pour chaque requête, on doit parcourir tous les documents dans
la base. Dans la pratique, il y en a des centaines de milliers, voire
des millions. Il n'est donc envisageable d'utiliser cette approche
que sur des collections très petites (avec un contenu textuel pas
très chargé)

29

SRI & Big Data

 Problématique de la RI
• Exemples de SRI avec l’approche simple :
• Recherche de fichiers de code dans les Frameworks de
développement informatique
• Recherche dans les e-mails (outlook, gmail, …)
• Fonctionnalité de recherche dans l’historique de navigation dans
un navigateur web

30

SRI & Big Data

 Problématique de la RI
• Approche par indexation :
Correspondance
Correspondance entre les
X Y Z mots de la requête et les
Index
index (représentations
des documents) Représentations

• Idée de base :
• On ne peut pas parcourir les documents à chaque requête
• On va donc prétraiter les documents pour savoir rapidement dans quel
document apparaît un mot.
• Technique : => L’indexation
• Prétraiter les documents (sélectionner les termes clés qui les
représentent)
• Constituer une liste de termes pour chaque document
• Construire une structure de données associant termes et documents => 31
Base d’index

SRI & Big Data

 Problématique de la RI
• Critique de l’approche par indexation:
• Elle est plus rapide car plus besoin du parcours séquentiel. Avec
la structure d'index, on peut directement savoir quels sont les
documents qui contiennent tel ou tel mot
• L’expression des requêtes peut être intelligente (avec des
opérateurs de logique ente les mots), exprimant des besoins
d'information complexes
• Le prix à payer pour ces avantages est le besoin d’espace de
stockage supplémentaire pour la structure d'indexes. En général,
cet espace peut aller de 40% jusqu’à 200% de la taille de la
collection de documents, selon la complexité de l'indexation

32

SRI & Big Data

 Problématique de la RI
• Exemples de SRI avec l’approche d’indexation:
• Tous les moteurs de recherche web,
• Certains moteurs intégré dans les logiciels du marché (logiciels
professionnel de gestion, ERP, CRM,…),
• Outils de GED,
• Moteur de recherche des réseaux sociaux,
• …

33

SRI & Big Data

 Problématique de la RI
Besoin
d’information

Sources d’information
Input

Matching
Requête utilisateur
…
Documents textuels, images, vidéos, …

Output

34

SRI & Big Data

 Problématique de la RI
• Pertinence des résultats :
• La pertinence est le degré de correspondance entre une requête
et la liste des documents retournés en résultats
• Côté utilisateur humain, la pertinence est subjective: les résultats
peuvent paraitre pertinents pour un utilisateur et pas assez
pertinents pour un autre (pour une même requête)
• Côté système, la pertinence est algorithmique : termes de la
requête dans un document (grâce aux index) = document
pertinent
• Le but de rechercher l’information dans un SRI est de trouver
seulement les documents pertinents à une requête, et pertinents
pour la majorité des utilisateurs du système
• Aucun système de RI n’est parfait. L’objectif final est de trouver le
bon rapport entre requête/résultat 35

SRI & Big Data

 Synthèse de la problématique
• Caractéristiques d’un SRI :
• Le système doit être simple à utiliser (expression facile de la
requête, possibilité d’exprimer des requêtes logiques,…)
• Le système doit conjuguer avec les différents formats et contenus
des documents / sources d’information
• Le système doit fournir les meilleures réponses possibles, et ces
réponses doivent être « pertinentes » pour l’utilisateur
• Le système doit fournir un nombre raisonnable de réponses
• Le système doit fournir des réponses rapides (délai raisonnable)

=> Comment essayer de satisfaire toutes ces caractéristiques à

la fois?
36

SRI & Big Data

 Solution : L’indexation
Sources d’information
Besoin
d’information

Input …
Documents textuels, images, vidéos, …

Matching
Requête utilisateur
Index Index Index

Output

37

SRI & Big Data

 L’indexation

38

SRI & Big Data

 L’indexation
• C’est quoi l’indexation?
• Processus permettant de construire un ensemble de termes clés
(« index ») permettant de représenter le contenu d’un document
• L’index peut représenter :
• Un mot simple: « pomme »
• Un groupe de mots : « pomme de terre »
• L’indexation peut être :
• Manuelle (experts des documents)
• Automatique (ordinateur)
• Semi-automatique (combinaison des deux)
• Basée sur :
• Un langage libre (éléments pris directement des documents)
• Un langage contrôlé (lexique, thesaurus, ontologie/réseau
39
sémantique,…)

SRI & Big Data

 Vocabulaire contrôlé
• Types de vocabulaires contrôlés:
• Lexique : Liste de mots clés
• Liste hiérarchique (taxonomie) : de concepts, de notations,…
• Thésaurus : Liste de mots clés + relation sémantiques entre les
mots clés
• Ontologie / réseau sémantique : Liste de concepts + relations
entre les concepts
• Dictionnaire de mots : Exemple : WordNet (pour l’anglais)

40

SRI & Big Data

 Vocabulaire contrôlé
• WordNet est un dictionnaire (gratuit) de mots anglais créé par
des chercheurs à l’université de Princeton
• Contenu de WordNet :
• Mots en anglais organisés en synsets : ensembles de mots
synonymes
• Les synsets ont des définitions et des relations entre elles
• Un mot peut appartenir à plusieurs synsets
• Relations sémantiques entre synsets :
• Hyperonymie/hyponymie(généralisation/spécialisation) : is-a
• Antonymie (opposé à)

41

SRI & Big Data

 Exemple : « City » dans WordNet

42

SRI & Big Data

 Types d’indexation

• Manuelle
• Automatique
• Semi-automatique

43

SRI & Big Data

 L’indexation manuelle
• Idée de l’Indexation manuelle :
• On identifie pour chaque document les termes clés qui les
représentent
• On enrichie manuellement la base d’indexes (Terme /
Documents). Les termes peuvent être issus d’un langage contrôlé
(recommandé)
• L’indexation manuelle se fait par le biais d’une interface
d’indexation telle un formulaire (pas besoin d’être un
informaticien)

• Précondition:
• Nécessité d’être un expert des documents concernés par
l’indexation (bien connaître les documents et leur contenu)
44

SRI & Big Data

 L’indexation manuelle
• Exemple :

45

SRI & Big Data

 L’indexation manuelle
• Cas d’application :
• Souvent utilisées pour l’indexation des livres dans les
bibliothèques et les centres de documentation
• Indexation de fichiers multimédias (images, vidéos, sons/
enregistrements vocaux, …)
• Indexation de fichiers spécifiques d’applications (cas où il est
difficile d’en extraire du texte, ou le texte n’a pas de sens)

46

SRI & Big Data

 L’indexation manuelle
• Avantages :
• Permet l’indexation de tous documents/fichiers sans se soucier
de leurs formats et contenus
• Cas d’utilisation d’un vocabulaire contrôlé :
• Fournit une terminologie standard pour indexer et rechercher les
documents
• Permet la classification (regroupement) de documents (par sujets,
thème,…)
• Permet facilement une recherche par navigation dans les concepts et
terminologies

47

SRI & Big Data

 L’indexation manuelle
• Inconvénients :
• Indexation très coûteuse:
• pour construire le vocabulaire
• pour affecter les concepts (termes) aux documents
• Difficile à maintenir:
• La terminologie évolue, plusieurs termes sont rajoutés tous les jours
• Processus humain donc subjectif :
• Des termes différents peuvent être affectés à un même document
par des indexeurs (humains) différents
• Les utilisateurs ne connaissent pas forcément le vocabulaire
utilisé par les indexeurs

48

SRI & Big Data

 Types d’indexation

• Manuelle
• Automatique
• Semi-automatique

49

SRI & Big Data

 L’indexation automatique
• Idée de l’indexation automatique :
• Le système (programme) informatique se charge de parcourir
chaque document et d’en extraire les termes qui serviront à
l’indexation

• Approche :
• L’approche courante est statistique avec les hypothèses suivantes:
• La redondance d’un mot marque son importance
• La cooccurrence des mots marque le sujet d’un document
• Autre critère pouvant être pris en compte: la position du terme dans
le document (important dans le cas où la requête est une expression)

50

SRI & Big Data

 L’indexation automatique : les étapes
• Démarche générale de l’indexation automatique :
• Etape 1 : Extraction des termes
• Etape 2 : Normalisation des mots / lemmatisation (regroupement
des variantes d’un mot )
• Etape 3 : Pondération (discrimination entre les termes
clés/importants/significatifs et les autres)

51

SRI & Big Data

 L’indexation automatique : les étapes
Etape 1 : Extraction des termes
• Extraction de termes = tockenization
• Terme (tocken) : mot (simple/compose), mots clés, concepts
• Mot : suite de caractères séparés par des séparateurs (espace,
signe de ponctuation, caractères spéciaux, retour à la ligne,
tabulation,…), Nombres
• Les termes retenus seront les index utilisés pour la recherche
• Il faut prendre en compte les spécificités des langues :
• Langue française :
• Pomme de terre : 1, 2 ou 3 termes?
• Langue Allemande les mots composés ne sont pas segmentés:
• Lebensversicherungsgesellschaftsangestellter = "life insurance
company employee" 52

SRI & Big Data

 Etape 1 : Extraction de termes
• Pas d’espaces en chinois et en japonais
• Ne garantit pas l’extraction d’un terme de manière unique
• Le Japonais encore plus compliqué avec différents alphabets

• La langue arabe s’écrit de droite à gauche avec certains termes

écrits de gauche à droite (ex : les chiffres)

53

SRI & Big Data

 Etape 1 : Extraction de termes
• Suppression des mots « vides » (stoplist / Common Words
removal) :
• Il s’agit de mots trop fréquents et pas utiles (à supprimer lors de
la tockenisation)
• Il peut s’agir d’articles, de pronoms, de mots de liaison… (le choix
des stopwords dépendent de la langue et du contexte)
• Exemples :
• Anglais : the, or, a, you, I, us, to, …
• Français : le , la, de, des, je, tu, à, aux, …
• Il faut faire attention à certaines exceptions: Certaines
abréviations font référence à autre chose qu’aux stopwords
• Exemple: “US” pour dire ”USA”
54

SRI & Big Data

 L’indexation automatique : les étapes
Etape 2 : Normalisation
• Il s’agit de Lemmatisation (radicalisation, racinisation) /
(stemming en anglais) :
• Processus consistant à regrouper les variantes d’un mot (mot de
même famille) pour lui donner la forme neutre (canonique) qu'il a
(forme proche du radical / racine). cette forme canonique est
appelée lemme.
• Exemples :
• grand, grande, grands, grandes, grandement => grand
La forme canonique de tous ces mots dont le sens premier exprime une
taille importante est grand.
• Pour l’anglais : retrieve, retrieving, retrieval, retrieved, retrieves
=> retriev est le lemme de tous ces mots 55

SRI & Big Data

 Etape 2 : Normalisation
• Techniques de normalisation:
• Approche algorithmique de transformation de mots en lemme :
ces algorithmes appliquent des règles de désuffixation
(suppression des suffixes). Soit le suffixe est supprimé, soit il est
transformé selon des règles pour avoir la forme canonique du
mot. Les algorithmes les plus connus :
• Algorithme de Porter pour l’anglais
• Algorithme de Carry pour le français
• Algorithme de Paice/Husk
• Approche par dictionnaire :
• Lemmatisation avec un lexique / dictionnaire : suppression de
suffixes puis recherche de la racine correspondante dans le
dictionnaire
• Technique de Troncatures: couper jusqu’à X caractères 56

SRI & Big Data

 Approche algorithmique
• L’algorithme de Porter :
• Permet la désuffixation de mots anglais (enlever les suffixes) à
commencer par la transformation du pluriel au singulier. Les règles de
transformation sont classées en sept phases successives (traitement des
pluriels et verbes conjugués, traitement des adverbes ...)
• Il comprend cinq règles de contexte, qui indiquent les conditions dans
lesquelles un suffixe devra être supprimé. La terminaison en -ing, par
exemple, ne sera enlevée que si le radical comporte au moins une
voyelle. Exemple :
• "troubling" deviendra "troubl", mais "sing" restera "sing".
• Les mots à analyser passent par toutes les étapes de désuffixation, et,
dans le cas où plusieurs règles pourraient leur être appliquées, c'est
toujours celle comprenant le suffixe le plus long qui est choisie. La
racinisation (désuffixation) est accompagnée à chaque étape de règles
de recodage 57

SRI & Big Data

 L’algorithme de Porter
• Exemples :
Règles Exemples en anglais
SSES → SS caresses → caress
SS → SS caress → caress
S→ cats → cat
ATIONAL → ATE relational → relate
TIONAL → TION conditional → condition
ATIVE → formative → form
ALIZE → AL formalize → formal

• Exemples de transformation du mot : Generalizations

étape1: Generalization
étape 2: Generalize
étape 3: General
58
étape 4: Gener

SRI & Big Data

 L’algorithme de Porter
• Aperçu des étapes:

59

SRI & Big Data

 L’algorithme de Porter
• Implémentation de l’algorithme de porter (disponible an
plusieurs langages de programmation) :

[Link]

60

SRI & Big Data

 Approche algorithmique
• Pour la langue française :
• Les lemmes de la langue française peuvent avoir plusieurs formes
en fonction :
• du genre (masculin ou féminin),
• de leur nombre (un ou plusieurs),
• de leur personne (moi, toi, eux…),
• de leur mode (indicatif, impératif,…)
• L’algorithme Carry fonctionne sur le même principe que
l’algorithme de porter, et est téléchargeable gratuitement sur le
site du projet GALILEI
[Link]

61

SRI & Big Data

 Approche avec lexique
• Approche avec utilisation d’un lexique : L’outil TreeTagger
• [Link]
• Version online: [Link]
• Il s’agit d’un outil de lemmatisation et d’annotation de texte, créé
par Helmut Schmid à l’université de Stuttgart
• Prend en compte plusieurs langues (français, anglais, allemand,
italien, espagnol, portugais, russe, …) et peut être adapté à de
nouvelles langues (si le lexique est fourni + un corpus entrainé )
• De manière générale on y applique les règles suivantes:
• Pour un verbe conjugué: on prend sa forme à l'infinitif
• Pour un nom, adjectif, article, ... : sa forme au masculin singulier
• L’outil peut être utilisé dans un cadre d’études / recherche /
enseignement, mais est interdit d’usage commercial 62

SRI & Big Data

 Exemple avec TreeTagger
• Phrase à lemmatiser :
« Il s’agit d’un cours d’informatique sur la recherche d’information »
• Résultat :

63

SRI & Big Data

 Etape 2 : Normalisation
• Utilisation de Troncature :
• Il s’agit de couper un mot au Xème caractère pour supprimer
éventuellement des suffixes
• Valeur optimale de X pour le français : 7 caractères
• Exemple de troncature à 7 caractères
• économiquement : écomoni
• Quelques limites :
• Le nombre de caractère dépend de la langue. Certaines langues ne
peuvent pas supporter cette technique
• Pas suffisant pour trouver une racine : certains mots, notamment les
verbes, changement complètement de forme
Exemple : verbe être : est, fut, soit
• Certains mots ont des sens différents mais deviennent le même
lemme à la troncature.
Exemple : Informatique et information => informa 64

SRI & Big Data

 Etape 2 : Normalisation
• Autre technique : méthode des n-gram :
• Un n-gram est une succession de n lettres
• n = 1, 2, 3
• Exemple : retrieval
• 1-gram : r, e, t, r, i, e, v, a, l
• 2-gram : re, et, tr, ri, ie, ev, va, al
• 3- gram : ret, etr, tri, rie, iev, eva, val

• Utile pour la racinisation pour certaines langues complexes, où il

est difficile de trouver des règles de désuffixations

65

SRI & Big Data

 Méthode des n-gram
• Hypothèse retenue: si les n-gram de deux mots ont une forte
similitude alors ils ont de fortes chances d’être de la même famille
• Exemple : Comparaison de retrieve et retrieval avec 3-gram:
• A=retrieve :
• ret, etr, tri, rie, iev, eve
• B=retrieval
• ret, etr, tri, rie, iev, eva, val
• On calcule leur similitude avec la formule :
• Sim (A,B)=2*nb_comm/(nb_A +nb_B) Sim(A,B) = 0.76

• Plus le rapport est proche de 1, plus la similitude est forte (il faut
pour cela déterminer un seuil au delà duquel on accepte la
similitude)
66

SRI & Big Data

 Etape 2 : Normalisation
• Avantages de la normalisation :
• Permet d’avoir un terme commun qui fait référence à tous les
termes d’une même famille
• Augmente les chances de répondre efficacement à une requête
(quelque soit la technique de matching appliquée…)
• Permet de réduire la taille de la base d’index (c’est surtout pour
cette raison qu’on utilise la normalisation)

67

SRI & Big Data

 Etape 2 : Normalisation
Limites de la normalisation :
• Peut conduire à une normalisation « agressive »
• Exemples :
• avec l’algorithme de Porter: policy/police, university/universe,
organization/organ
• avec troncature: Internet/Interne
• Oubli de quelques normalisations intéressantes:
• Exemples :
• matrices/matrix, machine/machinery ne sont pas normalisés avec
Porter
• Produit des mots difficiles à interpréter :
• Exemples :
• avec Porter: “iteration” produit “iter”, “general” produit “gener” 68

SRI & Big Data

 L’indexation automatique : les étapes
Etape 3 : Pondération
• Comment caractériser l’importance des termes dans un
document ?
• Associer un (ou plusieurs) poids a un terme
• Idée sous jacente :
Les termes importants doivent avoir un poids fort
• Approche la plus répandue : [Link] (du « Modèle vectoriel »)
• Enregistrer la position du terme dans le document (pour identifier
les expressions et mots composés fréquents)
• Exemple: pomme de terre

69

SRI & Big Data

 Types d’indexation

• Manuelle
• Automatique
• Semi-automatique

70

SRI & Big Data

 L’indexation semi-automatique
• L’indexation semi-automatique est la combinaison des deux
techniques manuelles et automatiques
• Exemple : Dans le cas de documents contenant du texte :
• On automatise d’abord l’extraction des termes des documents
(suppression de stopwords, lemmatisation, pondération
éventuellement …)
• Les termes sélectionnés vont être proposés à l’utilisateur (expert
de l’indexation manuelle) pour correction / validation et/ou pour
l’ajout de nouveaux termes

71

SRI & Big Data

 L’indexation : Synthèse
Sources d’information

Processus …
d’indexation Documents textuels, images, vidéos, …
(manuel, auto,
semi-auto)
Index Index Index

A quoi ressemble une

base d’index ?
72

SRI & Big Data

 Structure de la base d’index
• Quelque soit la méthode et techniques d’indexation choisies, la
rapidité et l’efficacité de la recherche dans la base d’index dépend
de sa structure
• L’indexation permet d’obtenir (par défaut) une liste de termes
décrivant chaque document :

• Le problème de cette forme de structure est que la recherche d’un

terme est lente : on recherche le terme séquentiellement dans chaque
document
• ⟹ La structure d’index la plus communément utilisée dans les
moteurs de recherche est de forme : inverted index (fichier inversé)
73

SRI & Big Data

 Structure de la base d’index
• Structure inverted index : Terme → {doc1, Doc2, …}

• Une structure inverted index contient chaque terme sélectionné

dans les documents comme index, avec pour chaque index la
référence à tous les documents qui le contiennent
• Cette structure peut être enrichie par: la fréquence du terme
dans chaque document et la position

74

SRI & Big Data

 Structure de la base d’index
• Exemple 1:
• Les documents D1, D2 et D3 contiennent les textes suivants:

• Pour chaque document des termes seront sélectionnés (après

traitement), on parle de bag of words (sac de mot )
• Pour D1 = c’ , est, ce, que
• Pour D2 = c’, est, ceci
• Pour D3 = ceci, est, une, banane
• Ces mots seront utilisés comme index

75

SRI & Big Data

 Structure de la base d’index
• La structure inverted index résultante :

• N.B: chaque index dans une structure d’index est unique

76

SRI & Big Data

 Structure de la base d’index
• Il existe deux types de structure d’index inversé :
• Record-Level Inverted Index : Le fichier d'index inversé contient
une liste de références aux documents pour chaque terme utilisé
comme index
• Word-Level Inverted Index : Le fichier d'index inversé contient
non seulement la liste de références aux documents, mais
également les positions de chaque mot dans un document. Cette
dernière forme offre plus de fonctionnalités mais nécessite plus
de puissance de traitement et d'espace pour être créée.
• Un autre critère est aussi pris en compte pour les deux types de
structures: la fréquence du mot dans le document . La fréquence
d’un mot permet de connaître son importance dans le document
pour:
• décider de le sélectionner ou pas (cas de collections importantes)
• de savoir où le classer dans la liste des résultats
77

SRI & Big Data

 Structure de la base d’index
• Exemple 2: fréquence
DocId
[positions]

Inverted Index
78

SRI & Big Data

 Structure de la base d’index
• Avantages:
• Recherche efficace : les index inversés permettent une recherche
efficace de grands volumes de données textuelles. En indexant
chaque terme de chaque document, l'index peut identifier
rapidement tous les documents contenant un terme ou une
expression de recherche donnée, réduisant ainsi
considérablement le temps de recherche.
• Mises à jour rapides : les index inversés peuvent être mis à jour
rapidement et efficacement à mesure que du nouveau contenu
est ajouté au système. Cela permet une indexation et une
recherche de nouveau contenu en temps quasi réel.
• Compression : les index inversés peuvent être compressés pour
réduire les besoins de stockage. Diverses techniques telles que le
delta encoding, gamma encoding, variable byte encoding, etc.
peuvent être utilisées pour compresser efficacement.
79

SRI & Big Data

 Structure de la base d’index
• Prise en charge de plusieurs langues : les index inversés peuvent
prendre en charge plusieurs langues, permettant aux utilisateurs
de rechercher du contenu dans différentes langues en utilisant le
même système.

80

SRI & Big Data

 Structure de la base d’index
• Comment rechercher dans une base d’index:
• Recherche séquentielle : temps linéaire dans la taille du
vocabulaire indexé (Utile pour une petite base d’index
uniquement).
• Recherche dichotomique : les index doivent être triés. on regarde
le mot du milieu, on cherche sur le même principe dans la
première ou seconde moitié (Temps logarithmique dans la taille
du vocabulaire).
• Recherche avec un arbre de recherche : arbre dont les feuilles
donnent accès à la ligne et les noeuds disent quelle branche
suivre (Temps logarithmique dans la taille du vocabulaire).
• Recherche avec une fonction de hachage : fonction qui calcule le
numéro de ligne à partir du mot. (Temps constant).
81

SRI & Big Data

 Structure de la base d’index
• Remarque :
• Le stockage d’une structure d’index peut s’avérer très couteux en
espace de stockage mais également en recherche.
• Dans le cas de très larges collections il faut penser à un système
distribué pour les tâches d’indexation. L’un des modèles connus
pour cela est le modèle du MapReduce de Google.

82

SRI & Big Data

 Conclusion sur l’indexation
• L’indexation est une phase complexe qui nécessite des choix à faire à
plusieurs niveaux (indexation manuelle ou automatique ou les deux,
techniques d’extraction, de normalisation, structure de la base
d’index,…). Ces choix dépendent aussi de :
• La taille de la collection
• La nature des ressources (documents/ fichiers) concernées par la RI
• Les techniques de RI utilisées pour le matching requête/documents
• Remarque :
• Pour déterminer si la représentation d'un document correspond à celle
de la requête, on doit développer un processus de matching (avec
évaluation des résultats pour vérifier son efficacité)
• Différents modèles ont été développés en relation avec la représentation
de documents et de requêtes. C'est cet ensemble de représentations et la
technique de mise en correspondance et de sélection des résultats qu'on
appelle un modèle de RI.
83

SRI & Big Data

 Les modèles de RI

84

SRI & Big Data

 Les modèles de RI
• Notion de modèle dans le processus de RI :

X Y Z

Représentation des documents

Représentation
matching
de la requête Index

• Un modèle de RI spécifie comment est la représentation d’une

requête, comment est la représentation d’un document et
comment faire la mise en correspondance (matching) entre les
deux représentations 85

SRI & Big Data

 Les modèles de RI
• Il existe deux formes de matching (mise en correspondance /
appariement) dans la RI : exact matching / best matching
• Exact matching:
• On spécifie dans la requête les termes recherchés de manière
précise
• L’ensemble des documents respectant exactement la requête sont
sélectionnés (mais pas ordonnés)
• Best matching :
• On spécifie dans la requête les termes recherchés
• Les documents sont sélectionnés selon un degré de pertinence
(similarité/ probabilité ) vis-à-vis de la requête et sont ordonnés (par
pertinence)

86

SRI & Big Data

 Les modèles de RI
• Plusieurs modèles de RI existent :
• Modèle booléen (1950)
• Modèle vectoriel (1970)
• Modèle probabiliste (1976)
• Modèle inférentiel (1992)
• Modèle LSI (Latent Semantic Indexing) (1994)
• Modèle de langage (1998)
• …

87

SRI & Big Data

 Modèle Booléen
• Il s’agit du premier modèle de RI (modèle booléen strict)
• Caractéristiques :
• Représentation d’un document: un document est représenté par
un ensemble de termes (qui indexent le document) :
D = (𝑡1 , 𝑡2 , …, 𝑡𝑖 ) avec i ∈ [1, … , 𝑁]
• Représentation de la requête : une requête est une expression
logique de termes avec des opérateurs booléens:
• AND (ᴧ)
• OR (ᴠ)
• NOT (¬)
• Exemple : Q = (𝑡1 ᴧ 𝑡2 ) ᴠ (𝑡3 ᴧ ¬ 𝑡4 )
• Technique d’appariement « Exact match » : présence des termes
de la requête dans la représentation d’un document → document
sélectionné 88

SRI & Big Data

 Modèle Booléen
• Exemple :
• D1 = (𝑡1 , 𝑡3 , 𝑡4 )
• D2 = (𝑡2 , 𝑡4 )
• D3 = (𝑡1 , 𝑡2 , 𝑡4 , 𝑡5 )
• D4 = (𝑡1 , 𝑡4 )
• Q1= (𝑡2 ᴧ 𝑡4 )
• Q2 = 𝑡5 ᴠ (𝑡1 ᴧ ¬ 𝑡3 )
⟹ D2 et D3 répondent à la requête Q1
⟹ D3 et D4 répondent à la requête Q2

89

SRI & Big Data

 Modèle Booléen
• Limites du modèles :
• Formulation de la requête avec les opérateurs de logique pas
évidente (voire difficile) pour beaucoup d’utilisateur
• Sélection des documents sur décision binaire (soit le document
répond à la requête, soit il n’y répond pas)
• Pas de classement des documents sélectionnés (pas de degré de
pertinence entre les documents car ils n’ont pas de poids)
• Pour les collections volumineuses : risque de sélection de
beaucoup trop de documents en résultat (surtout à cause de
l’opérateur OR)

90

SRI & Big Data

 Modèle Booléen pondéré
Extension du modèles : Modèle booléen pondéré
• On intègre des pondérations dénotant la représentativité de
tous les termes T d’une requête pour un document
• La fonction de pondération 𝑊𝐷 pour un document est:
𝑊𝐷 : T → [0,1]. Pour chaque terme de la requête, le poids de
ce terme dans D vaut :
• 0 pour un terme non présent dans le document
• 1 pour un terme présent dans le document
• La fonction de correspondance entre les termes de la requête
et des documents, notée Sim, est basée sur un calcul de
similarité selon l’opérateur logique (AND, OR, NOT)

91

SRI & Big Data

 Modèle Booléen pondéré
• Cas de l’opérateur NOT: 𝑺𝒊𝒎 𝑫, ¬𝒂 = 𝟏 − 𝑾𝑫 (a)
• Cas des opérateurs AND et OR :
• Formules 1 inspirées de la logique floue (ne tenant pas compte de
tous les termes de la requête)
• 𝑺𝒊𝒎 𝑫, 𝒂 ᴠ 𝒃 = 𝑴𝒂𝒙 [𝑾𝑫 (a), 𝑾𝑫 (b)] (a, b les termes d’une
requête)
• 𝑺𝒊𝒎 𝑫, 𝒂 ᴧ 𝒃 = 𝑴𝒊𝒏 [𝑾𝑫 (a), 𝑾𝑫 (b)]

• Formules 2 avec prise en compte de tous les termes de la requête

𝑾𝑫 𝒂 2 + 𝑾𝑫 𝒃 2
• 𝑺𝒊𝒎 𝑫, 𝒂 ᴠ 𝒃 = 𝟐

𝟏−𝑾𝑫 𝒂 𝟐
+ 𝟏−𝑾𝑫 𝒃 𝟐
• 𝑺𝒊𝒎 𝑫, 𝒂 ᴧ 𝒃 = 𝟏 − 𝟐

92

SRI & Big Data

 Modèle Booléen pondéré
• Exemple : on considère A et B les termes d’une requête
Modèle pondéré

Documents A B (A ᴠ B) (A ᴧ B) (A ᴠ B) (A ᴧ B)
(formule 2) (formule 2)
D1 1 1 1 1 1 1
D2 1 0 1 0 0,7 0,29
D3 0 1 1 0 0,7 0,29

• La pondération permet ici de classer les documents

• Exemple: Pour la requête (A ᴠ B) avec le modèle pondéré, D1 sera
classé en 1er, suivi de D2 et D3 dans le même ordre.

93

SRI & Big Data

 Modèle Vectoriel
• Modèle créé au début des années 70 par Gerard Salton,
appliqué pour la RI avec le système SMART (System for the
Mechanical Analysis and Retrieval of Text)
• Caractéristiques :
• Modèle best-match le plus commun
• Requête en texte libre (un ou plusieurs termes)
• Documents ordonnés dans les résultats : on tient compte du poids
des termes de la requête dans les documents pour pouvoir les classer
(on parle de pondération)
• Les documents et la requête sont représentés comme des
vecteurs dans un espace vectoriel : il s’agit de vecteur de poids
• Document : dj= (w1j, w2j, …, wNj) avec :
Wij poids du terme ti dans le document dj 94
• Requête : q= (w1q, w2q, …, wNq)
Wiq : poids du terme ti dans la requête q

SRI & Big Data

 Modèle Vectoriel
• Illustration : représentations des documents et d’une requête dans un
espace vectoriel de termes ti

• Plus les vecteurs représentant les documents sont proches, plus

les documents sont similaires
• Plus l’angle entre la requête est le document est petit, plus le
document répond à la requête
• On calcule la similarité vectorielle entre l’angle d’un document et
d’une requête en utilisant le poids des termes (la mesure de 95
similarité la plus utilisée est la formule du cosinus)

SRI & Big Data

 Modèle Vectoriel
• Notion de pondération :
• Pondérer les termes permet de connaître leur importance dans la
recherche pour sélectionner les documents les plus pertinents et
les classer
• La pondération des termes pour une requête est simple :
fréquence du terme dans la requête (term frequency)
• La pondération pour les documents est une notion plus
complexe. Elle tient compte de :
• l'importance du terme dans le document (pondération locale)
• l'importance du terme dans la collection (pondération globale)
• La mesure la plus connue pour la pondération des termes pour
un document est : [Link]
96

SRI & Big Data

 Modèle Vectoriel
• Les mesures:
• tf = Term Frequency
• est la fréquence du terme dans le document
• df = Document Frequency
• est la fréquence du terme dans la collection (corpus entier)
• on utilise la mesure df inversée, notée idf (Inverted Document
Frequency)

97

SRI & Big Data

 Modèle Vectoriel
• Formules :
• tf : (terme frequency)
• Formule simple du tf: est la fréquence du terme ti dans le document
dj (nombre d’occurrences)
tfi,j = freq(ti, dj)
• Variante du tf: fréquence normalisée logarithmiquement
tfi,i = 1+ log(freq(ti, dj)) si freq(ti, dj) ≠ 0
• idf : (inverted document frequency)
• Formule simple :
idfj = 1 / dfj avec dfj nombre de documents où apparait le terme tj
• Formule normalisée logarithmiquement :
idfj = log(N / dfj) avec N le nombre de documents du corpus
• Le poids de chaque terme ti dans un document dj est calculé: 98
Wi,j = tfi,[Link]
SRI & Big Data
 Modèle Vectoriel
• Exemple de calcul de pondération :
• On considère la structure inverted index suivante :

Terme DocId Freq

Pomme d1 1
d2 3
d3 2
Poire d1 1
d3 2
d4 1

99

SRI & Big Data

 Modèle Vectoriel
→ Pondération pour le terme t1 = pomme avec formule simple :
• Wt1,d1 = 1 x (1/3) = 0,33
• Wt1,d2 = 3 x (1/3) = 1
• Wt1,d3 = 2 x (1/3) = 0,67
→ Pondération pour le terme t1 avec formule logarithmique :
• Wt1,d1 = (1 + log(1)) x (log(4/3)) = 0,12
• Wt1,d2 = (1 + log(3)) x (log(4/3)) = 0,18
• Wt1,d3 = (1 + log(2)) x (log(4/3)) = 0,16
• N.B : d4 n’est pas indexé avec le terme pomme, il ne sera donc pas pris en
compte dans le calcul des poids

100

SRI & Big Data

 Modèle Vectoriel
Fonction de matching:
• La similarité entre les représentations d’une requête Q et d’un
document D est notée Sim(Q,D) et est calculée grâce à la
formule du cosinus (cosine similarity):

𝑆𝑖𝑚 (𝑄, 𝐷) = cos(𝑄, 𝐷) =

avec :
Wi Q : poids des termes dans la requête (tf)
Wi D : poids des termes dans le document ([Link])

N.B: La similarité est comprise entre 0 et 1: résultat proche de 1 si les

termes sont similaires, proche de 0 sinon.
Dans le cas de larges collections, l’idéal est d’avoir un seuil de pertinence 101
ou de choisir les k-best score
SRI & Big Data
 Modèle Vectoriel
• Remarques :
• D’autres mesures de similarité existent en RI, telles que:
• Coefficient de Dice :

• Mesure de Jaccard :

qi : poids du terme ti dans la requête

di : poids du terme ti dans le document 102

SRI & Big Data

 Modèle Vectoriel
• Avantages:
• Le langage de requête est simple (liste de mots)
• La pondération améliore les résultats de recherche
• La mesure de similarité permet d’ordonner les documents selon
leur pertinence vis à vis de la requête
• Limites :
• Le modèle considère les termes indépendants, alors que ce n’est
pas forcément le cas. Exemple: « pomme » et « pomme de terre »
sont deux notions différentes. Si la structure d’index contient la
position des termes, il est souhaitable d’en tenir compte (par
exemple, inclure une condition qui vérifie d’abord la position des
termes avant de calculer leur fréquence)
• Il n'y a pas de schéma de pondération optimal (dépend du corpus
et de la requête)
103

SRI & Big Data

 Amélioration des résultats
• Il existe des techniques pour améliorer les résultats retournés
par un SRI (après l’affichage des résultats)
• La plus connues est la technique du Relevance feedback :il
s’agit de reformuler la requête à partir des résultats et grâce
au retour de l’utilisateur
• Principe du Relevance feedback:
• On estime que la première requête de l’utilisateur est souvent
naïve et spontanée
• On permet à l’utilisateur de donner son avis (feedback) sur les
résultats (sous une forme précise)
• La requête originale est reformulée (étendue avec de nouveaux
termes) et re-pondérée
104

SRI & Big Data

 Relevance feedback
• Illustration : Résultats : Ensemble de documents
ordonné

+
Feedback utilisateur

Nouvelle requête étendue

• Exemple de feedback :
• L’utilisateurs examine les k meilleurs documents et les étiquettes
avec des valeurs [1,0]
• L’utilisateur classe les k meilleurs résultats par ordre de pertinence 105
selon son point de vue

SRI & Big Data

 Les modèles de RI
• Remarque 1:
• Les modèles de RI ont été inventés avant l’apparition de la technique de
lemmatisation des mots dans l’indexation automatique. Les lemmes qui
servent d’index peuvent être légèrement différents des termes de la
requête et donc peuvent poser problème lors de la recherche. Exemple:
on saisit le terme «économique» dans la requête mais c’est « économi »
qui est enregistré dans la base.
• Il est possible de vérifier la similarité entre deux termes en utilisant des
mesures de calcul de similarité (edit-distance). Parmi les plus connues:
• Levenshtein distance
• Damerau- Levenshtein distance
• Jaro-Winkler distance
• …

106

SRI & Big Data

 Les modèles de RI
• Remarque 2 :
• Le stockage d’une structure d’index peut s’avérer très couteux en
espace de stockage mais également en recherche.
• Dans le cas de très larges collections il faut penser à un système
distribué pour les tâches d’indexation. L’un des modèles connus
pour cela est le modèle du MapReduce de Google.

107

SRI & Big Data

 Evaluation des SRI

108

SRI & Big Data

 Evaluation des SRI
• Notion de pertinence des résultats :
• La pertinence est:
• la correspondance entre un document et une requête,
• un degré de relation (chevauchement, relativité, …) entre le
document et la requête;
• un degré de la surprise qu'apporte un document, qui a un rapport
avec le besoin de l'utilisateur;
• une mesure d'utilité du document pour l'utilisateur;
• …
• Les utilisateurs d'un système de RI ont des besoins très variés. Ils
ont aussi des critères très différents pour juger si un document
est pertinent ou pas.

109

SRI & Big Data

 Evaluation des SRI
• Certains paramètres entrent en compte dans la pertinence
des résultats d’un SRI (surtout pour les moteurs web):
• Profil de l’utilisateur
• Un besoin d’information exprimé par deux personnes de la même
manière ne fournit pas forcément les mêmes réponses (prise en
compte du profil de l’utilisateur quand il est connecté par exemple)
• Expérience de l’utilisateur à chaque même requête (relevance
feedback)
• Contexte « externe » du besoin d’information
• Temporel : Un besoin d’information exprimé à différents moments
n’a pas le même sens
• Géographique : Un besoin d’information exprimé à différents
endroits n’a pas le même sens) (« restaurant » à Marrakech ne
nécessite pas forcément de réponses de restaurants à Paris)
110

SRI & Big Data

 Evaluation des SRI
• De manière générale, le but de la RI est de trouver seulement
les documents pertinents à une requête, et donc utiles pour
l'utilisateur
• Document pertinent = document où l'utilisateur doit pouvoir trouver les
informations dont il a besoin.
• La qualité d'un système doit être mesurée en comparant les
réponses du système avec les réponses idéales que
l'utilisateur espère recevoir. Plus les réponses du système
correspondent à celles que l'utilisateur espère, mieux est le
système
• Pour arriver à une telle évaluation, on doit d'abord connaître
les réponses idéales de l'utilisateur. L'évaluation d'un système
se fait ensuite avec :
• un corpus de test
111
• et des métriques connues en RI : Précision et Rappel.

SRI & Big Data

 Evaluation des SRI
• Dans un corpus de test, il y a:
• un ensemble de documents
• un ensemble de requêtes
• la liste de documents pertinents pour chaque requête (d’un point
de vue utilisateur)
• Prérequis (pour des résultats assez objectifs):
• Les requêtes doivent traiter des sujets variés
• Il faut une collection assez variées contenant les documents
pertinents (qui répondent aux requêtes) et d’autres moins
pertinents
• Il faut des utilisateurs experts qui savent juger la pertinence d’un
document (pour chaque requête, quelles sont les résultats
attendus) 112

SRI & Big Data

 Evaluation des SRI
• On compare les résultats obtenus par le système avec les
résultats établis par les experts
• Les métriques utilisées en RI:

• Précision : proportion de document pertinents retrouvés parmi tous

les documents retrouvés par le système
• Rappel : proportion de document pertinents retrouvés parmi tous les
documents pertinents dans la collection

113

SRI & Big Data

 Evaluation des SRI
• Illustration :
Résultats obtenus
Pas obtenus (sélectionnés)

False True False True

Negative Positive Positive Negative
(FN) (TP) (FP) (TN)

Pertinents Non pertinents

114

SRI & Big Data

 Evaluation des SRI
• Ces mesures permettent d’améliorer :
• la qualité des index
• la formulation des requêtes
• la technique de matching entre les deux
• Il n’y a pas de bons taux de précision et de rappel. Ces deux
mesures sont fortement liées: quand l’une augmente, l’autre
diminue.
• L’objectif est de trouver le bon rapport entre la précision et le
rappel: on parle de moyenne harmonique
• La moyenne harmonique entre précision et rappel est
nommée:
F-mesure (ou F-score) :
115

SRI & Big Data

 Evaluation des SRI
• Exemple : (pour 1 requête)
• Nombre de docs dans la collection : 100
• Nombre de docs pertinents dans la collection : 60
• Nombre de docs sélectionnés : 30 dont 10 non pertinents
Matrice de confusion Selected
(confusion matrix)
TP = 20 FP = 10
Predicted
FN = 40 TN = 30

• Precision = 20/(20+10) = 0,67

• Rappel = 20/(20+40) = 0,33
• F-score = 0,44
116

SRI & Big Data

 Exemples d’implémentations
• Frameworks et moteurs de RI connus:
• Lucene : est une bibliothèque d’indexation et de recherche
d’information textuelle, écrite en Java (existe aussi en: C++, C#, Perl,
Python,…), disponible sous licence Apache. Le processus d’indexation et
de recherche est traité de manière générale. Beaucoup de classes sont
abstraites et doivent être spécialisée (par exemple, pour l’extraction
automatique des termes pour les index, il y a une classe abstraite
Analyzer, pour la recherche, une classe abstraite Query proposant
différentes méthodes abstraites pour des requêtes booléennes, requêtes
avec préfixe, …).
• Moteurs et applications de RI basées sur Lucene: Elastic seach, Solr,
Nutch (web crawler)
• Xapian : moteur open source écrit en C++ offrant des fonctions
d’indexation et de recherche (licence GPL). Il met en œuvre l’approche
probabilistique de la RI et des opérateurs booléens pour la recherche 117

SRI & Big Data

 Notion de métamoteur
• Un métamoteur (ou méta-chercheur) est un moteur de
recherche qui puise ses informations d’autres moteurs de
recherche connus :
• Le métamoteur interroge plusieurs moteurs de recherche
(Google, Bing, Ask, Yahoo!,…) et retourne les résultats de chacun
d'eux.
• Il n’y a pas de redondance dans les résultats puisque les résultats
similaires sont éliminés (par exemple: si les moteurs
Google et Yahoo! renvoient quelques mêmes liens, le métamoteur
ne va les afficher qu'une seule fois dans la liste des résultats).
• Certains métamoteurs indiquent de quels moteurs de recherche
provient chaque résultat
• Exemples :
• Moteurs généralistes: DogPile, Yippy, StartPage, Metacrawler
• Moteurs spécialisés: SiteSeerX, GoogleScholar, CCSearch, Indeed 118

SRI & Big Data

 La RI sur le web

119

SRI & Big Data

 La RI sur le web
• Caractéristiques du web :
• Taille : très grand nombre de documents (milliards et plus)
• Hétérogénéité : très grande variété de documents
• Répartition : documents répartis sur Internet
• Structure du Web : documents interconnectés par des hyperliens
• ⟹ Environnement complexe :
• Il faut parcourir le web tous les jours, toutes les heures … pour indexer la
nouveauté
• La recherche doit être rapide et les résultats assez pertinents pour le plus
d’utilisateurs possibles (sinon le moteur ne sera pas utilisé)
• Les moteurs de recherche web se basent sur les fondamentaux de la
RI (indexation avec inverted index, recherche avec pondération,
classement,…), mais ont leur propre techniques pour indexer et
rechercher 120

SRI & Big Data

 La RI sur le web
• Côté indexation : Les moteurs web utilise des web crawler
(robots d’indexation ou collecteur)
• Un web crawler parcourt le web, visite le contenu des ressources
trouvées (page web, documents,…) et extrait le maximum
d’informations (pour ensuite en faire des index)
• Il procède en suivant récursivement les hyperliens trouvés à
partir d'une page
• De manière générale un robot d'indexation se charge des
questions suivantes :
• quelles pages télécharger
• quand vérifier s'il y a des changements dans les pages
• comment éviter les surcharges de pages Web (délais en général)
• comment coordonner les tâches de manière distribuée (parallélisme)
121

SRI & Big Data

 La RI sur le web
• Les index sont extraits à partir de plusieurs éléments des ressources
web :
• le contenu du document des pages et toutes ressources du site
• la structure du titre : titres de niveau 1, de niveau 2,…
• les métadonnées : title, keywords
• l’adresse de la ressource web
• Les mots clés utilisés pour le référencement chez l’hébergeur du
site
• Un fichier d'exclusion ([Link]) placé dans la racine d'un site Web
permet de donner aux robots une liste de ressources à ignorer.
• En résultat de l’indexation, on obtient :
• Des Index de très grande dimension : taille du vocabulaire → des millions
et de la base de ressources → des trillions
• Des Index répartis : des fermes de calcul réparties dans le monde entier
(le stockage aussi) 122

SRI & Big Data

 La RI sur le web
• Exemples de web crawler :
• GoogleBot de Google
• AppleBot d’Apple (se charge aussi de l’assistant SIRI)
• Baiduspider du moteur de recherche chinois Baidu
• BingBot pour Bing et Yahoo!

123

SRI & Big Data

 La RI sur le web
• Côté recherche :
• La requête de la recherche est une liste de mots clés (on trouve
aujourd’hui des filtres dans les moteurs : par langue, par date,…)
• Le calcul du score de similarité entre la requête et les ressources
web s’inspirent du modèle vectoriel (c-à-d avec pondération et
classement selon le score). Les formules de calcul de score de
similarité dans les moteurs web sont secrètes (et elles évoluent
constamment)
• D’autres spécificités sont en plus prises en compte dans la
sélection et le classement (outre le référencement naturel des sites):
• La langue et le pays de l’utilisateur /géolocalisation de la requête
• Historique de navigation / profil utilisateur
• Popularité d’une page, d’un site
• … 124

SRI & Big Data

 La RI sur le web
• Une spécificité de Google: le PageRank
• Google a inventé la notion de PageRank qui consiste à évaluer la
popularité/notoriété d’une page web
• Principe du PageRank : une page est importante si beaucoup de
pages importantes pointent sur elle
• Plus la valeur du PageRank est élevée, plus la page en question
est populaire

125

SRI & Big Data

 La RI sur le web
• L’algorithme du PageRank mesure quantitativement la notoriété
d’une page : il attribue à chaque page un score sous la forme d’une
valeur sur une échelle de 0 à 10. Ce score estime le nombre de fois
que cliquerait sur la page web un utilisateur à partir d’autres pages
• Parmi les éléments utilisés pour le calcul du score d’une page:
• les liens entrants et sortants, les ancres (liens HyperText)
• le trafic associé à la page
• le choix de la page dans les résultats d’une requête
• le nom de domaine
• A noter que PageRank est une marque déposée de Google et le
principe est breveté
• Le PageRank joue un rôle majeur dans le classement des
résultats du moteur Google
126

SRI & Big Data

 Synthèse
• Pour créer un bon SRI il faut :
• Identifier toutes les ressources (documents) concernées par la
recherche dans le système
• Choisir une bonne technique d’indexation (adaptées à la nature
des ressources recherchées)
• Mettre en place une structure d’index inversée et même enrichie
(N.B : choisir une technologie qui supporte l’évolution de la taille
de la base)
• Définir la manière de formuler les requêtes (simple et intuitive)
• Choisir un modèle de RI approprié ou définir une technique de
matching (mesure de similarité) efficace et adaptée au système
• Cas de grandes collections : il faut penser au traitement distribué
(pour l’indexation et la recherche)
127

SRI & Big Data

 Références
• [MOO 48] Mooers, C.N., Application of Random Codes to the
Gathering of Statistical Information, MIT Master's Thesis,
1948.
• [CLE 67] Cleverdon, C.W., The Cranfield tests on index
language devices. Aslib Proceedings 19(6), 173-193, 1967.
• [LAN 68] Lancaster, F.W., Evaluation of the MEDLARS Demand
Search Service, National Library of Medicine, Bethesda,
Maryland, 1968.
• [SAL 71] Salton, G., The SMART Retrieval System. Prentice Hall,
Englewood Cliffs, NJ, 1971.
• [SAL 83] Salton, G., Fox, E.A., Wu, H. Extended Boolean
Information Retrieval. Communications of the ACM 26(11),
1022-1036, 1983. 128

SRI & Big Data

 Références
• Le domaine de recherche d’information – Un survol d’une
longue histoire, Jian-Yun Nie, Université de Montréal
• Recherche d’information (RI) – Fondements -, Philipe Mulhen,
CLIP-IMAG
• Recherche d’information et traitement automatique du
langage, Laure Soulier, Science Sorbonne Université, 2019
• Modèles en recherche d’information, Cours Master Recherche
Paris 13 - Rechercher et extraction d’information, A.
Rozenknop
• Une introduction à la recherche d’information, Remi Guilleron,
Université Lille & INRIA Lille & Cristal UMR CNRS
129

SRI & Big Data

 Références
• [Link]
[Link]/sites/default/files/bulk_media/m06s7/co/06_sec
tion7_4.html
• [Link]
%20de%20Porter,-
L'algorithme%20d%C3%A9velopp%C3%A9&text=Les%20mots
%20%C3%A0%20analyser%20passent,%C3%A9tape%2C%20d
e%20r%C3%A8gles%20de%20recodage.
• [Link]
• [Link]
• [Link]
130

SRI & Big Data

 Références
• [Link]
• [Link]
0une%20biblioth%C3%A8que%20open,%2C%20PHP%2C%20C
%23%2C%20Python.
• [Link]
• [Link]
• [Link]
pagerank/

131

SRI & Big Data