Introduction

A computer stores text by giving every character the same number of bits — eight for ASCII, for example. But that is wasteful. In English the letter e turns up constantly while z is rare, yet both get the same eight bits. Why pay full price for a letter that hardly ever appears?

The fix feels obvious once you hear it: give frequent symbols short codes and rare symbols long codes. That is exactly what Morse code did by hand a century ago — e is a single dot, q is a long dash-dash-dot-dash.

The catch is doing it optimally. Among the astronomically many ways to assign short and long codes, which one squeezes a given text into the fewest bits — and can you find it without a forbidding search? In 1952 a graduate student named David A. Huffman answered with a method so simple it fits in a paragraph, and so good it is provably the best any prefix code can do.

Build the Code

Type any short text below. The algorithm counts how often each character appears, then repeatedly takes the two least-frequent symbols and merges them under a new parent node whose weight is their sum. Repeat until a single tree remains; reading 0 for every left branch and 1 for every right branch spells out each symbol's code.

<p class="hint">Type some text. The algorithm counts how often each letter appears, then repeatedly <b>merges the two rarest symbols</b> into a tree. Frequent letters end up with short codes, rare letters with long ones — and the total is provably the smallest any prefix code can achieve.</p>
<input id="txt" type="text" maxlength="40" value="abracadabra" />
<div class="btns">
  <button id="build" type="button">Build Huffman tree</button>
  <button id="ex" type="button" class="ghost">Try "mississippi"</button>
</div>
<div id="codes" class="codes"></div>
<div id="result" class="result"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
input { font: 600 16px ui-monospace, monospace; padding: .45rem .6rem; width: 100%;
        max-width: 260px; border: 1px solid #adb1b8; border-radius: 8px; margin-bottom: .6rem; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .8rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.codes { display: grid; grid-template-columns: repeat(auto-fill, minmax(120px, 1fr));
         gap: 6px; margin: .4rem 0; }
.chip { background: #e8eef3; border: 1px solid #cdd9e3; border-radius: 8px; padding: .35rem .5rem;
        font: 13px ui-monospace, monospace; display: flex; justify-content: space-between; gap: .4rem; }
