Huffman Coding Principle: The Foundation of Compression Algorithms

Bottom line: Huffman coding is an optimal prefix variable-length code. The core idea is "high-frequency characters get short codes, low-frequency characters get long codes," generating a code table by building a Huffman tree to minimize overall encoding length. Taking the 11-character string "ABRACADABRA" as an example, fixed-length encoding requires 33 bits, while Huffman encoding needs only 23 bits, saving 30%. Huffman coding is a core component of mainstream compression formats like DEFLATE (ZIP/GZIP/PNG), and virtually all lossless compression algorithms include this stage. Below we start from frequency counting, progressively demonstrating Huffman tree construction and code generation.

If you're not yet familiar with the difference between lossless and lossy compression, we recommend first reading Lossless vs Lossy Compression: Key Differences.

1. Why Variable-Length Coding Is Needed

Computers typically store characters using fixed-length encoding, such as ASCII with 8 bits per character or Unicode with 16–32 bits per character. Fixed-length encoding offers convenient random access but is wasteful — in English text, the letter e appears at about 12.7% frequency while z is only 0.07%, yet both use the same code length. Variable-length encoding assigns different-length codewords based on character frequency: higher frequency means shorter codes, thereby compressing the overall size.

Encoding Method	Principle	Codeword Length	Decoding Ambiguity	Typical Application
Fixed-length	Fixed N bits per character	Fixed	Unambiguous	ASCII, Unicode
Variable-length (non-prefix)	Different lengths by frequency	Variable	Potentially ambiguous	Not practical
Huffman prefix coding	Frequency-based + prefix constraint	Variable	Unambiguous	DEFLATE, JPEG
Arithmetic coding	Entire message mapped to a number	Fractional	Unambiguous	ZSTD, brotli

The key constraint of Huffman coding is the "prefix code" property: no character's code is a prefix of another character's code. For example, if character A is encoded as "0", then all other characters' codes cannot start with "0" — they must start with "1". This way, during decoding, bits are read one at a time, and a complete codeword is immediately decoded without ambiguity.

2. Huffman Coding Principle in Detail

Huffman code generation involves three steps: frequency counting, building the Huffman tree, and generating the code table. The entire process is a greedy algorithm — each time the two lowest-frequency nodes are selected and merged, ultimately forming an optimal binary tree.

2.1 Frequency Counting

The first step is to count the frequency of each character in the input data. Using "ABRACADABRA" as an example, we first count each character's occurrences.

Character	Count	Frequency (%)	Fixed-length (3-bit)
A	5	45.5%	000
B	2	18.2%	001
R	2	18.2%	010
C	1	9.1%	011
D	1	9.1%	100

With 5 character types, fixed-length encoding requires ceil(log2(5))=3 bits/character, totaling 33 bits for 11 characters. Note that ASCII encoding would need 11×8=88 bits, so 3-bit fixed-length already saves 70%, but Huffman can compress further.

2.2 Building the Huffman Tree

Building the Huffman tree is a greedy process: each time the two lowest-frequency nodes are selected from all nodes and merged into a new node whose frequency is the sum of both. This repeats until only one root node remains.

Step	Operation	Two Lowest Nodes Before Merge	New Node After Merge	Remaining Nodes
1	Merge C(1) and D(1)	C:1, D:1	CD:2	A:5, B:2, R:2, CD:2
2	Merge B(2) and R(2)	B:2, R:2	BR:4	A:5, CD:2, BR:4
3	Merge CD(2) and BR(4)	CD:2, BR:4	CDBR:6	A:5, CDBR:6
4	Merge A(5) and CDBR(6)	A:5, CDBR:6	Root:11	Complete

After construction, starting from the root, left branches are labeled 0 and right branches 1. The path to each leaf node gives that character's Huffman code. The highest-frequency character A (5 occurrences) is at the second level of the tree with only a 1-bit code; the lowest-frequency C and D are at the deepest level with 3-bit codes.

2.3 Generating the Code Table

Traverse from the root to each leaf node, recording the 0/1 sequence along the path to obtain the code table.

Character	Frequency	Huffman Code	Code Length	Bit Contribution
A	5	0	1	5×1=5
B	2	100	3	2×3=6
R	2	101	3	2×3=6
C	1	110	3	1×3=3
D	1	111	3	1×3=3

Verifying the prefix code property: A's code "0" is not a prefix of any other code; B "100", R "101", C "110", and D "111" are not prefixes of each other. During decoding, bits are read one at a time — encountering "0" means A, and encountering "1" requires reading two more bits to distinguish B/R/C/D, with no ambiguity.

3. Case Study: "ABRACADABRA" Encoding Comparison

Now let's use the generated code table to fully encode "ABRACADABRA" and compare the size difference between fixed-length and Huffman encoding.

Original text: A B R A C A D A B R A (11 characters)

Encoding process:

Position	Character	Huffman Code	Cumulative Bits
1	A	0	1
2	B	100	4
3	R	101	7
4	A	0	8
5	C	110	11
6	A	0	12
7	D	111	15
8	A	0	16
9	B	100	19
10	R	101	22
11	A	0	23

Encoding efficiency comparison:

Encoding Method	Bits/Char	Total Bits	Total Bytes	vs ASCII Compression
ASCII	8	88	11	— (baseline)
Fixed 3-bit	3	33	5	62.5%
Huffman	2.09 (avg)	23	3	73.9%
Theoretical entropy bound	2.04	22.5	3	74.4%

Result: Huffman encoding compresses the 11 characters from 88 bits in ASCII to 23 bits, saving 73.9%. Even compared to 3-bit fixed-length encoding, it saves 30%. The theoretical entropy bound is 22.5 bits, so Huffman encoding is only 0.5 bits above the theoretical optimum, achieving 97.8% efficiency. This is why Huffman coding is called the "optimal prefix code."

4. Huffman Coding in Mainstream Compression Algorithms

Huffman coding is rarely used alone; it typically serves as the final stage of a compression pipeline — entropy coding. First, dictionary algorithms like LZ77 eliminate repetitive patterns, then Huffman coding applies frequency-based compression to the residual data. The table below lists how Huffman is applied in mainstream compression formats.

Compression Format	Dictionary Stage	Entropy Coding Stage	Huffman Variant	Typical Ratio
DEFLATE (ZIP/GZIP)	LZ77	Huffman	Static + dynamic Huffman	50%–70%
PNG	LZ77	Huffman	DEFLATE built-in Huffman	50%–75%
JPEG	DCT transform	Huffman	Separate DC/AC coefficient encoding	10:1 (visually lossless)
ZSTD	LZ77 variant	FSE/Huffman	FSE + Huffman hybrid	60%–80%
brotli	LZ77 + context	Huffman + arithmetic	Context Huffman	65%–85%
BZIP2	BWT transform	Huffman	Multi-table Huffman	70%–85%

For detailed principles of LZ77 dictionary compression, see LZ77 Algorithm Explained: How Dictionary Compression Works. For the specific application of DEFLATE in PNG format, see PNG Compression Principle in Detail.

5. FAQ

Q1: What is Huffman coding?

Huffman coding is an optimal prefix variable-length coding method, proposed by David Huffman in 1952. The core idea: high-frequency characters use short codes, low-frequency characters use long codes, minimizing overall encoding length. It generates a code table by building a Huffman tree, ensuring that no character's code is a prefix of another's (prefix code property), so decoding is unambiguous.

Q2: Why is Huffman coding the optimal prefix code?

The optimality of Huffman coding is based on a greedy strategy: each time the two lowest-frequency nodes are merged, with low-frequency nodes placed deep in the tree (long codes) and high-frequency nodes near the top (short codes). It can be mathematically proven that for a given character frequency distribution, the expected code length of Huffman coding is no greater than that of any other prefix coding, achieving the theoretical lower bound of entropy coding (source entropy H). In the ABRACADABRA example, Huffman coding uses 23 bits, the theoretical entropy bound is 22.5 bits, and efficiency is 97.8%.

Q3: What is the difference between Huffman coding and arithmetic coding?

Huffman coding encodes at the character level, assigning each character an independent variable-length codeword; arithmetic coding maps the entire message to a fractional number in the [0,1) interval, offering finer encoding granularity. Huffman coding is simple to implement and fast, but limited by character-level encoding and cannot closely approach the source entropy; arithmetic coding achieves higher compression ratios (can approach the entropy value) but has higher computational complexity. DEFLATE uses Huffman, while modern ZSTD/brotli combine both.

Q4: Which compression formats use Huffman coding?

Huffman coding is a core component of DEFLATE (ZIP/GZIP/PNG), used in combination with LZ77; ZSTD uses FSE (Finite State Entropy) as a Huffman alternative with similar principles; brotli and JPEG (DC/AC coefficients) also use Huffman coding. Virtually all mainstream lossless compression formats include Huffman or its variants as the entropy coding stage.

Summary

Huffman coding is the foundation of compression algorithms. The core principle is "high frequency = short codes, low frequency = long codes," generating optimal prefix codes by building a Huffman tree. Using "ABRACADABRA" as an example, 11 characters are compressed from 88 bits in ASCII to 23 bits, achieving 97.8% of the theoretical entropy bound. Huffman coding is present in virtually all mainstream lossless compression formats, combined with LZ77 dictionary algorithms to form classic compression pipelines like DEFLATE/ZSTD.

Three keys to understanding Huffman coding: first, frequency counting determines code length allocation; second, the greedy construction of the Huffman tree guarantees optimality; third, the prefix code constraint ensures unambiguous decoding. Master Huffman coding, and you hold the key to understanding all modern compression algorithms.