Wavelet Tree, Part I: A Brief History

The field of compressed full-text indexing [29] involves the design of data structures (aka, indexes) that support fast substring matching using small amounts of space. For a text string $𝒯[1,n]$ over an arbitrary alphabet $\mathrm{\Sigma }$ of size $\sigma$ and a pattern $𝒫[1,m]$, the goal of text indexing is to preprocess $𝒯$ using succinct space so that queries like the following can be quickly answered: (1) count the number $\mathrm{𝑜𝑐𝑐}$ of occurrences of $𝒫$ in $𝒯$; (2) locate the $\mathrm{𝑜𝑐𝑐}$ positions in $𝒯$ where $𝒫$ occurs; and (3) starting at text position $\mathrm{𝑠𝑡𝑎𝑟𝑡}$, extract the length-$\mathrm{\ell }$ substring $𝒯[\mathrm{𝑠𝑡𝑎𝑟𝑡},\mathrm{𝑠𝑡𝑎𝑟𝑡}+\mathrm{\ell }-1]$.

A main goal is to create an index whose size is roughly equal to the size of the text in compressed format, with search performance comparable to the well-known indexes on uncompressed text, such as suffix trees and suffix arrays. Some compressed data structures are in addition self-indexes in that the data structure encapsulates the original text and, thus, can quickly recreate any portion of it. As a result, the original text is not needed, it can be discarded and replaced by only the (self-)index.

Most compressed indexing techniques developed in the last two decades make use of the powerful Wavelet Tree data structure, developed by Grossi, Gupta, and Vitter [16], with many applications to information retrieval, genome analysis, data mining, and web search. A Wavelet Tree supports fast rank and select queries on any string from a general multisymbol alphabet $\mathrm{\Sigma }$. As such, it provides an elegant extension of rank-select data structures for binary sequences [31, 29] to the general case of alphabets of arbitrary size.

The Wavelet Tree represents a string of symbols from an arbitrary alphabet $\mathrm{\Sigma }$ as a hierarchical set (or tree) of binary strings. It has the following key compression property: If each such binary string is compressed according to its information-theoretic minimum size, then the original string is compressed to its information-theoretic minimum size.

The Wavelet Tree tree structure can be thought of as a generalization in the context of computational geometry of the two-dimensional range search data structure of Chazelle [4] in which the two-dimensional points stored in a binary tree node are initially sorted in one dimension and then recursively partitioned into children based upon the second dimension. Kärkkäinen [21] used a similar data structure in a very different way and purpose in the context of highly repetitive texts.

Why the name “Wavelet Tree”? One of the codevelopers suggested the name based upon his research interests in the fields of image compression and database query optimizaton, where he used wavelet transforms and their hierarchical decompositions to approximate multiresolution data [33].

In this paper (PART I), we give a brief history of Wavelet Trees, including its varieties and practical implementations. We refer the reader to PART II, included in the Festschrift dedicated to Giovanni Manzini, for a discussion about the important role of Wavelet Trees in text indexing, particularly for compressed suffix arrays and the FM-index, which can produce self-indexes with size related to the higher-order entropy of the text.

