Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 37 ยท Huffman and Arithmetic Coding

Huffman: Optimality, Canonical Codes and Limits

Why Huffman coding is optimal, how canonical Huffman codes store only code lengths (as in DEFLATE), brute-force verification on small sources, and why a 1-bit minimum motivates arithmetic coding.

Huffman coding is optimal, but "optimal" has a precise, limited meaning: shortest average length among codes that give each symbol its own whole-number-of-bits codeword. This lesson explains why the algorithm works, shows the canonical form used by real file formats, and exposes the one weakness that arithmetic coding was invented to fix.

Why Huffman is optimal

Here is the proof idea, in three observations about any optimal prefix code:

  1. Lengths follow probabilities. If p_i > p_j then l_i <= l_j; otherwise swapping the two codewords would lower the average.
  2. The tree is full. Every internal node has two children; a node with one child could be shortened.
  3. The two least likely symbols can be siblings at the deepest level. Some optimal code has them as siblings; you can swap leaves at that depth freely.

Merge those two symbols into one with their combined probability. The expected length of the merged problem is exactly p_a + p_b smaller than the original, a constant, so an optimal code for the smaller problem extends to an optimal code for the larger one. Repeating this is precisely the Huffman algorithm.

Verify against brute force

For tiny alphabets we can enumerate every set of lengths that satisfies Kraft and find the true minimum. Huffman must match it.

Python Huffman versus brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All five trials report equal values. The brute force checks every length vector up to 7 bits, so it would find any code better than Huffman's if one existed.

Canonical Huffman codes

Two Huffman trees can have the same lengths but different bit patterns. Since only the lengths matter for compression, we can pick one standard assignment, the canonical code, so a decoder can rebuild it from the lengths alone. This is how DEFLATE (ZIP, gzip, PNG) saves space on the table.

Rule: sort symbols by (length, symbol). The first symbol gets all zeros of its length. Each next symbol gets the previous codeword plus 1, shifted left when the length increases.

Python Canonical code from lengths alone

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A decoder that knows the lengths (a short list of numbers) reproduces exactly this table, so the compressed file stores n small integers instead of n variable-length codewords. Canonical codes also decode quickly with a few comparisons instead of a tree walk.

Limits of Huffman coding

Huffman coding allocates a whole number of bits to each symbol. That is the source of its limits.

Limit 1: at least one bit per symbol

Even a certain symbol must cost 1 bit. For a source with p = (0.99, 0.01) the entropy is only 0.081 bits per symbol, yet Huffman spends 1 bit, an overhead of more than 1100%.

Python The one-bit floor

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Block coding (merge symbols into pairs, triples...) reduces this, but the table doubles with every extra symbol per block. Arithmetic coding sidesteps this problem entirely (next lesson).

Limit 2: changing statistics

Huffman assumes known, fixed probabilities. For data whose statistics change from block to block, you either send a new table often or use an adaptive Huffman scheme that updates the tree as symbols arrive (the FGK and Vitter algorithms). Adaptive models are much more natural with arithmetic coding.

Limit 3: no context

Plain Huffman treats each symbol independently, so it cannot exploit memory such as "q is usually followed by u". Context models belong in front of the coder (PPM, context mixing).

Python Block coding helps, at a cost

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The per-symbol cost falls from 1.0 toward the entropy (not perfectly smoothly: it dips to 0.4702 at block size 6 and creeps back up slightly at 8, because rounding losses depend on the block probabilities), but the table size doubles with each extra symbol. At block size 8 there are already 256 entries for a binary source.

Because Huffman is so cheap and fast, it still appears in nearly every format as the final entropy coding stage (JPEG, PNG, DEFLATE, HTTP/2 header compression). Modern codecs often use asymmetric numeral systems (ANS), which reach arithmetic-coding efficiency at Huffman-like speed.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In an optimal prefix code, if p_i > p_j, how do the lengths compare?

    A more probable symbol should not have a longer codeword, or swapping would reduce the average.
  2. 2. What does a canonical Huffman code let a file store?

    The canonical assignment is a fixed function of the lengths, so only lengths must be transmitted.
  3. 3. Why is Huffman coding poor for a source with p = 0.999 for one symbol?

    The 1-bit minimum per symbol dominates when entropy is about 0.01 bits.
  4. 4. How can you push Huffman closer to the entropy for skewed sources?

    Blocks spread the rounding loss over several symbols, but the number of blocks grows exponentially.

Summary

  • Huffman is optimal among symbol-by-symbol prefix codes, shown by an exchange argument and induction on merging the two least likely symbols.
  • Canonical Huffman codes are rebuilt from lengths alone, which is how DEFLATE stores its tables.
  • Limits: at least 1 bit per symbol, fixed known probabilities, no context.
  • Block coding reduces the overhead but grows the table exponentially; arithmetic coding removes the whole-bit constraint.

Next: Arithmetic Coding