Wavelet Tree

The recursive alphabet split

A wavelet tree is built from a sequence S of length n over an alphabet of size sigma, typically after the symbols are mapped to consecutive integers from 0 to sigma minus 1. The construction begins at the root with the full sequence and the full alphabet range. At each node, the alphabet range currently assigned to that node is split into a lower half and an upper half, usually as evenly as possible so the tree stays balanced. For every position in the node's sequence, the algorithm checks which half the symbol at that position belongs to and appends a 0 or 1 to a bitvector, in the same left-to-right order as the sequence itself. After the bitvector is built, the positions are partitioned by their bit value: all positions with a 0 are collected, preserving relative order, into the sequence that becomes the left child's input, and all positions with a 1 similarly form the right child's input. Crucially, this partition step does not need to be stored explicitly at query time, because the bitvector's rank operation can reconstruct the mapping between parent positions and child positions on demand. The left child then recurses on its half of the alphabet and its induced subsequence, and the right child does the same, until a node's alphabet range contains only a single symbol. That node is a leaf and needs no bitvector at all, since every position reaching it must already hold that one symbol. The recursion depth is bounded by the ceiling of the logarithm base two of sigma, because each level halves the alphabet range. Since every original position contributes exactly one bit at every level it passes through, and it passes through exactly one node per level, the total number of bits stored across all bitvectors in the tree is n times the tree height, which is order n log sigma. This is already close to the raw information content of an arbitrary sequence over that alphabet, and with entropy-aware bitvector encodings the space can shrink further toward the zero-order empirical entropy of S, which is typically much smaller than log sigma when symbol frequencies are skewed.

Succinct bitvectors: the engine underneath

The wavelet tree's guarantees rest entirely on the bitvectors at each node supporting rank and select efficiently, and this is where the word succinct earns its keep. A naive bitvector stored as a plain bit array can answer access, meaning read the bit at position i, in constant time, but computing rank, the count of 1-bits among the first i positions, would require scanning up to i bits, and select, finding the position of the k-th 1-bit, would be even slower. Succinct rank and select structures solve this by layering a small index on top of the raw bits: the classic approach divides the bitvector into blocks and superblocks, precomputing cumulative popcounts at block boundaries and using fast hardware popcount instructions, or small precomputed lookup tables, to finish the count within a block. The key achievement of these structures is that the auxiliary index occupies only order n over log n, or sometimes order n log log n over log n, bits on top of the n raw bits, which is asymptotically negligible compared to the bitvector itself, often described as taking o of n extra bits, essentially free space for constant-time queries. Select is handled either by an analogous auxiliary structure or, more commonly in practice, by binary searching over the rank index combined with local scanning, giving logarithmic or near-constant time depending on the variant used. Every single bitvector inside the wavelet tree, at every level of the recursion, is one of these rank and select supporting structures, not a plain array. This is the detail that is easy to overlook yet is the entire reason the wavelet tree works: without succinct support at each node, a rank query on the overall sequence would degrade to linear scanning at every level, destroying the logarithmic time bound the structure is designed to deliver. Because the per-level overhead is sublinear, the wavelet tree as a whole inherits both the near-entropy space bound and the fast query bound simultaneously, which is unusual among data structures that typically must trade one for the other.

Answering access, rank, and select

The three canonical queries a wavelet tree supports all follow the same recursive template of descending from the root to a leaf, using one rank or select operation on a bitvector at each level. Access, which asks what symbol sits at position i in the original sequence, starts at the root and reads the bit at position i in the root bitvector. If that bit is 0, the symbol belongs to the lower alphabet half, and the query recurses into the left child at the position given by rank of 0 up to i in the root bitvector, which tells us how many prior positions also went left, hence the corresponding position in the left child's sequence. If the bit is 1, the analogous rank of 1 computation gives the position in the right child. This repeats until a leaf is reached, and the leaf's associated symbol is the answer, after exactly height-many rank computations. Rank, which asks how many times symbol c occurs among the first i positions, follows the same downward path that c's alphabet range would take, but at each level it converts i into the corresponding position within the child's sequence using rank on the current node's bitvector, exactly as access does, while also tracking which branch to follow based on which half c falls into. When the leaf for c is reached, the transformed position value is itself the answer, since it represents exactly how many times the path bit pattern of c, and hence c, occurred in the prefix. Select, which asks for the position of the k-th occurrence of symbol c, works in the opposite direction: it starts at the leaf for c and walks upward toward the root, at each step using select on the parent bitvector to translate a position in the child's sequence back into a position in the parent's sequence, undoing the rank-based descent that access and rank perform. After height-many select operations, the position at the root is the answer. All three queries cost order log sigma rank or select operations, each themselves constant or near-constant time, so overall query time is order log sigma, independent of n.

