Arbre d'ondelettes

Un arbre d'ondelettes (en anglais wavelet tree) est une structure de données qui contient des données compressées dans une représentation presque optimale, appelée succincte. Cette structure étend les opérations de parcours et de sélection définies sur les vecteurs de bits (en) compressés à des alphabets quelconques.

Un arbre d'ondelettes pour la chaîne abracadabra. À chaque nœud, les symboles de la chaîne sont projetés sur une partition de l'alphabet en deux parties, et le vecteur de bits désigne la partie à laquelle appartiennent les symboles. Seuls les vecteurs de bits sont conservés, les chaînes indiquées dans les nœuds ne servent qu'à faciliter la présentation.

Introduits à l'origine pour représenter des tableaux des suffixes compressés, les arbres d'ondelettes ont trouvé des applications dans des contextes variés. L'arbre d'ondelettes est défini en partitionnant récursivement l'alphabet en deux sous-ensembles; les feuilles correspondent aux symboles de l'alphabet, et à chaque nœud est associé un vecteur de bits compressé qui mémorise le sous-ensemble auquel appartiennent les symboles.

Le nom dérive de l'analogie avec la transformée en ondelettes des signaux qui décompose récursivement un signal en composantes de fréquences basses et hautes.

Exemple

Dans l'exemple reproduit ci-dessus, l'alphabet de départ est partagé en deux sous-alphabets {a, b} et {c, d, r}. Le premier vecteur, à la racine, remplace les symboles du mot abracadabra par 0 ou 1, selon que le symbole est dans le premier sous-alphabet ({a, b}) ou dans le second ({c, d, r}). Au niveau suivant, on ne conserve plus que les symboles sélectionnés. La séquence de gauche est également partagée en deux, selon que la lettre est un a ou un b. Pour la séquence de droite, deux étapes sont nécessaires pour arriver à des alphabets formés d'un seul symbole. Pour trouver le deuxième a dans la chaîne initiale, on cherche d'abord le deuxième 0 dans le code 0100010 qui se trouve en troisième position, puis le troisième 0 dans le code 00101010010. C'est la quatrième lettre de cette chaîne, donc la quatrième du mot abracadabra.

Propriétés

Soit $\Sigma$ un alphabet fini à $k$ symboles. En utilisant un dictionnaire succinct (en) dans chaque nœud de l'arbre, une chaîne $s\in \Sigma ^{*}$ de longueur $n$ peut être représentée en place $nH_{0}(s)+o(n\log k)$, où $H_{0}(s)$ est l'entropie de Shannon d'ordre 0 de $s$.

Pour un tableau $B$ de bits de taille $n$ donné, les trois opérations considérées sont les suivantes :

• ${\mathsf {access}}(x)$ qui retourne l'élément qui est en position $x$ dans la chaîne $s$ de départ.
• ${\mathsf {rank}}_{q}(x)$ qui retourne le nombre d'éléments égaux à $q$ parmi les $x$ premiers éléments du tableau, formellement ${\mathsf {rank}}_{q}(x)=\operatorname {Card} \{y\in [0\cdots x]:B[y]=q\}$.
• ${\mathsf {select}}_{q}(x)$ qui retourne la plus $x$-ième position dans le tableau qui contient un $q$, formellement ${\mathsf {select}}_{q}(x)=\min\{y\in [0\cdots n):{\mathsf {rank}}_{q}(y)=x\}$.

Si l'arbre est équilibré, les trois opérations ${\mathsf {access}}$, ${\mathsf {rank}}_{q}$, et ${\mathsf {select}}_{q}$ peuvent être réalisées en temps $O(\log k)$.

Extensions

Plusieurs extensions de la structure de base ont été présentées dans la littérature. Pour réduire la hauteur de l'arbre, on peut utiliser des arbres dont les nœuds ont une arité supérieure aux nœuds binaires. La structure de données peut être rendue dynamique, ce qui permet des insertions et suppressions à des positions arbitraires de la chaîne ; ceci permet l'implémentation du FM-index dynamique. On peut encore généraliser ceci et autoriser de modifier l'alphabet de base : un wavelet trie exploite une structure de trie sur l’alphabet des chaînes pour permettre des modifications dynamiques.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Wavelet Tree » (voir la liste des auteurs).

Liens externes

• Wavelet Trees. Un blog qui décrit la construction d'un wavelet tree, avec exemples.
• Mikaël Salson, Structures d’indexation compressées et dynamiques pour le texte. Un manuscrit en français avec de nombreux exemples détaillés.