Indexation et Traitement des Requêtes
L'indexation et le traitement des requêtes englobent les structures de données et les algorithmes qui permettent à un système de recherche de répondre rapidement aux requêtes sur de vastes collections de textes, principalement grâce à l'index inversé.
Definition
L'indexation est la construction de structures de données, principalement l'index inversé qui associe les termes aux documents les contenant, et qui permet une recherche efficace, tandis que le traitement des requêtes est l'ensemble des algorithmes qui parcourent ces structures pour calculer les documents correspondant ou les mieux classés pour une requête.
Scope
Ce domaine couvre la manière dont les collections de textes sont transformées en structures interrogeables et comment les requêtes sont évaluées par rapport à celles-ci : la construction de l'index inversé, les décisions de tokenisation et de vocabulaire des termes qui la sous-tendent, la compression des listes de diffusion (postings) pour économiser de l'espace et accélérer l'accès, le traitement efficace des requêtes, y compris la récupération classée et la terminaison anticipée, ainsi que les techniques de récupération tolérante telles que les jokers (wildcard), la correction orthographique et la correspondance phonétique. Il aborde l'ingénierie des systèmes de récupération rapide, distincte des modèles de récupération qui définissent le classement et des méthodes d'évaluation qui mesurent la qualité.
Sub-topics
Core questions
- Comment un index inversé est-il construit et mis à jour pour une collection vaste et évolutive ?
- Comment les listes de diffusion (postings lists) peuvent-elles être compressées sans ralentir l'évaluation des requêtes ?
- Comment les requêtes sont-elles évaluées efficacement, en particulier les requêtes classées sur des millions de documents ?
- Comment un système peut-il récupérer de bons résultats sans évaluer chaque document ?
- Comment un système gère-t-il les fautes d'orthographe, les jokers (wildcards) et les correspondances approximatives ?
Key concepts
- index inversé
- liste de diffusion (postings list)
- tokenisation et vocabulaire des termes
- construction d'index (BSBI, SPIMI)
- compression d'index
- évaluation document par document et terme par terme
- élagage dynamique et terminaison anticipée
- recherche tolérante
Key theories
- L'index inversé comme structure de données centrale
- L'association de chaque terme à une liste de diffusion (postings list) des documents (et positions) où il apparaît permet à la récupération de ne concerner que les documents contenant les termes de la requête, ce qui en fait la structure fondamentale pour la recherche textuelle évolutive.
- Compromis compression-efficacité
- L'encodage des écarts d'identifiants de documents et des fréquences de termes avec des codes entiers compacts réduit considérablement la taille de l'index et, en diminuant les entrées/sorties et en améliorant le comportement du cache, peut également accélérer le traitement des requêtes.
- Évaluation efficace des requêtes classées
- Les stratégies document par document et terme par terme, combinées aux techniques d'élagage dynamique et de terminaison anticipée, permettent aux systèmes de renvoyer les résultats les mieux classés sans évaluer entièrement toute la collection.
Clinical relevance
Les index inversés et le traitement efficace des requêtes sont le moteur de tout système de recherche en production, des moteurs de recherche web et plateformes de recherche open source aux systèmes de recherche plein texte d'entreprise et de bases de données. Leur efficacité détermine directement la latence des requêtes, le coût matériel et l'échelle des collections pouvant être interrogées de manière interactive.
History
Les fichiers inversés sont utilisés pour la recherche textuelle depuis les premiers systèmes d'information, mais la théorie moderne de la construction d'index, de la compression et de l'évaluation efficace a été consolidée dans les années 1990, notamment par l'ouvrage Managing Gigabytes de Witten, Moffat et Bell. L'étude de Zobel et Moffat de 2006 a synthétisé deux décennies de recherche sur les index inversés, alors que la recherche à l'échelle du web rendait l'efficacité primordiale.
Key figures
- Justin Zobel
- Alistair Moffat
- Ian H. Witten
- W. Bruce Croft
Related topics
Seminal works
- zobel2006
- wittenmgb1999
- manning2008
Frequently asked questions
- Pourquoi l'index inversé est-il préféré à la lecture séquentielle des documents ?
- La lecture séquentielle de chaque document pour chaque requête est beaucoup trop lente à grande échelle. L'index inversé permet au système de passer directement au petit ensemble de documents qui contiennent les termes de la requête, de sorte que le temps de requête dépend des listes de diffusion (postings lists) impliquées plutôt que de la taille de l'ensemble de la collection.
- La compression de l'index ralentit-elle la recherche ?
- Généralement, c'est le contraire. Un index plus petit réduit le trafic disque et mémoire, et les codes entiers modernes se décompressent très rapidement, de sorte que le temps gagné sur les entrées/sorties et l'amélioration du comportement du cache l'emporte généralement sur le coût de décodage, rendant les index compressés à la fois plus petits et plus rapides.