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

Alphabetic code — where it appears

A prefix code whose code words are in the same order as the symbols they stand for, so the tree’s leaves run left to right in the alphabet’s order. That constraint costs a few per cent against Huffman on real text, and it is what lets a descent count the symbols it passed as smaller ones.

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

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.

AlphabetCompound operationHuffman codeIndex sizeTradeWavelet treeBidirectional indexCode lengthConstant factorDynamic programmingEntropyRank

All concepts