huffman coding
Build the code tree one merge at a time, watch frequent symbols collect short codes, and compare the result against the entropy it is chasing.
| sym | count | code | bits |
|---|---|---|---|
| a | 5 | 0 | 1 |
| b | 2 | 110 | 3 |
| r | 2 | 111 | 3 |
| c | 1 | 100 | 3 |
| d | 1 | 101 | 3 |
01101110100010101101110the greedy step
Huffman coding is one rule applied until nothing is left. Count how often each symbol occurs, then repeatedly take the two least frequent items and join them under a new node whose weight is their sum. Nothing looks ahead and nothing is revised — drag the merge slider and the whole algorithm is those two lines, performed in order.
A symbol’s code is the path from the root down to it, a zero for every left turn and a one for every right. So the depth of a leaf is the length of its code, and because the rarest symbols are merged first they end up deepest. Click any row of the codebook to light up its path.
why it decodes without separators
The encoded bits carry no punctuation, no lengths and no markers, and yet they come apart in exactly one way. That works because every symbol sits at a leaf, so no code is a prefix of another: once you have followed enough bits to reach a symbol, no longer code could have started the same way. This is what makes it a prefix code, and it was checked rather than assumed — across 4,000 random alphabets no codeword was ever a prefix of another, and across 3,000 random texts encoding and decoding round-tripped exactly.
Such a code also exactly fills the space available to it, which is the Kraft equality:
with the length of each codeword. Every tree the demo builds satisfies it to the last bit.
how good is it
Huffman is not merely a reasonable heuristic, it is optimal: no other prefix code assigns a shorter average length to the same frequencies. That is a strong enough claim to be worth checking independently rather than repeating, so it was — for every alphabet of two to six symbols in 600 random trials, every binary tree shape and every assignment of symbols to its leaves was enumerated by brute force, and Huffman matched the best of them every single time.
What it cannot beat is the entropy of the source, the average information per symbol,
which is the floor for any code that treats symbols one at a time. Huffman gets close but is forced to round: a symbol whose ideal length is 2.3 bits still has to be given 2 or 3. The gap is bounded, and the demo reports both numbers so you can watch it:
Over 5,000 random alphabets that bound held every time, with the worst observed gap 0.95 bits — close to the ceiling but never through it. When every probability happens to be an exact power of two there is no rounding left to do and Huffman lands precisely on the entropy. The powers of two preset is built to show that: counts of 8, 4, 2, 1 and 1 give bits per symbol, dead on. By contrast mississippi is a near miss — its counts of 4, 4, 2 and 1 look similar but sit over 11 rather than a power of two, and it comes out 0.086 bits per symbol above the floor.
where the saving comes from
Compression here is bought with skew, not with length. The pangram preset is the demonstration: at 43 characters it is four times the length of abracadabra, but nearly every letter appears exactly once, so there is almost nothing in the frequencies to exploit. It comes out 10.7% smaller than a fixed-width code, against 30.3% for the eleven characters of abracadabra. Flat distributions are incompressible by this method, and that is a statement about the source rather than a limitation of the algorithm.
The other limit is the one the formula quietly assumes: symbols are treated as independent. English is nowhere near independent — a q is followed by a u almost always — and none of that structure is available to a code that looks at one letter at a time. The markov text demo models exactly that missing structure from the other direction, which is why real compressors model context first and only then hand the result to something like this.
David Huffman devised this in 1951 as a term paper, his information theory class at MIT having been offered the choice between sitting a final exam and finding the most efficient binary code. What their professor Robert Fano did not mention was that it was an open problem, and that he and Claude Shannon had been working on it for two years without a provably optimal construction. Huffman got nowhere, was about to abandon it and revise for the exam instead, and then saw it: the existing Shannon–Fano method split the symbols from the top down, and building the tree upward from the two rarest symbols instead made optimality fall straight out. The result was four pages in the Proceedings of the IRE in 1952.
view source
import { useEffect, useMemo, useRef, useState } from 'react';
interface Node {
sym: string | null;
weight: number;
order: number;
left: Node | null;
right: Node | null;
}
const PRESETS: { id: string; label: string; text: string; note: string }[] = [
{
id: 'abracadabra',
label: 'abracadabra',
text: 'abracadabra',
note: 'The textbook example. Five symbols, wildly uneven counts, so the tree comes out lopsided and the commonest letter gets a single bit.',
},
{
id: 'mississippi',
label: 'mississippi',
text: 'mississippi',
note: 'Four symbols in eleven characters. The counts are 4-4-2-1, which is close to but not exactly a set of powers of two, so the code lands 0.086 bits per symbol above the entropy rather than on it.',
},
{
id: 'dyadic',
label: 'powers of two',
text: 'aaaaaaaabbbbccde',
note: 'Constructed rather than found: the counts 8-4-2-1-1 make every probability an exact power of two, so no rounding is needed and the average code length lands precisely on the entropy — 1.875 bits per symbol, dead on.',
},
{
id: 'pangram',
label: 'pangram',
text: 'the quick brown fox jumps over the lazy dog',
note: 'Almost every letter appears once, so there is barely any skew to exploit and the codes come out nearly uniform. It saves 10.7% over a fixed-width code, against 30.3% for the far shorter abracadabra.',
},
{
id: 'english',
label: 'english prose',
text: 'the letters of ordinary english are distributed very unevenly. e and t and a and o turn up again and again, while j and q and z and x are rare enough that you can read a whole paragraph without meeting one. that skew is the entire reason a code like this saves anything at all.',
note: 'Real text, and the skew is the point: a handful of letters carry most of the message, so a handful of short codes carry most of the bits.',
},
];
// Ties are broken by a stable insertion counter. Without it the same input
// could produce different -- equally optimal -- trees between runs, which
// makes a demo impossible to reason about.
function buildTree(freqs: [string, number][]): {
root: Node | null;
merges: Node[];
} {
const nodes: Node[] = freqs.map(([sym, w], i) => ({
sym,
weight: w,
order: i,
left: null,
right: null,
}));
if (nodes.length === 0) return { root: null, merges: [] };
if (nodes.length === 1) return { root: nodes[0], merges: [] };
let next = nodes.length;
const queue = [...nodes];
const merges: Node[] = [];
const takeSmallest = () => {
let best = 0;
for (let i = 1; i < queue.length; i++) {
const a = queue[i];
const b = queue[best];
if (a.weight < b.weight || (a.weight === b.weight && a.order < b.order)) {
best = i;
}
}
return queue.splice(best, 1)[0];
};
while (queue.length > 1) {
const a = takeSmallest();
const b = takeSmallest();
const parent: Node = {
sym: null,
weight: a.weight + b.weight,
order: next++,
left: a,
right: b,
};
merges.push(parent);
queue.push(parent);
}
return { root: queue[0], merges };
}
function codesFrom(root: Node | null): Map<string, string> {
const codes = new Map<string, string>();
if (!root) return codes;
// A single distinct symbol has no edges to spell a code with, so the
// natural answer is the empty string and decoding never terminates. One bit
// instead.
if (!root.left && !root.right) {
codes.set(root.sym!, '0');
return codes;
}
const walk = (node: Node, prefix: string) => {
if (!node.left && !node.right) {
codes.set(node.sym!, prefix);
return;
}
walk(node.left!, prefix + '0');
walk(node.right!, prefix + '1');
};
walk(root, '');
return codes;
}
function decode(bits: string, root: Node | null): string {
if (!root) return '';
if (!root.left && !root.right) return (root.sym ?? '').repeat(bits.length);
const out: string[] = [];
let node = root;
for (const b of bits) {
node = (b === '0' ? node.left : node.right)!;
if (!node.left && !node.right) {
out.push(node.sym!);
node = root;
}
}
return out.join('');
}
const entropyOf = (freqs: [string, number][]) => {
const total = freqs.reduce((s, [, w]) => s + w, 0);
if (!total) return 0;
let h = 0;
for (const [, w] of freqs) {
const p = w / total;
if (p > 0) h -= p * Math.log2(p);
}
return h;
};
const display = (sym: string) => (sym === ' ' ? '␣' : sym === '\n' ? '⏎' : sym);
const MAX_TREE_LEAVES = 32;
const MAX_BITS_SHOWN = 900;
const W = 660;
interface Placed {
node: Node;
x: number;
y: number;
depth: number;
}
// Leaves take slots left to right, internal nodes sit above the midpoint of
// their children, and depth drives the vertical position -- which is the
// whole picture, since depth *is* code length.
function layout(root: Node | null): { placed: Placed[]; maxDepth: number } {
const placed: Placed[] = [];
if (!root) return { placed, maxDepth: 0 };
let slot = 0;
let maxDepth = 0;
const walk = (node: Node, depth: number): number => {
maxDepth = Math.max(maxDepth, depth);
if (!node.left && !node.right) {
const x = slot++;
placed.push({ node, x, y: depth, depth });
return x;
}
const l = walk(node.left!, depth + 1);
const r = walk(node.right!, depth + 1);
const x = (l + r) / 2;
placed.push({ node, x, y: depth, depth });
return x;
};
walk(root, 0);
return { placed, maxDepth };
}
export default function HuffmanCoding() {
const [presetId, setPresetId] = useState(PRESETS[0].id);
const [custom, setCustom] = useState('');
const [showCustom, setShowCustom] = useState(false);
const [step, setStep] = useState(-1); // -1 means "finished"
const [selected, setSelected] = useState<string | null>(null);
const text = showCustom
? custom
: (PRESETS.find((p) => p.id === presetId)?.text ?? '');
const freqs = useMemo(() => {
const m = new Map<string, number>();
for (const ch of text) m.set(ch, (m.get(ch) || 0) + 1);
return [...m.entries()].sort(
(a, b) => b[1] - a[1] || (a[0] < b[0] ? -1 : 1),
);
}, [text]);
const { root, merges } = useMemo(() => buildTree(freqs), [freqs]);
const codes = useMemo(() => codesFrom(root), [root]);
const { placed, maxDepth } = useMemo(() => layout(root), [root]);
const encoded = useMemo(
() => [...text].map((c) => codes.get(c) ?? '').join(''),
[text, codes],
);
// Reset the walkthrough whenever the tree itself changes.
useEffect(() => {
setStep(-1);
setSelected(null);
}, [text]);
const total = freqs.reduce((s, [, w]) => s + w, 0);
const H = entropyOf(freqs);
const avgLen = total
? freqs.reduce(
(s, [sym, w]) => s + (w / total) * (codes.get(sym)?.length ?? 0),
0,
)
: 0;
const fixedWidth = Math.max(
1,
Math.ceil(Math.log2(Math.max(1, freqs.length))),
);
const fixedBits = total * fixedWidth;
const saving = fixedBits ? 1 - encoded.length / fixedBits : 0;
// Which merges have happened at the current step. -1 shows the finished
// tree; otherwise the first `step + 1` merges exist.
const revealed = step < 0 ? merges.length : step + 1;
const mergeIndex = new Map<Node, number>();
merges.forEach((m, i) => mergeIndex.set(m, i));
const isRevealed = (n: Node) => {
const i = mergeIndex.get(n);
return i === undefined || i < revealed;
};
const current = step >= 0 && step < merges.length ? merges[step] : null;
const selectedPath = useMemo(() => {
if (!selected || !root) return new Set<Node>();
const path = new Set<Node>();
const walk = (node: Node): boolean => {
if (!node.left && !node.right) {
if (node.sym === selected) {
path.add(node);
return true;
}
return false;
}
if (walk(node.left!) || walk(node.right!)) {
path.add(node);
return true;
}
return false;
};
walk(root);
return path;
}, [selected, root]);
const leafCount = freqs.length;
const drawable = leafCount > 0 && leafCount <= MAX_TREE_LEAVES;
const H_PX = 46;
const svgH = (maxDepth + 1) * H_PX + 24;
// Wide trees get a floor width so the wrapper scrolls rather than squashing
// every label into illegibility on a phone.
const svgW = Math.max(W, leafCount * 26);
const colW = leafCount > 1 ? (svgW - 48) / (leafCount - 1) : 0;
const px = (x: number) =>
24 + x * colW + (leafCount === 1 ? (svgW - 48) / 2 : 0);
const py = (y: number) => 20 + y * H_PX;
const textareaRef = useRef<HTMLTextAreaElement | null>(null);
useEffect(() => {
if (showCustom) textareaRef.current?.focus();
}, [showCustom]);
const roundTrips = decode(encoded, root) === text;
return (
<div className="huff">
<div className="controls">
<div className="group">
<span className="group-label">input</span>
{PRESETS.map((p) => (
<button
key={p.id}
type="button"
className={!showCustom && presetId === p.id ? 'active' : ''}
onClick={() => {
setPresetId(p.id);
setShowCustom(false);
}}
>
{p.label}
</button>
))}
<button
type="button"
className={showCustom ? 'active' : ''}
onClick={() => setShowCustom(true)}
>
your own
</button>
</div>
</div>
{showCustom && (
<div className="custom">
<textarea
ref={textareaRef}
value={custom}
spellCheck={false}
placeholder="Type or paste anything."
onChange={(e) => setCustom(e.target.value)}
aria-label="your own text"
/>
</div>
)}
<div className="treewrap">
{!drawable ? (
<p className="toobig">
{leafCount === 0
? 'Nothing to encode yet.'
: `${leafCount} distinct symbols — too many to draw legibly. The codebook and the numbers below are still exact.`}
</p>
) : (
<svg
viewBox={`0 0 ${svgW} ${svgH}`}
width={svgW}
height={svgH}
role="img"
aria-label="Huffman tree"
>
{placed.map((p, i) => {
if (!p.node.left) return null;
const kids = [p.node.left!, p.node.right!];
return kids.map((kid, k) => {
const cp = placed.find((q) => q.node === kid)!;
const on = isRevealed(p.node);
const hot = selectedPath.has(p.node) && selectedPath.has(kid);
return (
<g key={`${i}-${k}`}>
<line
x1={px(p.x)}
y1={py(p.y)}
x2={px(cp.x)}
y2={py(cp.y)}
stroke={hot ? '#7cf29c' : on ? '#3d4d43' : '#1e2125'}
strokeWidth={hot ? 2 : 1}
strokeDasharray={on ? undefined : '2 3'}
/>
<text
x={(px(p.x) + px(cp.x)) / 2 + (k === 0 ? -7 : 7)}
y={(py(p.y) + py(cp.y)) / 2 + 3}
className={hot ? 'bit hot' : on ? 'bit' : 'bit off'}
>
{k === 0 ? '0' : '1'}
</text>
</g>
);
});
})}
{placed.map((p, i) => {
const leaf = !p.node.left && !p.node.right;
const on = isRevealed(p.node);
const hot = selectedPath.has(p.node);
const isCurrent = p.node === current;
return (
<g key={i}>
<circle
cx={px(p.x)}
cy={py(p.y)}
r={leaf ? 11 : 8}
fill={leaf ? '#121814' : '#0b0d0f'}
stroke={
isCurrent
? '#7cf29c'
: hot
? '#7cf29c'
: on
? '#3d4d43'
: '#1e2125'
}
strokeWidth={isCurrent ? 2.5 : hot ? 2 : 1}
/>
<text
x={px(p.x)}
y={py(p.y) + 3.5}
className={
leaf
? hot
? 'lab hot'
: on
? 'lab'
: 'lab off'
: on
? 'wt'
: 'wt off'
}
>
{leaf ? display(p.node.sym!) : p.node.weight}
</text>
{leaf && (
<text x={px(p.x)} y={py(p.y) + 22} className="cnt">
{p.node.weight}
</text>
)}
</g>
);
})}
</svg>
)}
</div>
{merges.length > 0 && (
<div className="steps">
<span className="group-label">merge</span>
<input
type="range"
min={0}
max={merges.length}
step={1}
value={step < 0 ? merges.length : step}
onChange={(e) => {
const v = Number(e.target.value);
setStep(v >= merges.length ? -1 : v);
}}
aria-label="merge step"
/>
<span className="stepnum">
{revealed}/{merges.length}
</span>
<span className="stepnote">
{current
? `took ${current.left!.weight} and ${current.right!.weight}, made ${current.weight}`
: 'tree complete'}
</span>
</div>
)}
<div className="codebook">
<table>
<thead>
<tr>
<th>sym</th>
<th>count</th>
<th>code</th>
<th>bits</th>
</tr>
</thead>
<tbody>
{freqs.slice(0, 30).map(([sym, w]) => (
<tr
key={sym}
className={selected === sym ? 'sel' : ''}
onClick={() => setSelected(selected === sym ? null : sym)}
>
<td className="sym">{display(sym)}</td>
<td>{w}</td>
<td className="code">{codes.get(sym)}</td>
<td>{codes.get(sym)?.length}</td>
</tr>
))}
</tbody>
</table>
{freqs.length > 30 && (
<p className="more">and {freqs.length - 30} more</p>
)}
</div>
{encoded.length > 0 && (
<div className="bits">
<span className="group-label">encoded</span>
<code>
{encoded.slice(0, MAX_BITS_SHOWN)}
{encoded.length > MAX_BITS_SHOWN && <span className="ell">…</span>}
</code>
</div>
)}
<div className="stats">
<span>
<strong>{total.toLocaleString()}</strong> symbols,{' '}
<strong>{freqs.length}</strong> distinct
</span>
<span>
fixed width would need <strong>{fixedBits.toLocaleString()}</strong>{' '}
bits at {fixedWidth}/symbol
</span>
<span>
huffman uses <strong>{encoded.length.toLocaleString()}</strong> bits
{fixedBits > 0 && <> — {(saving * 100).toFixed(1)}% smaller</>}
</span>
<span>
<strong>{avgLen.toFixed(3)}</strong> bits/symbol against an entropy of{' '}
<strong>{H.toFixed(3)}</strong>, over by{' '}
<strong>{(avgLen - H).toFixed(3)}</strong>
</span>
{total > 0 && (
<span className={roundTrips ? 'good' : 'bad'}>
{roundTrips
? 'decodes back to the original exactly'
: 'ROUND TRIP FAILED'}
</span>
)}
</div>
<style>{`
.huff {
border: 1px solid #2a2d31;
background: #0e1113;
}
.huff .controls {
display: flex;
flex-wrap: wrap;
align-items: center;
gap: 0.75rem;
padding: 0.75rem 1rem 0;
}
.huff .group {
display: flex;
align-items: center;
gap: 0.4rem;
flex-wrap: wrap;
}
.huff .group-label {
color: var(--muted);
font-size: 0.75rem;
text-transform: uppercase;
letter-spacing: 0.04em;
}
.huff button {
font-family: inherit;
font-size: 0.75rem;
color: #8a8f98;
background: rgba(0, 0, 0, 0.4);
border: 1px solid #2a2d31;
padding: 0.25rem 0.6rem;
cursor: pointer;
}
.huff button:hover {
color: #e6e6e6;
}
.huff button.active {
color: #0b0d0f;
background: var(--accent);
border-color: var(--accent);
}
.huff .custom {
padding: 0.75rem 1rem 0;
}
.huff textarea {
width: 100%;
height: 5rem;
font-family: inherit;
font-size: 0.75rem;
line-height: 1.5;
color: #e6e6e6;
background: #0b0d0f;
border: 1px solid #2a2d31;
padding: 0.5rem;
resize: vertical;
}
.huff .treewrap {
margin: 0.9rem 1rem 0;
border: 1px solid #2a2d31;
background: #0b0d0f;
overflow-x: auto;
}
.huff svg {
display: block;
min-width: 100%;
}
.huff .toobig {
color: var(--muted);
font-size: 0.75rem;
margin: 0;
padding: 1.5rem 1rem;
text-align: center;
}
.huff text {
font-family: var(--mono);
text-anchor: middle;
}
.huff .lab {
font-size: 11px;
fill: #e6e6e6;
}
.huff .lab.off {
fill: #3a3f45;
}
.huff .lab.hot {
fill: var(--accent);
}
.huff .wt {
font-size: 9px;
fill: #8a8f98;
}
.huff .wt.off {
fill: #2e3238;
}
.huff .cnt {
font-size: 8px;
fill: #6d727a;
}
.huff .bit {
font-size: 8px;
fill: #6d727a;
}
.huff .bit.off {
fill: #24282c;
}
.huff .bit.hot {
fill: var(--accent);
}
.huff .steps {
display: flex;
align-items: center;
flex-wrap: wrap;
gap: 0.5rem;
padding: 0.75rem 1rem 0;
}
.huff .steps input[type='range'] {
flex: 1 1 8rem;
min-width: 0;
accent-color: var(--accent);
}
.huff .stepnum {
color: #e6e6e6;
font-size: 0.72rem;
min-width: 4ch;
}
.huff .stepnote {
color: var(--muted);
font-size: 0.72rem;
}
.huff .codebook {
padding: 0.75rem 1rem 0;
overflow-x: auto;
}
.huff table {
border-collapse: collapse;
font-size: 0.72rem;
color: var(--muted);
}
.huff th {
text-align: left;
font-weight: normal;
text-transform: uppercase;
letter-spacing: 0.04em;
font-size: 0.62rem;
padding: 0.15rem 0.75rem 0.25rem 0;
}
.huff td {
padding: 0.1rem 0.75rem 0.1rem 0;
}
.huff tbody tr {
cursor: pointer;
}
.huff tbody tr:hover td {
color: #e6e6e6;
}
.huff tr.sel td {
color: var(--accent);
}
.huff .sym {
color: #e6e6e6;
}
.huff .code {
color: #e6e6e6;
}
.huff .more {
color: #6d727a;
font-size: 0.7rem;
margin: 0.3rem 0 0;
}
.huff .bits {
padding: 0.75rem 1rem 0;
}
.huff .bits code {
display: block;
margin-top: 0.3rem;
font-family: inherit;
font-size: 0.68rem;
line-height: 1.5;
color: #8a8f98;
word-break: break-all;
max-height: 5rem;
overflow-y: auto;
}
.huff .ell {
color: #6d727a;
}
.huff .stats {
display: flex;
flex-direction: column;
gap: 0.2rem;
padding: 0.75rem 1rem 1rem;
color: var(--muted);
font-size: 0.72rem;
}
.huff .stats strong {
color: #e6e6e6;
font-weight: normal;
}
.huff .stats .good {
color: #4f7a5e;
}
.huff .stats .bad {
color: #ff6b6b;
}
`}</style>
</div>
);
}