Introduction

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.

Narrow the Interval

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">Each symbol of the message slices the current interval by its probability and we keep only its slice. After the last symbol, <b>any</b> number inside the final interval decodes back to the whole message. Pick a message and step through it.</p>
<div class="msgrow">
  <label for="msg">Message (use a, b, c):</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">Probabilities: a = 0.5, b = 0.3, c = 0.2</p>
<div id="bars" class="bars"></div>
<div class="status" id="status">Press <b>Step</b> to read the next symbol.</div>
<div class="btns">
  <button id="step" type="button">Step</button>
  <button id="all" type="button">Encode all</button>
  <button id="reset" type="button" class="ghost">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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Arithmetic coding: encode a whole message as ONE number in [0,1).
// Each symbol multiplies the interval [low,high) down to the sub-interval that
// matches its cumulative probability. The final interval’s midpoint encodes the
// entire message; any point inside it decodes back uniquely. Optimal (reaches Shannon entropy within ~2 bits). Witten, Neal & Cleary, 1987.
const P = { a: 0.5, b: 0.3, c: 0.2 };
const ORDER = ['a','b','c'];
// cumulative ranges within [0,1): a:[0,.5) b:[.5,.8) c:[.8,1)
function ranges(){ let lo=0, r={}; for(const s of ORDER){ r[s]=[lo, lo+P[s]]; lo+=P[s]; } return r; }
const R = ranges();

let msg='abca', i=0, low=0, high=1;

function fmt(x){ return x.toFixed(6); }
function setStatus(t,cls){ const s=document.getElementById('status'); s.innerHTML=t; s.className='status '+(cls||''); }

function drawBars(){
  const wrap=document.getElementById('bars'); wrap.innerHTML='';
  // current interval split into a/b/c slices
  const lbl=document.createElement('div'); lbl.className='barlabel';
  lbl.textContent='[low, high) = ['+fmt(low)+', '+fmt(high)+')   width='+(high-low).toExponential(3);
  wrap.appendChild(lbl);
  const bar=document.createElement('div'); bar.className='bar';
  const span=high-low;
  const next = i<msg.length ? msg[i] : null;
  for(const s of ORDER){
    const segLow=low+span*R[s][0], segHigh=low+span*R[s][1];
    const seg=document.createElement('div');
    seg.className='seg '+s+(s===next?' pick':'');
    seg.style.left=(R[s][0]*100)+'%'; seg.style.width=(P[s]*100)+'%';
    seg.textContent=s;
    bar.appendChild(seg);
  }
  wrap.appendChild(bar);
}

function step(){
  if(i>=msg.length){ finish(); return; }
  const s=msg[i]; const span=high-low;
  const nl=low+span*R[s][0], nh=low+span*R[s][1];
  low=nl; high=nh; i++;
  drawBars();
  if(i>=msg.length){ finish(); }
  else setStatus(i18nFmt(`Read <b>%s%</b> (symbol %i% of %length%). Interval narrowed.`, { s: s, i: i, length: msg.length }),'');
}
function finish(){
  const mid=(low+high)/2;
  // bits needed ~ -log2(width); rounded up, this is the compressed length.
  const bits=Math.ceil(-Math.log2(high-low))+1;
  drawBars();
  setStatus(i18nFmt(`Done. The fraction <b>%fmt%</b> encodes "%msg%".`, { fmt: fmt(mid), msg: msg }),'ok');
  const ent = msg.split('').reduce((a,s)=>a-Math.log2(P[s]),0);
  document.getElementById('out').textContent =
    i18nFmt(`encoded fraction : %mid%
final interval   : [%fmt%, %fmt2%)
bits to name it  : ~%bits%  (entropy of message = %ent% bits)
decoded message  : %decode%`, { mid: mid.toFixed(8), fmt: fmt(low), fmt2: fmt(high), bits: bits, ent: ent.toFixed(2), decode: decode(mid, msg.length) });
}
// Decode proves the fraction is enough: repeatedly find which slice mid falls in.
function decode(x, n){
  let out='', lo=0, hi=1;
  for(let k=0;k<n;k++){
    const span=hi-lo, t=(x-lo)/span;
    let chosen='a';
    for(const s of ORDER){ if(t>=R[s][0] && t<R[s][1]){ chosen=s; break; } }
    out+=chosen; const span2=hi-lo; hi=lo+span2*R[chosen][1]; lo=lo+span2*R[chosen][0];
  }
  return out;
}
// Run the whole message cleanly from [0,1) in one pass.
function recomputeFromScratch(){ low=0; high=1; for(const s of msg){ const span=high-low; const nl=low+span*R[s][0], nh=low+span*R[s][1]; low=nl; high=nh; } i=msg.length; }

function reset(){
  msg=(document.getElementById('msg').value||'').toLowerCase().replace(/[^abc]/g,'')||'a';
  document.getElementById('msg').value=msg;
  i=0; low=0; high=1; document.getElementById('out').textContent='';
  drawBars(); setStatus(`Press <b>Step</b> to read the next symbol.`,'');
}
document.getElementById('step').addEventListener('click',step);
document.getElementById('all').addEventListener('click',()=>{ reset(); recomputeFromScratch(); finish(); });
document.getElementById('reset').addEventListener('click',reset);
document.getElementById('msg').addEventListener('change',reset);
document.querySelectorAll('.samples button').forEach(b=>b.addEventListener('click',()=>{
  document.getElementById('msg').value=b.dataset.m; reset(); }));
reset();
Result
Console

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.

The Real Complexity

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

Where It Matters

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.

Conclusion

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.

Share this article

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

Comments

Loading comments...

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