Wavelet trees inside the FM-index for genome search

One of the most consequential applications of the wavelet tree is inside the FM-index, a compressed full-text index widely used in bioinformatics tools such as BWA and Bowtie for aligning short DNA reads against a reference genome. The FM-index is built around the Burrows-Wheeler transform, a reversible permutation of the text that tends to group similar contexts together, making the transformed string more compressible than the original. The core query the FM-index relies on is called backward search, and its inner loop repeatedly needs to count occurrences of a character within prefixes of the BWT string, an operation that is precisely the rank query a wavelet tree is built to answer. Storing the BWT string as a plain array would allow constant-time access but linear-time rank, which would make backward search far too slow for genome-scale texts containing billions of bases. Storing the BWT as a wavelet tree instead gives logarithmic-time rank for any of the alphabet symbols, and since DNA uses a tiny alphabet of four bases, adjusted by a handful of extra symbols for wildcards and sentinels, the effective query time is extremely fast in practice, often just two or three rank computations deep. Backward search extends a matched pattern one character at a time from its end, at each step using two rank queries on the wavelet-tree-encoded BWT to shrink an interval that represents all suffixes of the text beginning with the pattern matched so far. After processing the whole query pattern, the width of the final interval directly gives the number of occurrences of that pattern in the genome, answered without decompressing a single base of the original sequence. Locating the actual genomic positions of matches additionally uses select-like operations combined with a sampled suffix array, but the counting step alone, which is what most alignment tools use to quickly reject or confirm candidate matches, runs entirely on rank queries against the wavelet tree. Because the wavelet tree simultaneously compresses the BWT toward its entropy and supports these queries quickly, whole human-genome-scale indexes fit comfortably in a few gigabytes of memory rather than the tens of gigabytes a naive representation would need.

Construction, variants, and practical trade-offs

Building a wavelet tree naively, level by level with an explicit pass to partition symbols at each node, takes order n log sigma time and a similar amount of working space, which is adequate for many applications but can become a bottleneck for very large texts such as whole genomes or large text corpora. Faster construction algorithms exist that build all bitvectors of a given level in a single linear pass over the original sequence, using the fact that a symbol's path through the tree is fully determined by its bit representation, and some external-memory or parallel construction methods reduce peak memory further, which matters when the input itself is many gigabytes large. Balanced-alphabet wavelet trees, sometimes called wavelet trees with an explicit binary tree shape, split the alphabet range evenly at every node regardless of symbol frequency, which is simple and gives a height bound of exactly the ceiling of log base two of sigma. An alternative, the Huffman-shaped wavelet tree, instead builds the tree according to a Huffman code derived from symbol frequencies, so common symbols sit near the root with short codes and rare symbols sit deeper with longer codes; this shifts the space usage from order n log sigma bits toward the empirical zero-order entropy of the sequence, at the cost of losing the uniform log sigma bound on query time, since some queries become slower than others depending on symbol frequency. A further variant, the wavelet matrix, keeps a fixed number of levels equal to the bit-length of the alphabet but rearranges how positions are grouped at each level using a stable partition by bit value across the whole level rather than per node, which simplifies implementation, improves cache locality, and is often the preferred layout in modern succinct data structure libraries. Across all these variants, the underlying contract stays the same: replace the sequence with a tree of succinct rank and select bitvectors, and in exchange receive access, rank, and select all in roughly logarithmic time within space close to the sequence's own information content.

Frequently asked questions

Try it live

Everything above runs in your browser — open Wavelet Tree and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.