Index inversés

Un index inversé associe chaque terme d'une collection à une liste de publications (postings list) des documents qui le contiennent, permettant ainsi à un système de recherche de trouver les documents correspondants sans avoir à parcourir chaque document.

Definition

Un index inversé est une structure de données composée d'un dictionnaire de termes indexés, chacun pointant vers une liste de publications (postings list) qui énumère les documents contenant le terme, souvent annotée avec les fréquences et les positions des termes, de sorte que la récupération peut être effectuée en intersectant ou en fusionnant les listes de publications.

Scope

Ce sujet couvre la structure et la construction de l'index inversé : le dictionnaire de termes, les listes de publications (postings lists) enregistrant les identifiants de documents, les fréquences de termes et les positions, ainsi que les algorithmes qui construisent et mettent à jour les index sur de grandes collections, y compris l'indexation par tri par blocs (blocked sort-based indexing) et l'indexation en mémoire en un seul passage (single-pass in-memory indexing). Il aborde les informations positionnelles pour les requêtes de phrases et l'ingénierie de la maintenance des index, tout en laissant la compression et la stratégie d'évaluation des requêtes à des sujets connexes.

Core questions

• Que contient une entrée de dictionnaire et sa liste de publications ?
• Comment les positions sont-elles stockées pour prendre en charge les requêtes de phrases et de proximité ?
• Comment un index inversé est-il construit lorsque la collection est trop grande pour la mémoire ?
• Comment un index est-il mis à jour lorsque des documents sont ajoutés, modifiés ou supprimés ?
• Comment les listes de publications permettent-elles une intersection efficace pour les requêtes conjonctives ?

Key concepts

• dictionnaire de termes
• liste de publications
• identifiants de documents
• index positionnel
• stockage des fréquences de termes
• indexation par tri par blocs (BSBI)
• indexation en mémoire en un seul passage (SPIMI)
• fusion et mises à jour d'index

Key theories

Organisation du dictionnaire et des listes de publications

La séparation d'un dictionnaire de termes compact des listes de publications de longueur variable permet au système de rechercher rapidement un terme et de ne diffuser ensuite que les documents pertinents, ce qui constitue la base structurelle de toute récupération par index inversé.

Construction d'index évolutive

Les méthodes basées sur disque, telles que l'indexation par tri par blocs et l'indexation en mémoire en un seul passage, construisent des fichiers inversés pour des collections bien plus grandes que la mémoire en accumulant et en fusionnant des index partiels.

Clinical relevance

L'index inversé est la structure de données centrale de pratiquement tous les systèmes de recherche textuelle, y compris les moteurs de recherche web, les plateformes de recherche open source telles que Lucene et ses dérivés, et la recherche en texte intégral de bases de données. Sa conception détermine les types de requêtes pris en charge et la rapidité et le coût de leurs réponses.

History

Les fichiers inversés étaient utilisés dans les premiers systèmes de recherche bibliographique et sont devenus la structure standard pour la recherche en texte intégral à mesure que les collections augmentaient. La recherche dans les années 1990 et 2000, y compris les méthodes de construction évolutives telles que l'indexation en mémoire en un seul passage (single-pass in-memory indexing), a rendu pratique l'indexation de corpus à l'échelle du web, et cette structure est désormais le pilier de bibliothèques de recherche open source largement utilisées.

Key figures

• Justin Zobel
• Alistair Moffat
• Steffen Heinz

Seminal works

• zobel2006
• heinz2003
• manning2008

Frequently asked questions

Pourquoi est-il appelé index « inversé » ?

Un index normal (direct) liste, pour chaque document, les termes qu'il contient. L'index inversé inverse cette correspondance pour lister, pour chaque terme, les documents qui le contiennent. Cette inversion est précisément ce qui rend la recherche basée sur les termes rapide.

À quoi sert un index positionnel ?

Un index positionnel stocke les positions auxquelles chaque terme apparaît dans chaque document. Cela permet au système de répondre aux requêtes de phrases et aux requêtes de proximité, où l'ordre ou la proximité des termes est important, plutôt que de se limiter à la simple présence des termes dans le document.