Cairn
algorithms · compression · O(n) encode, O(n·k) decode — n = message length, k = distinct symbols

↩ back to Compression

Arithmetic Coding

Arithmetic coding encodes an entire message as a single number instead of one code per symbol. Start with the interval [0, 1), representing "everything is still possible." Each symbol gets a slice of that interval sized exactly to its probability — a symbol that occurs 90% of the time gets 90% of whatever's left. Reading the message one symbol at a time, narrow the current interval down to that symbol's slice of it, then repeat: the next symbol's slice is now a slice of the narrowed interval, not the original. After the whole message, any number that falls inside the final, tiny interval uniquely identifies it — decoding is just locating which nested slice that number keeps falling into.

The third Compression entry, after LZW Compression and Run-Length Encoding, and the first to directly take on Huffman Coding's own home turf: frequency-driven, one-code-per-symbol compression. Huffman coding is provably within one bit of the Shannon entropy bound, but it can only spend a whole number of bits on any one symbol, because every code is a path through a binary tree. That's invisible when a message's probabilities happen to land near powers of one-half, but it's a real, measurable cost otherwise — this page's job is to measure exactly how much, by narrowing an interval instead of walking a tree.

Try it

Type a message and press Load, then Step or Run. Each distinct character gets a fixed slice of [0, 1) sized by how often it occurs in the message, shown as the top rows below. The bottom row is the current range — it starts as the whole line and narrows into whichever symbol's slice is read next. Once every character has been read, the final range, the number of bits needed to pin a code inside it, and a live comparison against Huffman coding (run on this exact message) are shown below the log.

symbol intervals (fixed) and the narrowing current range

Press Load.

Why it works

Assigning each symbol a slice of [0, 1) proportional to its probability, and narrowing into the chosen slice at every step, gives every possible message of the same length its own non-overlapping sub-interval of [0, 1) — two different messages can never land in overlapping ranges, because at the first symbol where they differ, they're already confined to two disjoint slices, and everything nested inside a slice stays inside it. That's the whole decodability guarantee: a single number that falls inside one message's final interval cannot also fall inside any other message's.

The interval's width after n symbols is the product of those symbols' own probabilities — exactly the quantity whose negative log2 is the message's information content in bits. A symbol with probability p shrinks the interval by a factor of p, costing −log₂(p) bits — not necessarily a whole number, unlike a tree-walk code. That fractional cost is the entire advantage over Huffman coding: a symbol that occurs 90% of the time can be charged close to its true 0.15-bit cost instead of being rounded up to Huffman's cheapest possible whole bit.

Reference implementation

