Entropy Coding

Every time you save a ZIP file, stream a video, or send a message, a small algorithm decides how many bits each symbol deserves. The goal is always the same: use as few bits as possible without losing any information.

Claude Shannon proved in 1948 that there is a hard floor on how short any lossless code can be. For a symbol with probability p, the ideal code length is −$\log_{2}(p)$ bits — exactly. A coin-flip symbol (p = 0.5) deserves exactly 1 bit. A rare symbol (p = 0.0625) deserves 4 bits. The average across all symbols is the Shannon entropy of the source, and no lossless code can beat it.

Three generations of algorithms have chased that floor:

1. Huffman coding (1952) — assigns whole numbers of bits per symbol. Fast and simple, but whole-bit rounding wastes space whenever the ideal length is not an integer.
2. Arithmetic coding (1970s–80s) — encodes an entire message as a single fraction, achieving the entropy limit to arbitrary precision. Nearly optimal, but the multiplications and divisions make it slow.
3. ANS — Asymmetric Numeral Systems (Jarek Duda, ~2009) — encodes state in a single integer using table lookups, matching arithmetic coding's precision at speeds that rival Huffman coding.

Today ANS powers zstd, lz4, LZFSE, and every frame of video compressed with HEVC or AV1. Understanding why it replaced arithmetic coding means understanding what "reaching the entropy limit" actually costs — and how a clever bijection between integers and bit sequences makes it almost free.

Type any short text below and press Encode. The demo will run all three algorithms and show how many bits each one uses, along with the Shannon entropy lower bound. Watch how Huffman falls short when probabilities are not powers of two, while arithmetic coding and ANS get much closer.

<div class="controls">
  <label for="msg">{{label_text_to_encode}}</label>
  <input id="msg" type="text" value="aaaaabbbcd" maxlength="60" spellcheck="false" />
  <button id="encodeBtn" type="button">{{btn_encode}}</button>
</div>
<div id="results" class="results hidden"></div>
<div id="bars" class="bars hidden"></div>
<p class="note">{{note_hover}}</p>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 14px; }
.controls { display: flex; flex-wrap: wrap; gap: .5rem; align-items: center; margin-bottom: 1rem; }
label { font-size: .9rem; font-weight: 600; }
input { flex: 1 1 160px; padding: .4rem .6rem; border: 1px solid #c0c8d2; border-radius: 6px;
        font: 15px ui-monospace, monospace; min-width: 0; }
button { padding: .4rem 1rem; background: #1d3557; color: #fff; border: none;
         border-radius: 6px; font: 600 14px system-ui; cursor: pointer; white-space: nowrap; }
