Huffman Coding

Huffman coding constructs a binary prefix code that minimizes weighted codeword length for a known set of symbol frequencies:

$$\min \sum_s f_s\,\ell_s,$$

where $f_s$ is a symbol frequency and $\ell_s$ its code length.

Construction

1. Put one leaf per positive-frequency symbol into a min-priority queue.
2. Remove the two least frequent nodes.
3. Join them under a parent whose weight is their sum.
4. Reinsert the parent and repeat until one tree remains.
5. Label left/right edges with bits; each root-to-leaf path is a codeword.

Leaves cannot prefix one another, so concatenated codewords decode unambiguously given the tree or an equivalent canonical-code description.

Open full-size image

Start at the bottom-right: Z has frequency 1 and D has frequency 2, so their parent has weight 3. Every internal node likewise sums its two children. Frequent S, with count 27, lies three edges from the root; rare Z lies seven edges away. Reading left as 0 and right as 1 gives S the code 111. This twenty-symbol textbook example uses different frequencies from the four-symbol trace below.

Jeff Erickson, Algorithms, §4.4 (p. 167); code tree cropped from the PDF. · CC BY 4.0

Why the greedy merge is safe

In some optimal full binary prefix tree, two least frequent symbols can be made deepest siblings by exchanging leaf labels without increasing weighted length. Contracting those siblings produces the same problem on one combined frequency, which justifies the recursive greedy step.

Cost and boundary

For $k$ symbols, heap construction and merging take $O(k\log k)$ time and $O(k)$ space. Ties can produce different but equally optimal code lengths.

The encoded stream must also represent the codebook, padding, and original length as needed. Huffman coding is optimal for the stated prefix-code model, not universally optimal compression; block structure and richer probabilistic models can exploit dependencies it ignores.

Merge trace and tiny alphabets

For frequencies A:5, B:2, C:1, D:1, merge C and D to weight 2, merge that node with B to weight 4, then merge with A to weight 9. One code is A=0, B=10, C=110, D=111. Its weighted length is 5×1 + 2×2 + 1×3 + 1×3 = 15 bits, versus 18 for a fixed two-bit code. The merge weights also sum to 15: each merge adds one bit to every leaf beneath it.

The code below computes this optimal weighted length, not the codebook. Empty input costs zero. A one-symbol alphabet needs zero payload bits if the decoder knows the repetition count; a format requiring a nonempty codeword may instead assign 0, costing one bit per occurrence. That format convention must be shared by encoder and decoder. To build actual codes, store child nodes with heap entries and use a serial tie-breaker so tied weights never compare incompatible node objects.

from heapq import heapify, heappop, heappush

def huffman_bit_cost(frequencies):
    if any(f < 0 for f in frequencies):
        raise ValueError("negative frequency")
    heap = [f for f in frequencies if f > 0]
    heapify(heap)
    total = 0
    while len(heap) > 1:
        merged = heappop(heap) + heappop(heap)
        total += merged
        heappush(heap, merged)
    return total

assert huffman_bit_cost([5, 2, 1, 1]) == 15
assert huffman_bit_cost([]) == huffman_bit_cost([5]) == 0

Source

• Princeton Algorithms: Data Compression

My reading · Opened notes are remembered in this browser.