Introduction

Every time you send a photo, stream a song, or zip a folder, something is quietly squeezing the data into fewer bits. The idea is simple: real data is full of redundancy — repeated letters, smooth color gradients, silences — and you can describe the predictable parts more cheaply.

Store the text "aaaaaa" character by character and you waste space; write "6×a" and you've compressed it. Give common letters short codes and rare ones long codes, and English text shrinks by half. This part of the story is a triumph: for coding symbols one at a time, Huffman coding is provably optimal and runs in near-linear time. Compression, in practice, is solved.

But push to the edge and a strange wall appears. What's the absolute shortest description of a given file — the smallest program that could regenerate it? That quantity, its Kolmogorov complexity, turns out to be uncomputable: no algorithm can find it, or even reliably tell you how compressible your data truly is. This article lives on that fault line, between the easy and the impossible.

Squeeze It

Try it. Type some text and the demo builds a Huffman code from your letter frequencies: frequent letters get short bit-codes, rare ones get long codes. It shows the original size (fixed-width bits), the compressed size, and the ratio.

<p class="hint">Type text and the demo builds a <b>Huffman code</b> from your letter frequencies — frequent letters get short bit-codes, rare ones long. Watch it shrink below the raw 8-bits-per-character size, down toward the <b>entropy</b> floor.</p>
<textarea id="text" rows="3" class="ta"></textarea>
<div class="meters">
  <div class="m"><span>Original (8 bits/char)</span><b id="orig">—</b></div>
  <div class="m"><span>Huffman compressed</span><b id="comp" class="good">—</b></div>
  <div class="m"><span>Saved</span><b id="ratio" class="good">—</b></div>
  <div class="m"><span>Entropy floor</span><b id="ent">—</b></div>
