Arithmetic Coding

Every classic compressor faces a quiet tax. Huffman coding is optimal if you insist on giving each symbol its own bit-string — but a bit-string has a whole number of bits. If a symbol's ideal length is 1.3 bits, Huffman has to round up to 2, and that rounding adds up over millions of symbols.

Arithmetic coding simply refuses to play that game. Instead of a codeword per symbol, it represents the entire message as a single number in the interval [0, 1). Each symbol narrows the interval in proportion to its probability, and at the end you write down enough binary digits to pin down a point inside the final sub-interval.

The payoff: the average cost approaches the message's true entropy — the theoretical floor set by Claude Shannon in 1948 — including fractional bits per symbol. Where Huffman rounds, arithmetic coding glides.

Pick one of the sample messages (or type your own using a, b and c). Each symbol carves the current interval into slices sized by its probability, and we keep only the slice for the symbol we just read. Watch [low, high) close in.

<p class="hint">{{hint}}</p>
<div class="msgrow">
  <label for="msg">{{msg_label}}</label>
  <input id="msg" type="text" value="abca" maxlength="12" spellcheck="false" />
</div>
<div class="samples">
  <button type="button" data-m="abca" class="ghost">abca</button>
  <button type="button" data-m="aaab" class="ghost">aaab</button>
  <button type="button" data-m="cccc" class="ghost">cccc</button>
  <button type="button" data-m="abcabc" class="ghost">abcabc</button>
</div>
<p class="probs">{{probs}}</p>
<div id="bars" class="bars"></div>
<div class="status" id="status">{{status_init}}</div>
<div class="btns">
  <button id="step" type="button">{{btn_step}}</button>
  <button id="all" type="button">{{btn_encode_all}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<pre id="out" class="out"></pre>

* { 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; }
.msgrow { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; margin: .3rem 0; }
.msgrow label { font-size: .9rem; font-weight: 600; }
#msg { font: 600 15px ui-monospace, monospace; padding: .35rem .5rem; border: 1px solid #cdd9e3;
       border-radius: 7px; width: 9rem; letter-spacing: 2px; }
.samples { display: flex; gap: .4rem; flex-wrap: wrap; margin: .2rem 0 .4rem; }
.probs { font-size: .82rem; color: #1d3557; font-weight: 600; margin: .2rem 0 .6rem; }
.bars { display: flex; flex-direction: column; gap: 4px; margin: .4rem 0; }
.bar { position: relative; height: 30px; background: #eef2f6; border: 1px solid #d6dee6;
       border-radius: 6px; overflow: hidden; }
.seg { position: absolute; top: 0; height: 100%; display: flex; align-items: center;
       justify-content: center; font: 700 12px ui-monospace, monospace; color: #1d3557;
       border-right: 1px solid rgba(255,255,255,.7); }
.seg.a { background: #a8d5b5; } .seg.b { background: #f4d58d; } .seg.c { background: #f3a6a6; }
.seg.pick { outline: 2px solid #1d3557; outline-offset: -2px; z-index: 2; }
.barlabel { font: 600 12px ui-monospace, monospace; color: #555; margin: 2px 0; }
.status { font-size: .98rem; font-weight: 600; margin: .55rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
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; padding: .3rem .6rem; }
.out { font: 600 12.5px ui-monospace, monospace; background: #0f1d2e; color: #d7e3f0;
       padding: .6rem .7rem; border-radius: 8px; white-space: pre-wrap; margin: .6rem 0 0;
       line-height: 1.5; min-height: 2em; }

// Code not found

At the end, any number inside the final interval decodes back to the original message — so we report the midpoint as the fraction that encodes everything. Notice how a longer or more "surprising" message produces a tinier interval, which needs more binary digits to name: that digit count is essentially the compressed size, and it tracks the message's entropy, fractional bits and all.

How good is arithmetic coding, really? This is one of the solved corners of computation.

• Status: solved and optimal. Practical arithmetic coding was developed in the 1970s–80s; the classic implementation is Witten, Neal & Cleary (1987), building on ideas from Elias, Rissanen and Pasco. For a given probability model it provably reaches within about 2 bits of the total entropy of the message — not per symbol, total.
• It beats Huffman whenever symbols don't have power-of-two probabilities. Huffman's overhead is up to nearly 1 bit per symbol; arithmetic coding's overhead is a tiny constant for the whole file.
• Cost is linear. Encoding and decoding both run in $O(n)$ time for an n-symbol message, using only fixed-precision integer arithmetic in real implementations (the infinite-precision fractions here are just for intuition).
• The floor is real. No lossless coder can beat the entropy defined by Shannon; arithmetic coding's whole point is that it gets essentially all the way there.

So unlike the open and impossible problems elsewhere on KipuHub, there is nothing left to discover here about how well you can do — only engineering about how fast. The remaining cleverness (range coding, the modern ANS / asymmetric numeral systems) is about speed and integer tricks, not about beating the bound.

Arithmetic coding (and its faster cousins) is the silent entropy stage at the end of almost every serious compressor:

• Images: JPEG's optional arithmetic mode and JPEG 2000 use it to squeeze the last bits out of pixel data.
• Video: H.264 and H.265 ship CABAC (Context-Adaptive Binary Arithmetic Coding), a major reason modern streams look good at low bitrates.
• General compression: range coding and ANS — the descendant inside Zstandard and used by Facebook, Apple and the LZMA family — power everyday archives and game assets.
• Prediction = compression: pairing arithmetic coding with a strong predictive model (including neural ones) gives state-of-the-art results, which is why language models and compression are now deeply linked.

Anywhere you have good probabilities, arithmetic coding turns them into bits with almost no waste. It is the practical bridge from a model of the data to the theoretical compression limit.

Arithmetic coding is a small revelation: the best way to store a message isn't to spell out each symbol, but to point at a single number so precisely that only your message lands there. Each symbol shaves the interval; the final fraction is the file.

By dropping the "whole bits per symbol" rule that limits Huffman, it slides right up against Shannon's entropy — the proven floor of lossless compression. There is no clever trick waiting to beat that floor; this is settled territory. What remains is the everyday magic of it running, invisibly, inside the compression at the heart of your photos, your video calls, and your downloads.