UE : Bases de la recherche d’information textuelle

L3 Statistique et Informatique Décisionnelle

Lynda Tamine-Lechani
lechani@[Link]
 Principes de la Recherche d’Information Textuelle

Plan du cours
• Introduction au cours

• Chapitre 1 - Indexation de textes : notions de base et principes

• Chapitre 2 - Modèles de base de la recherche d’information

• Chapitre 3 - Evaluation d’un système de recherche d’information

2
Principes de la Recherche d’Information Textuelle

Chapitre 1

Indexation de Textes :
Notions de Base et Principes

3
 Le processus d’indexation Schéma de pondération des mots
dans les documents

Rappel : le processus de base de la recherche d’information

Documents Besoin en information

I.1. Comment représenter le contenu des

documents ? E.1. Quel besoin en
Indexation I.2 Comment représenter physiquement Expression information est associé
ces contenus ? à la requête ?

A.1. Comment estimer la pertinence

Représentants de d’un document pour une requête? Requête
documents
Appariement

Présentation
Documents sélectionnés

Feedback

E.1. Comment évaluer les performances d’un système de recherche d’information ?

4
 Le processus d’indexation Schéma de pondération des mots
dans les documents

Le processus de base de la recherche d’information…de plus près

Besoin en information
Collecte *

Corpus

Requête
Indexation

Fichier inversés
Appariement
Feedback

Présentation

* Crawling dans le cas du web 5

 Le processus d’indexation Schéma de pondération des mots
dans les documents
Langage d’indexation

Processus qui permet de transformer le document ou requête en substituts

capables de représenter leur contenu (Salton & McGill, 1983)

Sélection de descripteurs qui permettent de représenter le contenu

des documents

Plusieurs paramètres :

• Nature du descripteur : Mot, terme multi-mots, concept, acception

• Choix du descripteur : libre, contrôlé, mixte
• Générateur de descripteurs : manuel, automatique

6
 Le processus d’indexation Schéma de pondération des mots
dans les documents
Nature du descripteur

ü Mot : ou lemme combinaison de morphèmes, plus petite forme linguistique dotée

d’une autonomie et un sens
orange, oranger, orangeraie, …

ü Terme ou multi-mots : combinaison de mots ayant un sens

pomme de terre, prêt-à-porter, chou-fleur

ü Concept : entité abstraite qui représente un ensemble d’objets par partage de

propriétés
Locomotion (englobe voiture, vélo, car, …)

ü Acception : signification d’ un mot sur la base de son usage dans la langue

synset de Wordnet

7
 Le processus d’indexation Schéma de pondération des mots
dans les documents
Choix du descripteur

• Choix du descripteur
ü Contrôlé : descripteurs issus des entrées d’une ressource
o Thésaurus : descripteurs + relations d’hyperonymie, synonymie,
holonymie, référence (voir aussi)
o Dictionnaire : mot et liens entre les mots
o Base lexicale : relie les mots et multi-mots (lemmes) d’un domaine
o Terminologie : mots et liens entre mots d’un domaine
o Ontologie : concepts et liaisons entre concepts

ü Libre : descripteurs extraits du contenu du document selon les

règles de composition des mots de la langue

8
 Le processus d’indexation Schéma de pondération des mots
dans les documents
Choix du descripteur
UMLS, multi-terminologie médicale Entrée d’UMLS, terminologie médicale

The adrenal glands are responsible for many processes in the body. When
functioning correctly, they produce various hormones that trigger chemical activity
in every system. But what happens when disorders, such as Cushing's syndrome,
interfere with those hormonal mechanisms?

9
 Le processus d’indexation Schéma de pondération des mots
dans les documents
Générateur du descripteur
• Générateur du descripteur
ü Manuel
o Procédé d’indexation réalisé par des indexeurs humains,
généralement en utilisant un langage contrôlé

ü Automatique
o Indexeur automatique qui extrait les mots, multi-mot qui indexent le
document

• Manuel ou automatique : que choisir ?

ü Indexation manuelle coûteuse en temps
ü L’expérimentation montre que l’indexation automatique atteint au moins
les résultats de l’ indexation manuelle
ü La combinaison de l’ indexation manuelle et de l’indexation automatique améliore
les performances en recherche d’information

10
 Le processus d’indexation Schéma de pondération des mots
dans les documents
Processus d’indexation

Corpus de documents
à indexer

Formatage (Parsing)

Suppression des
Segmentation mots vides (stop words)

Normalisation
Linguistique

Génération des index

Fichiers d’indexation

11
 Le processus d’indexation Schéma de pondération des mots
