How Huffman's code shortens predictable data: short words for common blocks, why a fair coin does not compress, and why no code goes below the entropy.
Step 1 of 5 · Short words for what is common
Step 1 of 5
Short words for what is common
On the upper tape every flip takes one bit, even when the coin is very predictable. Compression makes use of the predictability: it records the same flips in fewer bits, without losing any.
Measure and compress is at Compressed. The lower tape is the same flips, written in Huffman’s code: the code reads the flips in blocks, here in pairs, and gives each block a codeword. The commonest pair, heads-heads, gets a one-bit word, and the rare pairs get longer ones. The lines between the tapes join each block to its word.
Step 2 of 5
Nothing to bet on
Compression is a bet: it gives short words to what it expects to see often, and pays with long words for what is rare. The bet pays off when some blocks are likelier than others.
The coin is now fair, and the code reads blocks of four flips. Think about what will happen to the lower tape.
Step 3 of 5
Longer blocks
A block of one flip has only two outcomes, and a codeword cannot be shorter than one bit. So a code that reads one flip at a time saves nothing, however biased the coin. The longer the block, the more different blocks there are, and the more their probabilities differ: the code has something to work with.
Step 4 of 5
No word starts another
The lower tape has no gaps between words, and still it can be read back. The secret: no codeword is the start of another. If 0 is a word, no other word starts with 0, so when the reader sees 0 it knows the word has ended.
That rule has a price. A one-bit word “uses up” half of all possible words, and all the other blocks must fit into the other half.
Step 5 of 5
The limit
Shannon proved that the entropy is not just an average: it is the fewest bits per flip that any code can spend on average without losing information. Huffman’s code on blocks of flips always lands between and . In blocks of six flips, as now, it is already at the limit.
Watch the count under the lower tape. Over a short stretch it can come out a little above the limit or a little below it, because a lucky run of heads is cheap to write. The limit holds on average, over long runs.
Loading the interactive version…
Loading the interactive version…
Each step sets up the Scene for you, and a control marked “fixed” stays put for that step.
Practice · Calculate
Chance of heads is 90% and Code block size is two flips. Huffman’s code gives each pair a codeword: heads-heads 0, heads-tails 10, tails-tails 110, tails-heads 111. The pairs’ probabilities are , , and , in the same order. How many bits does a pair cost, on average?
Practice · Calculate
Chance of heads is 90% and Code block size is two flips. Huffman’s code gives each pair a codeword: heads-heads 0, heads-tails 10, tails-tails 110, tails-heads 111. The pairs’ probabilities are , , and , in the same order. How many bits does a pair cost, on average?
Practice · Predict, then look
The coin is fair, and the code reads blocks of four flips. When you open the compressed tape, how many bits per flip will it cost?
Practice · Predict, then look
The coin is fair, and the code reads blocks of four flips. When you open the compressed tape, how many bits per flip will it cost?
Practice · Reach the target
Chance of heads is fixed at 90%. In blocks of one flip the code saves nothing: one bit per flip. Change Code block size until the code costs about bits per flip, then press Check.
Practice · Reach the target
Chance of heads is fixed at 90%. In blocks of one flip the code saves nothing: one bit per flip. Change Code block size until the code costs about bits per flip, then press Check.
Practice · Choose
In Huffman’s code for blocks of four flips of a 90% coin, the block four heads, the most common of all, gets a one-bit codeword. What does the block four tails, the rarest of all, get?
Practice · Choose
In Huffman’s code for blocks of four flips of a 90% coin, the block four heads, the most common of all, gets a one-bit codeword. What does the block four tails, the rarest of all, get?
Practice · Choose
A coin lands heads 90% of the time. Someone offers a clever code that records its flips, losing none, at bits per flip on average, over millions of flips. What do you make of it?
Practice · Choose
A coin lands heads 90% of the time. Someone offers a clever code that records its flips, losing none, at bits per flip on average, over millions of flips. What do you make of it?
Lesson complete. Every practice question here is done.