Entropy coding: Huffman, arithmetic coding and ANS
Turn probabilities into bits. Build a Huffman code by hand, see where its one-bit minimum wastes space, and learn how arithmetic coding and ANS spend fractions of a bit.
An entropy coder takes symbols and their probabilities and emits bits, giving likely symbols short codes. The codes must be prefix-free: no code is the start of another, so the decoder always knows where one ends without separators.
Building a Huffman code
- 01Count
Count how often each symbol appears.
- 02Merge the two rarest
Take the two least frequent nodes and join them under a new parent whose count is their sum.
- 03Repeat
Keep merging the two smallest until one tree remains.
- 04Read codes
Walk from the root to each leaf, writing 0 for left and 1 for right. That path is the symbol's code.
Build a Huffman code from your text
| Symbol | Count | Huffman code | Bits | Ideal −log₂ p |
|---|---|---|---|---|
a | 9 | 0 | 1 | 1.15 |
b | 2 | 1101 | 4 | 3.32 |
r | 2 | 1110 | 4 | 3.32 |
␠ | 1 | 11110 | 5 | 4.32 |
c | 1 | 11111 | 5 | 4.32 |
d | 1 | 1000 | 4 | 4.32 |
k | 1 | 1001 | 4 | 4.32 |
l | 1 | 1010 | 4 | 4.32 |
m | 1 | 1011 | 4 | 4.32 |
z | 1 | 1100 | 4 | 4.32 |
- 8-bit text
- 160 bits
- Huffman
- 55 bits
- Entropy floor
- 54 bits
Huffman's one-bit floor
Huffman is optimal among codes that give each symbol a whole number of bits. That restriction hurts when one symbol dominates. A symbol with probability 0.9 deserves about 0.15 bits, but Huffman must spend at least 1. In a skewed stream, that is roughly six times the ideal for the most common symbol.
- Source
- A with p = 0.9, B with p = 0.1
- Entropy
- 0.9 × 0.152 + 0.1 × 3.32 ≈ 0.47 bits per symbol
- Best Huffman code
- A =
0, B =1: exactly 1 bit per symbol - Waste
- 1 ÷ 0.47 ≈ 2.1× the floor
Arithmetic coding and ANS close this gap by spending fractional bits per symbol.
Arithmetic coding and ANS
Arithmetic coding represents an entire message as one number in [0, 1). Each symbol narrows the current interval in proportion to its probability; a likely symbol barely narrows it and so costs a fraction of a bit. It reaches the entropy almost exactly but was historically slow and patent-encumbered.
Asymmetric numeral systems, ANS, published by Jarek Duda around 2009, achieves arithmetic coding's compression at Huffman-like speed by keeping its state in a single integer and using table lookups. Zstandard's FSE is a table-based ANS variant. It is a large part of why zstd is both fast and strong.
Go deeperStatic, adaptive and context modelling
A static coder computes probabilities once and sends the table with the data, which is what DEFLATE does per block. An adaptive coder updates probabilities as it goes, so the decoder can mirror the updates and no table is sent.
Context modelling keeps separate probabilities depending on what came before, such as the previous byte. Brotli uses context modelling to choose among several literal codes; strong archivers mix many contexts. Each refinement is a better prediction, which is the whole game.
type Node = { weight: number; symbol?: string; left?: Node; right?: Node };
export function huffmanCodes(text: string): Map<string, string> {
const counts = new Map<string, number>();
for (const ch of text) counts.set(ch, (counts.get(ch) ?? 0) + 1);
let nodes: Node[] = [...counts].map(([symbol, weight]) => ({ symbol, weight }));
if (nodes.length === 1) return new Map([[nodes[0].symbol!, "0"]]);
while (nodes.length > 1) {
nodes.sort((a, b) => a.weight - b.weight); // a heap in real code
const [left, right, ...rest] = nodes;
nodes = [...rest, { weight: left.weight + right.weight, left, right }];
}
const codes = new Map<string, string>();
(function walk(node: Node, path: string) {
if (node.symbol !== undefined) return void codes.set(node.symbol, path);
walk(node.left!, path + "0");
walk(node.right!, path + "1");
})(nodes[0], "");
return codes;
}Real encoders use a priority queue, limit maximum code length, and send canonical codes so the table itself is small.
Where you will meet it
gzip, zip and PNG use Huffman codes over LZ77 output, with a new code table every block.
zstd uses Huffman for literals and FSE, a table-based ANS, for match lengths and offsets.
JPEG uses Huffman coding; modern video codecs use arithmetic coding (CABAC) for the extra efficiency.
Words to know
- Prefix-free code
- No code word is a prefix of another.
- Huffman code
- The optimal whole-bit prefix code for known frequencies.
- Arithmetic coding
- Encoding a whole message as an interval, achieving fractional bits per symbol.
- ANS / FSE
- Asymmetric numeral systems and its table-based form used in zstd.
Check yourself
Answer out loud before you open each one.
Why must codes be prefix-free?
So the decoder can tell where each code ends without separators.
Why did ANS beat Huffman?
Huffman spends whole bits per symbol; ANS spends fractions, approaching entropy, at comparable speed.
A symbol has probability 0.9. How many bits does it deserve?
About 0.15 bits, from −log₂ 0.9.
Try it
Run the Huffman function on a page of your own code. Compute the encoded size in bits and compare it with gzip -9 on the same text. gzip wins: why? (Hint: next lesson.)