Compression Codes

Short codes for common symbols

An interactive lesson with 8 steps, about 7 minutes: you predict, drag and solve, with instant feedback on every answer. It runs in your browser and needs JavaScript.

What you’ll learn

• Variable-length prefix codes give short codes to common symbols.
• Decodable lengths satisfy Kraft: $\sum 2^{-\ell} \le 1$; the average can't beat the entropy.
• Huffman’s algorithm builds an optimal code; random data can’t be compressed.

Steps

1. Not every letter is equal
2. Prefix-free
3. Design the code
4. The saving
5. Huffman’s algorithm
6. Building a Huffman tree
7. Build a Huffman code
8. Compressing everything?