button:hover { background: #2a4a7f; }
.results { margin-bottom: 1rem; }
.result-row { display: flex; align-items: baseline; gap: .5rem; margin: .3rem 0; font-size: .95rem; }
.label { width: 130px; font-weight: 600; flex-shrink: 0; }
.bits { font-variant-numeric: tabular-nums; color: #1d3557; }
.tag { font-size: .78rem; padding: 1px 6px; border-radius: 4px; background: #e8eef3; color: #555; }
.tag.best { background: #d4edda; color: #155724; }
.bars { display: flex; flex-direction: column; gap: .5rem; margin-top: .5rem; }
.bar-wrap { display: flex; align-items: center; gap: .5rem; }
.bar-label { width: 120px; font-size: .85rem; font-weight: 600; flex-shrink: 0; text-align: right; }
.bar-track { flex: 1; height: 22px; background: #e8eef3; border-radius: 4px; overflow: hidden; position: relative; cursor: default; }
.bar-fill { height: 100%; border-radius: 4px; transition: width .4s; }
.bar-fill.entropy { background: #a8d5a2; }
.bar-fill.huffman { background: #457b9d; }
.bar-fill.arith { background: #e9c46a; }
.bar-fill.ans { background: #2a9d8f; }
.bar-val { font-size: .82rem; color: #444; width: 52px; flex-shrink: 0; }
.note { font-size: .8rem; color: #666; margin-top: .8rem; line-height: 1.45; }
.hidden { display: none; }
.prob-table { margin: .7rem 0; font-size: .85rem; border-collapse: collapse; }
.prob-table th, .prob-table td { padding: 2px 10px; }
.prob-table th { font-weight: 600; border-bottom: 1px solid #ccc; }
.prob-table td { font-variant-numeric: tabular-nums; }

// Code not found

The entropy bound is the theoretical minimum: sum of −p·$\log_{2}(p)$ over all distinct symbols, multiplied by message length. Huffman's output is always ≥ the bound; arithmetic coding and ANS can get within fractions of a bit of it.

Why can't Huffman just be optimal?

• Huffman is optimal among prefix codes — no other assignment of whole-bit codewords gives a shorter average length. David Huffman proved this in 1952.
• The problem is whole bits. If the ideal code for a symbol is 2.3 bits, Huffman must round to 2 or 3. For a source with two symbols at probabilities 0.9 and 0.1, the entropy is only ~0.47 bits/symbol, but the shortest Huffman code still uses 1 bit/symbol — more than twice the limit.
• Arithmetic coding escapes the rounding trap by thinking about the message as a whole. It maps the message to a real number in [0, 1), updating an interval for each symbol. The final interval can be represented as a binary fraction of the right length, achieving entropy to within ~1 bit for the whole message regardless of length.
• The catch: divisions. Each symbol shrinks the interval by multiplying its width by a probability. Real arithmetic means slow hardware division, and patents on arithmetic coding blocked its use for decades.
• ANS keeps the precision, removes the divisions. Jarek Duda's key insight (2009, open-licensed): replace the continuous interval with a discrete integer state. Encoding a symbol with probability p/m replaces state x with ⌊x/p⌋·m + (x mod p) + offset — a table lookup. Decoding is the reverse lookup. The state "encodes" the history of the entire stream in a single integer, just as the interval did in arithmetic coding, but using only integer arithmetic that CPUs execute in a single cycle.
• Precision gap. Huffman wastes up to 1 bit per symbol. Arithmetic coding and ANS waste at most 1 bit per message (plus a small table-rounding overhead in ANS). For a 1 MB file with many symbols this is the difference between 20% overhead and 0.0001% overhead.

See the compression article for how Huffman trees are built. The ANS family includes rANS (range ANS, used in Zstandard) and tANS (table ANS, used in FSE and LZFSE); both are provably entropy-optimal in the limit of long messages.

Entropy coders are invisible but ubiquitous — they are the final stage of almost every compressor in daily use:

• File compression (zstd, brotli, lz4): Zstandard uses rANS (range-ANS) as its entropy back-end. At compression level 3 it beats gzip in both speed and ratio, powered entirely by integer table lookups.
• Video (HEVC / H.265, AV1): HEVC uses CABAC, an arithmetic coder. AV1 uses a faster arithmetic coder. Both codecs depend on near-optimal entropy coding to hit their bitrate targets for 4K streaming.
• Apple's LZFSE: uses tANS (table-ANS), the FSE variant. It is the default compression algorithm on macOS and iOS, chosen over zlib for its speed at comparable ratios.
• Images (JPEG): the original JPEG standard uses Huffman coding for its DCT coefficients. JPEG 2000 and JPEG XL use arithmetic coding and ANS respectively, achieving better ratios at the cost of more complexity.
• Machine learning inference: modern neural network weight files (GGUF, safetensors) use entropy coding to compress quantized weights; ANS variants are preferred for their speed during model loading.

Understanding entropy coding means understanding why there are multiple "optimal" compressors — they trade implementation simplicity (Huffman), extreme precision (arithmetic), and hardware speed (ANS) against each other. The right choice depends on the bottleneck: CPU speed, patent risk, or ratio budget.

Shannon drew a line in 1948 and dared engineers to reach it. Huffman got close but stumbled on fractions. Arithmetic coding crossed it but paid in division latency and patent disputes. ANS crossed it again with nothing but integer table lookups — and opened the door to compressors that are simultaneously optimal and fast enough for real-time use.

The race looks finished from the outside: ANS is in every modern compressor, every video codec, every operating system archiver released in the last decade. But entropy coding is only half the story — a compressor also needs a model that predicts which symbols are likely. The better the model, the closer the entropy bound sits to zero, and the tinier the file. That modeling problem — finding patterns in data — is where the interesting limits of compression still live.