Original URL: https://www.uglypear.com/en/blog/huffman-coding-principle.html
Huffman coding is an optimal prefix variable-length encoding scheme. Its core idea is 'high-frequency characters get short codes, low-frequency characters get long codes.' By constructing a Huffman tree to generate the code table, the overall encoded length is minimized. Using the string 'ABRACADABRA' (11 characters) as an example, fixed-length encoding requires 33 bits, while Huffman coding needs only 23 bits — a 30% savings. Huffman coding is a core component of DEFLATE (ZIP/GZIP/PNG) and virtually all lossless compression algorithms include this stage. This article walks through frequency statistics, tree construction, and code table generation step by step.
1. Why Variable-Length Encoding 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. The advantage of fixed-length encoding is convenient random access, but it's highly wasteful — in English text, the letter 'e' appears about 12.7% of the time, while 'z' appears only 0.07%, yet both use the same length encoding, which is clearly unreasonable. Variable-length encoding assigns different length codewords based on character frequency — the higher the frequency, the shorter the codeword — thereby compressing the overall size.
The key constraint of Huffman coding is the "prefix code" property: no character's encoding is a prefix of another character's encoding. For example, if character A is encoded as "0", then no other character's encoding can start with "0" — they must all start with "1". This way, during decoding, bits are read one by one, and when a complete codeword is encountered, it's decoded immediately without ambiguity.
| Encoding Method | Principle | Codeword Length | Decoding Ambiguity | Typical Applications |
|---|---|---|---|---|
| Fixed-length encoding | Fixed N bits per character | Fixed | No ambiguity | ASCII, Unicode |
| Variable-length (non-prefix) | Different lengths by frequency | Variable | Possible ambiguity | Impractical |
| Huffman prefix coding | Frequency-based + prefix code constraint | Variable | No ambiguity | DEFLATE, JPEG |
| Arithmetic coding | Entire message mapped to a number | Fractional | No ambiguity | ZSTD, brotli |
2. Huffman Coding Principle Explained
Huffman code generation involves three steps: frequency statistics, Huffman tree construction, and code table generation. The entire process is a greedy algorithm — each time the two lowest-frequency nodes are selected and merged, ultimately forming an optimal binary tree.
The first step is to count the frequency of each character in the input data. Taking "ABRACADABRA" as an example, we first count the occurrences of each character.
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 require 11×8=88 bits, so fixed 3-bit encoding already saves 70%, but Huffman can compress further.
Huffman tree construction 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 the two. This repeats until only one root node remains.
After construction, starting from the root node, the left branch is labeled 0 and the right branch 1. The path to each leaf node gives that character's Huffman encoding. The highest-frequency character A (5 occurrences) is at the second level of the tree with only a 1-bit code; the lowest-frequency characters C and D are at the deepest level with 3-bit codes.
By traversing from the Huffman tree root to each leaf node and recording the 0/1 sequence along the path, we obtain the code table.
Verifying the prefix code property: A's encoding "0" is not a prefix of any other encoding; B "100", R "101", C "110", D "111" are not prefixes of each other. During decoding, bits are read one by one — encountering "0" means A, encountering "1" requires reading two more bits to distinguish B/R/C/D, with no ambiguity.
| Character | Occurrences | 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 |
3. Practical Case: "ABRACADABRA" Encoding Comparison
Now let's encode "ABRACADABRA" using the generated code table and compare the size differences between fixed-length encoding and Huffman coding.
Original: A B R A C A D A B R A (11 characters)
Results: Huffman encoding compresses 11 characters from 88 bits in ASCII to 23 bits, saving 73.9%. Even compared to fixed 3-bit encoding, it saves 30%. The theoretical entropy lower 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."
| 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 |
4. Huffman Coding in Mainstream Compression Algorithms
Huffman coding is rarely used alone; it typically serves as the final stage of the compression pipeline — entropy coding. First, dictionary algorithms like LZ77 eliminate repeated patterns, then Huffman coding performs frequency compression on the residual data. The table below lists how Huffman is applied in mainstream compression formats.
For detailed principles of LZ77 dictionary compression, refer to LZ77 Algorithm Explained: How Does Dictionary Compression Work? For the specific application of DEFLATE in PNG format, refer to PNG Compression Principle Explained.
| Character | Frequency | Huffman Code | Code Length | Encoding Contribution (bits) |
|---|---|---|---|---|
| A | 5 times | 0 | 1 | 5×1=5 |
| B | 2 times | 100 | 3 | 2×3=6 |
| R | 2 times | 101 | 3 | 2×3=6 |
| C | 1 time | 110 | 3 | 1×3=3 |
| D | 1 time | 111 | 3 | 1×3=3 |
5. Frequently Asked Questions (FAQ)
Q1: What is Huffman coding?
Huffman coding is an optimal prefix variable-length encoding method proposed by David Huffman in 1952. The core idea: characters with high frequency get short codes, characters with low frequency get long codes, thereby minimizing the overall encoding length. It generates a code table by constructing a Huffman tree, ensuring that no character's encoding is a prefix of another character's encoding (prefix code property), so decoding produces no ambiguity.
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 deeper in the tree (longer codes) and high-frequency nodes near the top (shorter codes). Mathematically, it can be proven that for a given character frequency distribution, the expected code length of Huffman coding is no less than that of any other prefix encoding, i.e., it reaches the theoretical lower bound of entropy coding (source entropy H). In the ABRACADABRA example, Huffman coding uses 23 bits, with a theoretical entropy lower bound of 22.5 bits, achieving 97.8% efficiency.
Q3: What's the difference between Huffman coding and arithmetic coding?
Huffman coding encodes at the character level, assigning independent variable-length codewords to each character; arithmetic coding maps an entire message to a fraction in the [0,1) interval, achieving finer encoding granularity. Huffman coding is simple to implement and fast, but limited by character-level encoding, it cannot 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 conjunction with LZ77; ZSTD uses FSE (Finite State Entropy) as a Huffman alternative but 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.
| 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 |
6. Summary
Huffman coding is the cornerstone of compression algorithms. Its core principle is "high frequency gets short codes, low frequency gets long codes," generating optimal prefix codes by constructing a Huffman tree. Taking "ABRACADABRA" as an example, 11 characters are compressed from 88 bits in ASCII to 23 bits, achieving 97.8% of the theoretical entropy lower bound. Huffman coding exists in virtually all mainstream lossless compression formats, combined with LZ77 dictionary algorithms to form classic compression pipelines like DEFLATE/ZSTD.
The key to understanding Huffman coding is three points: first, frequency statistics determine code length allocation; second, the greedy construction of the Huffman tree guarantees optimality; third, the prefix code constraint ensures unambiguous decoding. Mastering Huffman coding gives you the key to understanding all modern compression algorithms.
| Encoding Method | Bits per Character | Total Bits | Total Bytes | vs ASCII Compression |
|---|---|---|---|---|
| ASCII encoding | 8 | 88 | 11 | — (Baseline) |
| Fixed 3-bit encoding | 3 | 33 | 5 | 62.5% |
| Huffman encoding | 2.09 (average) | 23 | 3 | 73.9% |
| Theoretical entropy bound | 2.04 | 22.5 | 3 | 74.4% |
| Compression Format | Dictionary Stage | Entropy Coding Stage | Huffman Variant | Typical Compression 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 encoding for DC/AC coefficients | 10:1 (visually lossless) |
| ZSTD | LZ77 variant | FSE/Huffman | Finite state entropy + Huffman hybrid | 60%–80% |
| brotli | LZ77 + context | Huffman + arithmetic | Context Huffman | 65%–85% |
| BZIP2 | BWT transform | Huffman | Multi-table Huffman | 70%–85% |
FAQ
Q: What is Huffman coding?
A: Huffman coding is an optimal prefix variable-length encoding scheme invented by David Huffman in 1952. Its core idea: high-frequency characters get short codes, low-frequency characters get long codes, minimizing the overall encoded length. It generates the code table by constructing a Huffman tree, ensuring that no character's code is a prefix of another (prefix code property), enabling unambiguous decoding.
Q: Why is Huffman coding considered optimal?
A: Huffman coding's optimality is based on the greedy strategy: merging the two lowest-frequency nodes at each step. Low-frequency nodes end up deeper in the tree (longer codes), high-frequency nodes near the top (shorter codes). Mathematically, for a given character frequency distribution, Huffman coding achieves the minimum expected code length among all prefix codes, approaching the theoretical entropy lower bound. In the ABRACADABRA example, Huffman coding achieves 97.8% of the theoretical entropy bound.
Q: What is the difference between Huffman coding and arithmetic coding?
A: Huffman coding assigns integer-length codes to individual characters. Arithmetic coding maps the entire message to a single number in [0,1), achieving finer granularity. Huffman is simpler, faster, and easier to implement, but cannot approach the entropy bound as closely. Arithmetic coding achieves higher compression ratios but is computationally more expensive. DEFLATE uses Huffman, while modern ZSTD/brotli combine both approaches.
Q: Which compression formats use Huffman coding?
A: Huffman coding is a core component of: DEFLATE (ZIP/GZIP/PNG) — paired with LZ77, JPEG — for DC/AC coefficient encoding, ZSTD — uses FSE (Finite State Entropy) as a Huffman alternative, brotli — uses context-based Huffman, and BZIP2 — uses multi-table Huffman after BWT transform. Virtually all mainstream lossless compression formats include Huffman coding or its variants as the entropy coding stage.
Summary
The key to huffman coding principle: the foundation... lies in identifying the sources of bloat and handling them accordingly. Choose the right compression strategy based on your scenario, prioritizing the largest contributors. SmartSlim can handle all compression steps in one click.
Related:
Top comments (0)