Workspace

Entropy coding: Huffman, arithmetic coding and ANS

3 day streakD

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.

DepthLesson 2 of 620 min

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

  1. 01
    Count

    Count how often each symbol appears.

  2. 02
    Merge the two rarest

    Take the two least frequent nodes and join them under a new parent whose count is their sum.

  3. 03
    Repeat

    Keep merging the two smallest until one tree remains.

  4. 04
    Read codes

    Walk from the root to each leaf, writing 0 for left and 1 for right. That path is the symbol's code.

Figure 2.1

Build a Huffman code from your text

SymbolCountHuffman codeBitsIdeal −log₂ p
a9011.15
b2110143.32
r2111043.32
␠11111054.32
c11111154.32
d1100044.32
k1100144.32
l1101044.32
m1101144.32
z1110044.32
a0b1101r1110a0c11111a0d1000a0b1101r1110a0␠11110a0l1010a0k1001a0z1100a0m1011
8-bit text
160 bits
Huffman
55 bits
Entropy floor
54 bits
The table lists each symbol's count, its Huffman code and its ideal length, −log₂ p. Common symbols get short codes. Compare the encoded size with 8 bits per character and with the entropy floor.

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.

Worked exampleThe cost of whole bits
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.

huffman.tsTypeScript
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

DEFLATE

gzip, zip and PNG use Huffman codes over LZ77 output, with a new code table every block.

Zstandard

zstd uses Huffman for literals and FSE, a table-based ANS, for match lengths and offsets.

Images and video

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.)

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap