Aller au contenu
English

L'index inversé

  • Leçon 8
  • 35 min
  • Module 3 : La recherche lexicale : la référence de base à battre

Où nous en sommes

Nous pouvons maintenant mesurer toute recherche avec notre jeu de test. La première à mesurer est la recherche classique. Dans cette leçon, nous construisons un index inversé à la main, puis avec SQLite. Nous voyons aussi pourquoi chercher un mot est si rapide.

Lue depuis YouTube. Rien ne se charge depuis YouTube avant que vous appuyiez sur lecture. Confidentialité

Ce que vous saurez faire

Trouvez les produits qui contiennent un mot sans lire chaque produit. C’est ainsi que toute recherche par mots reste rapide, y compris celle de Larkfield.

Carnet JupyterFaites les exemples de cette leçon dans un carnet JupyterColab · Kaggle · GitHub · en anglais

Le carnet (notebook) Jupyter construit à la main l’index de six produits. Il cherche des requêtes avec tous les mots, puis avec au moins un mot. Il utilise ensuite SQLite sur tout le catalogue. Vous construisez vous-même l’index de chaque titre de produit. Ses cellules de préparation téléchargent les données. Aucune préparation locale n’est donc nécessaire. Environ 20 minutes.

Le carnet est en anglais. Colab et Kaggle ouvrent votre propre copie. Il faut un compte Google ou Kaggle gratuit. Vous êtes bloqué ? Consultez le carnet de solution.

Avant de commencerCe qu’il faut savoir et avoir sous la mainEnviron 35 minutes

Ce que vous devez savoir

Ce qu’il vous faut sur votre ordinateur

  • Le projet larkfield-search des modules précédents, avec son environnement virtuel actif. Cette leçon n’y ajoute aucun fichier.
  • L’index que search check ou search index a construit dans outputs/index/. Si vous avez exécuté search reset, exécutez search index une fois.

Imaginez un épais livre de jardinage. Vous voulez lire sur les boyaux. Vous ne lisez pas les 400 pages pour trouver le mot « boyau ». Vous consultez l’index à la fin. Il indique « boyau : 112, 245 ». Vous ouvrez la page 112 et trouvez le passage en quelques secondes.

Quelqu’un a créé cet index une fois, à l’impression du livre. Cette personne a parcouru chaque page et noté les mots qui s’y trouvaient. Elle a ensuite inversé la liste : pour chaque mot, les pages. Chaque lecteur profite de ce travail, encore et encore, gratuitement.

Une vendeuse fait la même chose. Une nouvelle vendeuse parcourt chaque étagère pour trouver un boyau d’arrosage. Une vendeuse expérimentée connaît la réponse : « Les boyaux sont dans l’allée 7. » Dans sa tête, elle a une liste qui relie les mots aux endroits.

Un moteur de recherche a besoin de la même liste. Sans elle, chaque recherche doit lire chaque produit.

Larkfield a 40 066 produits. Chacun a un titre et une description, soit environ 72 mots en moyenne. Pour répondre à « garden hose » sans index, le programme doit tous les lire. Il garde ceux qui contiennent les deux mots.

Ce court script fait exactement cela. Puis il pose la même question à l’index SQLite du projet. Enregistrez-le sous scan.py dans le dossier larkfield-search :

import sqlite3
import time
import pandas as pd
cat = pd.read_csv("data/catalogue.csv.gz", keep_default_na=False)
texts = (cat["title"] + " " + cat["description"]).str.lower().tolist()
words = ["garden", "hose"]
start = time.perf_counter()
found = [i for i, t in enumerate(texts) if all(w in t.split() for w in words)]
scan_ms = (time.perf_counter() - start) * 1000
con = sqlite3.connect("outputs/index/fts.sqlite")
start = time.perf_counter()
rows = con.execute("SELECT product_id FROM products WHERE products MATCH ?", ('"garden" "hose"',)).fetchall()
index_ms = (time.perf_counter() - start) * 1000
print(f"Read every product: {len(found)} products in {scan_ms:.0f} ms")
print(f"Use the index: {len(rows)} products in {index_ms:.1f} ms")

Exécutez-le :

Fenêtre de terminal
python scan.py
Read every product: 24 products in 100 ms
Use the index: 24 products in 0.3 ms

