Wavelet Tree

Wavelet Tree is a succinct, hierarchical data structure in computation and algorithms that represents a sequence S[1 .. n] drawn from an alphabet Σ of size σ = |Σ| by recursively partitioning the alphabet into a balanced binary tree of bitvectors. Introduced by Roberto Grossi, Ankur Gupta, and Jeffrey Scott Vitter in 2003 for high-order entropy-compressed full-text indexing, the wavelet tree reduces symbol lookup, prefix counting (rank), occurrence location (select), and two-dimensional orthogonal range queries over an arbitrary alphabet Σ to O(log₂ σ) constant-time operations on binary bitvectors.

In classical information theory and computational complexity theory, storing an uncompressed string S ∈ Σⁿ requires n ⌈log₂ σ⌉ bits of memory, yet a plain packed array cannot answer how many times character c ∈ Σ occurs in a prefix S[1 .. i] without scanning O(i) positions. A wavelet tree occupies n log₂ σ + o(n log σ) bits—or n H₀(S) + o(n log σ) bits when compressed to the zero-order empirical Shannon entropy H₀(S)—while answering access, rank, and select in O(log σ) time, making it the foundational engine of the FM-index over the Burrows–Wheeler transform in large-scale text retrieval and bioinformatics read aligners.

Hierarchical Bisection of the Alphabet

Let S[1 .. n] be a string of length n over an ordered alphabet Σ = {1, 2, ..., σ}. A balanced wavelet tree T is a rooted binary tree with σ leaves (one leaf per symbol c ∈ Σ) and height ⌈log₂ σ⌉. Each internal node v of T is associated with a contiguous alphabet sub-interval Σ_v = [a, b] ⊆ [1, σ] and implicitly represents the subsequence S_v of S formed by retaining only those characters of S that belong to [a, b] in their original left-to-right relative order:

1. Root Initialization: At the root r, the alphabet interval is Σ_r = [1, σ] and the subsequence is the full string S_r = S[1 .. n] of length n_r = n.
2. Alphabet Midpoint Split: At any internal node v with interval [a, b] (a < b) and subsequence S_v[1 .. n_v], define the midpoint m = ⌊(a + b) / 2⌋, partitioning [a, b] into a left sub-alphabet Σ_left(v) = [a, m] and a right sub-alphabet Σ_right(v) = [m + 1, b].
3. Node Bitvector Construction: Node v stores a binary bitvector B_v[1 .. n_v] of length n_v rather than the characters of S_v themselves. For each position k ∈ {1, ..., n_v}:
   • B_v[k] = 0 if S_v[k] ∈ [a, m] (the character routes to the left child v₀), and
   • B_v[k] = 1 if S_v[k] ∈ [m + 1, b] (the character routes to the right child v₁).
4. Leaf Termination: All characters with B_v[k] = 0 form the subsequence S_left(v) in order, and all characters with B_v[k] = 1 form S_right(v). Recursion stops when a = b, where leaf c represents a unary string of symbol c and requires zero stored bits.

Succinct Bitvector Rank/Select Directories and Space Analysis

At each level ℓ ∈ {0, 1, ..., ⌈log₂ σ⌉ − 1} of the wavelet tree, every character S[i] of the original string belongs to one node v at depth ℓ, so the sum of bitvector lengths n_v across all nodes at level ℓ equals n. Across all ⌈log₂ σ⌉ levels, the raw bitvectors contain n ⌈log₂ σ⌉ bits in total—identical to the bit budget of an uncompressed packed string.

Each node bitvector B_v is augmented with Jacobson's (1989) and Clark's (1996) two-level directory structure, which precomputes cumulative popcounts in superblocks of size (log₂ n)² and blocks of size (log₂ n) / 2 using o(n_v) additional bits. This directory answers two fundamental bitvector queries in worst-case O(1) time using hardware POPCNT instructions:

• rank_b(B_v, i): Returns the number of bits equal to b ∈ {0, 1} in the prefix B_v[1 .. i]. Because every position holds either 0 or 1, rank₀(B_v, i) = i − rank₁(B_v, i).
• select_b(B_v, j): Returns the index i of the j-th occurrence of bit b ∈ {0, 1} in B_v.

By concatenating all bitvectors at each tree level into a single n-bit array of n × ⌈log₂ σ⌉ bits—known as the Wavelet Matrix (Claude, Navarro, & Ordóñez, 2015)—explicit tree pointers are eliminated, reducing pointer overhead from O(σ log n) bits to O(log σ · log n) bits.

Top-Down access(S, i) and rank_c(S, i)

1. Character Lookup access(S, i): To recover the character S[i] without storing S, begin at the root v ← r with position p ← i and alphabet range [a, b] ← [1, σ]. At each internal node v, inspect bit b_bit = B_v[p]:
   • If b_bit = 0, the character belongs to the left half [a, m], and its relative position inside the left child's subsequence is p ← rank₀(B_v, p). Set v ← left(v) and b ← m.
   • If b_bit = 1, the character belongs to the right half [m + 1, b], and its relative position inside the right child's subsequence is p ← rank₁(B_v, p). Set v ← right(v) and a ← m + 1.

After ⌈log₂ σ⌉ steps, a = b = S[i].

