Sign in

Browse by category

More

Learning Center · Compression · Beginner

Huffman coding explained: shorter codes for common symbols

Learn how Huffman coding builds a tree from symbol counts, gives frequent letters short codes, and decodes without separators, with a worked example.

By listme.name Updated 6 min read 1:16 video Share

1:16 video with captions. The text below has the detail and the sources.
Read the video transcript

Fixed codes waste bits

Plain text spends eight bits on every letter, common or rare. One tree decides every code.

Worked example: MISSISSIPPI

Eleven letters at eight bits each is eighty-eight bits. Count the letters. S and I appear four times, P twice, M once. Join the two rarest, again and again, until one tree remains. Left is zero, right is one. S takes one bit, I two, P and M three. The word takes twenty-one bits.

Decoding without separators

Read one bit, and step down the tree. Reach a leaf. No other code begins with those bits, so the letter is certain. Write the letter, then start again at the root. Repeat until the bits run out. No separators are needed.

Where it is used

DEFLATE, used by ZIP, gzip and PNG, Huffman-codes its symbols. JPEG photos use Huffman tables too. MP3 audio stores its values with Huffman codes as well.

What to remember

Huffman coding gives frequent symbols short codes, built from the counts alone. Read the full guide for the tree steps and the limits.

Huffman coding gives frequent symbols short codes and rare symbols long ones, so a message with uneven letter counts can take fewer bits than one that spends eight bits on every character. The method counts the symbols, joins the two rarest items into a tree again and again, and reads each code from the path to its leaf. No code is the start of another, so the bits decode without separators. The video above works through the word MISSISSIPPI in about 75 seconds; this page adds the tree steps, the cost of the table and the limits.

Why fixed-length codes waste space

A fixed-length code gives every symbol the same number of bits. Plain text stores one byte per character, eight bits, so the letter e costs the same as the letter z, even though English uses e far more often. With a fixed code, eleven characters always take 88 bits, whatever those characters are.

A symbol that appears often earns a shorter code, which saves bits every time it appears. The rare symbols pay for that with longer codes. The open question is how to choose the lengths so that a reader can still split the bit stream back into symbols. David Huffman's method answers both parts.

Count the symbols and join the rarest pair

Start with the counts. In MISSISSIPPI, M appears once, P twice, and I and S four times each, eleven letters in all. It starts with one leaf per symbol, weighted by its count. Then it repeats two steps: take the two lightest nodes, and join them under a new parent whose weight is their sum. When one node is left, it is the root.

Applied to MISSISSIPPI:

  1. Join M (1) and P (2). The new node weighs 3.
  2. Three nodes remain: I (4), S (4) and the node of weight 3. Join the two lightest, the node of weight 3 and I. The new node weighs 7. When S and I tie, either can go first. Joining S first also gives 21 bits, with different codes.
  3. Join S (4) and the node of weight 7. The root weighs 11, the length of the word.

The repository's demo prints the same result:

11 characters x 8 bits = 88 bits; Huffman = 21 bits (4 distinct symbols)
  'S': x4 -> 0
  'I': x4 -> 11
  'M': x1 -> 100
  'P': x2 -> 101
Symbol Count Code Bits (count times code length)
S 4 0 4
I 4 11 8
P 2 101 6
M 1 100 3
Total 11 21

Against 88 bits for the fixed code, the word needs 21 bits, which is 67 bits fewer. These figures count the letters only.

Read the codes from the tree

A code is the sequence of edges from the root to a leaf. A left edge adds a 0 and a right edge adds a 1. The root's left child is the leaf S, so S is 0. The root's right child is the node of weight 7. Its left child is the node of weight 3, whose children are M (left) and P (right), so M is 100 and P is 101. Its right child is I, so I is 11.

The codes are 0, 11, 100 and 101. None of them is the start of another: 0 does not begin 11, 100 or 101, and 11 does not begin 100 or 101. A decoder therefore reads one bit at a time, steps down its tree, and writes a letter when it reaches a leaf. The first leaf it reaches is the only possible answer, so no separator is needed.