Les deux méthodes trouvent les mêmes 24 produits. Lire chaque produit prend environ 100 millisecondes. L’index prend environ 0,3 milliseconde : il est environ 300 fois plus rapide. La première exécution peut être plus lente, car l’ordinateur lit le fichier d’index sur le disque. Vos temps seront différents, mais l’écart reste grand.

100 millisecondes semblent peu. Mais la recherche doit aussi classer les produits, construire la page et l’envoyer. Le budget d’Amira pour toute la recherche est de 200 millisecondes. Le temps de lecture de chaque produit augmente aussi avec le catalogue : deux fois plus de produits, deux fois plus de temps. Avec un index, le temps dépend surtout des mots de la requête, pas de la taille du catalogue.

Un index inverse la liste. Un produit énumère ses mots. L’index énumère, pour chaque mot, les produits qui le contiennent. C’est pourquoi on l’appelle un index inversé : « inversé » signifie tourné dans l’autre sens.

Trois mots le décrivent :

  • Un jeton (token) est un mot du texte, après un nettoyage simple. Ici, le nettoyage consiste à passer en minuscules, puis à séparer le texte à chaque espace et signe de ponctuation. « Grey Outdoor Cushion, 18 » devient quatre jetons : grey, outdoor, cushion, 18.
  • La liste de documents (posting list) d’un jeton regroupe les produits qui le contiennent. Dans un livre, ce sont les numéros de page après un mot.
  • Le vocabulaire est la liste de tous les jetons de l’index.

Voici six petits produits, de A à F. Pour construire l’index, prenez chaque produit et séparez son titre en jetons. Ajoutez ensuite le produit à la liste de documents de chaque jeton.

À gauche : six produits. A grey outdoor cushion, B blue outdoor cushion cover, C garden hose with reel, D grey sofa, E outdoor sofa with cushions, F hose reel cart. Une flèche nommée « segmenter en jetons » mène à l'index inversé à droite. Il contient 12 jetons et leurs listes de documents : blue B, cart F, cover B, cushion A et B, cushions E, garden C, grey A et D, hose C et F, outdoor A, B et E, reel C et F, sofa D et E, with C et E. Les lignes cushion et outdoor sont mises en évidence. En bas, la requête outdoor cushion : outdoor donne A, B, E et cushion donne A, B. Tous les mots donnent A et B; au moins un mot donne A, B et E.
Un index inversé de six produits. Pour répondre à une requête, la recherche lit seulement les listes de documents de ses jetons.
Description textuelle du diagramme

À gauche, six produits : A « grey outdoor cushion », B « blue outdoor cushion cover », C « garden hose with reel », D « grey sofa », E « outdoor sofa with cushions » et F « hose reel cart ». À droite, leur index inversé : 12 jetons en ordre alphabétique, chacun avec sa liste de documents. Par exemple, outdoor (extérieur) pointe vers A, B et E, cushion (coussin) vers A et B, et hose (boyau) vers C et F. cushions (coussins) pointe seulement vers E. En bas, la requête « outdoor cushion » lit deux lignes. Tous les mots : les produits dans les deux listes, A et B. Au moins un mot : les produits dans au moins une liste, A, B et E.

Regardez le produit E, « outdoor sofa with cushions ». Il contient le jeton cushions, pas cushion. Pour l’index, ce sont deux jetons différents, aussi différents que « sofa » et « cushion ». Retenez ce point : nous y revenons plus bas.

Pour répondre à la requête « outdoor cushion », la recherche ne lit pas les six produits. Elle lit deux lignes de l’index :

  • outdoor → A, B, E
  • cushion → A, B

Elle combine ensuite les deux listes. Il y a deux façons courantes de le faire :

Requête Tous les mots doivent correspondre (AND) Au moins un mot doit correspondre (OR)
outdoor cushion A, B A, B, E
grey cushion A A, B, D
outdoor cushions E A, B, E

Tous les mots garde les produits présents dans toutes les listes. En mathématiques, c’est l’intersection des listes. Au moins un mot garde les produits présents dans au moins une liste : l’union.

La dernière ligne montre le piège. « outdoor cushions », avec un s, trouve seulement E avec tous les mots. Les deux coussins A et B n’ont pas le jeton cushions, donc ils sont exclus. Une personne voit le même produit. L’index voit un mot différent.

