Huffman Coding

Huffman coding builds the optimal prefix code by repeatedly merging the two least likely symbols.

The algorithm

Start with one leaf per symbol weighted by its frequency. Repeatedly take the two lowest-weight nodes, join them under a new parent whose weight is their sum, and return it to the pool. When one node remains, the tree is complete.

Reading off the codes

Kronos motion — number counters

Label each left branch 0 and each right branch 1. The path from the root to a symbol's leaf is its codeword. Frequent symbols end up near the root with short codes; rare symbols sit deeper.

Optimality

Huffman coding produces the minimum average length among all prefix codes for a given set of symbol frequencies. Its greedy merging is provably optimal, a classic result in algorithm design.

How close to entropy

The average code length lands within one bit of the source entropy. It equals entropy exactly when every probability is a power of two; otherwise the whole-bit rounding leaves a small gap.

Limitations and uses

Because each symbol takes a whole number of bits, Huffman cannot beat that one-bit overhead; arithmetic coding does better on skewed sources. Even so, Huffman is fast and appears inside DEFLATE, JPEG, and MP3.

python

import heapq
def huffman(freq):
    h = [[w,[s,'']] for s,w in freq.items()]
    heapq.heapify(h)
    while len(h) > 1:
        lo = heapq.heappop(h); hi = heapq.heappop(h)
        for pair in lo[1:]: pair[1] = '0'+pair[1]
        for pair in hi[1:]: pair[1] = '1'+pair[1]
        heapq.heappush(h,[lo[0]+hi[0]]+lo[1:]+hi[1:])
    return {s:c for s,c in h[0][1:]}
print(huffman({'a':5,'b':2,'c':1,'d':1}))