Arbre d'ondelettes

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.

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

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

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

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

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[4]. 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[6] dynamique[7]. On peut encore généraliser ceci et autoriser de modifier l'alphabet de base : un wavelet trie[8] exploite une structure de trie sur l’alphabet des chaînes pour permettre des modifications dynamiques.

• 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.