THE FOLD / LOOT / THE JACKPOT / THE WAVELET TREE
THE WAVELET TREE
rank a symbol in O(log sigma) by halving the alphabet
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The wavelet tree stores a sequence over an alphabet so it can answer rank (how many times symbol c appears in the first i positions) and access (what symbol is at position i) in O(log σ) time — using near the sequence’s entropy in space. It recursively splits the alphabet in half: a bitvector marks whether each symbol went to the lower or upper half, and the two halves recurse. Rank becomes a walk down the tree counting bits. It is a cornerstone of compressed text indexing (FM-indexes, succinct data structures).
LIT verified live: over 200 random sequences, access(i) returns the true symbol and rankc(i) equals a brute prefix count for every position and symbol (window.__wavelet). FIG no framing; exact.
LIT verified live: over 200 random sequences, access(i) returns the true symbol and rankc(i) equals a brute prefix count for every position and symbol (window.__wavelet). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-jackpot — the big payout of succinct indexing: answer “how many of this symbol so far?” instantly, in tiny space. The wavelet tree is that index. AVAN (AI) built the instrument: the recursive alphabet split, the per-level bitvectors, the rank-by-bit-count walk, the access walk, and the brute cross-check.
Credit as content: Grossi, Gupta & Vitter (2003). The weave: David names the jackpot; I split the alphabet level by level and walk the bitvectors to count a symbol’s occurrences, confirming every rank and access matches a direct scan.
Credit as content: Grossi, Gupta & Vitter (2003). The weave: David names the jackpot; I split the alphabet level by level and walk the bitvectors to count a symbol’s occurrences, confirming every rank and access matches a direct scan.
3 ONE DIMENSION
At the root, each symbol becomes a bit: 0 if it is in the lower half of the alphabet, 1 if upper. The 0-symbols and 1-symbols each recurse into their own child — and rank walks down, counting bits, to tally any symbol.
4 TWO DIMENSIONS · INTERACTIVE
A sequence and its wavelet tree; query rank of a symbol at a position and compare against a brute count.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: rank and access via a tree of bitvectors.
AVAN’s addition (the inverse-companion): answer “how many c’s in the first i symbols?” in O(log σ) and near-entropy space by turning each symbol into a bit per level (lower/upper half) and recursing. The inverse of ‘scan the sequence to count a symbol’ is ‘walk a tree of bitvectors, counting bits.’ Magenta is the linear scan you avoid; green is the log-σ bit walk. Counting by halving the alphabet.
LIT Genuine wavelet tree (Grossi, Gupta & Vitter 2003). Verified live: over 200 random sequences, the recursive alphabet-splitting structure returns access(i) equal to the true symbol at i, and rank_c(i) equal to a brute prefix count of symbol c in the first i positions, for every position and symbol (window.__wavelet.access && .rank).
FIG No framing: the recursive alphabet split, the per-level bitvectors, the rank-by-bit-count walk, the access walk, and the brute cross-check run in-browser and agree exactly. The AVAN inverse is honest — turning each symbol into a bit per level (lower/upper half) and recursing answers rank in O(log sigma) and near-entropy space; magenta is the linear scan you avoid, green the log-sigma bit walk. Counting by halving the alphabet.
FIG No framing: the recursive alphabet split, the per-level bitvectors, the rank-by-bit-count walk, the access walk, and the brute cross-check run in-browser and agree exactly. The AVAN inverse is honest — turning each symbol into a bit per level (lower/upper half) and recursing answers rank in O(log sigma) and near-entropy space; magenta is the linear scan you avoid, green the log-sigma bit walk. Counting by halving the alphabet.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE JACKPOT · David Lee Wise (ROOT0), with AVAN