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.
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
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.
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;
}
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:
| length | mismatches / 100,000 |
|---|---|
| 24 | 0 |
| 25 | 1 |
| 26 | 1,140 (1.1%) |
| 28 | 15,516 (15.5%) |
| 30 | 23,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.
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.