Huffman coding

Text is stored as bits. If common letters get short codes and rare letters get long ones, the text takes fewer bits. Huffman coding finds the best such codes with a short greedy method: keep joining the two rarest things. It is used inside zip files, PNG images and many other formats.

Codes of different lengths

A code gives each letter a string of bits. With 6 letters, 3 bits each is enough (2³ = 2 × 2 × 2 = 8 patterns). A text of 100 letters then takes 300 bits. But if the letter f makes up 45 of those 100 letters, giving it a 1-bit code saves 90 bits at once, even if rare letters need 4 bits.

The difficulty is reading the bits back. If f is 0 and a is 01, then 01 could be a, or f followed by some code that starts with 1. Morse code solves this with pauses between letters. A better way needs no pauses at all.

Prefix-free codes are trees

A code is prefix-free when no letter’s code is the start of another letter’s code. Then the reader always knows where a code ends: as soon as the bits read so far form a whole code, that is the letter, because no longer code starts the same way.

A prefix-free code is the same thing as a binary tree with the letters at the leaves. A letter’s code is its path from the top: 0 for each step to the left, 1 for each step to the right. No code can be the start of another, because a leaf has nothing below it. Reading bits is walking down the tree, as the figure’s “Decode” variant shows.

The number of bits for the whole text is the cost of the tree: for each letter, its count times its depth (the length of its code). Huffman’s method finds a tree with the smallest cost.

In a best tree, every inner node has two children. If one had a single child, that node could be removed and everything below it moved up one level: every code under it gets one bit shorter, and the code stays prefix-free.

Building the tree

David Huffman found the method in 1952, as a student. Start with one tree per letter, weighed by its count. Then repeat until one tree is left:

1. take out the two lightest trees;
2. join them under a new node whose weight is the sum of theirs;
3. put the new tree back.

The greedy choice is “join the two lightest”. A tree that is joined early ends up deep, so its letters get long codes. Joining the light ones first gives long codes only to rare letters.

A useful fact: every time two trees are joined, every letter inside them moves one level deeper, which adds the new node’s weight to the cost. So the cost of the final tree is the sum of the weights of all the joined nodes. In the figure, 14 + 25 + 30 + 55 + 100 = 224.

Why it is the best

The proof has the two parts from lesson 1: the first choice is safe, and what is left is the same kind of problem.

The choice is safe (an exchange). Let x and y be the two rarest letters. Take any best tree. Its deepest level has two leaves with the same parent, say a and b (every inner node has two children). Swap x with a. x is at least as rare as a, and a was at least as deep as x, so the rarer letter moved down and the more common one moved up. The cost changes by (count(a) − count(x)) × (depth(x) − depth(a)), a number that is not negative times one that is not positive, so the cost does not go up. Do the same with y and b. Now there is a best tree where x and y are children of the same node, at the bottom.

What is left is the same problem. Join x and y into one new letter z with count(z) = count(x) + count(y). Any tree for the smaller set of letters becomes a tree for the full set by hanging x and y under z, and that adds exactly count(x) + count(y) to the cost. The amount added is the same whatever the tree, so the best tree for the smaller set gives the best tree for the full set. Huffman’s method then solves the smaller set the same way, and induction (CORR-3) finishes the proof.

The code

import heapq

def huffman_bits(counts):
    # counts: letter -> count
    heap = list(counts.values())
    heapq.heapify(heap)
    total = 0
    while len(heap) > 1:
        # the two lightest
        a = heapq.heappop(heap)
        b = heapq.heappop(heap)
        # every letter under them
        total += a + b
        # moves one level down
        heapq.heappush(heap, a + b)
    return total

This returns only the cost. To get the codes themselves, the heap must hold the trees too, as entries (weight, n, tree). The number n is a counter that goes up by one for each entry: when two weights are equal, Python compares the counters and never has to compare two trees (HEAP-4 used the same idea). Then walk the final tree, adding 0 to the code when going left and 1 when going right.

With k different letters there are k − 1 joins, each costing O(log k) with a heap, so the build is O(k log k). If the counts arrive already sorted, two plain queues do it in O(k): joined trees are made in order of weight, so they can wait in a second queue, and the lightest tree is always at the front of one of the two queues.