.chip .sym { font-weight: 700; color: #1d3557; }
.chip .freq { color: #777; }
.chip .bits { color: #0a7d33; font-weight: 700; }
.result { font-size: .95rem; line-height: 1.5; margin-top: .6rem; padding: .6rem .8rem;
          background: #f4f7fa; border-radius: 8px; min-height: 1.4em; }
.result b { color: #1d3557; }
.save { color: #0a7d33; font-weight: 700; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Huffman coding (Huffman, 1952): build the OPTIMAL prefix code.
// Repeatedly pop the two least-frequent nodes from a min-priority queue,
// merge them into a parent whose weight is their sum, push it back. The
// last node standing is the root; left edge = ’0’, right edge = ’1’.
// No code is a prefix of another (prefix-free), so decoding is unambiguous,
// and the resulting code minimizes total bits over all prefix codes.

function huffman(text){
  const freq = {};
  for (const ch of text) freq[ch] = (freq[ch] || 0) + 1;
  const syms = Object.keys(freq);
  if (syms.length === 0) return null;
  // Edge case: a single distinct symbol still needs 1 bit per occurrence.
  if (syms.length === 1) return { codes: { [syms[0]]: '0' }, freq };

  // Min-heap as a sorted array (small input, simplicity over speed).
  let nodes = syms.map(s => ({ sym: s, w: freq[s], l: null, r: null }));
  while (nodes.length > 1){
    nodes.sort((a, b) => a.w - b.w);
    const a = nodes.shift(), b = nodes.shift();
    nodes.push({ sym: null, w: a.w + b.w, l: a, r: b });
  }
  const root = nodes[0];
  const codes = {};
  (function walk(n, code){
    if (n.l === null && n.r === null){ codes[n.sym] = code; return; }
    walk(n.l, code + '0');
    walk(n.r, code + '1');
  })(root, '');
  return { codes, freq };
}

function run(){
  const text = document.getElementById('txt').value;
  const out = huffman(text);
  const codesEl = document.getElementById('codes');
  const resEl = document.getElementById('result');
  codesEl.innerHTML = '';
  if (!out){ resEl.textContent = 'Type some text first.'; return; }
  const { codes, freq } = out;
  const symsSorted = Object.keys(freq).sort((a, b) => freq[b] - freq[a]);
  for (const s of symsSorted){
    const label = s === ' ' ? '␣' : s;
    const chip = document.createElement('div');
    chip.className = 'chip';
    chip.innerHTML = '<span class="sym">' + label + '</span>' +
                     '<span class="freq">x' + freq[s] + '</span>' +
                     '<span class="bits">' + codes[s] + '</span>';
    codesEl.appendChild(chip);
  }
  // Compare against a fixed-width encoding (ceil(log2(#symbols)) bits each).
  const n = text.length;
  const distinct = symsSorted.length;
  const fixedBits = Math.max(1, Math.ceil(Math.log2(distinct))) * n;
  let huffBits = 0;
  for (const s of symsSorted) huffBits += freq[s] * codes[s].length;
  const saved = fixedBits === 0 ? 0 : Math.round((1 - huffBits / fixedBits) * 100);
  resEl.innerHTML =
    fmt('Fixed-width code: <b>%fixedBits% bits</b> (%max% bits x %n% chars).<br>Huffman code: <b>%huffBits% bits</b> — <span class="save">%saved%% smaller</span>, and no shorter prefix code exists.', { fixedBits: fixedBits, max: Math.max(1, Math.ceil(Math.log2(distinct))), n: n, huffBits: huffBits, saved: saved });
  console.log('Huffman:', huffBits, 'bits vs fixed', fixedBits, 'bits | codes', codes);
}

document.getElementById('build').addEventListener('click', run);
document.getElementById('ex').addEventListener('click', () => {
  document.getElementById('txt').value = 'mississippi'; run();
});
run();
Result
Console

Watch what happens: the most common letters bubble up near the root and get short codes, while the rarest sink deep and get long ones. No code is ever a prefix of another — that is what makes the stream decodable — and the total bit count always beats a plain fixed-width encoding. Try mississippi and you will see eleven characters squeezed below what 2-bits-per-letter would cost.

The Real Complexity

Huffman coding is one of the rare happy stories in this collection: the obvious greedy idea turns out to be exactly optimal, and it is fast.

  • It's a greedy algorithm. At each step it makes the locally cheapest move — merge the two rarest symbols — and never looks back. Greed usually only approximates the best answer, but here it hits it dead-on.
  • It's provably optimal. David A. Huffman proved in 1952 that no other prefix code can encode the same symbol frequencies in fewer total bits. The argument is a clean exchange proof: in any optimal tree the two least-frequent symbols can be assumed to be siblings at the deepest level, and merging them reduces the problem to a smaller identical one.
  • It's efficient. Using a min-priority queue (a binary heap), building the tree for n distinct symbols takes only O(nlog⁡n)O(n \log n) time — no exponential search anywhere.
  • The catch: "optimal" means optimal among prefix codes that assign whole bits per symbol. Methods like arithmetic coding can do slightly better by escaping the whole-bit constraint, and the true theoretical floor — Kolmogorov complexity — is uncomputable.

So Huffman sits firmly in the solved column: a problem with a fast algorithm that provably can't be improved within its rules. That is the opposite of the intractable monsters that need P vs NP to even discuss.

Where It Matters

Huffman coding is not a museum piece — it is running on your device right now, probably several times over:

  • ZIP and gzip: the DEFLATE algorithm pairs LZ77 with a Huffman pass to encode the back-references compactly.
  • JPEG and PNG: after the transforms and filters, the leftover symbols are Huffman-coded to finish the squeeze.
  • MP3 audio: quantized frequency coefficients are packed with Huffman tables built into the standard.
  • HTTP/2 headers: the HPACK compression scheme uses a fixed Huffman code to shrink repetitive web headers.

The lesson generalizes far beyond files: whenever some events are far more common than others, spend your cheap representations on the common ones. That principle — and the greedy strategy that nails it — also shows up in scheduling, in building decision trees, and across the optimization problems explored throughout KipuHub.

Conclusion

Huffman coding is a small miracle: an idea simple enough to explain in a sentence, greedy enough that it shouldn't work, and yet provably the best possible prefix code. Seventy years on it is still quietly compressing nearly every photo, song and web page you touch.

It is also a useful counterpoint to the rest of this site. Most problems we explore are stubbornly hard — undecidable, NP-complete, or open. Huffman is the reminder that some problems are completely tamed: a fast algorithm, a clean proof, and nothing left to wish for except the deeper limits set by the theory of compression itself.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/huffman-coding/Content licensed under CC BY-NC 4.0.