About this experiment
Every ZIP file, PNG image and MP3 track is smaller than the raw data because it removes repetition. Try two classic lossless methods on your own message. Run-length encoding replaces a run of identical symbols with a count, which is excellent for simple images and useless for ordinary text. Huffman coding gives common symbols short codes and rare ones long codes, built step by step from a tree, and gets within one bit per symbol of the theoretical limit Claude Shannon found in 1948.
Learning goals
- Explain the difference between lossless and lossy compression
- Encode and decode a message with run-length encoding and say when it helps
- Build a Huffman tree by repeatedly joining the two least frequent symbols
- Read code words from the tree and explain why no code is the start of another
- Compare compressed sizes with the entropy limit and calculate a compression ratio
How to use it
- 1Choose Pixel row and Run-length. How many bits does the row need before and after? Why does it work so well?
- 2Switch to Hamlet with Run-length. Why does the message get bigger?
- 3Choose Mississippi and press Build the tree. At each step, which two trees are joined and why?
- 4When the tree is finished, find the code word of the most common letter and of the rarest one. Count the bits.
- 5Decode the first few bits of the encoded message by hand by walking down the tree from the root.
- 6Type a message that uses only one letter, then one where every letter is different. Compare Huffman with the entropy limit in both cases.
The model
Assumptions
- Original size counts UTF-8 bytes. ASCII characters use one byte; other symbols may use several. Huffman coding treats each Unicode code point as one symbol.
- Each run-length pair stores an 8-bit count followed by the UTF-8 bytes of its symbol. Runs longer than 255 are split. Framing and code-table storage are excluded from the payload comparison.
- The Huffman size counts only the encoded message. A real file also has to store the code table or the counts, which matters for short messages.
- When two trees have the same weight, the one created first is taken first, and the lighter tree becomes the 0 branch. Other tie rules give different codes of the same total length.
Try this in class
- Q1Encode BBBBBWWWBBBBBBBB with run-length encoding. How many bytes does it need?
- Q2Build the Huffman tree for the counts A 5, B 2, R 2, C 1, D 1 and find the total number of bits for ABRACADABRA.
- Q3Why must a Huffman code be a prefix code? What would go wrong if A were 0 and B were 01?
- Q4A text uses 8 different letters equally often. What is its entropy, and can Huffman compress it?
- Q5JPEG and MP3 compress much more than Huffman coding. What do they give up to do so?
Frequently asked questions
Where is Huffman coding used today?
Inside many everyday formats: ZIP and gzip (the DEFLATE method), PNG images, JPEG images after the lossy step, and MP3 audio. It is usually the last stage, after another method has turned repetition into numbers.
Can any file be compressed?
No. A lossless method that made every file smaller would let you compress the result again and again, which is impossible because there are fewer short files than long ones. Random data and already compressed files usually do not get smaller.
Is the Huffman tree unique?
Not always. When counts are tied, different choices give different trees and different code words, but every Huffman tree for the same counts gives the same total number of bits.