Canonical Huffman (RFC 1951)

A Huffman tree built bottom-up is not unique — swap any two siblings and you get an equally optimal tree with different codes. Real codecs (DEFLATE, JPEG, MP3) need a deterministic, compact way to ship the codebook. The answer is canonical Huffman, defined in RFC 1951 section 3.2.2.

The key idea

If the decoder knows just the bit-length of each symbol's code, it can reconstruct the exact code. That means a DEFLATE header only stores 4 bits per symbol (lengths 0–15), not the actual codes.

The three-step algorithm

1. bl_count[L] = number of symbols with code length L
2. next_code[L] = (next_code[L-1] + bl_count[L-1]) << 1
   (starting from next_code[1] = 0)
3. For each symbol sorted by (length, value): assign next_code[length], then increment.

Worked example (RFC 1951)

Symbols A..H with lengths 3,3,3,3,3,2,4,4 yield:

Notice the codes for length 3 start right after F's 00 → next length-3 code is (00 + 1) << 1 = 010. The pattern continues. Shorter codes always have smaller numerical value when zero-padded — that property makes decoding extremely fast (a single table lookup of N bits picks the symbol directly).

Why this matters

A naïve Huffman header would ship 256 entries × (variable code) = potentially hundreds of bytes just for the codebook. Canonical Huffman compresses the header itself by storing only lengths, then runs another tiny Huffman over the lengths (RFC 1951 §3.2.7). That's why gzip overhead is ~10 bytes, not ~1 KB.

Implementation walkthrough

The three steps from RFC 1951

1. Count how many codes have each length:
     for L in code_lengths: bl_count[L] += 1
2. Compute the starting code for each length:
     code = 0
     for L in 1..MAX_BITS:
         code = (code + bl_count[L-1]) << 1
         next_code[L] = code
3. Assign codes to symbols sorted by (length, symbol):
     for sym in sorted(symbols, key=(length, value)):
         code_table[sym] = next_code[length]
         next_code[length] += 1

The left shift << 1 in step 2 ensures shorter codes never become a prefix of longer codes — this preserves the prefix property automatically, just like a real Huffman tree would.

Common pitfall

If you forget step 2's left-shift, you'll get colliding codes between different lengths. The shift is what makes a length-3 code never collide with a length-4 code: every length-3 code, padded with a zero, lands strictly below every length-4 code.