dans les documents
Formatage
• Objectif : identifier les parties significatives du texte, puis les corps de textes/
métadonnées associées
ü Basé sur un langage de description standard : SGML, HTML, XML
<!DOCTYPE html> <html lang="fr" dir="ltr" class="client-nojs"> <head> <meta charset="UTF-8" />
<title> Recherche d'information — Wikipédia</title> <meta name="generator" content="MediaWiki
1.25wmf18" /
</table> </div> <p>La <b>recherche d'<a href="/wiki/Information" title="Information">information</a></
b> (<b>RI</b><sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span
class="cite_crochet">[</span>1<span class="cite_crochet">]</span></a></sup>) est le domaine qui
étudie la manière de retrouver des informations dans un corpus. Celui-ci est composé de <a href= »
/wiki/Document" title="Document">documents</a> d'une ou plusieurs <a href= »
/wiki/Bases_de_donn%C3%A9es" title="Bases de données" class="mw-redirect">bases de
données</a>, qui sont décrits par un contenu ou les <a href="/wiki/M%C3%A9tadonn%C3%A9e"
title="Métadonnée">métadonnées</a> associées.

ü Format lié à un langage de description conventionnel (ex entreprise)

ü Pas de de format
Etape de parsing ignorée

12
 Le processus d’indexation Schéma de pondération des mots
dans les documents
Segmentation
• Objectif : identifier les unités linguistiques du texte

ü Unité linguistique, c’est quoi ? unité ayant un sens comme le mot, phrase,
le paragraphe

ü Comment identifier ces unités ?

o Dépend du langage : langage informatique pour :
v adresse e-mail : [Link]@[Link] à lechani@[Link]
v adress web : https//[Link] à https//[Link]
v adresse IP : [Link]

13
 Le processus d’indexation Schéma de pondération des mots
dans les documents
Segmentation

ü Dépend de la langue
o en français, les mots n’ont pas de caractères de ponctuation
donc facile à identifier

L’intelligence artificielle est la science L, intelligence, artificielle, est, la, science

qui recherche les méthodes qui, recherche, les, méthodes
de création ou simulation de l'intelligence. de, création, ou, simulation, de, l, intelligence

FAttention, quelques cas :

M. Xavier à M Xavier S. M. I. C à S M I C

o en Allemand le découpage des mots n’est pas basé sur les espaces,
Lebensversicherungsgesellschaftsangestellter (employé d’une société d’assurance vie)
o en Vietnamien, la plupart des mots sont une composition d’unités
de significations atomiques avec des espaces
o en arabe et en hebreu, les mots sont écrits de droite à gauche mais
les chiffres de gauche à droite

En conclusion : le segmenteur doit être adapté à la langue du document

14
 Le processus d’indexation Schéma de pondération des mots
dans les documents
Elimination des mots vides (phase optionnelle)
• Objectif : éliminer les mots non porteurs de sens
ü Eliminer les mots outils
o Dépend de langue
v en français
le, l’, la, les, me, te, se, ce, cet, ces, cette, que, qui, je, tu, il, ils, nous, vous, votre, …
v en anglais
an, a, has, to, and, are, as at, be, by, for, from, the, that, he, was, were, will, it its, on, …)

Fpeut être dangereux ex vitamine a

ü Permet de limiter l’index aux signifiants

ü L’anti-dictionnaire :
o peut être de taille longue (200-300 mots), de taille très petite (7-12 mots)
o peut être non utilisé (cas des moteurs de recherche sur le web)
o peut être construit en utilisant les statistiques sur les termes fréquents
o l’ élimination des 150 mots les plus fréquents (mots vides compris)
permet de réduire le posting de 20-30%

15
 Le processus d’indexation Schéma de pondération des mots
dans les documents
Normalisation
Objectif : réduire les variations lexicales et linguistiques
ü Variation lexicale
o Supprimer les points dans les abréviations
o Uniformiser la casse
o Supprimer les accents
o Normalisation des dates, des longueurs, des abréviations…

ü Variation linguistique
o Racinisation : réduire les mots à une racine
v Basée sur une approximation sans analyse morphologique
Ø Utilisation de dictionnaires, règles dépendantes de la langue
1) Français : traitement des affixes (suffixe, préfixe, infixe)
prétraitement-> traitement; impossible-> possible
calmement-> calme, peureux->peur

2) Français : réduction à la base (racine) toute catégorie confondue

malade, maladie, maladies, maladive -> malad

16
 Le processus d’indexation Schéma de pondération des mots
dans les documents
Normalisation

3) en anglais, algorithme de Porter [Link]/~martin/PorterStemmer, application de règles

Règles Exemple
SSES -> SS caresses -> caresse
IES -> I ponies -> poni
SS -> SS caress -> caress
S -> cats -> cat

