Skip to content
Tutorials Center
My learning

Topics

Lesson 169 of 225 ยท Greedy Algorithms

Huffman Coding

Learn Huffman coding in Python: prefix-free codes, building the tree with a heap, encoding and decoding text, compression ratios and why the greedy is optimal.

Every character in a plain text file normally takes the same space: 8 bits in ASCII. But letters are not equally common. In English text e appears constantly and z almost never. It seems wasteful to spend the same number of bits on both. What if frequent characters got short codes and rare characters got long ones?

That is the idea behind Huffman coding, invented by David Huffman in 1952 and still used inside formats such as ZIP/DEFLATE, gzip, PNG and JPEG. It is a perfect small greedy algorithm: repeatedly merge the two least frequent symbols, and the result is the shortest possible code among all codes that assign each symbol its own bit string with no code being the start of another. In this lesson you will build it from scratch with a heap, encode and decode text, and measure the compression.

Variable-length codes need a prefix-free rule

Suppose we give a the code 0, b the code 01 and c the code 1. The bit string 01 could be b, or a followed by c. Decoding is ambiguous. The fix is a prefix-free code (also called a prefix code): no code is a prefix of another code. Then you can read bits from the left and the moment they match a code, that symbol is certain.

The neat way to guarantee this is a binary tree where symbols live only at the leaves. A code is the path from the root: 0 for left, 1 for right.

TEXT
              (root)
             0/    \1
           (a)      ( )
                  0/   \1
                (b)     ( )
                      0/   \1
                    (c)     (d)

a = 0     b = 10     c = 110     d = 111

Because symbols sit at leaves, no path to one leaf can pass through another leaf, so no code can be a prefix of another. The cost of a code is the total number of bits used:

TEXT
total bits = sum over symbols of  (frequency of the symbol) x (length of its code)

So we want a tree where frequent symbols are close to the root (short paths). Huffman's algorithm finds the best such tree.

The algorithm in plain words

  1. Count how often each symbol occurs.
  2. Make a leaf node for each symbol, weighted by its frequency, and put all of them in a min-heap ordered by weight.
  3. While the heap holds more than one node: pop the two lightest nodes, create a new parent whose weight is the sum, give it those two as children, and push it back.
  4. The last node is the root. Read the codes off the tree (left = 0, right = 1).

Why the two lightest? They will end up deepest in the tree, with the longest codes, and we want the longest codes to cost as little as possible. Each merge also adds its weight to the total cost once for every bit it adds to the codes below it, so merging small weights first keeps that cost low.

Let us trace the text abracadabra: a appears 5 times, b twice, r twice, c once, d once.

TEXT
start:   c:1  d:1  b:2  r:2  a:5

merge c+d      -> (cd):2         heap: b:2  r:2  (cd):2  a:5
merge b+r      -> (br):4         heap: (cd):2  (br):4  a:5     (ties: any order is fine)
merge (cd)+(br)-> (cdbr):6       heap: a:5  (cdbr):6
merge a+(cdbr) -> root:11

Frequent a ends up one step from the root, and the rarest letters are deepest.

Python Build the Huffman tree and print the codes

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 (weight, counter, node) tuples in the heap matter. If two weights tie, Python would compare the next tuple items, and a Node has no ordering. The unique counter settles ties and also makes the result deterministic. Different tie-breaking yields a different tree, but always one with the same total cost.

Encoding and decoding

Encoding is a table lookup: replace each character by its code and concatenate. Decoding walks the tree: start at the root, move left on 0 and right on 1, and each time you land on a leaf, output its symbol and jump back to the root.

Python Encode, decode and check the round trip

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 prefix-free property means the decoder never needs separators between codes: the tree itself tells it where each symbol ends.

A real compressor must also store the tree (or just the symbol frequencies, or a canonical list of code lengths) in the file, otherwise the receiver cannot decode. For tiny inputs that header can be bigger than the saving. Huffman only pays off on larger inputs with uneven frequencies.

Measuring the compression

