Faculté des Sciences Année : 2024/2025
Matière : Recherche d’Information
Révision
Exercice 1
En considérant le document suivant :
the cat cut the hat
1) Calculer le nombre de bigrammes différents (y compris les espaces) dans ce document ?
2) Calculer le nombre d'occurrences total de bigrammes en incluant les répétitions ?
3) En considérant les caractères alphabétiques minuscules et les espaces, combien de
bigrammes sont possibles ?
4) Quel sont les paramètres (probabilités) d'un modèle de bigrammes utilisant le même
ensemble de caractères (alphabétiques minuscules et espaces) ?
5) Quelle est la probabilité des séquences suivantes, si les probabilités sont estimées en utilisant
la méthode MLE (maximum-likelihood estimation) sur le corpus ci-après :
– cutthechat
– cut the chat
Solution
En considérant le document suivant :
the cat cut the hat
1) Il y a 12 bigrammes différents (en notant ici l'espace avec 'X' pour une meilleure visibilité):
Xc, Xh, Xt, at, ca, cu, eX, ha, he, tX, th, ut.
2) Le nombre d’occurrence total en incluant les répétitions est18 bigrammes : Xc, 2 ; Xh, 1 ;
Xt, 1 ; at, 2 ; ca, 1 ; cu, 1 ; eX, 2 ; ha, 1 ; he, 2 ; tX, 2 ; th, 2 ; ut, 1.
3) Le nombre de bigrammes possible est : 272 =729 bigrammes possible
(avec 26 lettres en anglais en plus de l’espace, et on a une paire de lettres)
4) Les paramètres (probabilités) du modèle de 729 bigrammes est 729 probabilités : P(XX),
P(Xa), P(Xb),….P(aa), P(ab),….P(zz).
5) Calculer la probabilité des séquences suivantes en utilisant l’estimation du maximum de
vraisemblance.
– cutthechat
– cut the chat
Si la probabilité des bigrammes observés est proportionnelle à leur nombre d’occurences
(18 bigrammes), alors : P(Xc)=2/18 ; P(Xh) = 1/18 ; P(Xt) = 1/18 ; P(at) = 2/18 ; P(ca) =
1/18 ; P(cu) =1/18 ; P(eX) = 2/18 ; P(ha) = 1/18 ; P(he) = 2/18 ; P(tX) = 2/18 ; P(th) = 2/18
; P(ut) = 1/18 et la probabilité d’un bigramme non observé est de 0 (le bigramme 'ch'
n'ayant jamais été observé).
P(cutthechat) =0 et P(cut the chat)=0
1
Exercice 2
Soient les documents suivants :
Numéro du Document
Document 1 “italy is world champion 2006 ”
Document 2 “germany and italy played each other in the semifinal ”
Document 3 “germany was in the semifinal 2006 ”
Document 4 “germany won the semifinal in italy 1990 ”
Supposons que les termes suivants sont des mots vides : is, and, in, the, was, each, other.
1) Construire fichier inverse (index inversé).
2) Représenter chaque document avec son index correspondant.
Solution
Soient les documents suivants :
Numéro du Document
Document 1 “italy is world champion 2006 ”
Document 2 “germany and italy played each other in the semifinal ”
Document 3 “germany was in the semifinal 2006 ”
Document 4 “germany won the semifinal in italy 1990 ”
Supposons que les termes suivants sont des mots vides : is, and, in, the, was, each, other.
1) Construire fichier inverse (index inversé)
Terme Nombre Fréquence Pointeur
de
documents
1990 1 1 Doc4, 1
2006 2 2 Doc1,1 Doc3,1
champion 1 1 Doc1,1
germany 3 3 Doc2, 1
Doc3, 1 Doc4, 1
italy 3 3 Doc1, 1 Doc2, 1 Doc4, 1
played 1 1 Doc2,1
semifinal 3 3 Doc2, 1 Doc3, 1 Doc4, 1
won 1 1 Doc4, 1
world 1 1 Doc1,1
2) Représenter chaque document avec son index correspondant.
Document 1 : italy, 3, world, 1, champion, 1, 2006, 2
Document 2 : germany ,3, italy, 3, played 1, semifinal, 3
Document 3 : germany,3, semifinal , 3, 2006, 2
Document 4 : germany,3, won, 1, semifinal, 3 italy, 3 ,1990, 1
2
Exercice 3
Considérons l’ensemble des termes d’indexation distincts T={ t1,t2, t3, t4,t5, t6} et trois
documents d1(t1,t2,t5); d2(t1,t3,t5,t6); d3(t1,t2,t3,t4,t5).
1. Donner les représentations des trois documents dans le cas de l’utilisation du modèle
booléen.
Soit la requête q = t1 ∧ (t2 ∨¬t3)
2. Calculer la correspondance entre la requête q et les documents d1, d2 et d3.
3. Quels sont les documents pertinents à la requête q ?
Solution
T={ t1,t2, t3, t4,t5, t6}
d1(t1,t2,t5)
d2(t1,t3,t5,t6)
d3(t1,t2,t3,t4,t5)
1. Donner les représentations des trois documents dans le cas de l’utilisation du modèle
booléen (matrice d’incidence)
Doc t1 t2 t3 t4 t5 t6
d1 1 1 0 0 1 0
d2 1 0 1 0 1 1
d3 1 1 1 1 1 0
Soit la requête q = t1 ∧ (t2 ∨¬t3)
2. Calculer la correspondance entre la requête q et les documents d1, d2 et d3
RSV(q,d1)=1/ 1 and (1 ou 1 )= 1
RSV(q,d2)=0 / 1 and (0 ou 0)=0
RSV(q,d3)=1 / 1 et (1 ou 0) = 1
3. Quels sont les documents pertinents à la requête q ?
numDoct1∩ numDoc (t2 ∨ ¬t3) ={1, 2,3}∩ {1,3} ={1,3}
Exercice 4:
Soient les trois documents suivants :
D 1 : {Le langage de programmation python est très utilisé pour le traitement de texte}
D2 : {Le langage JAVA est basé sur le langage C++}
D3 : {Un langage de programmation est un langage utilisé pour traduire un algorithme en un
programme}
1) Indexer les 3 documents et donner le fichier inverse
Considérer la formule suivante pour la pondération :
𝑓𝑟𝑒𝑞𝑖𝑗 𝑁
𝑤(𝑡𝑖 , 𝑑𝑗 ) = ∗ log( + 1)
max{∀ 𝑡𝑙 ∈ 𝑑𝑗 } 𝑓𝑟𝑒𝑞𝑙𝑗 𝑛𝑖
3
Où ni représente le nombre de documents contenant le terme ti, N est le nombre de documents
et le logarithme est calculé en base 2.
2) Calculer la similarité entre chaque document et la requête Q : {langage python java} en utilisant
les quatre formules du modèle vectoriel (produit scalaire, coefficient de Dice, Cosine, et indice
de Jaccard)
Solution
Soient les trois documents suivants :
D 1 : {Le langage de programmation python est très utilisé pour le traitement de texte}
D2 : {Le langage JAVA est basé sur le langage C++}
D3 : {Un langage de programmation est un langage utilisé pour traduire un algorithme en un
programme}
3) Indexer les 3 documents et donner le fichier inverse
- Segmentation du texte en termes
- Suppression des mots vides
- Normalisation des termes (Porter, troncature à x caractères, N-gram)
- Calcul des fréquences des termes
3.1 ) Construire le dictionnaire des termes
Terme Numéro de
Trie des Terme Numéro de
document
termes document
langage 1
algorithme 3
programmation 1
basé 2
python 1
c++ 2
utilisé 1 java 2
traitement 1 langage 1
texte 1 langage 3
langage 3 langage 3
programmation 3 langage 2
langage 3 langage 2
utilisé 3 programmation 1
traduire 3 programmation 3
algorithme 3 programme 3
programme 3 python 1
langage 2 texte 1
java 2
traduire 3
basé 2
traitement 1
utilisé 1
4
utilisé 3
langage 2
c++ 2
3.2) Constuire le fichier inverse :
Terme Nombre Fréquence Pointeur
de
documents
Doc3, 1
algorithme (t1) 1 1
Doc2,1
basé (t2) 1 1
Doc2,1
c++(t3) 1 1
Doc2,1
java(t4) 1 1
Doc1, 1 Doc2, 2 Doc3, 2
langage (t5) 3 5
Doc1,1 Doc3, 1
programmation 2 2
(t6)
programme 1 1 Doc3, 1
(t7)
python(t8) 1 1 Doc1,1
texte(t9) 1 1 Doc3,1
traduire(t10) 1 1 Doc1,1
traitement(t11) 1 1 Doc1,1
Doc1,1 Doc3,1
utilisé (t12) 2 2
3.3) Indexer les documents :
D 1 : {Le langage de programmation python est très utilisé pour le traitement de texte}
D1 : langage, 5, programmation, 2, python, 1, utilisé, 2, traitement, 1, texte, 1
D2 : {Le langage JAVA est basé sur le langage C++}
D2 : langage, 5, java, 1, basé, 1, c++, 1}
D3 : {Un langage de programmation est un langage utilisé pour traduire un algorithme en un
programme}
D3 : langage, 5, programmation, 2, utilisé, 2, traduire, 1, algorithme, 1, programme, 1
Considérer la formule suivante pour la pondération :
𝑓𝑟𝑒𝑞𝑖𝑗 𝑁
𝑤(𝑡𝑖 , 𝑑𝑗 ) = ∗ log( + 1)
max{∀ 𝑡𝑙 ∈ 𝑑𝑗 } 𝑓𝑟𝑒𝑞𝑙𝑗 𝑛𝑖
Où ni représente le nombre de documents contenant le terme ti, N est le nombre de documents
et le logarithme est calculé en base 2.
5
4) Calculer la similarité entre chaque document et la requête Q : {langage python java} en utilisant
les quatre formules du modèle vectoriel (produit scalaire, coefficient de Dice, Cosine, et indice
de Jaccard)
Produit scalaire :
𝑛
𝑅𝑆𝑉(𝑞, 𝑑𝑗 ) = ∑ 𝑤𝑖𝑞 𝑤𝑖𝑗
𝑖=1
Coefficient de Dice :
2 ∑𝑛𝑖=1 𝑤𝑖𝑞 𝑤𝑖𝑗
𝑅𝑆𝑉(𝑞, 𝑑𝑗 ) = 𝑛
∑𝑖=1(𝑤𝑖𝑞 )2 + ∑𝑛𝑖=1(𝑤𝑖𝑗 )2
Coefficient de Cosine :
∑𝑛𝑖=1 𝑤𝑖𝑞 𝑤𝑖𝑗
𝑅𝑆𝑉(𝑞, 𝑑𝑗 ) =
√∑𝑛𝑖=1(𝑤𝑖𝑞 )2 √∑𝑛𝑖=1(𝑤𝑖𝑗 )2
Indice de Jaccard :
∑𝑛𝑖=1 𝑤𝑖𝑞 𝑤𝑖𝑗
𝑅𝑆𝑉(𝑞, 𝑑𝑗 ) = 𝑛
∑𝑖=1(𝑤𝑖𝑞 )2 + ∑𝑛𝑖=1(𝑤𝑖𝑗 )2 − ∑𝑛𝑖=1 𝑤𝑖𝑞 𝑤𝑖𝑗
Calculer la matrice de fréquences des termes-documents
D1 D2 D3
algorithme (t1)
0 0 1
basé (t2)
0 1 0
c++(t3)
0 1 0
java(t4)
0 1 0
langage (t5)
1 2 2
programmation
(t6) 1 0 1
programme
(t7) 0 0 1
python(t8)
1 0 1
texte(t9)
1 0 1
traduire(t10)
0 0 1
traitement(t11)
1 0 0
6
utilisé (t12)
1 0 1
Produit scalaire :
𝑅𝑆𝑉(𝑞, 𝑑1 ) = ∑𝑛𝑖=1 𝑤𝑖𝑞 𝑤𝑖𝑗 =1*1+1*2 +0*1
𝑅𝑆𝑉(𝑞, 𝑑1 ) =3
𝑅𝑆𝑉(𝑞, 𝑑2 ) = ∑𝑛𝑖=1 𝑤𝑖𝑞 𝑤𝑖𝑗 =2
𝑅𝑆𝑉(𝑞, 𝑑3 ) = ∑𝑛𝑖=1 𝑤𝑖𝑞 𝑤𝑖𝑗 =1
(refaire tous les calculs)
w(D1) w(D2) w(D3) w(q) (=freq)
algorithme (t1)
0 0 1 /
basé (t2)
0 1 0 /
c++(t3)
0 1 0 /
java(t4)
0 1 0 1
langage (t5)
1 1 1 1
programmation
(t6) 1.32 0 1 /
programme
(t7) 0 0 0.66 /
python(t8)
2 0 0 1
texte(t9)
2 0 0 /
traduire(t10)
0 0 1 /
traitement(t11)
2 0 0 /
utilisé (t12)
1.32 0 0.66 /
Coefficient de Dice
𝑅𝑆𝑉(𝑞, 𝑑1 )=0.4
𝑅𝑆𝑉(𝑞, 𝑑2 )=0.85
𝑅𝑆𝑉(𝑞, 𝑑3 )=0.76
Coefficient de Cosine (devoir)
Indice de Jaccard (devoir)