La recherche de Larkfield utilise aujourd’hui SQLite FTS5. SQLite est la petite base de données fournie avec Python. FTS5 est sa partie consacrée à la recherche en texte intégral. Elle construit un index inversé du texte. Dans le projet, larkfield_search/index.py le crée avec une seule instruction :

con.execute("CREATE VIRTUAL TABLE products USING fts5(product_id UNINDEXED, title, description, "
"tokenize = 'unicode61 remove_diacritics 2')")

Le paramètre tokenize indique comment FTS5 crée les jetons. Il sépare le texte aux espaces et à la ponctuation, utilise les minuscules et supprime les accents. Ainsi, « é » devient « e ». La colonne product_id est UNINDEXED (non indexée) : elle est stockée, mais ses mots n’entrent pas dans l’index. Les deux prochaines leçons y reviennent.

FTS5 peut montrer son propre vocabulaire, avec le nombre de produits pour chaque jeton. Ce script affiche la taille de la liste de documents de chaque mot d’une requête. Il compte ensuite les produits avec tous les mots et avec au moins un mot. Enregistrez-le sous postings.py dans larkfield-search :

import sqlite3
import sys
query = sys.argv[1]
con = sqlite3.connect("outputs/index/fts.sqlite")
con.execute("CREATE VIRTUAL TABLE temp.vocab USING fts5vocab(main, 'products', 'row')")
words = query.lower().split()
for w in words:
row = con.execute("SELECT doc FROM temp.vocab WHERE term = ?", (w,)).fetchone()
print(f"{w:<12} in {row[0] if row else 0:>6,} products")
for name, joiner in [("every word", " AND "), ("any word", " OR ")]:
match = joiner.join(f'"{w}"' for w in words)
n = con.execute("SELECT count(*) FROM products WHERE products MATCH ?", (match,)).fetchone()[0]
print(f"{name:<12} {n:>9,} products")

fts5vocab est une vue de l’index que FTS5 crée pour vous. La partie temp. signifie que la vue existe seulement pendant l’exécution du script. Le fichier d’index ne change donc pas. Exécutez-le pour deux requêtes :

Fenêtre de terminal
python postings.py "garden hose"
python postings.py "grey outdor cushion"
garden in 1,352 products
hose in 111 products
every word 24 products
any word 1,439 products
grey in 240 products
outdor in 0 products
cushion in 1,284 products
every word 0 products
any word 1,511 products

Lisez la première requête. 1 352 produits contiennent « garden » et 111 contiennent « hose ». Seulement 24 contiennent les deux. Ce sont les 24 produits de scan.py. Avec au moins un mot, 1 439 produits correspondent : chaque produit de jardin et chaque boyau.

Lisez maintenant la deuxième requête. « outdor » est une faute d’orthographe, et aucun produit ne le contient. Sa liste de documents est vide. Donc, « tous les mots doivent correspondre » ne renvoie rien, même si 1 284 produits contiennent « cushion ». C’est la page vide du module 1. L’index a fait son travail correctement : la règle « tous les mots » est le problème.

L’index FTS5 de Larkfield contient 44 757 jetons différents dans les titres et les descriptions. Dans combien de produits chacun apparaît-il? Le graphique regroupe les jetons selon la taille de leur liste de documents.

Les 44 757 jetons de l'index FTS5 de Larkfield (titre et description), regroupés selon le nombre de produits qui les contiennent (1, 2 à 9, 10 à 99, 100 à 999, 1 000 ou plus). La moitié des jetons sont dans un seul produit.
Description textuelle du graphique

Le graphique a cinq barres. Chaque barre regroupe des jetons selon le nombre de produits qui les contiennent. 22 895 jetons sont dans un seul produit. 13 525 jetons sont dans 2 à 9 produits. 5 859 jetons sont dans 10 à 99 produits. 2 108 jetons sont dans 100 à 999 produits. Seulement 370 jetons sont dans 1 000 produits ou plus. Les jetons les plus courants sont « and » (30 588 produits), « a » (29 081), « the » (28 152), « with » (26 779) et « to » (26 610).

