Variable-length codes

Plain text usually stores every character in the same number of bits, 8 for ASCII. But in most texts some characters are far more common than others: in English, e is about a hundred times as common as z. Giving common characters short codes and rare characters long codes makes the whole text shorter. That is the idea behind Morse code, and behind the compression inside ZIP, gzip, PNG and JPEG.

For the encoded bits to be decodable without separators, no code may be the beginning of another. This is called a prefix code (or prefix-free code). With the codes A = 0, B = 10, C = 11, the bits 010110 can only mean A B C A. A prefix code is the same thing as a binary tree with the characters at the leaves: a character's code is the path from the root to its leaf, with left = 0 and right = 1.

Code tree with leaf A on the left (code 0) and B and C under the right child (codes 10 and 11); the bits 010110 split into 0, 10, 11, 0 and decode to A B C A
In a prefix code every character is a leaf, so a decoder just walks the tree bit by bit and restarts at the root after each character.

Huffman's algorithm

Which tree gives the shortest encoding? If character c appears f(c) times and sits at depth d(c), the encoded text has Σ f(c) · d(c) bits. David Huffman found, as a student in 1952, that a simple greedy rule builds the best tree:

huffman(characters with frequencies):
    make a one-node tree for each character, weighted by its frequency
    put all the trees in a min-priority queue
    while the queue holds more than one tree:
        a = extractMin();  b = extractMin()        // the two lightest trees
        insert a new tree with root weight a + b,
               left subtree a, right subtree b
    return the last tree

The two rarest characters end up deepest in the tree. In the animation, the forest is drawn in priority-queue order (lightest on the left), leaves are yellow, and each new parent's edges are labelled 0 and 1. Once the tree is built, each character's path is highlighted and its code is written into the table.

Why the greedy choice is safe

Two facts make the greedy rule optimal. First, in some optimal tree the two least frequent characters are siblings at the deepest level: if a more frequent character were deeper, swapping it with a rarer one could only reduce the total. Second, once those two are joined, the rest of the problem is the same problem again with one fewer "character" (their combined tree), and the cost only changes by the constant f(a) + f(b). By induction, joining the two lightest trees at every step gives an optimal prefix code.

Running time

With k distinct characters there are k − 1 merges, each doing two extractMin operations and one insert. With a binary heap, that is O(k lg k) time, plus O(n) to count the n characters of the text. Ties can be broken in any order: different choices give different codes, but always the same total length.

Huffman codes are optimal among codes that encode each character separately. Compressors such as gzip first replace repeated phrases (LZ77) and then Huffman-code the result, and arithmetic coding can do slightly better by not rounding each code to a whole number of bits.

Worked example

The text ABRACADABRA has 11 characters: A × 5, B × 2, R × 2, C × 1, D × 1. The queue starts as C:1, D:1, B:2, R:2, A:5.

join C:1 + D:1 → 2        queue: B:2  R:2  (CD):2  A:5
join B:2 + R:2 → 4        queue: (CD):2  (BR):4  A:5
join (CD):2 + (BR):4 → 6  queue: A:5  (CDBR):6
join A:5 + (CDBR):6 → 11  the Huffman tree

codes (left = 0, right = 1):   A = 0     C = 100   D = 101   B = 110   R = 111
Huffman tree for ABRACADABRA: join 1 combines C:1 and D:1 into 2, join 2 combines B:2 and R:2 into 4, join 3 combines those into 6, join 4 combines A:5 and 6 into 11. Codes: A = 0, C = 100, D = 101, B = 110, R = 111, 23 bits in total against 88 in ASCII
Joining the two lightest trees each time puts the frequent A one step from the root and the rare C and D deepest, for 23 bits in total.

Encoded length: 5·1 + 2·3 + 2·3 + 1·3 + 1·3 = 23 bits, against 88 bits in 8-bit ASCII and 33 bits with the shortest fixed-length code (5 characters need 3 bits each). The frequent A gets a 1-bit code; the rare C and D sit deepest. Decoding 0 110 111 0 walks the tree from the root and restarts at the root at every leaf: A B R A.

Common mistakes and details

  • The decoder needs the tree. A compressed file must also store the code table (or the frequencies), which is why Huffman coding does not pay off for very short texts.
  • Ties can be broken any way you like. Different choices give different codes, but the total length is always the same minimum.
  • One distinct character gives a tree with a single leaf and an empty code; give it a 1-bit code by convention (this page uses 0).
  • It is always the two lightest trees that are joined, not the lightest tree and the next character, and the new tree goes back into the queue.
  • Canonical Huffman codes (used by DEFLATE/gzip) keep only each code's length and rebuild the codes in a fixed order, which makes the table smaller to store.

Where Huffman coding is used

Huffman coding is not a historical curiosity: it is running inside almost every file you open and every page you load. It usually appears as the final entropy-coding stage of a larger compression scheme, after some other transform has made the symbol distribution lopsided enough to be worth exploiting.

  • DEFLATE, and therefore gzip, zlib, ZIP and PNG. After matches are replaced with length/distance pairs, the literals, lengths and distances are Huffman coded — and the code tree is written into the stream so the decoder can rebuild it, exactly as here.
  • JPEG. Baseline JPEG Huffman codes the quantised DCT coefficients; the quantisation does the lossy work, the Huffman stage does the lossless packing afterwards.
  • MP3 and AAC audio, for the quantised frequency coefficients.
  • HTTP/2 and HTTP/3 headers. HPACK and QPACK compress header strings with a fixed Huffman code built from measured frequencies in real web traffic — a static table rather than a per-message tree.
  • Modern general-purpose compressors. Brotli uses Huffman coding with context modelling; Zstandard uses it for literals alongside a finite-state entropy coder for the rest.
  • Fax. The ITU-T G.3 and G.4 standards use modified Huffman codes for run lengths, one of the earliest mass deployments.

It is worth knowing the limit as well. A Huffman code must spend a whole number of bits per symbol, so when a symbol's probability is not a power of one half it cannot quite reach the entropy bound — costly when one symbol dominates, say at 90% probability, where the ideal is about 0.15 bits but Huffman must spend one. Arithmetic coding and asymmetric numeral systems do reach it, which is why newer codecs such as AV1 and Zstandard use them for the hardest parts. Huffman survives anyway, because decoding is a table lookup and is very hard to beat for speed.

See also Base64 encoding, which goes the other way: a fixed 6 bits per character that makes data a third bigger, so bytes can travel as text.