Algorithms & Data Structures
the bound is a claim, and it is checkable
Generator

A balanced wavelet tree over "abracadabra": 217 bits

Rendered here at the parameters it defaults to, with every essay that calls it — which is the same list as the blast radius of changing it.
A balanced wavelet tree over "abracadabra": 217 bitsEvery node is a bit vector: one bit per symbol still in play, saying which half of the remaining alphabet that symbol falls in. A rank for a symbol walks its code from the root, one bit-vector rank a level, and no symbol is ever compared with another. The whole structure is 33 bits of payload and 184 bits of directory and code table, over 11 characters and 5 distinct symbols.00100000010root000101000000101000100001010010one box = one bit · left child 0, right child 15 symbols, 217 bits

A balanced wavelet tree over "abracadabra": 217 bits

Every node is a bit vector: one bit per symbol still in play, saying which half of the remaining alphabet that symbol falls in. A rank for a symbol walks its code from the root, one bit-vector rank a level, and no symbol is ever compared with another. The whole structure is 33 bits of payload and 184 bits of directory and code table, over 11 characters and 5 distinct symbols.

Drawn at 700 × 244, wide on the page. Everything above is what wavelet-tree returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

6 essays call wavelet-tree. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.

Where it is called

Changing this generator changes every one of these figures.

0$abracadabra1a$abracadabr2abra$abracad3abracadabra$4acadabra$abr5adabra$abrac6bra$abracada7bracadabra$a8cadabra$abra9dabra$abraca10ra$abracadab11racadabra$aball 12 rotations of "abracadabra$", sorted0 character comparisons The index that replaces the text

A search that runs backwards

 balanced, bits49,2616.01 b/chHuffman-shaped, bits39,0614.77 b/chranks per access5.003.95entropy = 3.90 bitsEnglish-like, sigma = 22 · upper bar balanced, lower Huffman-shapedH0 = 3.90 bits/symbol What the machine does

Rank is the only thing it does

 1,00010,00010³bits of select supportpositions inspected, worst casebinary search, no extra bits: 510L=8L=256L=8L=256one position per L onesdense and sparse6,554 ones in 65,536 positions · sub-blocks of 8worst cases, every k What the machine does

Select is not rank backwards

 patterns of 225%60 selectspatterns of 441%94 selectspatterns of 863%118 selectspatterns of 1682%117 selectsEnglish-like · 8 copies of 512share of steps needing no lookup40 patterns a row The index that replaces the text

The occurrence carried through the search

 level 0 · left335 keptlevel 1 · right+207 smallerlevel 2 · left61 keptlevel 3 · right+33 smallerlevel 4 · left8 keptpositions still in play, and the half the code leaves behindsmaller symbols before position 400: 240rank of "m": 8 — from the same 5 operationsσ 21 · code 010105 ranks, not 105 The index that replaces the text

Every child at once

 level 0 · left585 keptlevel 1 · right+351 smallerlevel 2 · right+113 smallerlevel 3 · right+39 smallerlevel 4 · right+40 smallerpositions still in play, and the half the code leaves behindsmaller symbols before position 700: 543rank of "s": 42 — from the same 5 operationsσ 21 · code 011115 ranks, not 105 What the machine does

The count that was already there

The library, page 5 of 5 — where wavelet-tree sits