1. Prefix Symbol Counting rank_c(S, i): To count occurrences of target symbol c ∈ Σ in S[1 .. i], traverse top-down from the root v ← r with prefix length p ← i. At each node v, check which half of [a, b] contains c:
   • If c ≤ m, update p ← rank₀(B_v, p) and descend to left(v).
   • If c > m, update p ← rank₁(B_v, p) and descend to right(v).

When the traversal reaches the leaf for c, the remaining value of p is the count of c in S[1 .. i], computed in O(log σ) time.

Bottom-Up select_c(S, j)

To find the position i of the j-th occurrence of symbol c in S, start at the leaf corresponding to c with position p ← j and ascend upward to the root along parent pointers. If the current node u is the left child of its parent v, the p-th character of S_u corresponds to the p-th zero bit in B_v, so update p ← select₀(B_v, p). If u is the right child of v, update p ← select₁(B_v, p). Upon reaching the root r, p equals select_c(S, j) in O(log σ) time.

Range Quantiles (Range k-th Smallest Element) in O(log σ) Time

Beyond string indexing, Claude and Navarro (2008) and Gagie, Puglisi, and Turpin (2012) observed that a wavelet tree over an array A[1 .. n] answers the Range Quantile Query—finding the k-th smallest element in any subarray A[l .. r]—in O(log σ) time without sorting the subarray. Starting at the root with interval [l, r] and target rank k, let c₀ = rank₀(B_v, r) − rank₀(B_v, l − 1) be the number of elements in A[l .. r] that fall into the left alphabet half [a, m]:

• If k ≤ c₀, the k-th smallest element lies in [a, m]; descend to the left child with mapped range [l′, r′] = [rank₀(B_v, l − 1) + 1, rank₀(B_v, r)] and unchanged k.
• If k > c₀, the k-th smallest element lies in [m + 1, b]; descend to the right child with mapped range [l′, r′] = [rank₁(B_v, l − 1) + 1, rank₁(B_v, r)] and updated rank k′ ← k − c₀.

Similarly, viewing (i, A[i]) as a planar grid point, a wavelet tree counts the number of points inside any orthogonal rectangle [l, r] × [y₁, y₂] in O(log σ) time by summing rank intervals across the O(log σ) canonical tree nodes covering [y₁, y₂].

Compression via Huffman Topology and Bioinformatics FM-Indexing

When the binary tree topology is constructed using Huffman coding probabilities rather than balanced bisection, a symbol c of empirical probability p_c = n_c/n resides at depth ≈ log₂(1/p_c), compressing the total bitvector length to n(H₀(S) + 1) bits and reducing average access and rank latency to O(H₀(S)). Alternatively, keeping the balanced tree topology while encoding each node bitvector B_v with the Raman–Raman–Rao (RRR, 2002) succinct bitvector achieves n H₀(S) + o(n log σ) bits—and, when applied to the Burrows–Wheeler transform L = BWT(T) of a text T, automatically compresses the index to the k-th order empirical entropy n H_k(T) via the Ferragina–Manzini (FM-index) backward search equation alongside a sampled suffix array.

How does a wavelet tree achieve k-th order entropy compression n H_k(T) without partitioning the text into context blocks?

When a wavelet tree with RRR zero-order compressed bitvectors is built over the Burrows–Wheeler Transform string L = BWT(T), all occurrences of characters sharing the same length-k right context in T are grouped into contiguous intervals in L. The local 0/1 block encoding of RRR adapts to the skewed bit densities inside each contiguous context interval, achieving n H_k(T) + o(n log σ) space implicitly across all context orders k simultaneously.

Why is the Wavelet Matrix faster in practice than a pointer-based Wavelet Tree for large alphabets?

For large alphabets (such as 32-bit integers or Unicode vocabularies where σ ≈ 10⁶), a pointer-based wavelet tree allocates σ nodes and splits small bitvectors across scattered heap allocations, causing CPU translation lookaside buffer (TLB) misses and storing O(σ log n) bits of node metadata. The Wavelet Matrix merges all nodes at depth ℓ into one contiguous n-bit array and stores only a single integer z_ℓ (the total count of 0-bits at level ℓ) per level, requiring only ⌈log₂ σ⌉ integers of tree metadata regardless of alphabet size.

1. Grossi, R., Gupta, A., & Vitter, J. S. (2003). "High-order entropy-compressed text indexes." Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '03), 841–850. https://doi.org/10.5555/644108.644250
2. Ferragina, P., Giancarlo, R., Manzini, G., & Sciortino, M. (2005). "Boosting textual compression in optimal linear time." Journal of the ACM, 52(4), 688–713. https://doi.org/10.1145/1082036.1082043
3. Gagie, T., Puglisi, S. J., & Turpin, A. (2012). "Range quantile queries: Another virtue of wavelet trees." IEEE Transactions on Information Theory / SPIRE 2009, LNCS Vol. 5721, 1–6. https://doi.org/10.1007/978-3-642-03784-9_1
4. Navarro, G. (2014). "Wavelet trees for all." Journal of Discrete Algorithms, 25, 2–20. https://doi.org/10.1016/j.jda.2013.07.004
5. Claude, F., Navarro, G., & Ordóñez, A. (2015). "The wavelet matrix: An efficient wavelet tree for large alphabets." Information Systems, 47, 15–32. https://doi.org/10.1016/j.is.2014.06.002