Wavelet tree
A wavelet tree represents a symbol sequence through recursive alphabet partitions and routing bitmaps that support access, rank and select queries.
Structure: In the basic ordered binary form, each internal node splits its symbol range and stores one routing bit per symbol in its subsequence. Stable partitioning preserves relative order within each child; subsequences need not be stored explicitly. [1]
Queries: Access recovers a symbol, rank counts its occurrences in a prefix, and select locates an occurrence. Balanced trees take O(log sigma) steps for alphabet [0, sigma), assuming constant-time bitmap rank/select. Prefix endpoints and occurrence numbering must be stated. [2]
Space: For n symbols, the basic routing bitmaps use at most n * ceil(log2(sigma)) bits. Rank/select support and tree representation add space. Compressed bitmaps or Huffman shaping change this accounting; a tree alone does not ensure compression. [1]
Order: Ordered symbol partitions support range counting and quantiles. Ordinary Huffman shaping need not preserve numeric order, so those operations do not transfer unchanged. This is an exact sequence index, not a signal-processing wavelet transform. [1] [3]
Relations
- related
- RRR bitvector, Wavelet matrix, Rank/select, Huffman coding
Citations
- Gonzalo Navarro: Wavelet Trees for All, Journal of Discrete Algorithms 25 (2014), sections 1-4 and 6.2
- Francisco Claude and Gonzalo Navarro: The Wavelet Matrix, SPIRE 2012, sections 1-2
- Claude, Navarro and Ordonez: Efficient Compressed Wavelet Trees over Large Alphabets, arXiv:1405.1220, sections 2 and 6
Sources & caveats
- Primary-source synthesis of sequence indexing and space bounds, not a benchmark replication or a universal speed comparison.