Huffman Coding

Introduction

Huffman coding, invented by David Huffman in 1952 while a graduate student at MIT, is a lossless data compression algorithm that assigns variable-length binary codes to characters based on their frequencies. Characters that appear more frequently receive shorter codes, while rare characters receive longer codes. This produces an encoding that uses fewer total bits than a fixed-length encoding.

The algorithm is greedy: it builds the encoding tree bottom-up by repeatedly combining the two lowest-frequency nodes. This simple strategy produces an optimal prefix code -- no other prefix code can achieve a shorter expected encoding length for the given frequency distribution.

Huffman coding is a fundamental component of many compression formats including DEFLATE (used in ZIP and gzip), JPEG, MP3, and numerous other file formats. It is often used in combination with other techniques such as run-length encoding or Lempel-Ziv algorithms.

Prefix Codes

A prefix code (also called a prefix-free code) is a coding scheme where no codeword is a prefix of another codeword. This property allows unambiguous decoding without needing delimiters between codewords. For example, if 'a' is encoded as "0" and 'b' as "01", the string "001" is ambiguous (is it "aa1" or "ab"?). But if 'a' is "0" and 'b' is "10", every bit string has a unique decoding.

Any prefix code can be represented as a binary tree where characters are leaves. Left edges represent 0 and right edges represent 1. The code for each character is the sequence of edge labels on the path from root to leaf. The prefix property is guaranteed because characters are only at leaves -- no character's path is a prefix of another's.

Kraft's inequality states that for a prefix code with n codewords of lengths l1, l2, ..., ln, the sum of 2^(-li) must be at most 1. Conversely, for any set of lengths satisfying Kraft's inequality, a prefix code with those lengths exists.

Huffman's Algorithm

procedure HuffmanCoding(characters, frequencies): // Create a leaf node for each character priorityQueue = new MinHeap() for each character c with frequency f: priorityQueue.insert(Node(c, f)) // Build the tree bottom-up while priorityQueue.size() > 1: left = priorityQueue.extractMin() right = priorityQueue.extractMin() // Create internal node with combined frequency parent = Node(null, left.freq + right.freq) parent.left = left parent.right = right priorityQueue.insert(parent) root = priorityQueue.extractMin() // Generate codes by traversing the tree assignCodes(root, "")

The algorithm greedily combines the two nodes with the smallest frequencies at each step. This ensures that the characters with the lowest frequencies end up deepest in the tree (longest codes), while high-frequency characters are near the root (shortest codes).

Worked Example

Encode the characters with these frequencies:

Tree construction:

1. Combine f(5) and e(9) -> [fe](14)2. Combine c(12) and b(13) -> [cb](25)3. Combine [fe](14) and d(16) -> [fed](30)4. Combine [cb](25) and [fed](30) -> [cbfed](55)5. Combine a(45) and [cbfed](55) -> root(100)

Compression: Fixed-length uses 3 * 100 = 300 bits. Huffman uses 1*45 + 3*13 + 3*12 + 3*16 + 4*9 + 4*5 = 45 + 39 + 36 + 48 + 36 + 20 = 224 bits. Savings: 25.3%.

Optimality Proof

Huffman's algorithm produces an optimal prefix code. The proof establishes two key properties:

1. Greedy choice property: An optimal tree exists in which the two least-frequent characters are siblings at the maximum depth. This is proved by exchange: if they are not siblings, swapping them with the actual deepest siblings cannot increase total cost because lower-frequency characters moved deeper contribute less to the weighted path length.
2. Optimal substructure: After merging the two least-frequent characters into a single "super-character" with combined frequency, the optimal code for the remaining n-1 characters (including the super-character) yields an optimal code for the original n characters when the super-character is split back.

The expected code length of a Huffman code is between H(X) and H(X) + 1, where H(X) is the Shannon entropy of the source. Shannon's source coding theorem proves that no lossless code can do better than H(X) bits per symbol on average.

Complexity Analysis

Space complexity: O(n) for the tree and the priority queue.

If the frequencies are already sorted, a more efficient O(n) algorithm exists using two queues instead of a priority heap (van Leeuwen, 1976).

Implementation

import heapqclass HuffmanNode: def __init__(self, char, freq): self.char = char self.freq = freq self.left = None self.right = None def __lt__(self, other): return self.freq < other.freqdef huffman_coding(char_freq): heap = [HuffmanNode(c, f) for c, f in char_freq.items()] heapq.heapify(heap) while len(heap) > 1: left = heapq.heappop(heap) right = heapq.heappop(heap) merged = HuffmanNode(None, left.freq + right.freq) merged.left = left merged.right = right heapq.heappush(heap, merged) codes = {} def build_codes(node, code): if node.char is not None: codes[node.char] = code return build_codes(node.left, code + "0") build_codes(node.right, code + "1") build_codes(heap[0], "") return codes

Compression Analysis

The effectiveness of Huffman coding depends on the frequency distribution of characters. The more skewed the distribution, the better the compression:

• Highly skewed distributions: One dominant character gets a 1-bit code, achieving near-maximum compression.
• Uniform distributions: All characters get codes of similar length, approximating a fixed-length encoding with no compression benefit.
• Shannon entropy bound: The average code length L satisfies H(X) <= L < H(X) + 1, where H(X) = -sum(p_i * log2(p_i)) is the entropy.

For English text, Huffman coding typically achieves about 4.5-5.5 bits per character compared to 8 bits for ASCII, a compression ratio of roughly 30-40%.

Variants and Extensions

• Adaptive Huffman Coding: Updates the Huffman tree dynamically as data is processed, eliminating the need for two passes over the data. Used when frequency distributions are unknown or changing.
• Canonical Huffman Codes: A standardized form where codes of the same length are assigned in lexicographic order. This allows the codebook to be reconstructed from just the code lengths, reducing header overhead.
• Extended Huffman Coding: Groups of symbols (e.g., pairs or triples of characters) are coded together, approaching entropy more closely at the cost of a larger alphabet.
• Length-Limited Huffman Codes: Restricts the maximum code length (useful for hardware implementations with fixed-width registers). Solved by the package-merge algorithm.
• Arithmetic Coding: An alternative that encodes the entire message as a single fraction, achieving compression arbitrarily close to entropy without the integer-bit-length constraint of Huffman codes.

References

• Huffman, D. A. "A Method for the Construction of Minimum-Redundancy Codes." Proceedings of the IRE, vol. 40, no. 9, 1952, pp. 1098-1101.
• Shannon, C. E. "A Mathematical Theory of Communication." Bell System Technical Journal, vol. 27, 1948, pp. 379-423.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. "Introduction to Algorithms." MIT Press, Chapter 16, 2009.
• Vitter, J. S. "Design and Analysis of Dynamic Huffman Codes." Journal of the ACM, vol. 34, 1987, pp. 825-845.
• van Leeuwen, J. "On the Construction of Huffman Trees." Proceedings of the 3rd International Colloquium on Automata, Languages, and Programming, 1976, pp. 382-410.