Huffman Coding

#How does it work?

Huffman coding is one of the basic methods of lossless compression. Instead of giving every letter a fixed-length code (e.g. 8 bits), it gives frequent letters short codes and rare letters long ones.

The codes are prefix-free: no code is the start of another. That lets the text be decoded unambiguously without separators between codes.

The greedy rule: each letter is a one-node tree weighted by its frequency. At every step the two lightest trees are joined under a new node. In the end the path from the root to a letter is its code: left is 0, right is 1. For ABRACADABRA, Huffman uses 23 bits; a fixed 3-bit code would need 33.

#Try it yourself

#Step by step

1. 01Count each letter's frequency and make a one-node tree for each letter.
2. 02Pick the two lightest trees (with a priority queue).
3. 03Join them under a new node whose weight is their sum.
4. 04Repeat until one tree is left; the paths from the root to the leaves give the codes.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

import heapq
from collections import Counter


def huffman_bits(text: str) -> int:
    """Total bits of the Huffman-coded text: each merge adds its weight once per level."""
    heap = list(Counter(text).values())
    heapq.heapify(heap)
    bits = 0
    while len(heap) > 1:
        a = heapq.heappop(heap)  # the two lightest trees
        b = heapq.heappop(heap)
        bits += a + b            # every letter below the new node gets one more bit
        heapq.heappush(heap, a + b)
    return bits


text = "ABRACADABRA"
print(huffman_bits(text))  # 23
distinct = len(set(text))
print(len(text) * (distinct - 1).bit_length())  # a fixed-length code: 3 bits per letter

#Complexity

n is the length of the text and k the number of distinct letters. Each of the k − 1 merges takes O(log k) in the priority queue. Huffman gives the smallest total length among prefix-free codes with one code per letter; ties can produce different codes of the same total length.

#When to use it?

ZIP/DEFLATE, gzip, PNG, JPEG and MP3 all use Huffman coding in one stage of compression. The idea also shows up in data compression in general, saving bandwidth in communication, and optimising decision trees.

#Practice

Log in to answer questions and save your progress.