Arithmetic Coding
Huffman gives every symbol a code of a whole number of bits, and that is its ceiling. A symbol that turns up nine times in ten carries about 0.15 bits of information, and Huffman has to spend one on it, because there is no code of a seventh of a bit. Arithmetic coding does not give symbols codes at all. It starts with the interval between zero and one and narrows it once per symbol, so the entire message ends as a single number, and naming that number can cost a fractional number of bits in effect. This page encodes, decodes, and prints both costs against the entropy that neither of them may go under.
New to why Huffman is not optimal? Start here
Huffman gives every symbol a code of a whole number of bits, and that is its ceiling. If a symbol turns up nine times in ten, the information it carries is about 0.15 bits, and Huffman has to spend one -- nearly seven times what the symbol is worth. There is no code of half a bit.
Arithmetic coding does not give symbols codes at all. It takes an interval between zero and one and narrows it once per symbol, so the entire message ends up as a single number, and the number of bits needed to name that number can be fractional in effect. This page encodes, decodes, and prints the cost of each next to the floor neither may go under.
Only patterns can be spent
A file gets smaller for one of two 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.
Both are spending a pattern, and a pattern can only be spent once. Compress a compressed file and nothing happens, because the first pass already took what was there. That is also why nothing compresses everything: shortening some inputs must lengthen others, and the machines here are choosing which inputs to be good at.
The machine for this idea on its own is Huffman, if you would rather press it than read about it.
Machines here that come first: Huffman.
The whole message becomes one number
1 The symbols counted, and the slice of the interval each one claims
A message, its symbols counted, and the slice of the interval each one claims. The slice is the symbol's frequency, which is the only thing either coder is told.
| symbol | count | share | ideal bits | Huffman bits |
|---|
2 One interval narrowed by every symbol in turn, until the message is a single number
One interval, narrowed by every symbol in turn. The numbers below are the actual bounds the encoder held, rescaled whenever its top and bottom agreed about a bit — which is the part Rissanen and Pasco added, and the reason this can be done in fixed precision at all.
| step | symbol | width | bits out |
|---|
3 That number read back symbol by symbol, and checked against what went in
Read back, symbol by symbol, from nothing but that number and the counts. This is the check that matters: a compressor that cannot decompress has proved nothing at all.
4 The cost, against Huffman and against the entropy neither of them may beat
And the three costs together. The entropy is a floor neither coder may go under; where Huffman is already sitting on it, arithmetic coding has nothing to win.
| message | entropy | Huffman | arithmetic |
|---|
| claim | held | measured |
|---|---|---|
| every message decodes back to exactly what went in, 4 of 4 | yes | a compressor that cannot decompress has proved nothing |
| no encoding goes under this model's entropy, which is the bound for THIS model | yes | skewed: 15 bits against 13.9; even: 66 bits against 64.0; english: 190 bits against 188.6; single: 2 bits against 0.0. An order-zero model treats every symbol as independent; a model that knows q is followed by u has a LOWER floor, which is how real compressors go under this one without contradicting it |
| on the skewed message Huffman spends 49 bits where the entropy is 13.9 | yes | it has no code shorter than one bit, so a symbol worth 0.063 bits still costs a whole one |
| and arithmetic coding spends 15 for the same message | yes | it never assigns a code to a symbol at all: the message is one number in an interval, and the interval narrows by a fraction each time |
| on an evenly-spread message the two are within a few bits of each other | yes | 64 against 66. Where every symbol's ideal length is already a whole number of bits, Huffman has nothing to lose and the gap closes |
| the model is not counted in either figure | yes | both encoders here are given the symbol counts for free. A real file has to carry them or build them adaptively, and that cost falls on both methods but not equally. Neither number on this page is a file size |
| the idea is older than 1976 and the year is not one person's | yes | Elias had it before 1963 and never published it, because it needed unbounded precision. Rissanen and Pasco independently made it finite in 1976. Witten, Neal and Cleary in 1987 are why anyone uses it |
What is real here, and what is not
The model is free here and is not free anywhere else
Both coders on this page are handed the symbol counts. A real file has to carry them, or build them adaptively as it goes, and that cost falls on both methods but not equally. None of the numbers here is a file size, and a comparison that ignored the model would be flattering whichever method needs a bigger one.
Where Huffman is optimal it is not beaten
On the evenly-spread message every symbol's ideal length is already a whole number of bits, Huffman lands exactly on the entropy, and arithmetic coding comes out two bits worse for the terminating flush. That is the honest result and the page prints it rather than choosing four messages that all favour one method.
1976 is two people, and the idea is older
Peter Elias had it before 1963 and never published it, because narrowing a real interval forever needs unbounded precision. Jorma Rissanen and Richard Pasco independently made it work in finite arithmetic in 1976, which is the renormalisation this page performs. Witten, Neal and Cleary's 1987 paper is why anyone uses it. Four parties, so a single name against a single year is wrong about all of them.
Thirty-two bits of precision, and that is a choice
The interval is held in 32-bit integers and rescaled when its ends agree. Too little precision and the range collapses and the coding fails; too much and nothing is gained. The page states the figure rather than leaving it an implementation detail, because it is the whole difference between Elias's version and a usable one.
The floor is this model's floor, not a floor
The entropy printed here is computed from the counts in the string above and nothing else, which makes it the bound for an order-zero model: one that treats every symbol as independent. No coder using THAT model may go under it, and neither of these does. Real compressors go far below it, and that is not a contradiction: they use a different model, one that knows q is followed by u, and a better model has a lower floor. The page said both things without saying which model each belonged to, and an outside review was right to call that a contradiction.
Sources
- Ian H. Witten, Radford M. Neal and John G. Cleary, Arithmetic Coding for Data Compression, CACM 30(6):520-540, June 1987 — the paper that made the method usable, and the source of the renormalisation scheme here.
- Huffman, on this site — the coder this one is measured against, and the reason the whole-bit ceiling matters.
- Logical Art, the studio this belongs to.