Huffman Coding in Python: Building Optimal Prefix Codes

By Engr. Henry Akpan

Shorter Codes for Common Letters

A computer normally stores each character in 8 bits, whether it is a common letter like "e" or a rare one like "z". That is wasteful. Morse code had a better idea long ago: give common letters short codes (E is a single dot) and rare letters long ones. Huffman coding, invented by David Huffman in 1952 while he was a student, does this optimally. Given how often each symbol appears, it builds the shortest possible prefix code, which is why it is still used inside ZIP files, PNG images, JPEG and MP3. This tutorial explains prefix codes, the greedy algorithm that builds a Huffman tree with a priority queue, encoding and decoding in Python, measuring the compression, and the limits of the method. All outputs come from running the code.

Variable-Length Codes and the Prefix Property

If codes have different lengths, how does the decoder know where one ends and the next begins? Suppose a = 0, b = 1 and c = 01. Then "01" could mean "ab" or "c": the code is ambiguous.

The fix is a prefix code: no code is the beginning (prefix) of another code. Then a decoder reading bits from left to right knows a symbol is complete the moment the bits match a code. Prefix codes can be drawn as a binary tree: each symbol sits at a leaf, and its code is the path from the root, with 0 for a left branch and 1 for a right branch. Because symbols are only at leaves, no code can be a prefix of another.

Huffman's Greedy Algorithm

  1. Count how often each symbol occurs. Make each symbol a single-node tree whose weight is its count.
  2. Put all the trees in a priority queue (a min-heap) ordered by weight.
  3. Repeatedly remove the two lightest trees, join them under a new parent whose weight is their sum, and put the new tree back.
  4. When one tree remains, it is the Huffman tree. Read off each symbol's code from the path to its leaf.

The rarest symbols are merged first, so they end up deepest in the tree with the longest codes, while frequent symbols stay near the root with short codes.

Huffman Coding in Python: Building the Tree

We use heapq for the priority queue. Each heap entry is (weight, tie-breaker, tree); the tie-breaker number keeps the order deterministic when weights are equal and stops Python from trying to compare trees. A leaf is a single character; an internal node is a pair (left, right).

import heapq
from collections import Counter
from itertools import count

def huffman_codes(text):
    freq = Counter(text)
    tick = count()
    heap = [(w, next(tick), sym) for sym, w in sorted(freq.items())]
    heapq.heapify(heap)
    if len(heap) == 1:                           # only one distinct symbol
        return {heap[0][2]: "0"}, freq
    while len(heap) > 1:
        w1, _, left = heapq.heappop(heap)
        w2, _, right = heapq.heappop(heap)
        heapq.heappush(heap, (w1 + w2, next(tick), (left, right)))
    codes = {}
    def walk(node, path):
        if isinstance(node, str):
            codes[node] = path
        else:
            walk(node[0], path + "0")
            walk(node[1], path + "1")
    walk(heap[0][2], "")
    return codes, freq

codes, freq = huffman_codes("abracadabra")
for sym in sorted(codes, key=lambda s: (len(codes[s]), s)):
    print(sym, freq[sym], codes[sym])

Output:

a 5 0
b 2 110
c 1 100
d 1 101
r 2 111

"a" appears 5 times out of 11 and gets a 1-bit code; the rarest letters get 3-bit codes. Check the prefix property: no code is the start of another.

Encoding and Decoding

def encode(text, codes):
    return "".join(codes[ch] for ch in text)

def decode(bits, codes):
    lookup = {code: sym for sym, code in codes.items()}
    out, current = [], ""
    for bit in bits:
        current += bit
        if current in lookup:            # prefix property: first match is the symbol
            out.append(lookup[current])
            current = ""
    return "".join(out)

bits = encode("abracadabra", codes)
print(bits, len(bits), "bits")
print(decode(bits, codes))

Output:

01101110100010101101110 23 bits
abracadabra

The 11 characters take 23 bits instead of 11 × 8 = 88 bits in standard 8-bit encoding. Even compared with a fixed-length code using 3 bits per symbol (enough for 5 symbols), Huffman needs only 23 bits instead of 33. A real decoder walks down the tree bit by bit instead of building strings, which is faster.

Measuring the Compression

The average code length is the total bits divided by the number of symbols. Information theory gives a lower limit for any symbol-by-symbol code, the entropy H = −Σ p log₂ p, where p is each symbol's probability. Huffman coding always comes within 1 bit per symbol of this limit.

import math

def report(text):
    codes, freq = huffman_codes(text)
    n = len(text)
    total_bits = sum(freq[s] * len(codes[s]) for s in freq)
    entropy = -sum((w / n) * math.log2(w / n) for w in freq.values())
    fixed = max(1, math.ceil(math.log2(len(freq))))
    print(f"{n} chars, {len(freq)} symbols: Huffman {total_bits} bits "
          f"({total_bits / n:.2f} per symbol), fixed {fixed * n}, ASCII {8 * n}, "
          f"entropy {entropy:.2f}")

report("abracadabra")
report("the quick brown fox jumps over the lazy dog " * 3)
report("aaaaaaaaab")

Output:

11 chars, 5 symbols: Huffman 23 bits (2.09 per symbol), fixed 33, ASCII 88, entropy 2.04
132 chars, 27 symbols: Huffman 582 bits (4.41 per symbol), fixed 660, ASCII 1056, entropy 4.34
10 chars, 2 symbols: Huffman 10 bits (1.00 per symbol), fixed 10, ASCII 80, entropy 0.47

The last line shows a limitation: with only two symbols, each code must be at least 1 bit, so Huffman cannot get below 1 bit per symbol even though the entropy is only 0.47. Arithmetic coding and the newer ANS coders get around this by not giving each symbol a whole number of bits.

Why the Greedy Choice Is Optimal

Huffman coding produces the shortest possible prefix code for the given frequencies. The proof rests on two observations:

  • In some optimal tree, the two least frequent symbols are siblings at the deepest level. (If a rarer symbol were higher than a more common one, swapping them would not increase the total length.)
  • Merging those two symbols into one combined symbol gives a smaller problem of the same kind, and an optimal tree for the smaller problem expands into an optimal tree for the original.

So making the greedy choice at every step never loses optimality. This makes Huffman coding a classic example of a greedy algorithm, alongside Dijkstra's algorithm and activity selection.

Complexity and Practical Details

  • With k distinct symbols, building the tree takes O(k log k) using a heap; encoding n symbols takes O(n).
  • The decoder needs the code table (or the frequencies) too, so it must be stored with the compressed data. For very short texts this overhead can exceed the savings.
  • Real formats use canonical Huffman codes: codes are assigned in a standard order so that only the code lengths need storing.
  • Huffman coding compresses symbols independently. Formats like ZIP and PNG first use LZ77, which replaces repeated strings with back-references, and then Huffman-code the result (the DEFLATE method). JPEG and MP3 Huffman-code their transformed and quantised data.

Summary

  • Huffman coding gives frequent symbols short codes and rare symbols long codes, building an optimal prefix code.
  • Prefix codes need no separators: no code is the beginning of another, so decoding is unambiguous.
  • Algorithm: repeatedly merge the two lightest trees from a min-heap until one tree remains.
  • The average code length is within 1 bit of the entropy; with very skewed data, other coders do better.
  • Huffman coding is part of ZIP, PNG, JPEG and MP3, usually after other compression steps.

Related Tutorials