Le graphique montre deux types de jetons. Quelques jetons sont partout : « and » est dans 30 588 des 40 066 produits. Un tel mot vous dit très peu sur un produit. La plupart des jetons sont rares : la moitié sont dans un seul produit. Ce sont des noms, des modèles, des fautes de frappe dans les descriptions et des mots inhabituels.

Un mot rare en dit beaucoup. Si une personne tape « emma », seulement 6 produits le contiennent. Si elle tape « chair », 4 293 produits le contiennent. La prochaine leçon transforme cette observation en une partie du score.

Le vocabulaire montre aussi comment le catalogue écrit les mots. « gray » est dans 1 496 produits, et « grey » dans seulement 240. Une personne qui tape « grey » manque la plupart des produits gris, car l’index voit deux mots. Le module 4 corrige cela.

La recherche de Larkfield utilise aujourd’hui tous les mots. Le carnet mesure ce que cela coûte sur les 60 requêtes de validation en anglais. Avec tous les mots, 24 ne trouvent rien; avec au moins un mot, aucune ne reste sans résultat.

Donc, « au moins un mot » élimine les pages vides. Mais cela apporte un nouveau problème. « garden hose » avec au moins un mot correspond à 1 439 produits. Une personne en lit dix. Quels sont les dix premiers?

FTS5 peut lui-même ordonner ses résultats. La recherche de Larkfield les trie avec le score de FTS5. Mais elle le fait seulement après que « tous les mots » a éliminé la plupart des produits. L’exécution bm25 du projet utilise au moins un mot et son propre calcul de score. Vous avez vu les deux lignes du tableau comparatif dans le module 1 :

Exécution Correspondance NDCG@10 sur les requêtes de test (intervalle à 95 %) Aucun résultat
current tous les mots doivent correspondre 0,195 (0,155 à 0,237) 66,7 %
bm25 au moins un mot doit correspondre 0,429 (0,381 à 0,476) 12,8 %

L’index inversé trouve les candidats. Le classement décide de leur ordre. Les deux exécutions utilisent un index inversé. Elles diffèrent par les produits qu’elles gardent et la façon de les ordonner.

Quand l’utiliser, quand l’éviter et ce qu’il coûte

Section intitulée « Quand l’utiliser, quand l’éviter et ce qu’il coûte »

Utilisez un index inversé quand les gens cherchent des mots présents dans votre texte. Toute recherche par mots le fait : recherche de produits, centre d’aide, boîte de courriels. C’est la base de la prochaine leçon et de toute recherche lexicale dans ce cours. Lexical signifie « basé sur les mots eux-mêmes ».

Ce qu’il coûte. Vous le construisez une fois et le stockez. L’index FTS5 de Larkfield occupe 35,8 Mo sur le disque pour 40 066 produits. Le projet le construit, avec BM25, en environ 2 secondes. Quand un produit change, l’index doit changer aussi. Le module 8 montre comment le garder à jour.

Ce qu’il ne peut pas faire. Il trouve les jetons exacts, rien de plus :

  • « cushions » et « cushion », ou « grey » et « gray », sont des jetons différents. Normaliser le texte aide (module 4).
  • « couch » et « sofa » n’ont aucun jeton en commun. L’index ne peut pas savoir qu’ils signifient la même chose. Les synonymes (module 4) et la recherche par le sens (module 5) aident.
  • Un mot absent du texte ne peut pas être trouvé. Les codes de produit comme LK-91857 sont dans la colonne product_id, pas dans le titre ou la description. La dernière leçon de ce module ajoute une règle pour eux.

Exécutez postings.py pour « teal chair », « ligth bulb » et « light bulb ». Pour chacune, prédisez d’abord : « tous les mots » trouvera-t-il quelque chose? Comparez ensuite les tailles des listes de documents.

Voici nos résultats : « teal chair » trouve 8 produits avec tous les mots (teal 211, chair 4 293). « ligth bulb » ne trouve rien, car « ligth » n’est dans aucun produit. Mais au moins un mot trouve les 523 produits contenant « bulb ». « light bulb » en trouve 473 avec tous les mots. Une seule lettre incorrecte fait passer de 473 produits à aucun.

Erreur courante

Le pluriel trouve d'autres produits

Symptôme : vous cherchez « outdoor cushions » et « outdoor cushion ». Vous attendez les mêmes produits, mais postings.py donne des nombres différents :