How good is it? Two yardsticks help.

  • Fixed-length code: with k distinct symbols you need at least ceil(log2 k) bits each (3 bits for 5 symbols).
  • Entropy: the theoretical lower bound for coding each symbol independently is -sum(p * log2 p) bits per symbol on average, where p is a symbol's probability. Huffman is always within 1 bit per symbol of entropy, and it matches entropy exactly when every probability is a power of 1/2.
Python Compression ratio and entropy

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.

Look at the uniform row: all eight symbols are equally likely, so Huffman gives each a 3-bit code, exactly the fixed-length cost. Compression comes from uneven frequencies; the skewed row shows the biggest saving. And the Huffman total is never below the entropy figure, but it stays within one bit per symbol of it.

Why the greedy choice is optimal

The exchange argument (the proof technique from Greedy Algorithms) goes like this:

  1. In an optimal tree, the two least frequent symbols can be placed as siblings at the deepest level. If a rarer symbol were shallower than a more frequent one, swapping them would shrink the total cost, a contradiction.
  2. So merging those two into one combined symbol (whose weight is the sum) is a safe first step, and the remaining problem is a smaller instance of the same problem with one fewer symbol.
  3. Induct: the best tree for the smaller problem, with the merged leaf expanded back into two children, is a best tree for the original.

That gives both required properties: the greedy choice property and optimal substructure. Huffman's code is optimal among all prefix codes that code symbols one at a time. (Other methods, such as arithmetic coding or methods that code pairs of symbols, can do better than the one-symbol-at-a-time limit.)

Complexity

With n the length of the text and k the number of distinct symbols:

Step Time Space
Count frequencies O(n) O(k)
Build the tree (k - 1 merges, each with heap operations) O(k log k) O(k)
Make the code table O(k) O(k)
Encode O(n) in the output length O(n) bits
Decode O(output length) O(1) beyond the tree

For text, k is small (at most a few hundred bytes or characters), so the run time is dominated by the linear passes over the data. If the frequencies are already sorted you can build the tree in O(k) using two queues instead of a heap.

Common mistakes

  • Comparing nodes in the heap. Tied weights make Python compare Node objects and raise TypeError. Add a counter (as above) or define ordering on the node.
  • Forgetting the one-symbol case. A text such as "aaaa" gives a tree with a single leaf and an empty code. Assign a 1-bit code like "0" explicitly.
  • Making symbols internal nodes. If a symbol is not at a leaf, its code is a prefix of other codes and decoding breaks.
  • Expecting a unique answer. Ties produce different but equally good trees; the code lengths may even differ between valid trees, but the total cost is the same.
  • Ignoring the header. A real format must transmit the tree or frequencies.
  • Treating a string of "0" and "1" characters as compressed. In Python each of those characters is a whole character, not one bit. A real compressor packs the bits into bytes.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does it mean for a code to be prefix-free?

    Then a decoder can stop at the first match, since a shorter code can never hide inside a longer one.
  2. 2. Which two nodes does Huffman's algorithm merge at each step?

    Merging the smallest weights first pushes the rarest symbols deepest, where long codes cost the least.
  3. 3. For abracadabra, frequencies are a:5, b:2, r:2, c:1, d:1. How many merges build the tree?

    k distinct symbols need k - 1 merges to reduce k nodes to one, so 5 - 1 = 4.
  4. 4. When does Huffman coding give no saving over a fixed-length code?

    Uniform frequencies mean every symbol gets the same code length, equal to the fixed-length cost.
  5. 5. Why do heap entries include a unique counter?

    When two weights are equal, tuple comparison moves on to the next field. The counter is always unique and orderable.

Summary

  • Huffman coding gives frequent symbols short bit strings and rare symbols long ones, with all symbols at the leaves of a binary tree so the code is prefix-free.
  • Build: heap of leaves, repeatedly merge the two lightest nodes; k symbols need k - 1 merges and O(k log k) time.
  • Encode by table lookup; decode by walking the tree from the root, bit by bit.
  • Compression comes from uneven frequencies; with uniform frequencies there is no gain, and the result is never better than the entropy bound for independent symbols.
  • Optimal among prefix codes that code one symbol at a time, by an exchange argument (the two rarest symbols are deepest siblings).
  • Watch the single-symbol case, heap tie-breaking and the cost of storing the tree.

Next: Greedy Problems