Huffman Coding: Shorter Codes for Common Symbols

in progressThis lesson is still being built - content, demos, and checkpoints may change before release.

Huffman coding

Loading interactive demo…

A text is counted, every symbol becomes a leaf weighing its count on a min-heap, and the two lightest nodes are merged into a parent until one root remains. The path from the root to a leaf, left 0 and right 1, is that symbol's code word: common symbols get short ones, rare symbols long ones, and no code word starts another.Take the tour, or press and explore. Legend:

The panel beside the stage is the real HuffmanCoder class from the published library executing in your browser, with the current line highlighted.

Nodes waiting on the heap, hollow; the heap strip shows their storage order.
The two lightest nodes just popped, in hand.
The node just made or the code word being assigned; the character being counted or encoded.
Leaves whose code word is assigned, and the edges of the finished tree.
The tapped symbol's path from its leaf to the root, and its chips in the text.

symbols counts the distinct characters found so far,heap the nodes waiting, avg bits the bits spent per character encoded so far, entropy the bound for this text, ratio the bits against a fixed-width code. Tap a chip in the text to light its symbol's path.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

Prefix-free codes. A variable-length code is decodable without separators when no code word is a prefix of another. Put the symbols at the leaves of a binary tree and read each path as bits, left $0$ and right $1$ : a leaf is never on the way to another leaf, so the code is prefix-free by construction, and a decoder walks from the root, restarting at every leaf. The cost of a code is its average length,

L = \sum_s p_s \, \ell_s ,

the depth of each leaf weighted by how often its symbol occurs.

Why the greedy merge is optimal. Two facts about an optimal tree: it is full (an internal node with one child could be removed, making its subtree shallower), and the two least frequent symbols can be taken as siblings at the deepest level (swap any deeper leaf with a lighter one and $L$ does not go up). So the two lightest symbols may be merged into one symbol of their combined weight, adding exactly that weight to $L$ ; an optimal code for the smaller alphabet unfolds into an optimal one for the original. Induction on the alphabet size does the rest.

The entropy bound. The entropy lesson showed that no prefix-free code averages fewer than $H = -\sum_s p_s \log_2 p_s$ bits per symbol, and the prefix codes lesson that Shannon's lengths $\lceil -\log_2 p_s \rceil$ satisfy Kraft's inequality and cost less than $H + 1$ . Huffman is at least as good as that code, so it averages less than $H + 1$ too. The whole bit is real, though: a text of one symbol has entropy $0$ and still costs one bit per character, and a symbol with $p = 0.99$ still costs a whole bit. Arithmetic coding closes the gap by coding the text as one long number.

Cost. Counting is $O(n)$ over the text; with $k$ symbols the heap sees $k$ pushes and $k - 1$ merge rounds of two pops and a push, so building the tree is $O(k \log k)$ . The code words are one walk of the $2k - 1$ nodes, and encoding is $O(n)$ again. Sorting the counts once lets the tree be built in $O(k)$ with two queues, the trick real encoders use.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

Every node enters the heap through one private method, so the push counter numbers leaves and merged parents alike, and the trace can name a node by its id before it exists on the stage.
The heap is the graph lessons' BinaryHeap with the node's weight as its priority; ties fall to push order, so the same text always builds the same tree.
The walk emits before it branches, one call site for the assign tag whether the node is a leaf or a parent; a leaf records its code, a parent recurses with the prefix grown by one bit.
A one-symbol text gets the code 0, since a lone root has no path; the decoder handles that tree as a special case and every other tree by walking.
entropyBits is a static on the coder, so the bound the lesson compares against is in the same file as the code that meets it.

In 1951 David Huffman, a graduate student in Robert Fano's information theory course at MIT, was offered a term paper in place of the final exam. The problem was the most efficient binary code for symbols with known frequencies, which Shannon and Fano had each attacked from the top down without a proof of optimality. Huffman was about to give up and study for the exam when the idea came: build the tree from the bottom up, merging the two least frequent symbols first. The 1952 paper made it a standard; the method sits inside DEFLATE, JPEG, and MP3 today.

