Huffman Codes Lab

The idea before the name

A binary code is a dictionary from symbols to bits. For example, a code might say A = 0, B = 10, and N = 11.

The trick is that code lengths are allowed to differ. A letter that appears 6 times pays for its code 6 times, so saving one bit on that letter matters 6 times.

A Huffman code is the code you get from a specific greedy recipe: keep joining the two least common symbols, then read 0s and 1s from the tree. The result gives common symbols short codes while staying decodable.

What you will build

1. 1
   Count the letters that actually appear, because missing letters cost nothing.
2. 2
   Merge the two smallest piles so rare letters get pushed farther away.
3. 3
   Read each root-to-letter path as a bit code: left is 0, right is 1.
4. 4
   Test that the final bitstream can be decoded without spaces or separators.