Huffman coding — where it appears
Named by 3 essays across 3 fields — each of them below, with the objects they name alongside it.
Also named here as prefix code — the same set of essays touches all of them, so they are one junction rather than several.
The bits a coder emits
A stream of 16,384 symbols with a zeroth-order entropy of 3.891 bits per symbol was coded by a Huffman coder into 3.937 and by an arithmetic coder into 3.898, and neither went under 3.891 because neither can. That floor is a third kind of limit, the first that is a property of a model rather than of a question, and the same stream has a different one under every model of it.
The optimal code that is beaten
Huffman's code is optimal, the proof is correct, and on a stream where one symbol arrives 99 times in a hundred it spends 1.030 bits per symbol against an arithmetic coder's 0.119. Both facts hold. The word "optimal" in the theorem has a precondition attached that almost nobody quotes with it, and everything interesting about coding lives on the other side of that precondition.
The fold that minimises the wrong thing
A fold charges per level and a survivor pays the cuts on its path, so the bill looks like a weighted external path length — and Huffman's construction minimises that quantity by proof. Built and measured on thirty-two uneven shards it does minimise it, 181,407 against a balanced tree's 200,000, and leaves more damage than the tree does.
Named alongside it
The objects these essays reach for when they reach for this one.
Prefix codeArithmetic codingBits per symbolEntropyOptimalityBlockingCost modelGuaranteeHeavy hitterInformation-theoretic boundKraft inequalityMeasured count