1948Claude Shannon - Describes a variable-length coding method in 'A Mathematical Theory of Communication'; Fano gives a related top-down method in a 1949 technical report. Neither is always optimal.source
1951David A. Huffman - Given the choice of a term paper or a final exam in an MIT information theory course, works out the bottom-up construction that guarantees an optimal prefix code.source
1952David A. Huffman - Publishes 'A Method for the Construction of Minimum-Redundancy Codes' in the Proceedings of the IRE.source
1996L. Peter Deutsch - RFC 1951 specifies DEFLATE, Phil Katz's PKZIP format, as LZ77 matching followed by Huffman coding; it is what zip, gzip, and PNG use.source
1998IEEE Information Theory Society - Awards Huffman its Golden Jubilee Award for Technological Innovation for 'the invention of the Huffman minimum-length lossless data-compression code'; the IEEE Hamming Medal follows in 1999.source

Used today

DEFLATE - zip, gzip, and PNG code the LZ77 tokens with Huffman codes; the format sends the code lengths, and the decoder rebuilds the tree.
JPEG and MP3 - Both entropy-code their quantised coefficients with prefix codes; most use pre-defined tables rather than a tree built per file.
A building block - Any place symbols have skewed frequencies: text, sensor logs, the tokens of another compressor.

text

skew1.2

symbols: 8 of 8
heap: 0
avg bits: 2.71
entropy: 2.70
ratio: 0.90

huffman-coder.ts