Let $\mathrm{\Sigma }=\{0,1,\mathrm{\dots },\sigma -1\}$ be a finite ordered alphabet of size $\sigma$. Let $𝒯=𝒯[0,n-1]$ be a text string consisting of $n$ symbols from alphabet $\mathrm{\Sigma }$. For simplicity, we assume that $𝒯[n-1]$ is a special end-of-text symbol $\mathrm{\#}$ that is the lexicographically smallest symbol in $\mathrm{\Sigma }$. We use $𝒯[i,j]$ to denote the substring of $𝒯$ consisting of the symbols $𝒯[i]𝒯[i+1]\mathrm{\dots }𝒯[j]$. A prefix of $𝒯$ is a substring of the form $𝒯[0,i]$, and a suffix is a substring of the form $𝒯[j,n-1]$.

Two key operations we will need for accessing and traversing Wavelet Trees are $\mathrm{𝑟𝑎𝑛𝑘}$ and $\mathrm{𝑠𝑒𝑙𝑒𝑐𝑡}$:

A more stringent notion of entropy is the information-theoretic minimum (or 0th-order finite-set entropy), given by

It is always less than or equal to the 0th-order empirical entropy.

Higher orders of entropy can be defined readily if we encode symbols based upon their frequencies of occurrence when grouped into common contexts.

In a like manner, we can define the $k$th-order finite-set entropy by

where $n_{y,𝗑}$ for $y\in \mathrm{\Sigma }$ is the number of occurrences of $y𝗑$ as a substring in $𝒯$. The $k$th-order finite-set entropy is always less than or equal to the $k$th-order empirical entropy.

In other words, the key point of the $k$th-order entropy definition is that we can achieve it by encoding the relevant parts of $𝒯$ using 0th-order entropy. (This property was later appropriately dubbed “boosting.”) In particular, if we form the substrings ${𝒯}_{𝗑}$ for each relevant $k$-context $𝗑$ and compress each ${𝒯}_{𝗑}$ to achieve space of $n_{𝗑}$ times its 0th-order empirical entropy ${\mathscr{H}}_0({𝒯}_{𝗑})$, then the resulting compression for the full text string $𝒯$ will be $n$ times the $k$th-order empirical entropy ${\mathscr{H}}_k(𝒯)$. Wavelet Trees are a natural and elegant way to compress each substring ${𝒯}_{𝗑}$ to $n_{𝗑}{\mathscr{H}}_0({𝒯}_{𝗑})$ bits plus lower-order terms, and thus the resulting cumulative encoding of $𝒯$ has size in bits bounded by $n{\mathscr{H}}_k(𝒯)$ plus lower-order terms. This fact is exploited in PART II to show how Wavelet Trees can be used to create text indexes that use space related to the high-order entropy of $𝒯$.

For two strings $S$ and $T$, we define the lexicographic order $S\prec T$ (and say that $S$ is smaller than $T$) if $S$ is a proper prefix of $T$, or if there exists an index $1\le i\le \min \{|S|,|T|\}$ such that and for all , $S[j]=T[j]$.

We use $\mathrm{𝑆𝐴}[0,n-1]$ to denote the suffix array ($\mathrm{𝑆𝐴}$) of $𝒯$. It consists of the positions of all the suffixes of $𝒯$ in lexicographical order. For example, in the text string $𝒯=\text{tcaaaatatatgcaacatatagtattagattgtat\#}$ in Table 1, the smallest suffix begins at position $\mathrm{𝑆𝐴}[0]=35$, and the next smallest suffix begins at position $\mathrm{𝑆𝐴}[1]=2$. The ordered suffixes are pictured in the (wide) second-to-last column of the table. For convenience, we regard text $𝒯$ as a circular string and implicitly use modular arithmetic base $n$ for the indices of $𝒯$. In other words, references to a symbol $𝒯[i]$ actually refer to $𝒯[imodn]$.

Further development of suffix arrays that leads to the notion of compressed suffix arrays is discussed in PART II. Compressed suffix arrays are self-indexes that use space proportional to the high-order entropy of the text and provide fast pattern-matching queries. The key notion that leads to the compression of suffix arrays is the important neighbor function, which for each $i\in [0,n-1]$ maps $i$ to the lexicographic order of the suffix formed by taking the $i$th smallest suffix of $𝒯$ and rotating it to the left by one symbol.

The Burrows-Wheeler Transform (BWT) is another reversible transformation of a text string $𝒯$ that rearranges the symbols of $𝒯$ in a way that groups together the same symbols from similar contexts, thus resulting in high compressibility [2, 26]. In terms of Table 1, the BWT is represented by the last subcolumn (designated by $L$). PART II provides further development of the BWT that leads to the FM-index, which like the compressed suffix array, uses space proportional to the high-order entropy of the text and provides fast pattern-matching queries. The key notion behind the FM-index and its compression is the $\mathrm{𝐿𝐹}$ function, which is the inverse of the neighbor function for compressed suffix arrays mentioned above. That is, the $\mathrm{𝐿𝐹}$ function maps each $i$ to the lexicographic order of the suffix formed by taking the $i$th smallest suffix of $𝒯$ and rotating it to the right (rather than to the left) by one symbol. The symbol under $L$ in row $i$ is the same symbol under $F$ in row $\mathrm{𝐿𝐹}(i)$.

Wavelet Trees provide an elegant and efficient implementation of rank-select data structures for strings of symbols from an arbitrary multisymbol alphabet. They generalize the well-known rank-select data structures such as RRR [31] that handle binary strings.

Conceptually, the Wavelet Tree is most simply described as a full (and often balanced) binary tree (see the example in Figure 1). The root node is a bit array $ℬ$ of the same length as the input text $𝒯$ and partitions the text’s alphabet into two sets, where a 0-bit indicates that the corresponding text symbol is in the left set and a 1-bit indicates that the text symbol is in the right set. (See Table 1 for the bit array $ℬ$ applied to the string $L$.) Such a bit array representation happens recursively at each internal node, where the text at the internal node is of the symbols dispatched from the parent node with their order in the text preserved. Each leaf node represents a distinct symbol of the alphabet of the input text, with its multiplicity preserved.

Operations of $\mathrm{𝑟𝑎𝑛𝑘}$ and $\mathrm{𝑠𝑒𝑙𝑒𝑐𝑡}$ on binary strings, as defined in Definition 1, are used to navigate up and down the Wavelet Tree. For example, in the root node of the Wavelet Tree of Figure 1, consider the symbol $a$ in the sixth position of $L$, which is represented by a 0, which means that its corresponding entry on the next level is in the left subtree. To find that entry, we compute ${\mathrm{𝑟𝑎𝑛𝑘}}_0(L,6)=5$ using a data structure such as RRR; we thus find that the corresponding entry is entry 5 in the left subtree. To go from that entry on level 2 back to the position of the corresponding entry in root node, we compute ${\mathrm{𝑠𝑒𝑙𝑒𝑐𝑡}}_0(L,5)=6$.

Of course, extra data structures are needed in order to support the needed query operations and functionality in an efficient way. Those details are not given here in this survey. Instead we focus on the main ideas that make wavelet trees such an elegant and powerful method.

The key aspect of Wavelet Trees is that they cleverly decompose the text into a hierarchy of bit arrays without introducing any redundancy, so that the total size of the raw bit arrays in the Wavelet Tree is exactly the same as the size (in bits) of the input text, regardless of the shape of the Wavelet Tree. If the bit array at each node is 0th-order entropy compressed, the resulting cumulative space usage of the Wavelet Tree is equal to $n$ times the 0th-order entropy-compressed size of the input text, again regardless of the shape of the tree [16, 11].

The Wavelet Tree pictured in Figure 1 is a balanced binary tree, in which the number of symbols at each internal node are partitioned as evenly as possible for the level below. As such it has at most $\log \sigma$ levels, and each level (in raw uncompressed form) consists of a bit array of length $n$. Using RRR [31] to encode each internal node allows fast rank and select queries for general alphabets on the overall tree.

For an internal node of $m$ bits with $\mathrm{\ell }$ 1-bits and $m-\mathrm{\ell }$ 0-bits, the RRR encoding [31] uses $\log \left(\genfrac{}{}{0pt}{}{m}{\mathrm{\ell }}\right)+o(\mathrm{\ell })+𝒪(\log \log m)$ bits, where $\log \left(\genfrac{}{}{0pt}{}{m}{\mathrm{\ell }}\right)$ is the information theoretic minimum. This form of entropy is called 0th-order finite-set entropy; it is always less than or equal to the empirical entropy of Definition 2, since it removes dependence from the statistical model. Summing the $\log \left(\genfrac{}{}{0pt}{}{m}{\mathrm{\ell }}\right)$ terms over all the internal nodes of the Wavelet Tree cascades into the multinomial coefficient $\left(\genfrac{}{}{0pt}{}{n}{n_1,n_2,\mathrm{\dots },n_{\sigma }}\right)$ [17], which is less than or equal $n$ times the 0th-order empirical entropy of the text $𝒯$.

There is much interesting work on efficient ways to construct Wavelet Trees. For example, Munro et al. [27] show that construction can be done in $𝒪\left(n(\log \sigma )/\sqrt{\log n}\right)$ time.

There are several variants of Wavelet Trees. In this section, we focus on Huffman Wavelet Trees, Pruned Wavelet Trees, and Wavelet Trees with multiway branching.

In [24, 28] the authors propose giving the Wavelet Tree the Huffman shape of the frequencies with which the symbols appear in the text string $𝒯$. It has been shown that the total number of bits stored in the Huffman Wavelet Tree is exactly the number of bits output by a Huffman compressor that takes the symbol frequencies in $𝒯$, which is upper-bounded by $n({\mathscr{H}}_0(𝒯)+1)$. Moreover, the accesses to the leaves in the Huffman Wavelet Tree can be obtained with frequency proportional to their number of occurrences in $T$. Huffman shapes can be combined with multiway Wavelet Trees and entropy compression of the bitmaps [1]. In this case, one can achieve space $n{\mathscr{H}}_0(𝒯)+o(n)$ bits, worst-case time $𝒪(1+(\log \sigma )/\log \log n)$, and average case time $𝒪(1+{\mathscr{H}}_0(𝒯)/\log \log n)$ for both rank and select queries.

Ferragina, Giancarlo, and Manzini [11] addressed the impact of the Wavelet Tree data structure on data compression by providing a theoretical analysis of a wide class of compression algorithms based upon Wavelet Trees, and proposing a novel framework, called pruned Wavelet Trees, that aims for the best combination of Wavelet Trees of properly-designed shapes and compressors either binary (like, run-length encoders) or non-binary (like, Huffman and arithmetic encoders). There were three main contributions in that paper.

First, they proposed a thorough analysis of Wavelet Trees as stand-alone general-purpose compressor, by considering two specific cases (extending [13]) in which either the binary strings associated to their nodes are compressed via RLE (referred to as the Rle Wavelet Tree) or via Gap Encoding (referred to as the Ge Wavelet Tree). These analyses provided compression bounds that depended on the features of these prefix-free encoders and the 0th-order entropy of the input string. As a result, the authors were able to prove that Rle Wavelet Trees can achieve a compression bound in terms of the $k$th order empirical entropy, whereas Ge Wavelet Trees cannot. This result has been then strengthened in [25] where the authors showed that Rle can be replaced by the succinct dictionaries of [31].

Ferragina et al. [11] introduced the pruned Wavelet Trees that generalize and improve Wavelet Trees by working on (C.1) the shape (or topology) of the binary tree underlying their structure; and on (C.2) the assignment of alphabet symbols to the binary-tree leaves. The authors showed that it is possible to exhibit an infinite family of strings over an alphabet $\mathrm{\Sigma }$ for which changing the Wavelet Tree shape influences the coding cost by a factor $\mathrm{\Theta }(\log \sigma )$, and changing the assignment of symbols to leaves influences the coding cost by a factor $\mathrm{\Theta }(\sigma )$. Moreover, they showed that (C.3) Wavelet Trees commit to binary compressors, losing the potential advantage that might come from a mixed strategy in which only some strings are binary and the others are defined on an arbitrary alphabet (and can be compressed via general-purpose 0th-order compressors, such as arithmetic and Huffman coding). Again, that paper showed that it is possible to exhibit an infinite family of strings for which a mixed strategy yields a constant multiplicative factor improvement over standard Wavelet Trees.

It is exactly to address these questions that Ferragina et al. [11] introduced the pruned Wavelet Trees where only a subset of their nodes is binary, and then developed a combinatorial optimization strategy addressing (C1)–(C3) simultaneously. As a corollary, they specialized that strategy to design a polynomial-time algorithm for finding the optimal pruned Wavelet Tree of fixed shape and assignment of alphabet symbols to its leaves; or, for selecting the optimal tree shape when only the assignment of symbols to the leaves of the tree is fixed.

Ferragina et al. [12] showed that increasing the branching factor in the wavelet tree nodes can reduce the time for rank and select queries to constant time, assuming that the alphabet size satisfies $\sigma =𝒪(polylogn)$.

In this section, we review some approaches for designing fast and compact implementations of Wavelet Trees. Grossi, Vitter, and Xu [18] provided a full generic package of Wavelet Trees for a wide range of options on the dimensions of coding schemes and tree shapes. Their experimental study reveals the practical performance of the various modifications. It provides potential users a rationale for how to implement a Wavelet Tree based upon the particular characteristics of the underlying datat.

The authors[18] considered three styles of Wavelet Trees:

• $\mathrm{■}$

  Normal: Each node is partitioned by alphabetically dividing the symbols represented in the node into two nearly equal-sized halves;

• $\mathrm{■}$

  Alphabetic weight-balanced: Each node is partitioned by alphabetically dividing the symbols represented in the node into two nearly equal-weighted halves, where the weights are designated by the frequencies of the symbols; and

• $\mathrm{■}$

  Huffman: Each node is partitioned as in Huffman compression.

They also considered several styles of encoding the conceptual bit array in each node, the main ones being

• $\mathrm{■}$

  None: The raw bit array is used at each node; support for member, rank, and select queries is provided by $o(n)$-space auxiliary structures using superblocks and lookup-table based popcount operations [15];

• $\mathrm{■}$

  RRR: The practical implementation of the RRR method [31] given in [6];

• $\mathrm{■}$

  RLE+$\gamma$: Run-length encoding with Elias $\gamma$ encoding [8] for the runs; queries are supported using the $o(n)$-space auxiliary structures [15];

• $\mathrm{■}$

  RLE+$\delta$: Same as RLE+$\gamma$, but using Elias $\delta$ encoding [8] instead of $\gamma$;

• $\mathrm{■}$

  SC: Small-integer $t$-subset encoding [22];

• $\mathrm{■}$

  AC: Arithmetic coding [19]; and

• $\mathrm{■}$

  LP/$\ast$: Bit arrays are compressed by a specified method iff there are at most three distinct symbols represented in the node, since nodes close to the leaf level are typically highly compressible.

The overall results of experiments on 33 Wavelet Tree options on texts from English, Protein, and Genome sources (several with very low entropy) suggest that RLE-encoded Wavelet Trees are the best in space efficiency when coding BWTs or sequences with very low 0th-order entropy, but are slower in query performance. RLE+$\delta$ is especially space-efficient for low-entropy sequences. AAWT and Huffman-shaped Wavelet Trees have similar performance, with the latter more space efficient for low-entropy sequences. When used with RRR encoding, both offer good all-around space and query time performance. AAWT+None is generally the fastest in all the experiments for queries and construction time.

Many existing implementations construct the Wavelet Matrix [7], which is an alternative representation for the Wavelet Tree, dropping its structure and thus achieving faster performance in practice. It is especially effective for large alphabets.

At the first level of the Wavelet Matrix, the most significant bits (MSBs) of the symbols are stored, analogous to the first level of the Wavelet Tree. Then, to construct the next level $\mathrm{\ell }$, starting with the second, the text is stably sorted using the $(\mathrm{\ell }-1)$th MSB as key. Just as with the Wavelet Tree, the symbols are represented using their $\mathrm{\ell }$th MSB on each level $\mathrm{\ell }$. However, the order of the symbols on each level is given by the stably sorted text. This removes the tree structure of the Wavelet Tree. However, the same intervals as in the Wavelet Tree occur on each level, just in a bit-reversal permutation order ¹¹1See https://oeis.org/A030109, last accessed 2025-02-24.. The number of 0s in each level is stored in an array. This information is needed to answer queries using one less binary rank and/or select query per level compared to Wavelet Trees. In the following, we use Wavelet Tree to refer to both Wavelet Tree and Wavelet Matrix, and refer the interested reader to [7] for more details.