wavelet-matrix · shipping · also Wavelet matrices

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

  1. Francisco Claude and Gonzalo Navarro: The Wavelet Matrix, SPIRE 2012, section 4 (accessed 2026-11-17)
  2. Claude, Navarro and Ordonez: Efficient Compressed Wavelet Trees over Large Alphabets, arXiv:1405.1220, sections 4-6 (accessed 2026-11-17)
  3. Gonzalo Navarro: author corrections to The Wavelet Matrix: An Efficient Wavelet Tree for Large Alphabets, Algorithm 5 (accessed 2026-11-17)
  4. Hesela: constructed missing-offset example, executable scanning reference (CC0) (accessed 2026-11-17)
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.

JSON: /data/terms/wavelet-matrix.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Wavelet matrix. Hesela. 2026-11-17. https://hesela.dev/terms/wavelet-matrix/