Wavelet matrix
A wavelet matrix represents a symbol sequence with levelwise bitmaps and stable zero-before-one partitions, supporting access, rank and select without explicit tree nodes.
Layout: The basic binary matrix processes symbol bits from most to least significant. At each level it stably partitions the entire sequence for that level into zero-bit and one-bit groups, rather than partitioning each tree node separately. A zero count is stored per level. [1]
Navigation: For zero-based position i, let rank_b(i) count bit b strictly before i and z be the level's total zero count. A zero maps to rank_0(i); a one maps to z + rank_1(i). For bitmap 10, position 0 maps to 1; omitting z sends it to 0. [4] The author's Algorithm 5 erratum restores this offset. [3] These conventions translate the paper's one-based, inclusive formulas. [1]
Space: For n symbols in [0, sigma), the basic full-height bitmaps occupy n * ceil(log2(sigma)) bits, before rank/select support, level zero counts and other metadata. Avoiding node pointers does not remove all overhead or automatically compress the sequence. [1]
Trade-offs: In the basic fixed-height form, access, rank and select take O(log sigma) steps with constant-time bitmap operations. Compressed and Huffman-shaped variants change the space/time trade-off; published timing comparisons depend on datasets, query mix and bitmap implementation. [2]
Relations
- related
- RRR bitvector, Wavelet tree, Rank/select, Huffman coding
Citations
- Francisco Claude and Gonzalo Navarro: The Wavelet Matrix, SPIRE 2012, section 4
- Claude, Navarro and Ordonez: Efficient Compressed Wavelet Trees over Large Alphabets, arXiv:1405.1220, sections 4-6
- Gonzalo Navarro: author corrections to The Wavelet Matrix: An Efficient Wavelet Tree for Large Alphabets, Algorithm 5
- Hesela: constructed missing-offset example, executable scanning reference (CC0)
Sources & caveats
- Navigation uses the original paper's section 4 prose translated to zero-based positions and exclusive-prefix rank.
- Primary-source synthesis of the basic binary structure and its variants; no native implementation benchmark or measured storage saving is claimed.
- The author-published correction is linked, not claimed as a new Hesela discovery. Our constructed [2,1] fixture decodes as [3,1] when the offset is deliberately omitted; it is not a native implementation benchmark.