Wavelet Matrix: Rank and Select Over Large Alphabets

A Wavelet Matrix is a compact, succinct data structure designed to efficiently store sequences over large alphabets while supporting core query operations: access, rank, and select. By breaking symbols down into their binary representations and storing them across a sequence of bitvectors, the Wavelet Matrix generalizes binary operations to arbitrary alphabet sizes. Unlike traditional Wavelet Trees, the Wavelet Matrix simplifies pointer-less navigation and enhances cache efficiency by reordering symbols using stable partitioning at each bit level.

What is a Wavelet Matrix?

A Wavelet Matrix represents a sequence \(S\) of length \(n\) composed of symbols from an alphabet \(\Sigma = [0, \sigma - 1]\). If each symbol is encoded using \(\ell = \lceil \log_2 \sigma \rceil\) bits, the Wavelet Matrix consists of \(\ell\) bitvectors \(B_0, B_1, \dots, B_{\ell - 1}\), each of length \(n\).

While a standard Wavelet Tree recursively divides the alphabet in a balanced tree structure, a Wavelet Matrix processes all elements globally level-by-level based on their binary representation from the Most Significant Bit (MSB) to the Least Significant Bit (LSB).

Construction Using Binary Representation

  1. Level 0 (MSB): The bitvector \(B_0\) contains the most significant bit of each character in the original sequence \(S\).
  2. Reordering: To construct the sequence for the next level, elements with a 0 at the current bit position are placed first (preserving their relative order), followed by all elements with a 1 (also preserving relative order).
  3. Subsequent Levels: The process repeats for levels \(1\) through \(\ell - 1\). At level \(k\), \(B_k\) stores the \(k\)-th most significant bit of the reordered sequence from level \(k-1\).
  4. Zero-Count Tracking: For each level \(k\), a single integer \(z_k\) is stored, representing the total number of 0 bits in \(B_k\). This acts as the boundary offset where 1 bits begin in the subsequent level.

Generalizing Rank and Select Operations

The primary power of the Wavelet Matrix is extending binary rank and select primitives—which count and locate bits in \(O(1)\) time using succinct bitvectors (such as Elias-Fano or Clark’s select structures)—to work over large alphabets in \(O(\log \sigma)\) time.

1. The Access Operation

access(S, i) retrieves the symbol \(S[i]\): - Start at index \(p_0 = i\). - At each level \(k\) from \(0\) to \(\ell - 1\): - Read bit \(b = B_k[p_k]\). - Append \(b\) to the reconstructed binary value of the character. - If \(b = 0\), the next index is \(p_{k+1} = \text{rank}_0(B_k, p_k) - 1\). - If \(b = 1\), the next index is \(p_{k+1} = z_k + \text{rank}_1(B_k, p_k) - 1\). - After \(\ell\) steps, the assembled bits form the original symbol.

2. The Rank Operation

rank_c(S, i) counts how many times symbol \(c\) appears in the prefix \(S[0 \dots i-1]\): - Let \(c_{\ell-1} \dots c_0\) be the binary representation of \(c\). - Start with range boundary \(p = i\). - For each level \(k\) from \(0\) to \(\ell - 1\): - If the \(k\)-th bit of \(c\) is 0, update \(p \leftarrow \text{rank}_0(B_k, p)\). - If the \(k\)-th bit of \(c\) is 1, update \(p \leftarrow z_k + \text{rank}_1(B_k, p)\). - After traversing all \(\ell\) levels, the final value of \(p\) minus the starting offset of symbol \(c\) at the bottom level yields the exact rank.

3. The Select Operation

select_c(S, j) returns the position of the \(j\)-th occurrence of symbol \(c\): - Find the starting position of character \(c\) in the implicitly sorted bottom level. The index at level \(\ell\) is \(p_\ell = \text{start\_pos}(c) + j\). - Trace the position upward from level \(\ell - 1\) down to level \(0\): - If the \(k\)-th bit of \(c\) is 0, calculate \(p_k = \text{select}_0(B_k, p_{k+1})\). - If the \(k\)-th bit of \(c\) is 1, calculate \(p_k = \text{select}_1(B_k, p_{k+1} - z_k)\). - The resulting index \(p_0\) corresponds to the index of the \(j\)-th occurrence of \(c\) in \(S\).

Advantages Over Standard Wavelet Trees