Trouver un mot parmi des millions de pages
Un index inversé est un tableau qui associe chaque mot à la liste des documents où il apparaît. Il permet de trouver les documents d’un mot sans relire aucun texte.
Le restaurant universitaire garde 50 000 fiches de menus. Un étudiant tape « poisson » : la réponse doit venir en une fraction de seconde, pas après la lecture de 50 000 fiches.
À la fin de cette leçon
Remarque
Je peux trouver les documents d’un mot avec un index inversé.
Mots clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Document | un texte que l’on veut pouvoir retrouver | |
| Jeton | un mot isolé du texte | restaurant |
| Index inversé | un tableau qui donne, pour chaque mot, ses documents | |
| Liste de documents | les numéros des documents qui contiennent un mot | [0, 2] |
| Requête booléenne | une recherche qui combine des mots avec ET ou OU |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Tout relire à chaque recherche est trop lent
La méthode la plus simple lit chaque document et regarde si le mot s’y trouve. Avec 50 000 fiches, le programme lit 50 000 textes pour chaque question.
Il vaut mieux faire le travail une seule fois, avant les questions. On lit tous les documents une fois, et on range le résultat dans un index.
Exemple travaillé : quatre documents numérotés
| Numéro | Texte du document |
|---|---|
| 0 | le restaurant universitaire ouvre a midi |
| 1 | la bibliotheque universitaire ouvre a huit heures |
| 2 | le restaurant propose un menu a trois euros |
| 3 | la bibliotheque prete un livre pour trois semaines |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Découper une phrase en jetons
docker exec jupyter python3 -c 'print("le restaurant ouvre a midi".split())'Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
L’index range chaque mot avec ses documents
Pour construire l’index, on découpe chaque document en jetons. Pour chaque jeton, on ajoute le numéro du document à la liste de ce mot, une seule fois.
On l’appelle inversé parce qu’on part des mots pour retrouver les documents. Le texte, lui, va des documents vers les mots.
Exemple travaillé : l’index des quatre documents
| Mot | Documents | Lecture |
|---|---|---|
| restaurant | [0, 2] | Présent dans les documents 0 et 2 |
| bibliotheque | [1, 3] | Présent dans les documents 1 et 3 |
| ouvre | [0, 1] | Présent dans les documents 0 et 1 |
| trois | [2, 3] | Présent dans les documents 2 et 3 |
| midi | [0] | Présent dans le seul document 0 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
ET garde les numéros communs, OU les rassemble
Une requête booléenne combine des mots. Avec ET, on garde les documents qui contiennent les deux mots : les numéros présents dans les deux listes.
Avec OU, on garde les documents qui contiennent l’un ou l’autre : tous les numéros des deux listes, sans doublon.
Exemple travaillé : trois requêtes
| Requête | Listes | Résultat |
|---|---|---|
| restaurant ET ouvre | [0, 2] et [0, 1] | [0] |
| restaurant OU bibliotheque | [0, 2] et [1, 3] | [0, 1, 2, 3] |
| bibliotheque ET trois | [1, 3] et [2, 3] | [3] |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Garder les numéros des deux listes
docker exec jupyter python3 -c 'print(sorted(set([0, 2]) & set([0, 1])), sorted(set([0, 2]) | set([1, 3])))'Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Une erreur fréquente
Attention
Beaucoup pensent que ET colle les deux listes l’une après l’autre. C’est le rôle de OU. ET ne garde que les numéros présents dans les deux listes, donc au plus la plus courte des deux.
Construire un index en Python
documents = [
"le restaurant universitaire ouvre a midi",
"la bibliotheque universitaire ouvre a huit heures",
"le restaurant propose un menu a trois euros",
"la bibliotheque prete un livre pour trois semaines",
]
index = {}
for numero in range(len(documents)):
for mot in documents[numero].split():
if mot not in index:
index[mot] = []
if numero not in index[mot]:
index[mot].append(numero)
print(index["ouvre"])
print(index["restaurant"])
print(index["trois"])
# Affichez maintenant index["bibliotheque"].
Pour aller plus loin
Dans un carnet de JupyterLab, écrivez six courtes phrases sur le restaurant, la bibliothèque et le gymnase. Construisez leur index avec votre fonction du devoir.
Cherchez un mot, puis deux mots avec ET. Quel mot a la liste la plus longue ? Que dit-elle sur ce mot ?