import { BinaryHeap } from "../graphs/binary-heap";import type { Tracer } from "../trace";/** A node of the code tree: a leaf carries a symbol, a parent its two children. */export interface HuffmanNode {  /** The push counter when the node was made: leaves first, then merges. */  id: number;  /** How many characters the node stands for. */  weight: number;  /** The character at a leaf; null on a merged node. */  symbol: string | null;  left: HuffmanNode | null;  right: HuffmanNode | null;}export interface HuffmanResult {  /** Symbol counts, in order of first appearance. */  counts: Map<string, number>;  /** The code tree, null for an empty text. */  root: HuffmanNode | null;  /** Each symbol's code word, a string of 0s and 1s. */  codes: Map<string, string>;  /** The whole text as code words, concatenated. */  bits: string;  /** What a fixed-width code of the same alphabet would cost. */  fixedBits: number;}/** * Huffman coding: count the symbols, put every symbol on a min-heap as a * leaf weighing its count, and repeatedly merge the two lightest nodes * into a parent weighing their sum until one node remains. The root's * paths, left 0 and right 1, are the code words: a common symbol ends up * near the root with a short code, a rare one deep down with a long one, * and no code word is a prefix of another because symbols sit only at * the leaves. Ties on the heap go by push order, so the tree is * deterministic. A one-symbol text gets the single code "0". * * Time: O(n + k log k) for n characters over k symbols. Space: O(k). */export class HuffmanCoder {  private pushes = 0;  constructor(private readonly tracer?: Tracer) {}  /** Shannon entropy of a count table, in bits per symbol: the bound no prefix-free code beats on average. */  static entropyBits(counts: Iterable<number>): number {    const values = [...counts].filter((c) => c > 0);    const total = values.reduce((sum, c) => sum + c, 0);    if (total === 0) return 0;    let bits = 0;    for (const c of values) {      const p = c / total;      bits -= p * Math.log2(p);    }    return bits;  }  encode(text: string): HuffmanResult {    this.pushes = 0;    const counts = new Map<string, number>();    for (let i = 0; i < text.length; i++) {      const symbol = text[i]!;      const count = (counts.get(symbol) ?? 0) + 1;      counts.set(symbol, count);      // ▸ one more of this character      this.tracer?.emit("count", { index: i, symbol, count });    }    // Ties go to the node pushed first: ids count pushes.    const heap = new BinaryHeap<HuffmanNode>((node) => node.weight, (node) => node.id);    for (const [symbol, weight] of counts) {      this.push(heap, { id: this.pushes, weight, symbol, left: null, right: null });    }    while (heap.size > 1) {      const lo = heap.pop()!;      const lighter = heap.pop()!;      const hi = heap.pop()!;      const heavier = heap.pop()!;      // ▸ the two lightest nodes come off      this.tracer?.emit("pop-pair", { leftId: lo.id, rightId: hi.id, leftWeight: lo.weight, rightWeight: hi.weight, remaining: heap.size });      this.tracer?.emit("pop-pair", { leftId: lighter.id, rightId: heavier.id, leftWeight: lighter.weight, rightWeight: heavier.weight, remaining: heap.size });      const parent: HuffmanNode = { id: this.pushes, weight: lo.weight + hi.weight, symbol: null, left: lo, right: hi };      const parent: HuffmanNode = { id: this.pushes, weight: lighter.weight + heavier.weight, symbol: null, left: lighter, right: heavier };      // ▸ a parent weighing both, lighter on the 0 side      this.tracer?.emit("merge", { id: parent.id, weight: parent.weight, leftId: lo.id, rightId: hi.id });      this.tracer?.emit("merge", { id: parent.id, weight: parent.weight, leftId: lighter.id, rightId: heavier.id });      this.push(heap, parent);    }    const root = heap.pop() ?? null;    const codes = new Map<string, string>();    if (root) this.assign(root, "", 0, codes);    let bits = "";    for (let i = 0; i < text.length; i++) {      const symbol = text[i]!;      const code = codes.get(symbol)!;      bits += code;      // ▸ swap each character for its code word      this.tracer?.emit("encode", { index: i, symbol, code, bits: bits.length });    }    const width = Math.max(1, Math.ceil(Math.log2(Math.max(1, counts.size))));    return { counts, root, codes, bits, fixedBits: text.length * width };  }  /** Replays the bits down the tree: a leaf yields its symbol and the walk restarts at the root. Untraced. */  decode(bits: string, root: HuffmanNode | null): string {    if (!root) return "";    let out = "";    // A one-leaf tree has no branches: every bit is that leaf's symbol.    if (!root.left || !root.right) return root.symbol!.repeat(bits.length);    let node = root;    for (const bit of bits) {      node = (bit === "0" ? node.left : node.right)!;      if (node.symbol !== null) {        out += node.symbol;        node = root;      }    }    return out;  }  /** Every node enters the heap here, so the push counter numbers leaves and parents alike. */  private push(heap: BinaryHeap<HuffmanNode>, node: HuffmanNode): void {    this.pushes += 1;    heap.push(node);    // ▸ onto the heap, lightest at the top    this.tracer?.emit("push", { id: node.id, weight: node.weight, symbol: node.symbol, heap: heap.toArray().map((n) => n.id) });  }  /** Walks the finished tree, left 0 and right 1, and records the path at each leaf. */  private assign(node: HuffmanNode, acc: string, depth: number, codes: Map<string, string>): void {  private assign(node: HuffmanNode, prefix: string, depth: number, codes: Map<string, string>): void {    const leaf = node.symbol !== null;    // A lone root has no path; "0" gives it a one-bit code.    const code = leaf && acc === "" ? "0" : acc;    const code = leaf && prefix === "" ? "0" : prefix;    // ▸ the path down from the root is the code word    this.tracer?.emit("assign", { id: node.id, symbol: node.symbol, code, depth });    if (leaf) {      codes.set(node.symbol!, code);      return;    }    this.assign(node.left!, acc + "0", depth + 1, codes);    this.assign(node.left!, prefix + "0", depth + 1, codes);    this.assign(node.right!, acc + "1", depth + 1, codes);    this.assign(node.right!, prefix + "1", depth + 1, codes);  }}

bits =: 46
fixed =: 51
avg bits =: 2.71
entropy =: 2.70
ratio =: 0.90

46 bits against 51 at a fixed width: 2.71 bits per symbol, with the entropy at 2.70. Ratio 0.90.

import { BinaryHeap } from "../graphs/binary-heap";import type { Tracer } from "../trace";/** A node of the code tree: a leaf carries a symbol, a parent its two children. */export interface HuffmanNode { /** The push counter when the node was made: leaves first, then merges. */ id: number; /** How many characters the node stands for. */ weight: number; /** The character at a leaf; null on a merged node. */ symbol: string | null; left: HuffmanNode | null; right: HuffmanNode | null;}export interface HuffmanResult { /** Symbol counts, in order of first appearance. */ counts: Map<string, number>; /** The code tree, null for an empty text. */ root: HuffmanNode | null; /** Each symbol's code word, a string of 0s and 1s. */ codes: Map<string, string>; /** The whole text as code words, concatenated. */ bits: string; /** What a fixed-width code of the same alphabet would cost. */ fixedBits: number;}/** * Huffman coding: count the symbols, put every symbol on a min-heap as a * leaf weighing its count, and repeatedly merge the two lightest nodes * into a parent weighing their sum until one node remains. The root's * paths, left 0 and right 1, are the code words: a common symbol ends up * near the root with a short code, a rare one deep down with a long one, * and no code word is a prefix of another because symbols sit only at * the leaves. Ties on the heap go by push order, so the tree is * deterministic. A one-symbol text gets the single code "0". * * Time: O(n + k log k) for n characters over k symbols. Space: O(k). */export class HuffmanCoder { private pushes = 0; constructor(private readonly tracer?: Tracer) {} /** Shannon entropy of a count table, in bits per symbol: the bound no prefix-free code beats on average. */ static entropyBits(counts: Iterable<number>): number { const values = [...counts].filter((c) => c > 0); const total = values.reduce((sum, c) => sum + c, 0); if (total === 0) return 0; let bits = 0; for (const c of values) { const p = c / total; bits -= p * Math.log2(p); } return bits; } encode(text: string): HuffmanResult { this.pushes = 0; const counts = new Map<string, number>(); for (let i = 0; i < text.length; i++) { const symbol = text[i]!; const count = (counts.get(symbol) ?? 0) + 1; counts.set(symbol, count); // ▸ one more of this character this.tracer?.emit("count", { index: i, symbol, count }); } // Ties go to the node pushed first: ids count pushes. const heap = new BinaryHeap<HuffmanNode>((node) => node.weight, (node) => node.id); for (const [symbol, weight] of counts) { this.push(heap, { id: this.pushes, weight, symbol, left: null, right: null }); } while (heap.size > 1) { const lo = heap.pop()!; const lighter = heap.pop()!; const hi = heap.pop()!; const heavier = heap.pop()!; // ▸ the two lightest nodes come off this.tracer?.emit("pop-pair", { leftId: lo.id, rightId: hi.id, leftWeight: lo.weight, rightWeight: hi.weight, remaining: heap.size }); this.tracer?.emit("pop-pair", { leftId: lighter.id, rightId: heavier.id, leftWeight: lighter.weight, rightWeight: heavier.weight, remaining: heap.size }); const parent: HuffmanNode = { id: this.pushes, weight: lo.weight + hi.weight, symbol: null, left: lo, right: hi }; const parent: HuffmanNode = { id: this.pushes, weight: lighter.weight + heavier.weight, symbol: null, left: lighter, right: heavier }; // ▸ a parent weighing both, lighter on the 0 side this.tracer?.emit("merge", { id: parent.id, weight: parent.weight, leftId: lo.id, rightId: hi.id }); this.tracer?.emit("merge", { id: parent.id, weight: parent.weight, leftId: lighter.id, rightId: heavier.id }); this.push(heap, parent); } const root = heap.pop() ?? null; const codes = new Map<string, string>(); if (root) this.assign(root, "", 0, codes); let bits = ""; for (let i = 0; i < text.length; i++) { const symbol = text[i]!; const code = codes.get(symbol)!; bits += code; // ▸ swap each character for its code word this.tracer?.emit("encode", { index: i, symbol, code, bits: bits.length }); } const width = Math.max(1, Math.ceil(Math.log2(Math.max(1, counts.size)))); return { counts, root, codes, bits, fixedBits: text.length * width }; } /** Replays the bits down the tree: a leaf yields its symbol and the walk restarts at the root. Untraced. */ decode(bits: string, root: HuffmanNode | null): string { if (!root) return ""; let out = ""; // A one-leaf tree has no branches: every bit is that leaf's symbol. if (!root.left || !root.right) return root.symbol!.repeat(bits.length); let node = root; for (const bit of bits) { node = (bit === "0" ? node.left : node.right)!; if (node.symbol !== null) { out += node.symbol; node = root; } } return out; } /** Every node enters the heap here, so the push counter numbers leaves and parents alike. */ private push(heap: BinaryHeap<HuffmanNode>, node: HuffmanNode): void { this.pushes += 1; heap.push(node); // ▸ onto the heap, lightest at the top this.tracer?.emit("push", { id: node.id, weight: node.weight, symbol: node.symbol, heap: heap.toArray().map((n) => n.id) }); } /** Walks the finished tree, left 0 and right 1, and records the path at each leaf. */ private assign(node: HuffmanNode, acc: string, depth: number, codes: Map<string, string>): void { private assign(node: HuffmanNode, prefix: string, depth: number, codes: Map<string, string>): void { const leaf = node.symbol !== null; // A lone root has no path; "0" gives it a one-bit code. const code = leaf && acc === "" ? "0" : acc; const code = leaf && prefix === "" ? "0" : prefix; // ▸ the path down from the root is the code word this.tracer?.emit("assign", { id: node.id, symbol: node.symbol, code, depth }); if (leaf) { codes.set(node.symbol!, code); return; } this.assign(node.left!, acc + "0", depth + 1, codes); this.assign(node.left!, prefix + "0", depth + 1, codes); this.assign(node.right!, acc + "1", depth + 1, codes); this.assign(node.right!, prefix + "1", depth + 1, codes); }}