Huffman compression

Cost and properties

build	O(n + R log R)
optimality	provably minimal for a prefix code
prefix-free	all symbols are leaves
used by	JPEG, MP3, PDF, gzip

Reference: Sedgewick & Wayne, §5.5; Huffman 1952.

Huffman compression in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

import heapq

class Node:
    def __init__(self, freq, char=None, left=None, right=None):
        self.freq, self.char = freq, char
        self.left, self.right = left, right
    def __lt__(self, other):              # heapq needs an ordering
        return self.freq < other.freq

def build_trie(text):
    freq = {}
    for c in text:
        freq[c] = freq.get(c, 0) + 1
    pq = [Node(f, c) for c, f in sorted(freq.items())]
    heapq.heapify(pq)
    while len(pq) > 1:
        left = heapq.heappop(pq)          # the two LEAST frequent nodes
        right = heapq.heappop(pq)
        heapq.heappush(pq, Node(left.freq + right.freq, None, left, right))
    return pq[0]

def build_code(node, prefix='', table=None):
    table = {} if table is None else table
    if node.char is not None:             # a LEAF: its path is its code
        table[node.char] = prefix or '0'
    else:
        build_code(node.left, prefix + '0', table)   # left  = 0
        build_code(node.right, prefix + '1', table)  # right = 1
    return table

Why it works

Why prefix-free matters

If one symbol's code were a prefix of another's, decoding would be ambiguous. Huffman guarantees this by construction: every symbol is a leaf, so no code is a prefix of any other, and decoding is just “walk down from the root, one bit per link, emit on reaching a leaf”. No separators and no lengths need to be stored.

Why merging the two smallest is optimal

The two least frequent symbols must be siblings at the greatest depth in some optimal tree — if they were not, swapping them with whatever is deepest would not increase the total cost. Merging them therefore cannot rule out an optimal solution, and the argument repeats on the smaller problem. That is a genuine optimality proof for a greedy algorithm, and Huffman found it as a student, after his professor offered the class the open problem instead of a final exam.

What optimal does not mean

Huffman is the best character-by-character code, and no more. It cannot exploit context (‘u’ after ‘q’ is nearly free in English) and it wastes space when one symbol's ideal length is fractional — with 90% probability the ideal code is 0.15 bits, but Huffman must spend at least 1. Arithmetic coding gets those fractions; LZ methods get the context. Modern formats combine them: DEFLATE Huffman-codes the output of an LZ77 pass.

Shipping the table

The decoder needs the trie, so the compressed file must carry it — pure overhead, which is why Huffman can expand very short inputs. The usual encoding is a preorder walk of the trie: one bit per node saying leaf or internal, with the symbol's bits following each leaf.

What to try in the animation

Watch which symbols end up deepest — they are the rare ones. The code table and the bit count appear as the trie is built.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

• abracadabra — abracadabra
• very skewed frequencies — aaaaaaaaaaaaaaaabbbbccd
• all equal frequencies — abcdabcdabcdabcd
• course example — it was the best of times it was the worst of times

Open Huffman compression in the player →

The rest of Data compression

• Run-length encoding Replace each run of identical symbols by the symbol and its length.
• LZW compression Emit the code for the longest known phrase, then learn that phrase plus one more character.