Arithmetic Coding

Huffman has a hard limit: every symbol gets an integer number of bits. If a symbol's true information content is 1.7 bits, Huffman wastes 0.3 bits on it. For highly skewed distributions (think a probability-0.99 symbol that "should" take 0.014 bits), Huffman is shamefully bad.

Arithmetic coding (Witten/Neal/Cleary 1987) solves this. Instead of giving each symbol a code, it represents the entire message as a single fractional number in [0, 1). Each symbol narrows the interval by a factor of its probability. The final bitstring is just enough bits to identify that interval.

The theory

Starting interval: [0, 1). Process symbol s with probability p(s) and cumulative range [lo(s), hi(s)):

new_lo = old_lo + (old_hi - old_lo) * lo(s)
new_hi = old_lo + (old_hi - old_lo) * hi(s)

After all symbols, output enough bits to uniquely identify a number inside the final interval. The total bits ≈ -sum(log2(p(s))) = H(X), the Shannon entropy — exactly the lower bound.

The practical problem

Real machines can't store arbitrary-precision fractions. The trick is renormalization — observe that once the high bit of both lo and hi agree, that bit can never change, so emit it and shift left:

loop:
  if hi < HALF:       emit 0;             # E1: both in lower half
  elif lo >= HALF:    emit 1; -= HALF     # E2: both in upper half
  elif STRADDLE:      pending++; -= QTR   # E3: straddling halfway
  else: break
  lo <<= 1
  hi = (hi << 1) | 1

The pending counter handles the trickiest case: the interval is around the halfway mark but not yet decided. We defer the bit until we know which side it lands on.

How modern codecs use it

• JPEG arithmetic mode (1992 spec, rarely deployed due to patents until ~2007)
• H.264 CABAC (Context-Adaptive Binary Arithmetic Coding)
• Zstandard FSE / tANS — a finite-state approximation of arithmetic coding that's both fast AND near-optimal. It's the reason zstd beats gzip both in ratio and speed.

Why this matters

For text, Huffman is fine — entropy is ~5 bits/byte, and Huffman wastes <1%. But for images, video residuals, or any source with skewed probabilities, arithmetic coding (or its modern descendant tANS) compresses 10–30% smaller than Huffman.

Implementation walkthrough

Integer arithmetic coding loop

When emit(b) runs after pending E3 events, also emit 1-b once per pending — those deferred bits get resolved retroactively. The EOF symbol (separate from data alphabet) tells the decoder when to stop.

Common pitfall

The single most common bug is forgetting to emit 1 - bit for every pending count on the next E1 or E2 emission. Skipping this corrupts every message that ever straddles the halfway boundary — about half of them — but tiny inputs may accidentally avoid it during testing.