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

Compound operation — where it appears

A structure operation returning two quantities from one traversal, where a caller would otherwise perform two. The instance here returns a symbol’s rank and the count of every smaller symbol from one descent of a wavelet tree, at exactly the operation count of the rank alone.

Named by 4 essays across 4 fields — each of them below, with the objects they name alongside it.

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

Every child at once

A bidirectional extension counts the occurrences of every symbol smaller than the one being added, and this collection did it with one rank per symbol — 139.7 operations an extension on a twenty-six-letter alphabet. One walk down the tree gives the same number.

indexes · Symbol 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

The count that was already there

A bit vector's rank of one is the position minus its rank of zero. Every walk down a wavelet tree computes one of them at every level, and this collection asked for the other separately for years.

machine · Symbol a fixed-length code97,718 bits5.00 ranks · in orderthe best ordered tree77,890 bits3.98 ranks · in orderthe best tree of any shape76,789 bits3.92 ranks · unorderedσ 21 · the ordered tree is 1.43% above the unordered optimum16,384 characters of englishorder costs 1.43%

The tree the operation insists on

The compound walk means "everything that went left is smaller", which is true only if the leaves are in the alphabet's order. Huffman's tree is the smallest and its leaves are in frequency order, so the operation that makes a bidirectional search affordable costs the shape that makes an index small.

structures · Symbol 051015510152025symbols in the alphabetfactor saved, and per cent paidranks saved, as a factorbits paid, per cent8,192 characters · 2 errorsx14.0 for 0.04%

A factor of fourteen, for four per cent

The compound walk removes a factor of σ from every interval extension. It requires a tree whose leaves are in order, which costs between nothing and five per cent of the wavelet tree. Both numbers on one plate, and the trade is not close.

bounds · Symbol

Named alongside it

The objects these essays reach for when they reach for this one.

AlphabetIndex sizeWavelet treeRankAlphabetic codeBidirectional indexBit vectorHuffman codeSearch schemeTradeBackward searchCode length

All concepts