outdoor in 3,252 products
cushions in 1,577 products
every word 702 products
any word 4,127 products
outdoor in 3,252 products
cushion in 1,284 products
every word 425 products
any word 4,111 products

Cause : l’index stocke les jetons exactement comme le nettoyage les a produits. cushion et cushions sont deux lignes de l’index, avec deux listes de documents différentes. Un produit qui dit « cushion » une fois n’est pas dans la liste de documents de cushions.

Diagnostic : cherchez chaque mot de la requête dans le vocabulaire, comme le fait postings.py. Quand un mot attendu a une liste courte ou vide, vérifiez les autres formes. Regardez le pluriel, l’autre orthographe, le mot avec un accent.

Correction : traitez la requête et les produits de la même façon. Si vous changez « cushions » en « cushion » dans la requête, vous devez aussi le changer dans chaque produit avant de construire l’index. Le module 4 le fait avec un raciniseur. Il mesure ce que cela corrige et ce que cela brise.

Conséquence dans le travail en IA : chaque système de recherche a une étape de nettoyage avant l’index. Quand la recherche « manque » un produit évident, la raison est souvent les jetons, pas le classement.

Vérifiez votre compréhension

Utilisez l'index des six produits. Quels produits « grey outdoor » trouve-t-il avec tous les mots, puis avec au moins un mot? Combien de lignes de l'index la recherche lit-elle?

Afficher la réponse

La recherche lit deux lignes : grey (gris) → A, D et outdoor → A, B, E. Avec tous les mots, elle garde les produits dans les deux listes : A. Avec au moins un mot, elle garde les produits dans au moins une liste : A, B, D, E. Elle ne lit jamais les produits eux-mêmes, seulement deux lignes.

Vérifiez votre compréhension

L'index de Larkfield indique : « garden » dans 1 352 produits, « hose » dans 111 produits. Combien de produits « tous les mots » peut-il renvoyer au maximum? Pourquoi la réponse est-elle 24 et non 111?

Afficher la réponse

Au maximum 111 : chaque produit contenant les deux mots est dans la liste la plus courte, celle de « hose ». La vraie réponse est 24, car la plupart des boyaux ne disent pas « garden ». De plus, la plupart des produits de jardin ne sont pas des boyaux. Tous les mots garde seulement les produits dans les deux listes. Au moins un mot garde les produits dans au moins une liste : 1 439.

Vérifiez votre compréhension

Tomás dit : « Notre recherche ne renvoie rien pour “grey outdor cushion”. L'index doit être brisé. Reconstruisons-le. » Que répondez-vous et que vérifieriez-vous d'abord?

Afficher la réponse

L’index n’est pas brisé. Il n’a pas de liste de documents pour « outdor », car aucun produit ne contient ce mot. Avec tous les mots, une seule liste vide rend toute la réponse vide. Reconstruire l’index ne change rien. Vérifiez d’abord la liste de documents de chaque mot de la requête, comme le fait postings.py : « grey » 240, « outdor » 0, « cushion » 1 284. La correction est dans la requête, pas dans l’index : autorisez au moins un mot ou corrigez l’orthographe (module 4).

Récapitulatif

  • Un index inversé énumère, pour chaque jeton, les produits qui le contiennent : sa liste de documents. Il est construit une fois et utilisé par chaque recherche.
  • Une requête lit seulement les listes de documents de ses propres jetons. « Tous les mots » garde les produits dans toutes les listes. « Au moins un mot » garde les produits dans au moins une liste.
  • La recherche de Larkfield utilise SQLite FTS5, un index inversé. Une consultation de l’index prend bien moins d’une milliseconde; lire chaque produit prend environ 100 millisecondes.
  • L’index trouve seulement les jetons exacts : « cushion » n’est pas « cushions », « grey » n’est pas « gray ». Un code de produit n’est pas dans le texte.
  • La plupart des 44 757 jetons sont rares, et quelques-uns sont dans la plupart des produits. Un mot rare en dit plus sur un produit qu’un mot courant.

Vous pouvez maintenant trouver rapidement chaque produit qui contient les mots d’une requête. Mais « garden hose » avec au moins un mot correspond à 1 439 produits, et une personne en lit dix. Ensuite, vous attribuez un score à chaque produit avec BM25 et examinez chaque partie du score.

Leçon suivante : BM25