Huffman coding: Understanding lossless compression

In short: Huffman coding gives frequent characters short and rare characters long bit sequences, so that data becomes smaller without loss of information.

In more detail: Normally every character occupies the same number of bits (ASCII: 8). But letters occur with different frequency (in German “e” is very frequent, “q” rare). David Huffman (1952) found the optimal prefix-free method: frequent characters → short codes. It is in ZIP/DEFLATE, PNG, JPEG, MP3.

In Depth

The principle

1. Count frequencies (how often does each character occur?).
2. Build nodes from the characters and always combine the two rarest into a new node (sum of frequencies) until a tree results.
3. Path from the root to the character: left = 0, right = 1 → the character’s code. Prefix-free: no code is the beginning of another, so the bit stream can be translated back unambiguously without separators.

Example

Text “ABRAKADABRA” (11 characters): A=5, B=2, R=2, K=1, D=1.

1. K(1) + D(1) → KD(2)
2. B(2) + R(2) → BR(4)
3. KD(2) + BR(4) → KDBR(6)
4. A(5) + KDBR(6) → root(11) Left = 0, right = 1 gives for example: A = 0, K = 100, D = 101, B = 110, R = 111. Bit length: 5·1 + 1·3 + 1·3 + 2·3 + 2·3 = 23 bits instead of 11 · 8 = 88 bits (without code table). The exact codes depend on the order with equal frequencies; the total length is optimal.

Properties

• Lossless: decoding returns the original data exactly.
• Optimal among all symbol-by-symbol prefix codes; the limit is given by the entropy (information content). Better are methods that use patterns (LZ77/LZ78, LZW) or fractions of bits (arithmetic coding, ANS).
• The code table (tree) must be sent along or built adaptively.
• With uniformly distributed characters Huffman brings nothing (for example with already compressed or encrypted data).

Practice

DEFLATE (ZIP, gzip, PNG) = LZ77 + Huffman. JPEG uses Huffman for the coefficients after transformation and quantisation. Morse code has a similar principle (frequent “E” = one dot). For practice: count the character frequencies of a text, draw the tree, derive codes and calculate the saving. In Python this can be programmed with heapq in a few lines. Lossless vs. lossy: see compression.

See also: Compression, Heap and priority queue, ASCII and character sets, ZIP files