Huffman Coding

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.

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">{{hint}}</p>
<input id="txt" type="text" maxlength="40" value="abracadabra" />
<div class="btns">
  <button id="build" type="button">{{btn_build}}</button>
  <button id="ex" type="button" class="ghost">{{btn_example}}</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; }

// Code not found

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.

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

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.

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.