ü Avantages, inconvénients
+ Réduction considérable de la taille de l’index
- Normalisation agressive
Policy -> police
- Normalisation non applicable
matrices -> matrix
- Mots générés avec peu voire pas de sens troncature ->
troncature-> troncat
+ Peut être améliorée en utilisant une analyse de corpus

17
 Le processus d’indexation Schéma de pondération des mots
dans les documents
Normalisation

ü Variation linguistique
o Lemmatisation : réduire les mots au même lemme
v basée sur une analyse morphologique
v Deux étapes :
1) Analyse morphologique de phrases en contexte
identifier la classe grammaticale : nom, verbe, pronom, etc.

2) Réduction au lemme selon la catégorie

Les enseignants doivent assurer leurs cours -> enseignant devoir assurer leur cours

• Quelques résultats expérimentaux (Maginini, 2006)

La lemmatisation permet de réduire :
ü la taille du dictionnaire de 40%
ü la taille du posting de 7%

18
 Le processus d’indexation Schéma de pondération des mots
dans les documents
Génération de l’index

Objectif : Génération des index de documents permettant une recherche efficiente

1. Extraction des index des documents

a) Extraction de chaque descripteur
b) Association descripteur-document

2. Tri des index

3. Regroupement des index

a) Précision du nombre de descripteurs par document
b) Constituer les entrées (index, document)

4. Constitution du dictionnaire et du posting

a) Pour chaque index, calculer le nombre total de documents -> Dictionnaire
b) Pour chaque index, constituer une liste de postings qui associe pour chaque
document le nombre d’occurrences de cet index

19
 Le processus d’indexation Schéma de pondération des mots
dans les documents

Doc 1 I did enact Julius Caesar: I was killed Doc 2 So let it be with Caesar. The noble Brutus
I’the Capitol; Brutus killed me hath told You Caesar was ambitious

Term DocId Term DocId Term DocId Freq. Terme

I 1 ambitious 2 ambitious 2 1

did 1 be 2 be 2 1

enact 1 brutus 1 brtutus 1 1

julius 1 brutus 2 brutus 2 1

casear 1 capitol 1 capitol 1 1

I 1 caesar 1 caesar 1 1

was 1 caesar 2 caesar 2 2

2. Regroupement
1. Tri
killed 1 caesar 2 des index did 1 1

I’ 1 did 1 enact 1 1

the 1 enact 1 hath 1 1

capitol 1 hath 1 i 1 1

brutus 1 i 1 i’ 1 1

killed 1 i’ 1 it 2 1

me 1 it 2 julius 1 1

so 2 julius 1 killed 1 2

let 2 killed 1 let 2 1

it 2 killed 1 me 1 1

be 2 let 2 noble 2 1

with 2 me 1 so 2 1

caesar 2 noble 2 the 1 1

The 2 so 2

Noble 2 the 1
20
 Le processus d’indexation Schéma de pondération des mots
dans les documents
Génération de l’index

Term DocId Freq. Terme Term Df Freq.

Totale
ambitious 2 1
ambitious 1 1 2:1
be 2 1
be 1 1 2:1
brtutus 1 1
brutus 2 2 1:1 2:1
brutus 2 1
capitol 1 1 1:1
capitol 1 1
caesar 2 3 1:1 2:2
caesar 1 1 3. Index
did 1 1 1:1
caesar 2 2
enact 1 1 1:1
did 1 1
hath 1 1 1:1
enact 1 1
i 1 2 1:2
hath 1 1
i’ 1 1 1:1
i 1 2
it 1 1 2:1
i’ 1 1
julius 1 1 1:1
it 2 1
killed 1 2 1:2
julius 1 1
let 1 1 2:1
killed 1 2
me 1 1 1:1
let 2 1
noble 1 1 2:1
me 1 1
so 1 1 2:1
noble 2 1
the 1 1 1:1
so 2 1
the 1 1
Dictionnaire Posting

21
 Le processus d’indexation Schéma de pondération des mots
dans les documents
Génération de l’index : exemple
• Soit les exemples de documents suivants :

D1 : Big cats are nice and funny

D2 : Small dogs are better than big dogs
D3 : Small cats are afraid of small dogs

• Quel est le vocabulaire du corpus ?

• Construire l’index et le posting

22
Le processus d’indexation Schéma de pondération des mots
dans les documents

• Considération de la position des mots dans le texte

ü Pour chaque mot du vocabulaire, on garde trace de ses différentes
positions

D1 : Être ou ne pas être

D2 : Etre nous donne le droit d’être
D3 : Droit de vivre et droit de donner la vie

Df Freq.
Totale
droit 2 3 3 : 2 <1,5>

etre 2 4 1 : 2 <1,5> 2 : 2 <1,7>

