Les index inversés |
 |
Petit rappel
Il est possible que vous sentiez le besoin de revoir le texte présenté sur la notation grand-O (dans la première semaine) avant de lire le présent texte. Dans ce cas, n’hésitez pas à le revoir.
Les index inversés
Nous avons vu, dans le module portant sur les expressions régulières, que la recherche d’un mot dans des dizaines de documents pouvait prendre plusieurs minutes. Imaginons maintenant une recherche sur le web parmi 8 milliards de pages web !
Il faut donc une structure de données particulière appelée « index inversé » qui, pour un mot donné, nous donne directement la liste des documents où il apparaît, et ce, très rapidement.
L’idée n’est pas nouvelle et on utilise depuis longtemps des concordances [1] en littérature, c’est-à-dire l’ensemble des passages d’un texte où figure un terme. Au début du vingtième siècle, établir une table de concordance d’un roman était un travail qui pouvait prendre des mois d’effort. En comparaison, nous allons voir qu’un moteur de recherche comme Lucene peut faire un travail comparable en quelques secondes !
Définition
Dans sa forme la plus simple, un index est tout simplement
une structure qui nous donne, pour chaque mot trouvé dans un corpus, la liste des documents où il se trouve.
Un index inversé peut prendre plusieurs formes. Certains
index peuvent ne donner que la liste des documents où les
mots apparaissent, d’autres vont aussi donner la position
des mots dans les documents. Certains index vont effectuer
préalablement la troncature des mots, remplaçant trouvent
par trouve, mais d’autres non. La casse des mots doit aussi être traitée, etc.
Exemple
Soit le corpus suivant :
D1 = "La vie est belle"
D2 = "Belle belle"
Un index inversé simple prendra la forme suivante :
| la | D1 |
| vie | D1 |
| est | D1 |
| belle | D1 D2 |
Un index inversé, indiquant en plus la position des mots,
prendra la forme suivante : [2]
| la | D1,1 |
| vie | D1,2 |
| est | D1,3 |
| belle | D1,4 D2,1 D2,2 |
Notons qu’à partir de cette dernière version, on peut reconstruire exactement le corpus initial ! L’index inversé capture donc la totalité de l’information contenue dans le corpus !
Complexité et stockage
Normalement, un index inversé permet de trouver, étant
donné un mot, ses positions correspondantes, en temps O(1). En d’autres mots, si on double le nombre de documents, le temps de recherche ne sera pas affecté... en autant qu’il s’agisse de mots peu fréquents.
Par contre, le temps de mise à jour de l’index, lors de l’ajout
ou de la modification d’un document, peut prendre un temps linéaire O(n)
dans le pire des cas [3]. Cela signifie que la construction d’un
index peut être très, très coûteuse. En d’autres mots, un index
inversé est une structure qui privilégie la rapidité de la réponse
aux requêtes, mais qui peut, autrement, coûter très cher en temps de
construction et de mise à jour. Nous ferons quelques tests dans le module suivant avec le moteur Lucene, pour évaluer le temps nécessaire à la construction d’un index.
Comme un index inversé peut contenir autant d’information que le
corpus lui-même, son espace de stockage nécessaire peut être encore plus
grand que celui requis par le corpus. Par contre, avec des techniques de compression [4], on obtient généralement un index qui est significativement
plus petit que la somme des documents, mais un index occupera toujours
au moins 10 % de l’espace requis pour stocker les documents eux-mêmes. La compression de l’index peut améliorer les performances globales en limitant la lecture de données sur le disque [5].
(Matériel optionnel) Pour comprendre comment on peut compresser un index inversé, il suffit de constater que pour chaque terme, nous avons une liste de documents (D1, D3, D7, ...) où ce terme apparaît. Une telle liste de documents peut se représenter sous la forme d’une liste de nombres (1,3,7,12,...). Pour compresser une telle liste, on utilise généralement la transformation Gamma qui consiste à stocker la différence des nombres en partant de zéro (1,3,7,12,... devient 1,3-1,7-3,12-7 ... ou 1,2,4,5,...), puis on peut appliquer une technique de compression usuelle telle que le codage de Huffman.
Un index inversé simple en Java
Avec la classe java.util.HashMap, on peut facilement implémenter un index inversé simple [6]. La classe suivante implémente l’exemple simple que nous avons présenté ci-dessous :
import java.util.*;
public class IndexeInverse {
HashMap<String, Vector<Integer> > index = new HashMap<String, Vector<Integer> >();
public IndexeInverse() {}
public void ajoute(String mot, int position) {
if(! index.containsKey(mot))
index.put(mot,new Vector<Integer>());
index.get(mot).add(position);
}
public Vector<Integer> trouve(String mot) {
return index.get(mot);
}
public static void main(String[] args) {
String[] D1 = new String("La vie est belle").split(" ");
String[] D2 = new String("Belle belle").split(" ");
IndexeInverse ii = new IndexeInverse();
for(String s: D1) {
ii.ajoute(s,1);
}
for(String s: D2) {
ii.ajoute(s,2);
}
System.out.println("Je cherche le mot vie...");
for(int i : ii.trouve("vie"))
System.out.println("dans le document: "+i);
System.out.println("Je cherche le mot belle...");
for(int i : ii.trouve("belle"))
System.out.println("dans le document: "+i);
}
}Mémoire interne ou externe
En pratique, les index inversés utilisent beaucoup de mémoire et
doivent persister d’une session à l’autre. Contrairement à l’exemple de la classe HashMap, on veut souvent les stocker sur disque (mémoire externe).
Il n’est pas nécessairement facile d’implémenter un index inversé efficace sur disque. Heureusement, il y a plusieurs librairies qui peuvent être utilisées à cette fin.
Le moteur de recherche Lucene implémente ses propres index inversés,
mais on pourrait aussi utiliser la classe Depot de QDBM.
Pour des questions de vitesse, il peut quand même être utile de stocker un maximum de données en mémoire. Dans ce cas, on compressera les données autant que possible.
(Optionnel) Voir, par exemple, l’article suivant (en anglais) :
Daniel Lemire and Leonid Boytsov, Decoding billions of integers per second through vectorization, Software : Practice & Experience, 2013.
Fréquence des termes et fréquence inverse des termes
Si on utilise surtout un modèle vectoriel de recherche d’informations,
on peut souhaiter que l’index nous permette de calculer très rapidement
la fréquence d’un terme dans un document (nombre d’occurrences) et la
fréquence inverse d’un terme : 
où 
est le nombre total de documents et 
est le nombre de documents où le terme apparaît.
À cette fin, on voudra sans doute disposer d’une implémentation hiérarchique de l’index qui nous donnera d’abord la liste des documents où le terme apparaît, puis ensuite nous permettra de chercher la liste des
endroits où le terme apparaît dans un document donné.
Parallélisation
Pour faire des recherches dans de grands ensembles de données, il est parfois utile de diviser l’index inversé en plusieurs index plus petits, chaque petit index traitant un petit nombre de documents. On peut ainsi mettre à profit les machines à multiprocesseurs ou des réseaux de machines.
Index binaires
Les index binaires (bitmap index) sont une alternative aux index inversés. Ils sont particulièrement efficaces quand on doit supporter le modèle booléen. Le but des index binaires n’est pas de réduire la complexité algorithmique (notation grand-O), mais d’accélérer tout de même grandement le traitement.
Prenons un exemple... Soit le corpus suivant :
D1 = "La vie est belle"
D2 = "Belle belle"
Un index binaire simple prendra la forme suivante :
| Document | Bitmap |
| D1 | 1111 |
| D2 | 0001 |
Le premier bit de chaque bitmap nous indique la présence du mot La, le second, la présence du mot vie, et ainsi de suite. Il est donc très rapide pour un ordinateur de passer tous les bitmaps un à un et de chercher, par exemple, un document contenant à la fois les mots vie et belle. De plus, il est facile de diviser le problème et d’avoir un processeur qui se charge de la première moitié des documents pendant qu’un autre se charge de l’autre moitié.
Naturellement, s’il y a des milliers de mots, le bitmap utilisera beaucoup de bits (autant de bits qu’il y a de mots). Bien qu’il existe des méthodes de compression des bitmaps [7], on réserve généralement ce type d’index pour le cas où il y a peu de mots.
Recherche d’expressions
Une requête sera souvent constituée de plusieurs termes formant une expression. Par exemple, si je fais une recherche sur l’« Union européenne », je souhaite que les deux mots soient voisins. On peut obtenir ce résultat en cherchant d’abord tous les documents contenant le terme Union, puis tous les documents contenant le terme européenne pour ensuite calculer leur intersection. Dans l’intersection qui ne contiendra, on l’espère, que peu de documents, on peut ensuite chercher l’occurrence d’Union européenne en mettant à profit le fait que notre index inversé contient aussi les emplacements où les termes Union et européenne apparaissent. Cette approche peut être efficace si les deux mots sont rares : l’intersection est alors petite. Dans l’éventualité où l’un des mots est fréquent, comme dans « sex on the beach » (les mots sex et the étant fréquents sur le web), le calcul de l’intersection sera coûteux.
Afin d’accélérer la recherche, on pourrait suppléer à l’index inversé un second index qui contient toutes les expressions de deux mots débutant par un mot fréquent. De cette manière, on peut remplacer la recherche de sex, par la recherche de sex on. Pour trouver les documents où se trouve l’expression sex on the beach, on commencera par chercher l’expression sex on, puis l’expression the beach, et on calculera l’intersection des deux pour finalement trouver, dans cette intersection, les documents dans lesquels l’expression sex on the beach apparaît.
Référence
H. Williams, J. Zobel, et P. Anderson, What’s next ? Index structures for efficient phrase query, Proc. Australasian Database Conference, 1999.
Pertinence et fin hâtive
En pratique, les documents sont présentés à l’utilisateur par ordre décroissant de pertinence. La pertinence peut être calculée à l’aide du modèle vectoriel ou avec l’algorithme PageRank de Google. Un bon index inversé trouvera les documents par ordre de décroissance sans chercher à tout trouver d’un coup. De cette manière, s’il y a 20 000 documents correspondant à votre requête, le système d’information n’a pas à stocker et traiter 20 000 documents immédiatement, surtout qu’il est improbable que vous vouliez consulter une liste complète.
Finalement, un bon index inversé devrait être aussi capable de garder en mémoire tampon les requêtes les plus fréquentes, de manière à ne pas avoir à les recalculer à partir de zéro.
Comme nous pouvons le voir, bien que conceptuellement simple, la construction d’un index inversé efficace n’est pas une chose facile. Heureusement, il n’est pas nécessaire de réinventer la roue et le logiciel Open Source Lucene fournit un excellent index inversé à peu de frais.
Référence
– Justin Zobel et Alistair Moffat, Inverted files for text search engines, ACM Comput. Surv, vol. 38, No. 2, 2006.
[1] Voir par exemple la concordance de Balzac.
[2] Dans la pratique, un index inversé stockera souvent la position des mots de manière distincte.
[3] En effet, si un document est ajouté, il faut le traiter au complet ce qui peut être long. Dans certains cas même, l’ajout d’un document peut impliquer que l’index au complet doit être reconstruit.
[4] Y. Choueka, A. S. Fraenkel, S. T. Klein, Compression of concordances in full-text retrieval systems, SIGIR , 1998 ou
Navarro, G. and Mäkinen, V. Compressed full-text indexes. ACM Comput. Surv. 39, 1, avril 2007 ou Paolo Ferragina, Rodrigo Gonzalez, Gonzalo Navarro, Rossano Venturini, Compressed Text Indexes:From Theory to Practice !.
[5] Rappelez-vous qu’un ordinateur peut faire des millions d’opérations pendant la lecture de données sur un disque.
[6] On se rappellera qu’une table de hachage permet l’insertion et autres requêtes en temps constant, c’est-à-dire que les performances de la classe HashMap ne se détériorent pas au fur et à mesure que le nombre d’éléments stockés augmente. Naturellement, l’utilisation de la mémoire augmente et vient limiter la taille maximale possible.
[7] À titre d’exemple, citons l’algorithme Byte-aligned Bitmap Compression (BBC) développé par Oracle ou l’algorithme Word-Aligned Hybrid (WAH) développé plus récemment par Wu et al.