Builds each symbol's cumulative interval from the message's own letter frequencies (sorted alphabetically, the same deterministic tie-break Huffman Coding's own reference implementation uses), then narrows [low, high) one symbol at a time exactly as described above. decode mirrors it: at each step it checks which symbol's interval the fixed code number falls into, relative to the current [low, high), emits that symbol, and narrows the same way the encoder did. Round-trip tested with a 100,000-trial fuzz harness (random alphabet size 1–4, random length 1–24) — zero mismatches. That length cap is not an arbitrary demo limit; see the first Pitfall below for exactly what happens past it, and why.

function buildRanges(freq, total) {
  const symbols = [...freq.keys()].sort();
  const ranges = new Map();
  let acc = 0;
  for (const s of symbols) {
    const p = freq.get(s) / total;
    ranges.set(s, { lo: acc, hi: acc + p });
    acc += p;
  }
  return ranges;
}

function arithmeticEncode(message) {
  const freq = new Map();
  for (const ch of message) freq.set(ch, (freq.get(ch) || 0) + 1);
  const ranges = buildRanges(freq, message.length);

  let low = 0, high = 1;
  for (const ch of message) {
    const width = high - low;
    const r = ranges.get(ch);
    const newLow = low + width * r.lo;
    const newHigh = low + width * r.hi;
    low = newLow;
    high = newHigh;
  }
  const code = (low + high) / 2; // any number strictly inside [low, high) decodes correctly
  return { code, freq, length: message.length };
}

function arithmeticDecode({ code, freq, length }) {
  const ranges = buildRanges(freq, length); // table transmitted alongside, like Huffman's tree
  let low = 0, high = 1, out = '';
  for (let i = 0; i < length; i++) {
    const width = high - low;
    const target = (code - low) / width;
    for (const [sym, r] of ranges) {
      if (target >= r.lo && target < r.hi) {
        out += sym;
        low = low + width * r.lo;
        high = low + width * (r.hi - r.lo);
        break;
      }
    }
  }
  return out;
}

Pitfalls

Plain floating-point numbers run out of precision far sooner than their exponent range suggests — and it fails silently. A JavaScript number has 52 mantissa bits of precision regardless of how small it gets; narrowing [low, high) keeps multiplying by numbers less than 1, and once the relative gap between low and high drops below that precision, the two become literally the same float. Measured directly: encoding and decoding 100,000 random messages per length, alphabet size 1–4, the fuzz harness above stays perfect through length 24, then degrades fast:

lengthmismatches / 100,000
240
251
261,140 (1.1%)
2815,516 (15.5%)
3023,537 (23.5%)

There's no exception, no NaN, no crash at any of these lengths — decode just occasionally returns the wrong string, because target landed a few floating-point units outside the true interval. The threshold lands around 25 symbols here specifically because this test's alphabet carries roughly 2 bits of information per symbol on average (log₂4) — 25 symbols × 2 bits ≈ the ~52-bit precision budget a double actually has. A lower-entropy source spends that same 52-bit budget more slowly: encoding a deliberately skewed two-symbol source (90% one symbol, 10% the other — about 0.47 bits/symbol) the same way, the interval width hits exactly zero — not just imprecise, genuinely unrecoverable — at symbol 120, not 25, because each symbol there costs less than a quarter of a bit. Past that point every further narrowing step is a no-op: newLow and newHigh both collapse back to the same frozen low, whatever symbol comes next. Confirmed directly by freezing that source's probability table at the 120-symbol mark (the way a real adaptive coder only ever uses statistics from symbols already seen, never from symbols still to come) and feeding the same frozen table five more As versus five more Bs — both produce byte-for-byte identical (low, high) pairs, two genuinely different messages the encoder can no longer tell apart. Real arithmetic coders fix this with fixed-width integer arithmetic and a renormalization step that shifts out already-decided leading bits as soon as they stop changing, so precision never has to cover the whole message at once — not built here, to keep the interval-narrowing idea itself the whole focus.

The frequency table — and the message length — have to travel separately from the code. Symmetric to Huffman coding's own need to transmit its tree: a single number in [0, 1) carries no signal for where to stop decoding on its own, since nested intervals keep subdividing forever. A real encoder either sends the length alongside the code (what the reference implementation above does) or folds a dedicated end-of-message symbol into the alphabet itself so the decoder recognizes its own stopping point from the stream.

The entropy advantage over Huffman shows up on skewed, small alphabets — not on the tiny example above. On abracadabra (the same 11-character message Huffman Coding's own page uses), the two land within a bit of each other: Huffman's actual reference implementation produces 23 bits; the formula this page's own encoder relies on for a provably decodable code, ⌈−log₂(width)⌉ + 1, gives 24 — one worse, here, because that +1 is a safety margin for the general case, not a tight count for this particular message (a direct search for the shortest binary fraction that still lands inside the final interval finds one needing only 22 bits, one better than Huffman, without that margin). The real, structural gap opens on a message Huffman is forced to treat badly: a 20-symbol run that's 90% one character and 10% the other (AAAAAAAAABAAAAAAAAAB) has a true information content of 9.4 bits, but a 2-symbol alphabet gives Huffman exactly two leaves and therefore exactly one bit per symbol no matter how skewed the frequencies are — 20 bits, confirmed by running the same huffman() function this site already ships. Arithmetic coding's own guaranteed formula costs 11 bits on the identical message — essentially half of Huffman's, and within two bits of the theoretical floor, specifically because the probabilities here (0.9 and 0.1) aren't anywhere near a power of one-half, which is exactly the case a one-bit-per-symbol tree code can't adapt to and a narrowing interval can.

Complexity

Time: O(n) to encode a message of length n — one pass to count frequencies, one pass to narrow the interval, plus O(k log k) to sort the k distinct symbols into their cumulative ranges. The reference decode above is O(n·k): it walks the symbol list linearly at every one of the n steps to find which interval the target falls into. A real implementation keeps the ranges in a cumulative-frequency array and binary-searches it, bringing decode down to O(n log k) — not built here, to keep the decode loop's shape a direct mirror of encode's. Space: O(k) for the frequency table and ranges, independent of n — unlike LZW's dictionary, nothing here grows with the message itself; the entire per-message cost beyond the table is the two numbers low and high.

See Choosing a Compression Approach for how this entry compares against Huffman Coding and the site's other five Compression entries — short version: the gap over Huffman is real but opens only on small, heavily skewed alphabets, and this page's own output length is verified order-independent, unlike RLE's or LZW's.