vivre 1 2 3: 1 <3>

ü Utile quand la pertinence est estimée sur la base de la proximité des mots de
la requête dans le document
 Le processus d’indexation Schéma de pondération des mots
dans les documents

Extensions de l’index de base : index basé sur les n-grams

• n-gram caractères, n-grams mots : c’est quoi ?
Séquence de n caractères (n-gram caractères) ou n mots (n-grams mots) consécutifs
extraits à partir d’un texte
• Objectif : détecter la similarité des textes en utilisant le nombre de n-grams
caractères/mots en commun

Exemple : Texte ‘to*be*or*not*to*be’

2-gram/bigram caractère : *t, to, o*, *b, be, e*,*o, or, r*, *n, no, ot, t*, *o, *b,
be (en considérant les espaces)
3-gram/trigram caractère : **t, *to, to*, *be, be*, e*o, *or, or*, r*n, *no, not,
ot*, t*t, *to, to*, o*b, *be, be*, e** (en considérant les espaces)

2 gram mot : to be, be or, or not, not to, to be

3-gram mot : to be or, be or not, or not to, not to be

Copyright [Link]-Lechani 24
 Le processus d’indexation Schéma de pondération des mots
dans les documents

Extensions de l’index de base : index basé sur les n-grams

• n-gram caractères, n-grams mots : c’est quoi ?
Séquence de n caractères (n-gram caractères) ou n mots (n-grams mots) consécutifs
extraits à partir d’un texte
• Objectif : détecter la similarité des textes en utilisant le nombre de n-grams
caractères/mots en commun

Mot : ‘dream’

2-gram/bigram caractère : d, dr, re, ea, am, m

3-gram/trigram caractère : dr, dre, rea, eam, am

Copyright [Link]-Lechani 25
 Le processus d’indexation Schéma de pondération des mots
dans les documents
Génération de l’index
• Considération de n-grams
ü Créer un index classique mot -> documents
ü + pour chaque combinaison de n caractères de chaque mot du
vocabulaire, appelé n-gramme, associer les mots du vocabulaire
où il est présent : n-gramme-> mot

theatre : the, hea, eat, tre

etre : etr, tre

3-gram
Df Freq. etre
etr
Totale
tre etre theatre
etre 2 4 1:2 2:2
1:1 2:1 the theatre
theatre 1 2

ü Utile pour parer aux variations lexicales des mots de la requête

et du document :
- erreurs de typographie gerant, grant
- variantes d’écriture du même mot cle, clef
- variantes d’écriture dûes à la langue university, universite
26
 Le processus d’indexation Schéma de pondération des mots
dans les documents
Génération de l’index : éléments d’implémentation

• Structure de données
ü Liste triée

ü B-arbre

ü Table de hachage

27
 Le processus d’indexation Schéma de pondération des mots
dans les documents
Génération de l’index : éléments d’implémentation

• Construction du fichier inverse

28
Copyright Manning et al. 2008
 Le processus d’indexation Schéma de pondération des mots
dans les documents
Génération de l’index : éléments d’implémentation

• Indexation dynamique dans le cas du web

o Problème de mise à jour dynamique du dictionnaire et du

posting après ajout, suppression de documents à l’issue de la
phase de collecte

o Solutions :
v Reconstruction intégrale de l’index après chaque phase
(périodique) de collecte
v Construction dynamique en gardant les traces de mises à
jour
ü Maintenir un index en mémoire des changements
(ajout/suppression)
ü Dès que l’index en mémoire est saturé, le fusionner
avec la version précédente de l’index sur disque

29
 Le processus d’indexation Schéma de pondération des mots
dans les documents
Importance des mots dans les documents
• Soit les exemples de documents suivants :

D1 : Big cats are nice and funny

D2 : Small dogs are better than big dogs
D3 : Small cats are afraid of small dogs

• Quel sont les mots les plus importants pour traduire le contenu du document ?
• Quel mot est plus important que quel autre dans le document ?
• Quels mots permettent de distinguer le contenu d’un document d’un autre document
?

30
 Le processus d’indexation Schéma de pondération des mots
dans les documents
Hypothèses du schéma de pondération TFXIDF
• Hypothèses de base
ü Plus un mot est fréquent dans le document, plus il est important : TF

Informatique : 4, ordinateur : 2, technique : 2, ….

ü Moins il y a de documents de la collection où apparaît le mot, plus ils est

important : IDF
Distinguer des mots très fréquents mais peu significatifs (mots vides)

• Formalisons :

Importance (Mot, Document)= TF (Mot, Document) X IDF (Mot, Collection)

• Comment calculer TF(Mot, Document) ?

• Comment calculer IDF (Mot, Collection) ?

31