AlgoScope

Huffman Coding

algorithmintermediateTime O(n log n)Space O(n)

A fixed-width code spends the same number of bits on the character that appears twenty times and the one that appears once, which is obviously wasteful. Huffman fixes that with one greedy rule: the two lightest roots in the forest merge under a new parent, over and over, until a single tree remains. Every merge pushes the characters underneath it one level deeper and therefore one bit longer, so merging the lightest first is exactly the choice that keeps the common characters near the top and short. Because characters only ever sit at leaves, no code is a prefix of another, and a decoder can read a stream of bits straight through without any separator between codes.

a:5b:2c:1d:1r:2

Encode "abracadabra" in as few bits as possible. Count how often each character appears: a appears 5 times, b appears 2 times, c appears 1 time, d appears 1 time, r appears 2 times. Each count starts as a root of its own. Merge the two lightest roots under a new parent, over and over, until one tree is left; the path down to a character is then its code.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 3, with their answers.

  1. Which two roots merge next?

    • c:1 and d:1
    • c:1 and b:2
    • r:2 and a:5

    Answer: c:1 and d:1. Always the two lightest. Merging anything heavier would push more characters deeper than they need to be, and every level is a bit per occurrence.

  2. Which two roots merge next?

    • b:2 and r:2
    • b:2 and 2
    • 2 and a:5

    Answer: b:2 and r:2. Always the two lightest. Merging anything heavier would push more characters deeper than they need to be, and every level is a bit per occurrence.

  3. Which two roots merge next?

    • 2 and 4
    • 2 and a:5

    Answer: 2 and 4. Always the two lightest. Merging anything heavier would push more characters deeper than they need to be, and every level is a bit per occurrence.

How it runs, step by step

  1. Encode "abracadabra" in as few bits as possible. Count how often each character appears: a appears 5 times, b appears 2 times, c appears 1 time, d appears 1 time, r appears 2 times. Each count starts as a root of its own. Merge the two lightest roots under a new parent, over and over, until one tree is left; the path down to a character is then its code.

    Huffman over 5 characters of "abracadabra".

  2. There are 5 roots: c:1, d:1, b:2, r:2, a:5. The two lightest are c:1 and d:1, so they merge. Burying a root one level deeper costs one extra bit for every character under it, which is why the lightest go first.

    Merging c:1 and d:1.

  3. The new parent weighs 1 + 1 = 2 and takes their place in the queue. The edge to the left child is labelled 0 and the edge to the right child 1; those labels, read from the top down, are the codes.

    New parent of weight 2.

  4. There are 4 roots: 2, b:2, r:2, a:5. The two lightest are b:2 and r:2, so they merge. Burying a root one level deeper costs one extra bit for every character under it, which is why the lightest go first.

    Merging b:2 and r:2.

  5. The new parent weighs 2 + 2 = 4 and takes their place in the queue. The edge to the left child is labelled 0 and the edge to the right child 1; those labels, read from the top down, are the codes.

    New parent of weight 4.

  6. There are 3 roots: 2, 4, a:5. The two lightest are 2 and 4, so they merge. Burying a root one level deeper costs one extra bit for every character under it, which is why the lightest go first.

    Merging 2 and 4.

  7. The new parent weighs 2 + 4 = 6 and takes their place in the queue. The edge to the left child is labelled 0 and the edge to the right child 1; those labels, read from the top down, are the codes.

    New parent of weight 6.

  8. There are 2 roots: a:5, 6. The two lightest are a:5 and 6, so they merge. Burying a root one level deeper costs one extra bit for every character under it, which is why the lightest go first.

    Merging a:5 and 6.

  9. The new parent weighs 5 + 6 = 11 and takes their place in the queue. The edge to the left child is labelled 0 and the edge to the right child 1; those labels, read from the top down, are the codes.

    New parent of weight 11.

  10. Walk from the root down to a, reading 0 for every left edge and 1 for every right: the code is 0, 1 bit for a character that appears 5 times, so a costs 5 bits in total.

    The code for a is 0.

  11. Walk from the root down to b, reading 0 for every left edge and 1 for every right: the code is 110, 3 bits for a character that appears 2 times, so b costs 6 bits in total.

    The code for b is 110.

  12. Walk from the root down to c, reading 0 for every left edge and 1 for every right: the code is 100, 3 bits for a character that appears 1 time, so c costs 3 bits in total.

    The code for c is 100.

  13. Walk from the root down to d, reading 0 for every left edge and 1 for every right: the code is 101, 3 bits for a character that appears 1 time, so d costs 3 bits in total.

    The code for d is 101.

  14. Walk from the root down to r, reading 0 for every left edge and 1 for every right: the code is 111, 3 bits for a character that appears 2 times, so r costs 6 bits in total.

    The code for r is 111.

  15. The codes are a=0, b=110, c=100, d=101, r=111. "abracadabra" becomes 23 bits, against 33 with a fixed 3-bit code for 5 characters: a saving of 10. No code is a prefix of another, because every character sits at a leaf, so a decoder can read the bits straight through without separators and never has to guess where one code ends.

    23 bits against 33 fixed-width.

