Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 37 ยท Huffman and Arithmetic Coding

Huffman Coding

Learn Huffman coding: merge the two least likely symbols until one tree remains. Implement it with heapq, encode and decode text, and measure the average length against entropy.

In 1952 David Huffman, then a graduate student, found a simple greedy algorithm that produces the shortest possible prefix code for a known distribution. It is still used inside ZIP (DEFLATE), PNG, JPEG, MP3 and many other formats. This lesson builds it from scratch and shows each step.

The algorithm

Start with one leaf per symbol, weighted by its probability (or count). Repeat until one tree remains:

  1. Take the two nodes with the smallest weights.
  2. Create a parent whose weight is their sum, with these two as children.
  3. Put the parent back into the pool.

Finally, label every left edge 0 and every right edge 1; a symbol's codeword is the path from the root. Rare symbols get merged early, so they end up deep in the tree with long codewords. Common symbols join late and stay near the root.

flowchart TD
    R["1.00"] -- "0" --> A["a 0.4"]
    R -- "1" --> X["0.6"]
    X -- "0" --> B["b 0.3"]
    X -- "1" --> Y["0.3"]
    Y -- "0" --> C["c 0.15"]
    Y -- "1" --> Z["0.15"]
    Z -- "0" --> E["e 0.05"]
    Z -- "1" --> D["d 0.1"]

A Huffman tree for a 0.4, b 0.3, c 0.15, d 0.1, e 0.05. First e and d merge into 0.15, then that merges with c into 0.3, and so on.

Implementation with a heap

A min-heap gives the two smallest weights in logarithmic time. Because heap entries must be comparable, we add a running counter as a tie-breaker; otherwise Python would try to compare tree nodes when two weights are equal.

Python Huffman code from scratch

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 average length is 2.05 bits against an entropy of 2.0087, within about 2% of the limit. Compare it with the Shannon code from the last lesson: shorter, and provably the best a symbol code can do.

Encode and decode a message

A real use starts from the text itself: count characters, build the code, encode, decode, and compare sizes. The receiver needs the code table (or the counts) to decode, so a real file format stores it; here we just keep it in memory.

Python Compress a string with Huffman coding

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 Huffman length lands within a few percent of the entropy bound H * n, and it is far below the 8 bits per character of the raw text. The round trip prints True.

Properties worth knowing

  • Prefix-free and complete. The tree has two children at every internal node, so the Kraft sum is exactly 1.
  • Not unique. Ties can be broken in several ways, producing different codes with the same average length. A different tie counter order changes the bits but not the optimum.
  • Lengths in bits. The two least likely symbols always get the longest length (and the same length).
  • Average length satisfies H <= L < H + 1, like every optimal prefix code. In practice it is much closer than H + 1 unless some probability is very large.
Python Huffman satisfies Kraft with equality

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.

Counting merges is a neat way to get the lengths without building the tree explicitly. The Kraft sum is exactly 1: nothing is wasted.

The cost of the table

Huffman decoding needs the code (or the symbol counts). In a short message the table can eat the savings. DEFLATE solves this by sending only the code lengths and rebuilding a canonical Huffman code from them (see Optimality, Canonical Codes and Limits).

When the alphabet is large and the probabilities are almost uniform, Huffman gains little over fixed length. Its power shows when the distribution is skewed, like letters in English or opcodes in a program.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In each Huffman step, which nodes are merged?

    Merging the two least likely symbols first pushes them deepest, giving them the longest codewords.
  2. 2. Why does the Python implementation add a counter to each heap entry?

    When two weights are equal, the heap would compare the next tuple element; the unique counter prevents comparing symbols with tuples.
  3. 3. What is the Kraft sum of a Huffman code?

    Every internal node has two children, so the tree is full and the Kraft sum equals 1.
  4. 4. Which of these does Huffman coding guarantee?

    It is optimal among symbol-by-symbol prefix codes, but the code itself is not unique and can still exceed the entropy by up to one bit.

Summary

  • Huffman builds an optimal prefix code by repeatedly merging the two least likely nodes.
  • Use heapq with a tie-breaking counter; codewords are paths from the root.
  • Average length satisfies H <= L < H + 1 and is usually within a few percent of H.
  • The result is not unique, is complete (Kraft sum 1), and the decoder needs the code table.

Next: Optimality, Canonical Codes and Limits