Huffman coding: entropy coding with variable-length codes
Huffman coding is the lossless entropy-coding method invented by David Huffman in 1952. Its idea is to give every symbol a bit code whose length depends on how often the symbol appears: frequent symbols get short codes, rare symbols get long codes. Averaged over the data, the common short codes dominate, so the total number of bits is smaller than if every symbol used a fixed-width code.
Huffman is the second stage of DEFLATE: after the first LZ77 stage turns the input into a stream of literals and match tokens, Huffman coding packs that token stream into the fewest bits. It is also the entropy stage behind gzip, and it appears inside PNG and JPEG. Understanding Huffman is what makes the DEFLATE pipeline click into place.
Why variable-length codes save bits
Suppose you store each byte in a flat 8 bits. That is fair only if every byte value is equally likely, which real data almost never is — English text uses space and the letter "e" far more than "z" or "q". Huffman exploits that skew: it assigns the common symbols codes as short as 1 or 2 bits and relegates rare symbols to 9 or 10 bits. The average bits per symbol drops below 8, and for text it can drop a lot.
There is a catch. If codes are variable length and packed back-to-back, the decoder must be able to tell where one ends and the next begins — it cannot rely on a fixed boundary. Huffman solves this with prefix-free codes: no code is a prefix of any other. Read bit by bit, there is exactly one point at which the bits consumed so far match a valid code, so decoding is unambiguous without any separators.
How the code tree is built
Huffman builds the codes from a frequency count. You start with one leaf node per symbol, weighted by its frequency, in a queue. Repeatedly you remove the two least-frequent nodes, join them under a new parent node whose weight is their sum, and put the parent back. When one node remains, it is the root of a binary tree. To get a code, walk from the root to each leaf, appending a 0 for one branch and a 1 for the other. Frequent symbols end up near the root (short codes), rare symbols far down (long codes).
This greedy construction is provably optimal for symbol-by-symbol coding: no other prefix-free code that encodes one symbol at a time uses fewer bits given those exact frequencies. (Better ratios are possible only by coding multiple symbols jointly, which is what arithmetic and range coding do — at much higher cost, and it is the lever LZMA pulls to beat DEFLATE.)
Fixed vs dynamic Huffman in DEFLATE
DEFLATE offers two flavors of Huffman tables. Fixed Huffman uses a table baked into the spec — every reader and writer knows it, so it needs zero overhead, but it assumes a generic frequency distribution that is rarely a good fit for your specific data. Dynamic Huffman transmits a custom table, tuned to this block’s actual symbol frequencies, in the compressed stream itself, then uses it to decode the block. For each block the compressor picks whichever produces the smaller output.
Dynamic tables cost some bits to store the table, but on any block with real skew they earn those bits back and then some, which is why most compressed output in practice uses dynamic Huffman. The block also carries a "final block" flag and a type tag (stored / fixed / dynamic), which is how the decoder knows how to read what follows.
Where Huffman appears beyond ZIP
Huffman is not unique to ZIP. It is the entropy stage in gzip (which is DEFLATE under another name), and it is used inside other formats too: PNG applies it after its filtering step, JPEG Huffman-codes the run-length symbols that come out of its quantized DCT coefficients, and many media codecs lean on it at one stage or another. Wherever the final task is "turn a stream of unevenly-frequent symbols into bits," Huffman or a close relative is usually doing it. In every case it is [lossless](/glossary/lossless-compression) — it only re-encodes symbols more efficiently, never discards them.
Frequently asked questions
What is Huffman coding?
Huffman coding is a lossless entropy-coding method that assigns each symbol a variable-length bit code based on its frequency: common symbols get short codes, rare symbols get long codes. The codes are prefix-free (no code is a prefix of another), so a decoder can read them back-to-back unambiguously. It is the entropy stage of DEFLATE, gzip, and parts of PNG and JPEG.
How does Huffman coding work?
You count how often each symbol appears, put one leaf node per symbol into a queue ordered by frequency, then repeatedly combine the two least-frequent nodes under a new parent until one tree remains. Walking from the root to each leaf yields a bit code (a 0 or 1 per branch); frequent symbols end up near the root with short codes. This greedy construction is optimal for coding one symbol at a time.
Why are Huffman codes prefix-free?
So that variable-length codes packed back to back can still be decoded without separators. If no code is a prefix of any other, then as the decoder reads bits there is exactly one moment when the consumed bits match a complete valid code, so it always knows where one symbol ends and the next begins. The Huffman tree guarantees this property by construction.
What is the difference between fixed and dynamic Huffman in DEFLATE?
Fixed Huffman uses a table hard-coded in the specification, so it needs no overhead but assumes a generic frequency distribution. Dynamic Huffman transmits a custom table, tuned to the block’s actual symbol frequencies, inside the compressed stream. The compressor picks whichever is smaller per block; dynamic usually wins on skewed data after paying the cost of storing the table.
Is Huffman coding lossless?
Yes. Huffman only changes how symbols are represented in bits — it never discards information. Every symbol is re-encoded, just at a length matched to its frequency, so the decompressed output is identical to the input. Combined with the lossless LZ77 stage, this is why DEFLATE and ZIP round-trip byte-for-byte.