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.
New to compression? Start here
Only patterns can be spent
A file gets smaller for one of three reasons. Something in it repeats, so the second copy can be a note saying where the first one was. Or some symbols are commoner than others, so the common ones can be given shorter codes and the rare ones longer. Those two keep every bit, and are called lossless. The third is to throw information away on purpose, which works only where something can be relied on not to miss it: an eye, an ear, or an application that never needed it.
The first two are spending a pattern, and a pattern can only be spent once. Compress an already compressed file and you usually get nothing, or a little worse, because the first pass took what was there. Not always: a different method can find structure the first one was not looking for, which is why some formats chain two. What is certain is the counting argument underneath, and it is about all inputs rather than about yours: no lossless method can shorten every possible input, because shortening some must lengthen others. The machines here are choosing which inputs to be good at.
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 the word carries a second restriction: Huffman’s code is optimal among codes that give each symbol a whole number of bits, which is the ceiling Arithmetic Coding on this site goes under.
| 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: Restriction (c) makes it necessary that the two least 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.
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| on the 5 symbols of "abracadabra", Huffman's 23 bits equals the best of every prefix code there is | yes | each prefix code is a set of lengths satisfying Kraft, so they can be enumerated; 5 symbols is inside the limit of 9 and none of them beats it |
| the codeword lengths satisfy Kraft's inequality with equality, at 1.000000 | yes | less than one would mean a codeword could be shortened; more would mean the code is not decodable at all |
| encoding those 11 characters and decoding the 23 bits back returns them exactly | yes | a prefix code needs no separators between codewords, so this only works if no codeword is a prefix of another |
| the two rarest symbols get codewords identical except in their final digit | yes | Huffman's own requirement, checked on the code that was built: "c" is 100 and "d" is 101 |
| it beats fixed width (23 bits against 33), and on the 99-to-1 text it spends 100 bits where entropy asks for 8.1 | yes | a whole number of bits per symbol is the restriction; drop it and arithmetic coding gets closer, which is why the page says optimal among prefix codes rather than optimal |
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.