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

Huffman code — where it appears

The prefix code of least expected length for a given symbol distribution, built by merging the two lightest weights repeatedly. Its tree is the smallest of any shape and its leaves come out in frequency order — which is no order at all when a comparison is what is wanted.

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

equal lengths5.00 bits100.0%lengths as one over rank4.15 bits83.4%a few long, many short4.31 bits86.7%one document holding most of the text1.69 bits39.5%log₂ 3232 documents · 8,192 characters100.0% to 39.5%

The array is the length distribution

The document array holds each document once per character it contributed, so its symbol distribution is the collection's length distribution exactly. On equal-length documents its entropy is log d and no coding saves anything.

text · Index 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 024bits a symbolequalzipftwoSizesoneLargeone bit a symbolentropyplain vectorscompressed blocks32 documents1.26x on the skewed collection

A code word is at least one bit

A wavelet tree of plain vectors reaches the entropy by its shape, and a Huffman code word cannot be shorter than one bit. On a collection whose document array has an entropy of 1.69 the tree costs 1.98, and the gap is a floor rather than an inefficiency.

bounds · Index bits heldbalanced49,593huffman41,589the answer comes backbalanced: sorted · 26 operationshuffman: sorted · 24 operations32 documents · zipf lengths83.9% of the ordered tree

The smaller tree hands it back unsorted

A frequency-shaped tree is sixteen per cent smaller and returns its documents in code order. A balanced one is larger and returns them sorted. The trade is d log d comparisons against a saving, which is not close — until the answer is truncated.

practice · Index a fixed-length codeleaves in order␣acdefghilmnoprstuvwythe best ordered treeleaves in order␣acdefghilmnoprstuvwythe best tree of any shapeleaves in frequency order␣eahnrstdiloucfgmpvwythe symbols, in the order the descent reports them21 symbols in 2,048 positionsone set, 2 of 3 sorted

One set, three orders

The symbols an interval holds do not depend on the tree's shape. The order they come out in does, and a search that accumulates a running count as it reads them computes a plausible number that is wrong on eighty per cent of queries.

wrong · Symbol

Named alongside it

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

Wavelet treeIndex sizeDocument arrayEntropyAlphabetAlphabetic codeBidirectional indexCompound operationCorrectnessDescentDocument listingOrdered code

All concepts