Structures d'indexation de chaînes de caractères

Les structures d'indexation de chaînes de caractères prétraitent un texte sous une forme interrogeable — arbres de préfixes (tries), arbres de suffixes ou tableaux de suffixes — afin que de nombreuses requêtes ultérieures de motifs, ainsi que des questions sur les répétitions et les sous-chaînes communes, puissent être résolues rapidement.

Definition

Une structure d'indexation de chaînes de caractères est une structure de données construite à partir d'un texte (ou d'un ensemble de chaînes) qui permet des requêtes efficaces sur le texte — telles que la présence et la localisation d'un motif, la plus longue sous-chaîne répétée, ou la plus longue sous-chaîne commune à deux textes — généralement en représentant les préfixes ou les suffixes du texte.

Scope

Ce sujet couvre les structures de données qui indexent les chaînes de caractères pour des requêtes répétées rapides : les arbres de préfixes (tries) pour des ensembles de chaînes, les arbres de suffixes qui représentent tous les suffixes d'un texte pour une recherche de motifs en temps linéaire, les tableaux de suffixes comme leur équivalent économe en espace, et les structures de support telles que le tableau des plus longs préfixes communs (longest-common-prefix array). Il aborde leurs algorithmes de construction et les requêtes qu'ils accélèrent, et exclut la recherche de motifs ponctuelle (single-shot pattern matching), qui ne prétraite pas le texte.

Core questions

• Comment un arbre de préfixes (trie) organise-t-il un ensemble de chaînes pour une recherche basée sur les préfixes ?
• Comment un arbre de suffixes représente-t-il tous les suffixes de manière à ce que les requêtes de motifs prennent un temps proportionnel à la longueur du motif ?
• Comment les tableaux de suffixes atteignent-ils une puissance similaire avec moins de mémoire ?
• Quels algorithmes de construction permettent de bâtir ces structures efficacement, idéalement en temps linéaire ?
• Quels problèmes textuels (répétitions, sous-chaînes communes) ces index résolvent-ils élégamment ?

Key concepts

• arbre de préfixes (trie)
• arbre de suffixes
• tableau de suffixes
• tableau des plus longs préfixes communs
• construction en ligne
• plus longue sous-chaîne répétée
• plus longue sous-chaîne commune
• compromis espace-temps

Key theories

Arbres de suffixes et construction en temps linéaire

Un arbre de suffixes représente de manière compacte chaque suffixe d'un texte, permettant de rechercher un motif en un temps proportionnel à sa longueur ; l'algorithme d'Ukkonen le construit en ligne en un temps linéaire par rapport à la longueur du texte.

Tableaux de suffixes comme index économe en espace

Un tableau de suffixes stocke l'ordre trié de tous les suffixes dans un simple tableau d'entiers ; combiné à un tableau des plus longs préfixes communs, il permet une recherche rapide de motifs en utilisant beaucoup moins de mémoire qu'un arbre de suffixes.

Clinical relevance

Les index textuels sont essentiels pour la recherche à grande échelle et la bioinformatique : les tableaux de suffixes et les index compressés associés sont à la base des aligneurs de lectures génomiques et des moteurs de recherche plein texte, les arbres de préfixes (tries) prennent en charge l'autocomplétion et les tables de routage IP, et ces structures rendent pratiques les requêtes répétées sur des textes massifs là où une nouvelle analyse serait prohibitive.

History

Peter Weiner a introduit les arbres de suffixes en 1973, avec des constructions en temps linéaire plus simples par McCreight (1976) et Ukkonen (1995). Manber et Myers ont introduit les tableaux de suffixes en 1990 comme une alternative plus économe en espace, et des travaux ultérieurs sur les index compressés et FM ont étendu ces idées à de très grands textes et génomes.

Key figures

• Peter Weiner
• Edward McCreight
• Esko Ukkonen
• Udi Manber
• Gene Myers
• Dan Gusfield

Seminal works

• ukkonen1995
• manber1993
• gusfield1997

Frequently asked questions

Quand devrais-je utiliser un tableau de suffixes plutôt qu'un arbre de suffixes ?

Les tableaux de suffixes utilisent considérablement moins de mémoire que les arbres de suffixes et présentent un bon comportement de cache, ce qui les rend préférables pour les textes volumineux tels que les génomes. Les arbres de suffixes exposent plus directement la structure et peuvent rendre certains algorithmes conceptuellement plus simples, mais à un coût en espace plus élevé ; les tableaux de suffixes combinés à un tableau des plus longs préfixes communs récupèrent la majeure partie de cette puissance.

À quoi sert un arbre de préfixes (trie) ?

Un arbre de préfixes (trie) stocke un ensemble de chaînes par préfixes partagés, permettant une recherche rapide de préfixes, l'autocomplétion et un parcours ordonné. Il est bien adapté aux dictionnaires, aux suggestions d'autocomplétion et à la correspondance du plus long préfixe, comme dans le routage IP, où les clés partagent des débuts communs.