</div>
<div class="codes" id="codes"></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 .8rem; line-height: 1.45; }
.ta { width: 100%; font: 600 14px ui-monospace, monospace; padding: .6rem; border: 1px solid #cdd9e2; border-radius: 8px; resize: vertical; }
.meters { display: flex; gap: .6rem; flex-wrap: wrap; margin: .8rem 0; }
.m { flex: 1; min-width: 120px; background: #f6f8fa; border: 1px solid #e6e9ee; border-radius: 10px; padding: .55rem .7rem; }
.m span { display: block; font-size: .76rem; color: #777; }
.m b { font: 800 18px ui-monospace, monospace; color: #1d3557; }
.good { color: #0a7d33 !important; }
.codes { display: flex; flex-wrap: wrap; gap: .35rem; }
.code { font: 700 12px ui-monospace, monospace; background: #f1f3f5; border-radius: 6px; padding: .2rem .45rem; color: #1d3557; }
.code .ch { color: #c0392b; }
.code .bits { color: #457b9d; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Huffman coding: build an optimal prefix code from symbol frequencies.
// Frequent letters -> short codes. Optimal for symbol coding (O(n log n));
// it approaches but never beats the Shannon entropy floor.
function huffman(s) {
  const f = {}; for (const c of s) f[c] = (f[c] || 0) + 1;
  const syms = Object.keys(f);
  if (syms.length === 0) return { code: {}, bits: 0 };
  if (syms.length === 1) { const code = {}; code[syms[0]] = '0'; return { code, bits: s.length }; }
  let nodes = syms.map(c => ({ c, w: f[c] }));
  while (nodes.length > 1) {
    nodes.sort((a, b) => a.w - b.w);
    const a = nodes.shift(), b = nodes.shift();
    nodes.push({ w: a.w + b.w, l: a, r: b });
  }
  const code = {};
  (function walk(n, p) { if (n.c !== undefined) { code[n.c] = p || '0'; return; } walk(n.l, p + '0'); walk(n.r, p + '1'); })(nodes[0], '');
  let bits = 0; for (const c of s) bits += code[c].length;
  return { code, bits };
}
function entropy(s) { const f = {}; for (const c of s) f[c] = (f[c] || 0) + 1; let h = 0; for (const k in f) { const p = f[k] / s.length; h -= p * Math.log2(p); } return h; }
const show = c => c === ' ' ? '␣' : c === '\n' ? '⏎' : c;

function run() {
  const s = document.getElementById('text').value;
  if (!s) { document.getElementById('codes').innerHTML = ''; ['orig','comp','ratio','ent'].forEach(id=>document.getElementById(id).textContent='—'); return; }
  const r = huffman(s); const orig = s.length * 8;
  document.getElementById('orig').textContent = fmt('%orig% bits', { orig: orig });
  document.getElementById('comp').textContent = fmt('%bits% bits', { bits: r.bits });
  document.getElementById('ratio').textContent = Math.max(0, Math.round((1 - r.bits / orig) * 100)) + '%';
  document.getElementById('ent').textContent = fmt('%entropy% b/char', { entropy: entropy(s).toFixed(2) });
  const entries = Object.entries(r.code).sort((a, b) => a[1].length - b[1].length);
  document.getElementById('codes').innerHTML = entries.map(([ch, bits]) =>
    '<span class="code"><span class="ch">' + show(ch) + '</span> <span class="bits">' + bits + '</span></span>').join('');
}

document.getElementById('text').value = 'abracadabra abracadabra';
document.getElementById('text').addEventListener('input', run);
run();
Result
Console

Repetitive or skewed text (lots of the same few letters) compresses dramatically; random, uniform text barely shrinks. Notice the compressed size hugging a floor — the Shannon entropy of your text. That floor is a real theorem: you can reach it, but for symbol coding you can't beat it.

The Limit

Compression spans the full range of this site — from solved to impossible:

  • Symbol coding is solved. Huffman coding is provably optimal among prefix codes, built in O(nlog⁡n)O(n \log n); arithmetic coding does even better by fractions of a bit. Easy and exact.
  • There's an information floor. Shannon's entropy sets the minimum average bits per symbol for a given source. You can approach it, not beat it — a clean, computable limit.
  • You can't compress everything. A simple counting argument (pigeonhole): no lossless scheme can shrink every input — if some files get smaller, others must get larger. "Compress any file by 10%, repeatedly" is impossible.
  • The ultimate limit is uncomputable. The shortest possible description of a file — the smallest program that outputs it — is its Kolmogorov complexity. It's not computable: no algorithm can find it, and deciding whether a string is "compressible at all" reduces to the halting problem. The perfect compressor cannot exist.
  • Lossy trades fidelity. JPEG, MP3 and video codecs throw away detail your senses won't miss — a different game, optimized perceptually.

So compression is the rare topic where the everyday version is a textbook win and the idealized version is provably out of reach.

Where It Matters

Compression is one of the most-run computations on Earth:

  • Streaming: video and audio codecs (H.264/AV1, AAC) make Netflix and Spotify possible over real networks.
  • The web: gzip/Brotli shrink every page, script and style you load.
  • Storage and backups: filesystems and archives pack more into every drive.
  • Images: JPEG, PNG and WebP balance size against quality on billions of photos.
  • Genomics and science: compressing massive datasets to store and move them at all.

Because a few percent saved scales across the entire internet, compression research is continuous — and every byte you don't send is a small dividend of these ideas.

Conclusion

Compression is two stories in one. Up close it's a victory: Huffman codes are optimal, entropy tells you exactly how far you can go, and the codecs built on these ideas quietly run the internet. Step back to the ideal — the shortest possible description of anything — and you hit an uncomputable wall, a cousin of the halting problem hiding inside a zip file.

That contrast is the whole point. The same subject can be a solved, everyday tool and a window onto the absolute limits of computation. We compress the world beautifully without ever knowing the perfect answer — and, it turns out, we never can.

Share this article

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

Comments

Loading comments...

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