Huffman
Nearly everything in this studio is what somebody shipped. This is the rare thing that is provably the best, and the proof is short enough to run in your browser: there are only so many codes, and you can try all of them. What takes the page is the word provably, which carries four conditions and is false without them.
Counting, marrying, reading the codes off, and weighing the result
1 Count what the text actually contains
Huffman's method needs to know how often each symbol appears before it can build anything. That is the first restriction hiding inside the word optimal: the code is fitted to this text, and it is the best code for this text and no other.
| symbol | count | share |
|---|---|---|
| a | 5 | 45.5% |
| b | 2 | 18.2% |
| r | 2 | 18.2% |
| c | 1 | 9.1% |
| d | 1 | 9.1% |
2 Marry the two rarest and put the pair back
Take the two least frequent entries, whatever they are, and bind them together into one entry whose count is their sum. Put it back among the others and do it again. The paper's own words for what that binding means: the two codewords are required to be identical except in their final digits
. Nothing is ever taken apart again, so the tree grows upward from its leaves.
c1d1b2r2a5
5 entries waiting, rarest first.
3 Read the codes off the branches
Walk down from the top; each step left writes a 0 and each step right writes a 1. Every symbol is a leaf, so no codeword can be the beginning of another, which is what lets a decoder read a stream with no separators and no lengths. Whether left means 0 or 1 does not matter at all: swap them everywhere and you get a different codebook that costs exactly the same.
| symbol | codeword | bits | count |
|---|---|---|---|
| a | 0 | 1 | 5 |
| b | 110 | 3 | 2 |
| r | 111 | 3 | 2 |
| c | 100 | 3 | 1 |
| d | 101 | 3 | 1 |
Kraft sum exactly 1. An optimal prefix code spends its budget exactly.
4 Weigh it, against a fixed width and against the floor
Now the number that matters. Below is what the text costs in this code, what it would cost if every symbol got the same number of bits, and the floor that Shannon's entropy puts under any code that handles one symbol at a time. Huffman lands between the two, and where it lands is the whole story.
- this code
- 23 bits
- same width for all
- 33 bits, 3 each
- saved
- 30.3%
- the floor
- 22.4 bits
- over the floor by
- 0.051 bits per symbol
No prefix code with a whole number of bits per symbol can do better than this on this text.
Checked here, not asserted: every prefix code over these 5 symbols was enumerated and none was cheaper.
Why marrying the two rarest is the right move
The argument is short, and it runs backwards from the answer. In any code that cannot be improved, the two least frequent symbols must have the longest codewords, and those two lengths must be equal. If one were shorter you could swap it with a rarer symbol and spend less; if the longest codeword had no sibling you could drop its last digit for free and spend less again. Huffman states the first half of this as a consequence of his restrictions: probable messages have codes of equal length
.
So the two rarest end up as a pair of siblings at the bottom, whatever else happens. Once you know that, you can bind them together and forget they were ever separate: the pair behaves exactly like one symbol whose count is the sum. The problem is now smaller by one and has the same shape, and repeating it is the whole method.
What optimal is not
The paper's claim, in its own summary, is that the method yields the lowest possible average message length
, and it says immediately what that is measured over: a message ensemble with a finite number of members, and a given number of coding digits. Four conditions travel with the word and every one of them is a real limit.
It is optimal among prefix codes, where no codeword begins another. It is optimal with a whole number of bits per symbol. It is optimal for a distribution you already know. And it is optimal one symbol at a time.
The third and fourth are where the losses are, and they are not small. Press the 99 to 1 button above: the entropy floor is under a tenth of a bit per symbol, and Huffman is obliged to spend a whole one, because a bit is the smallest thing it can spend. Huffman is spending more than ten times what the floor asks. Arithmetic coding drops the whole-number restriction, lets a symbol cost a fraction of a bit, and gets close to that floor instead, so most of that gap is real and recoverable. No amount of cleverness inside Huffman's method would find it, because the loss is in the method's premise rather than in its execution.
What is real here, and what is not
The optimality is checked, not quoted
A prefix code is exactly a set of codeword lengths satisfying Kraft's inequality, so for a small alphabet every possible prefix code can be listed and compared. The page does that for the text you type whenever the alphabet is small enough, and says so under the readout. The test does it for over a thousand random distributions, and separately checks that the shortcut it uses to prune the search agrees with an unpruned enumeration. Above nine distinct symbols the page stops enumerating and says nothing rather than guessing.
The tree is not unique; the cost is
When two entries have the same count, which one you pick first is arbitrary, and different choices build genuinely different trees with different codeword lengths for individual symbols. The total never changes. The page breaks ties in a fixed, stated way so that what you see is reproducible, and the test builds the same distributions again under two other tie-breaking rules and requires the totals to match. If a codeword here differs from one in a textbook, that is why.
The codebook is not counted, and in real use it must be sent
Every figure on this page is the cost of the encoded text alone. A decoder cannot read a single bit of it without the codebook, so a real file has to carry that too, and for a short text the codebook can easily cost more than the compression saves. Real formats handle this in ways this page does not model: canonical Huffman transmits only the code lengths, DEFLATE Huffman-codes the code lengths themselves, and some formats agree a fixed table in advance and send nothing. Treat the percentage saved as the best case, not the outcome.
One character is one message, which is a choice
Huffman's ensemble is whatever you decide a message is, and this page decides a message is one character. That is the ordinary choice and it is also the fourth restriction: coding pairs of characters, or words, or the output of a model that predicts the next character, all beat coding characters one at a time on ordinary text. The floor shown here is the floor for this choice of message, not the floor for the text.
Why there is no number here comparing this with Morse
Morse is the obvious neighbour, and that page declines to compare the two, correctly. Morse could not invent his codewords: he was assigning fixed patterns of dots and dashes, and the question he faced was which existing pattern to give which letter. Huffman is allowed to invent the codewords, which is a different problem with a different answer. Putting a percentage on the gap would be measuring two things that are not the same size, so this page does not.
A single distinct symbol costs one bit each, not none
Type a text with only one character in it and the page charges a bit per symbol. Information-theoretically a stream of a known constant carries nothing and should cost nothing, but a zero-length codeword cannot be distinguished from the absence of a codeword, and Huffman's restrictions assume at least two messages. The page takes the honest reading of that boundary rather than printing a free lunch.
Sources
- D. A. Huffman, A Method for the Construction of Minimum-Redundancy Codes, Proceedings of the I.R.E. 40(9):1098–1101, September 1952. Four pages, and the method is one paragraph of them. The scan has no text layer, so the quotations on this page are matched against an OCR of it rather than against a transcript; where the OCR is imperfect the page quotes a fragment that came through clean instead of tidying one that did not.
- The same paper at IEEE Xplore, which is the citation of record. It sits behind an interstitial that an archiver cannot pass, which is why the copy above is the one this page checks itself against.
- Morse, on this site, for the problem Huffman is answering: a code whose codewords were already fixed, and the rearrangement question that leaves you with.
- Count Distinct, on this site, for the other machine here that is wrong by a known amount rather than right.