Comment fonctionne un index inversé ?

Question

IT Interview Practice · Accepted Answer

**Un index inversé associe chaque terme aux documents qui le contiennent.** Le moteur de recherche peut ainsi trouver les documents candidats sans relire intégralement chaque document à chaque recherche.

Pensez à l’index à la fin d’un livre : cherchez un mot, puis consultez les pages indiquées. Dans un moteur de recherche, les identifiants de documents remplacent les numéros de page.

## 1. Partir d’une petite collection

Prenons trois documents et un analyseur simple qui passe le texte en minuscules et sépare les mots. L’analyseur désigne les étapes transformant un texte en termes recherchables.

```text
D1: Red apple
D2: Green apple
D3: Red car

apple -> D1, D2
car   -> D3
green -> D2
red   -> D1, D3
```

Au départ, on passe du document aux mots. L’index inverse ce sens : du mot vers les documents, d’où son nom. La liste des documents correspondant à un terme s’appelle une liste d’occurrences, ou posting list.

## 2. Utiliser les listes pour répondre à une requête

Pour une requête exigeant red et apple, lisez leurs deux listes et prenez leur intersection : D1 figure dans les deux. Si l’un ou l’autre terme suffit, prenez leur union : D1, D2 et D3 sont candidats.

Cet exemple explique la correspondance, pas le classement. Si plusieurs documents correspondent, le moteur peut les noter selon la fréquence des termes et leur rareté dans la collection. Trouver les correspondances et décider de leur ordre sont deux étapes liées mais distinctes.

## 3. Faire correspondre indexation et recherche

La requête doit être analysée de manière compatible avec les termes indexés. Si l’indexation transforme Red en red mais que la recherche demande littéralement Red, elle peut manquer le résultat attendu.

L’analyse dépend du champ. Une description de produit bénéficie d’une analyse textuelle ; un identifiant de commande exige généralement une correspondance exacte. Découper cet identifiant en mots ordinaires peut en changer le sens. Voir l’explication Elastic de la [recherche plein texte](https://www.elastic.co/docs/solutions/search/full-text/how-full-text-works).

## 4. Stocker les informations nécessaires à la question

Un document contenant red et apple ne contient pas nécessairement l’expression red apple. Pour rechercher une expression, l’index doit connaître les positions afin de vérifier l’ordre et la proximité des mots.

- Les identifiants indiquent quels documents contiennent le terme.
- Les fréquences décrivent combien de fois il apparaît.
- Les positions permettent de situer les termes les uns par rapport aux autres.

Stocker davantage d’informations permet des recherches plus riches, mais augmente la taille de l’index et le travail d’indexation. Les recherches requises par l’application déterminent les informations utiles.

## 5. Comprendre le coût de la mise à jour

Lorsque le texte source change, son index doit aussi évoluer. Des systèmes comme Elasticsearch gèrent les données indexées en segments qu’ils fusionnent progressivement ; une mise à jour ne réécrit pas immédiatement toutes les listes existantes sur place. La visibilité dans la recherche dépend aussi du rafraîchissement du moteur.

Prévoyez donc du stockage supplémentaire, le coût d’indexation et un éventuel délai entre l’écriture d’un document et sa disponibilité dans la recherche. L’index inversé est particulièrement utile pour rechercher des termes dans du texte ; il ne remplace pas universellement les index servant aux recherches exactes, aux plages de valeurs ou aux accès transactionnels.

1. Partir d’une petite collection

2. Utiliser les listes pour répondre à une requête

3. Faire correspondre indexation et recherche

4. Stocker les informations nécessaires à la question

5. Comprendre le coût de la mise à jour

Questions connexes