MISSISSIPPI encodes to 100110011001110110111, 21 bits. The decoder reads 100 (M), 11 (I), 0 (S), 0 (S), 11 (I), 0 (S), 0 (S), 11 (I), 101 (P), 101 (P) and 11 (I). That is the original word, letter by letter.

What the decoder needs

The 21 bits hold only the data. The decoder must also know which code belongs to which symbol. A compressed file therefore carries the table, or the code lengths that rebuild it, or the codes are fixed in advance. That table is overhead, and on a short input it can cost more than the saving. As an illustration, suppose each table entry stores the symbol in 8 bits and its code length in 3 bits. The two-letter word AB takes 16 bits raw. Its codes are 0 and 1, so the data takes 2 bits, but the table takes two entries of 11 bits, 22 bits in all. The total is 24 bits, so the file grows. This header format is invented for the arithmetic. Real formats store their tables differently.

Whole bits, and what comes closer

Every Huffman code has a whole number of bits. The Wikipedia article on Huffman coding notes that a prefix code can only use an integer number of bits per symbol, so it matches a symbol's probability exactly only when that probability is one-half raised to a whole power. Other probabilities are not represented optimally.

The MISSISSIPPI counts show the gap. The Shannon entropy of a source is the expected value of minus the base-2 logarithm of each symbol's probability. Computed from these counts, it is about 1.82 bits per letter. Huffman averages 21 divided by 11, about 1.91 bits per letter. Arithmetic coding does not assign whole bits to symbols, so it can get closer to the entropy limit. Jarek Duda's 2013 paper on asymmetric numeral systems (ANS) describes arithmetic coding as "easily approaching theoretical compression rate limit (Shannon entropy)" and Huffman coding as one that "approximates probabilities with powers of 2". ANS aims for the speed of Huffman coding with a rate close to arithmetic coding.

Zstandard uses both families. RFC 8878 says Huffman codes compress the literals, while Finite State Entropy, an entropy codec based on ANS, handles all the other symbols: the literal length, match length and offset codes.

Where Huffman coding is used

DEFLATE, the format inside ZIP, gzip and PNG, uses Huffman codes for its literal, length and distance symbols. RFC 1951 defines each code by its bit lengths alone. A dynamic block stores those lengths, and the decoder assigns consecutive values to codes of each length to rebuild the same codes. Codes built this way are called canonical (section 3.2.2). A fixed block needs no stored codes, because the format defines them in advance (section 3.2.6).

JPEG and MP3 are lossy formats. They quantize their values, which loses detail, and then apply prefix codes. JPEG's baseline mode uses Huffman tables. RFC 2435 points to the standard tables in Annex K.3 of the JPEG standard, ITU-T T.81. MP3 also stores its quantized values with Huffman codes, as the Huffman routine in the minimp3 decoder shows. Wikipedia notes that most applications of these prefix codes use predefined tables. For the difference between lossy and lossless steps, see lossless vs lossy compression.

Huffman's paper, "A Method for the Construction of Minimum-Redundancy Codes", appeared in the Proceedings of the IRE in 1952, pages 1098 to 1101. Huffman wrote it as a Sc.D. student at MIT. For the bigger picture, read how file compression works. The next step in DEFLATE, pointers back into earlier text, is covered in LZ77 and DEFLATE. For choosing an archive format, see the file archivers ranking.

Sources

Keep learning

All lessons
1:24Beginner · 5 min readHow file compression worksSee how lossless compression shrinks files with run-length encoding, Huffman coding and LZ77 pointers, and why ZIP, gzip and PNG all rely on DEFLATE.1:26Intermediate · 6 min readLZ77 and DEFLATE: how ZIP, gzip and PNG compressLearn how LZ77 pointers, DEFLATE blocks and Huffman codes work together, why a pointer can overlap its own output, and how ZIP differs from tar.gz.1:26Beginner · 7 min readLossless vs lossy compression: what gets thrown awayLossless compression gives back every byte. Lossy compression discards detail on purpose. See what JPEG and MP3 drop, why re-saving hurts, and what to keep.

Related guides

All articles