Chapter 9 · Greedy Technique
Huffman Codes
Frequent symbols deserve short codewords. Huffman's greedy rule: keep merging the two lightest trees. The finished tree gives every symbol a prefix-free codeword with the smallest possible average length.
predictions: 0 / 0
Up to 10 distinct symbols. In a table, write the space as _. In text mode a space is shown as ␣.
🤔 Predict:
the two lightest trees (removed from the queue)
new merged tree
codeword path
decoder position
leaf = symbol, circle = merged weight
Priority queue (next to leave on top)
Codewords
Results
Encode / decode a message
Tie-breaking changes the tree, not the average (practice instance)
How to read this
- The stage shows the forest inside the priority queue, lightest tree on the left. Rectangles are symbols (leaves) with their frequency; circles are merged trees with their total weight.
- Each step removes the two lightest trees (yellow) and joins them under a new root (red). The first one removed becomes the left child (edge 0), the second the right child (edge 1).
- A symbol's codeword is the list of edge labels on the path from the root down to its leaf. Because symbols only live in leaves, no codeword is the prefix of another — decoding never needs separators.
- Average bits per symbol = Σ frequency × codeword length. Compare it with a fixed-length code, which needs ⌈log₂ n⌉ bits for n symbols.
Try this
- Textbook table (A .35, B .1, C .2, D .2, _ .15): expect codewords A 11, B 100, C 00, D 01, _ 101; 2.25 bits per symbol vs 3 fixed, a 25% saving.
- Practice instance (A .1, B .1, C .2, D .2, E .4): build it with both tie-breaking rules. Both average 2.2 bits, but the codeword-length variance is 0.16 with “oldest first” and 1.36 with “newest first”. Which would a data link prefer?
- Type text with one very common letter (e.g.
AAAAAAAABC). How short does that letter's codeword get? - Give all symbols equal weight (e.g. 8 symbols of 0.125). Huffman should reproduce a fixed-length 3-bit code.
- Encode
DAD_CAB, then animate decoding: at each 1 or 0 the decoder moves right or left; at a leaf it prints the symbol and jumps back to the root.