Write it yourself

Define huffmanBits(text) and return how many bits the text takes once it is Huffman coded. It runs in your browser against this lesson's own 4 examples.

// Repeatedly merge the two rarest symbols. The total is every character's count times the depth it ends up at.function huffmanBits(text) {    return 0;}
Ln 1, Col 16 linesTab indents; Escape then Tab leaves the editor. Ctrl-Enter runs, Cmd-Enter on a Mac.

Remember

  • Merge the two lightest roots; their parent weighs the sum and goes back in the queue.
  • Characters sit only at leaves, so no code is a prefix of another and no separators are needed.
  • The rarest character ends up deepest: a merge costs one extra bit for every character under it.

Topics covered

Related

Where this is used

Compressiongzip, zlib and PNG

DEFLATE is LZ77 followed by Huffman: back-references remove repeated strings, and what is left is a badly unbalanced alphabet of literals and match lengths that Huffman shortens. A dynamic block carries the code lengths for its own trees, so a block of English text and a block of pixel rows get different codes. PNG runs the same pipeline after its per-row filters, and so does the gzip in every HTTP stack.

GraphicsBaseline JPEG

After the cosine transform and quantisation, most high-frequency coefficients in a block are zero, so the run-length symbols describing them are wildly unequal in frequency, which is exactly the input Huffman is built for. The standard also publishes example tables measured on a large set of images, so an encoder can skip the counting pass, though whichever tables it used are still written into the file.

NetworkingHTTP/2 header compression (HPACK)

Headers repeat on every request and are mostly lowercase ASCII, slashes, digits and dates, so their character distribution is known before any traffic arrives. RFC 7541 freezes one Huffman table built from a large sample of real headers, which takes roughly a quarter to a third off string literals with no tree to transmit per message. A fixed table also keeps the decoder stateless for each string, which matters when a server parses headers for thousands of connections.

AudioMP3 and AAC audio

The encoder quantises the spectrum, and the resulting integers cluster hard around zero in the high bands. Both formats entropy-code them with a set of Huffman tables fixed by the specification and store only the table number per region, so nothing tree-shaped is in the stream and a decoder can run on very small hardware.

Why it works this way

Why merge the two lightest, and not any other pair?

Add up the weights of every internal node and you have the encoded size in bits, because each internal node is one level of depth charged to everything beneath it. The question is then which pairing keeps heavy weights out of that sum for as long as possible, and taking the two lightest roots every time is exactly that choice. The result is provably optimal: no other prefix code over the same frequencies uses fewer bits.

The decoder needs the same tree, and the tree is not free

The bit stream alone is meaningless, so the tree has to travel with it or be agreed in advance. What a format ships is not the tree shape but the code length of each symbol, and both sides rebuild the same canonical code from those lengths. That header is why Huffman can make a short string larger than it started, and why HPACK and MP3 avoid it entirely by fixing their tables in the specification.

Text with a single distinct character produces an empty code

With one leaf in the queue the merge loop never runs, and the walk reaches that leaf with the empty string as its code. Zero bits per character means the decoder has no way to tell how many characters there were, which is why the code above substitutes a single zero bit when the code comes out empty. It is the first case that breaks a fresh implementation, usually on a run of identical bytes.

Huffman can never spend less than one bit on a character

Code lengths are whole numbers, so a character that appears ninety percent of the time still costs a full bit when its ideal cost is about 0.15. On strongly skewed alphabets that rounding is the whole gap between Huffman and arithmetic coding or ANS, which can spend fractional bits; zstd uses an ANS coder for its length and offset symbols and keeps Huffman only for literals. Huffman survives because decoding a symbol is one table lookup, which is far faster than the alternatives.

Read more

Next up