Huffman Coding

Why compress?

In plain ASCII every character takes 8 bits. But in real text some characters are far more common than others — e and space appear constantly, z and q rarely. If we give common characters short codes and rare characters long codes, the total number of bits shrinks.

Huffman coding (David Huffman, 1952 — as a student project!) builds the best possible such code.

The algorithm

1. Count how often each character appears.
2. Make a leaf for each character and put all leaves in a min-priority queue keyed by frequency.
3. While there is more than one tree:
   • remove the two smallest trees,
   • join them under a new node whose frequency is their sum,
   • insert the new tree back into the queue.
4. The last remaining tree is the Huffman tree.
5. Label every left edge 0 and every right edge 1. A character’s code is the sequence of bits on the path from the root to its leaf.

Watch it in the 3D model: the two smallest trees light up yellow and merge, and the forest keeps re-sorting itself by frequency.

Worked example: ABRACADABRA

Merges: C+D (2) → B+R or (CD)+B … until one tree remains. A, being most frequent, ends up with a 1-bit code; C and D get the longest codes. The 11-character string needs 88 bits in ASCII but only 23 bits with Huffman codes — about 74% smaller.

Prefix codes — why decoding works

Every character sits at a leaf, so no code is the beginning (prefix) of another. That means a bit stream like 0101100… can be decoded unambiguously: walk down the tree bit by bit, and every time you hit a leaf, output its character and jump back to the root. No separators needed.

Code

import heapq
from collections import Counter

def huffman_codes(text):
    freq = Counter(text)
    # heap items: (frequency, tie-breaker, tree); a tree is a char or a (left, right) pair
    heap = [(f, i, ch) for i, (ch, f) in enumerate(sorted(freq.items()))]
    heapq.heapify(heap)
    count = len(heap)
    if count == 1:
        return {heap[0][2]: "0"}
    while len(heap) > 1:
        f1, _, a = heapq.heappop(heap)      # two smallest
        f2, _, b = heapq.heappop(heap)
        heapq.heappush(heap, (f1 + f2, count, (a, b)))
        count += 1
    codes = {}
    def walk(tree, code):
        if isinstance(tree, str):
            codes[tree] = code
        else:
            walk(tree[0], code + "0")
            walk(tree[1], code + "1")
    walk(heap[0][2], "")
    return codes

text = "ABRACADABRA"
codes = huffman_codes(text)
encoded = "".join(codes[c] for c in text)
print(codes)
print(len(encoded), "bits instead of", 8 * len(text))

Why is greedy optimal here?

The two least frequent symbols should be the deepest leaves — swapping them with anything shallower could only increase the total cost. Merging them first and then solving the smaller problem leads, by induction, to the optimal tree. (This “greedy choice + optimal substructure” argument is the standard way to prove greedy algorithms correct.)

Where is Huffman coding used?

Inside ZIP/gzip (DEFLATE), PNG, JPEG and MP3 — usually as the final step after other transformations. Modern formats sometimes use arithmetic coding or ANS, which squeeze out a little more, but Huffman remains everywhere because it is fast and simple.

Common mistakes

• Merging the two largest instead of the two smallest.
• Forgetting the special case of a text with only one distinct character.
• Assuming the tree is unique — ties can produce different trees, but every Huffman tree gives the same total number of bits.