Arithmetic Coding: One Number for the Whole Message

in progressThis lesson is still being built - content, demos, and checkpoints may change before release.

Arithmetic coding

Loading interactive demo…

The model gives every symbol a slice of the unit interval as wide as its share of the counts. Coding keeps the current interval and narrows it to each symbol's slice of itself, so the width ends as the product of the probabilities, and the shortest binary fraction inside the final interval is the code. The thin strip is the unit interval with the current interval marked; the wide one is the current interval zoomed, cut into slices.Take the tour, or press and explore. Legend:

The panel beside the stage is the real ArithmeticCoder class from the published library executing in your browser, with the current line highlighted.

The slice just kept, and the current interval on the strip; the character being coded.
The tapped symbol's slice.
The code point, once it is found: the shortest fraction inside the final interval.
The other slices of the shown interval.
Slices the table has not listed yet, faint.

bits is minus log2 of the interval's width so far, the information coded, code the length of the fraction once found, entropy the message's entropy times its length, huffman what the Huffman lesson's coder spends on the same message. Only the seeded chip reads the skew and seed. Tap a chip in the message to light its symbol's slice.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

The interval. The model gives symbol $s$ a probability $p_s$ and a slice $[c_s, c_s + p_s)$ of the unit interval, where $c_s$ is the probability of everything listed before it. Coding starts with $[0, 1)$ and, for each symbol of the message, replaces the interval $[\ell, \ell + w)$ by

[\ell + w c_s,\; \ell + w c_s + w p_s) ,

the symbol's slice of it. After the message the width is $w = \prod_i p_{s_i}$ , so

-\log_2 w = \sum_i -\log_2 p_{s_i} ,

the information of the message under the model: the surprisals added up, with no rounding per symbol.

The code. Any number in the final interval identifies the message, since the decoder can replay the narrowing and see which slice the number falls in at each step. A binary fraction with $L$ bits is a multiple of $2^{-L}$ , and an interval of width $w$ always contains one once $2^{-L} \le w / 2$ , so the shortest such fraction has at most $\lceil -\log_2 w \rceil + 1$ bits: the information plus fewer than two. Over a long message that overhead vanishes, and the cost per symbol is the entropy itself.

Why Huffman cannot match it. A prefix code spends a whole number of bits on each symbol. For a symbol with $p = 0.99$ that is one bit where the information is $0.015$ ; arithmetic coding narrows the interval by a factor of $0.99$ and pays the $0.015$ . The abracadabra message shows the gap; a one-symbol message shows the extreme, one bit in all against one per character.

The model is the whole game. The coder pays $-\log_2 q_{s}$ for each symbol, where $q$ is the model's probability, whatever the true probabilities are. Switch the model to uniform and every symbol costs $\log_2 k$ ; the extra bits over the message's own counts are the KL divergence between the counts and the model, which the next lesson measures. Real coders adapt the model as they go, so the decoder, replaying the same updates, needs no table sent ahead.

Precision. The exact fractions here have a denominator of $T^n$ for a total of $T$ and a message of $n$ symbols, which is why the stage stops at sixteen. A production coder keeps the interval in a fixed-width integer, shifts a bit out whenever both ends agree on it, and handles the case where they straddle the middle; the result is the same code, streamed.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

Three integers, not two floats. low, width, and den are BigInts, with den the total raised to the number of symbols coded so far; nothing rounds, so the decoder's comparisons land exactly where the encoder's did.
The slices are counts, not probabilities, so the table and the narrowing share one integer arithmetic; the probabilities in the trace are for the stage.
The shortest fraction is found by trying lengths from one up: the smallest multiple of $2^{-L}$ at or above low is inside the interval as soon as it is below low + width. A one-symbol message gets a single bit, where Huffman coding spends one per character.
decode is static and untraced: it replays the same narrowing, at each step picking the slice the fraction falls in, so a message is recovered from its bits, its model, and its length.

Shannon's 1948 paper already contained the seed: write the cumulative probabilities of the messages as binary fractions and the code lengths fall out. Peter Elias saw around 1960 that the interval could be narrowed symbol by symbol without ever enumerating the messages, an idea Norman Abramson's 1963 textbook credits to him unpublished. It stayed a curiosity, since the arithmetic needs unbounded precision, until Jorma Rissanen and Richard Pasco showed in 1976 how to do it in fixed-width integers; Witten, Neal, and Cleary's 1987 article with working C code made it a standard tool.

1948Claude Shannon - Describes coding a message by the binary expansion of its cumulative probability, the idea that arithmetic coding makes incremental.source
c. 1960Peter Elias - Works out the recursive interval narrowing; it appears, credited to him as unpublished, in Abramson's 1963 'Information Theory and Coding'.source
1976Jorma Rissanen and Richard Pasco - Independently show how to run the coder in finite-precision integers, renormalising as the interval shrinks, which makes it practical.source
1979G. N. N. Martin - Presents range coding, an equivalent formulation whose paper was overlooked for decades and later mattered because it predated the patents.source
1987Ian Witten, Radford Neal, and John Cleary - Publish 'Arithmetic Coding for Data Compression' in Communications of the ACM with complete C source, the reference most implementations descend from.source

Used today

Video and image codecs - H.264 and H.265 code their syntax elements with CABAC, a binary arithmetic coder with adaptive models; JPEG 2000 and JBIG2 use the MQ coder.
Context-mixing compressors - The strongest general-purpose compressors predict each bit from many models and hand the probability to an arithmetic coder.
Language model compression - A neural model's next-token probabilities, fed to an arithmetic coder, compress text below any dictionary method.

message

model

skew1.2

bits: 22.44
code: 21 bits
entropy: 22.44 bits
huffman: 23 bits

arithmetic-coder.ts

import type { Tracer } from "../trace";/** A symbol's slice of the unit interval under the model, as counts. */export interface SymbolRange {  symbol: string;  count: number;  /** The counts of every symbol before it in the table. */  before: number;}export interface ArithmeticCode {  /** The code: the shortest binary fraction inside the final interval. */  bits: string;  /** The final interval, as doubles for display; the coder itself works in exact fractions. */  low: number;  high: number;  /** Minus log2 of the final interval's width: the bits the message is worth under the model. */  information: number;}/** The longest message the exact fractions are sized for. */export const MAX_MESSAGE = 16;const ratio = (a: bigint, b: bigint): number => Number(a) / Number(b);const ceilDiv = (a: bigint, b: bigint): bigint => (a + b - 1n) / b;/** * Arithmetic coding: the whole message becomes one number. The model * gives each symbol a slice of the unit interval proportional to its * count; coding keeps the current interval and, symbol by symbol, * narrows it to that symbol's slice of itself. After the message the * interval's width is the product of the symbols' probabilities, so * minus log2 of it is the message's information, and any binary * fraction inside the interval identifies the message; the shortest * one needs at most two bits more than that. No symbol costs a whole * bit, which is what Huffman coding cannot manage. * * The arithmetic is exact: low, width, and den are integers (den is * the total raised to the message length), so nothing rounds and a * decoder replays the same comparisons. Time: O(n k) for n symbols * over k ranges. Space: O(n log total) bits of integer. */export class ArithmeticCoder {  constructor(private readonly tracer?: Tracer) {}  /** The symbol table: each symbol's count and the counts before it, in the model's order. */  static ranges(counts: ReadonlyMap<string, number>): { table: Map<string, SymbolRange>; total: number } {    const table = new Map<string, SymbolRange>();    let total = 0;    for (const [symbol, raw] of counts) {      const count = Math.max(0, Math.floor(raw));      table.set(symbol, { symbol, count, before: total });      total += count;    }    return { table, total };  }  encode(message: string, counts: ReadonlyMap<string, number>): ArithmeticCode {    if (message.length > MAX_MESSAGE) throw new RangeError(`message longer than ${MAX_MESSAGE} symbols`);    const { table, total } = ArithmeticCoder.ranges(counts);    if (message.length > 0 && total === 0) throw new RangeError("the model has no counts");    let index = 0;    for (const range of table.values()) {      // ▸ each symbol owns a slice of the interval, as wide as its share      this.tracer?.emit("table", { index, symbol: range.symbol, count: range.count, from: range.before / total, to: (range.before + range.count) / total, total });      index += 1;    }    const scaleBy = BigInt(total);    const totalCount = BigInt(total);    let low = 0n;    let width = 1n;    let den = 1n;    let denominator = 1n;    for (let i = 0; i < message.length; i++) {      const symbol = message[i]!;      const range = table.get(symbol);      if (!range || range.count === 0) throw new RangeError(`"${symbol}" has no count in the model`);      low = low * scaleBy + width * BigInt(range.before);      low = low * totalCount + width * BigInt(range.before);      width = width * BigInt(range.count);      den = den * scaleBy;      denominator = denominator * totalCount;      // ▸ keep only this symbol's slice of the current interval      this.tracer?.emit("narrow", { index: i, symbol, from: range.before / total, to: (range.before + range.count) / total, low: ratio(low, den), high: ratio(low + width, den), information: -Math.log2(ratio(width, den)) });      this.tracer?.emit("narrow", { index: i, symbol, from: range.before / total, to: (range.before + range.count) / total, low: ratio(low, denominator), high: ratio(low + width, denominator), information: -Math.log2(ratio(width, denominator)) });    }    // The shortest binary fraction m / 2^length with low <= m / 2^length < low + width.    let length = 0;    let numerator = 0n;    if (message.length > 0) {      for (length = 1; ; length++) {        const scale = 1n << BigInt(length);        numerator = ceilDiv(low * scale, den);        numerator = ceilDiv(low * scale, denominator);        if (numerator * den < (low + width) * scale) break;        if (numerator * denominator < (low + width) * scale) break;      }    }    const bits = length === 0 ? "" : numerator.toString(2).padStart(length, "0");    const information = -Math.log2(ratio(width, den));    const information = -Math.log2(ratio(width, denominator));    // ▸ the shortest binary fraction inside the interval is the code    this.tracer?.emit("finish", { bits, length, low: ratio(low, den), high: ratio(low + width, den), information, slack: length - information });    this.tracer?.emit("finish", { bits, length, low: ratio(low, denominator), high: ratio(low + width, denominator), information, slack: length - information });    return { bits, low: ratio(low, den), high: ratio(low + width, den), information };    return { bits, low: ratio(low, denominator), high: ratio(low + width, denominator), information };  }  /** Replays the narrowing from the code's fraction: at each step the slice the fraction falls in is the symbol. Untraced. */  static decode(bits: string, counts: ReadonlyMap<string, number>, length: number): string {    const { table, total } = ArithmeticCoder.ranges(counts);    const scaleBy = BigInt(total);    const totalCount = BigInt(total);    const numerator = bits === "" ? 0n : BigInt(`0b${bits}`);    const scale = 1n << BigInt(bits.length);    let low = 0n;    let width = 1n;    let den = 1n;    let denominator = 1n;    let out = "";    for (let i = 0; i < length; i++) {      // The fraction's position inside the current interval, as counts out of the total.      const value = numerator * den * scaleBy;      const value = numerator * denominator * totalCount;      for (const range of table.values()) {        if (range.count === 0) continue;        const from = (low * scaleBy + width * BigInt(range.before)) * scale;        const from = (low * totalCount + width * BigInt(range.before)) * scale;        const to = (low * scaleBy + width * BigInt(range.before + range.count)) * scale;        const to = (low * totalCount + width * BigInt(range.before + range.count)) * scale;        if (value >= from && value < to) {          out += range.symbol;          low = low * scaleBy + width * BigInt(range.before);          low = low * totalCount + width * BigInt(range.before);          width = width * BigInt(range.count);          den = den * scaleBy;          denominator = denominator * totalCount;          break;        }      }    }    return out;  }}

length =: 21
information =: 22.44
entropy =: 22.44
huffman =: 23

21 bits in all against 22.44 of entropy and 23 for Huffman coding; the message carried 22.44 bits under this model.

import type { Tracer } from "../trace";/** A symbol's slice of the unit interval under the model, as counts. */export interface SymbolRange { symbol: string; count: number; /** The counts of every symbol before it in the table. */ before: number;}export interface ArithmeticCode { /** The code: the shortest binary fraction inside the final interval. */ bits: string; /** The final interval, as doubles for display; the coder itself works in exact fractions. */ low: number; high: number; /** Minus log2 of the final interval's width: the bits the message is worth under the model. */ information: number;}/** The longest message the exact fractions are sized for. */export const MAX_MESSAGE = 16;const ratio = (a: bigint, b: bigint): number => Number(a) / Number(b);const ceilDiv = (a: bigint, b: bigint): bigint => (a + b - 1n) / b;/** * Arithmetic coding: the whole message becomes one number. The model * gives each symbol a slice of the unit interval proportional to its * count; coding keeps the current interval and, symbol by symbol, * narrows it to that symbol's slice of itself. After the message the * interval's width is the product of the symbols' probabilities, so * minus log2 of it is the message's information, and any binary * fraction inside the interval identifies the message; the shortest * one needs at most two bits more than that. No symbol costs a whole * bit, which is what Huffman coding cannot manage. * * The arithmetic is exact: low, width, and den are integers (den is * the total raised to the message length), so nothing rounds and a * decoder replays the same comparisons. Time: O(n k) for n symbols * over k ranges. Space: O(n log total) bits of integer. */export class ArithmeticCoder { constructor(private readonly tracer?: Tracer) {} /** The symbol table: each symbol's count and the counts before it, in the model's order. */ static ranges(counts: ReadonlyMap<string, number>): { table: Map<string, SymbolRange>; total: number } { const table = new Map<string, SymbolRange>(); let total = 0; for (const [symbol, raw] of counts) { const count = Math.max(0, Math.floor(raw)); table.set(symbol, { symbol, count, before: total }); total += count; } return { table, total }; } encode(message: string, counts: ReadonlyMap<string, number>): ArithmeticCode { if (message.length > MAX_MESSAGE) throw new RangeError(`message longer than ${MAX_MESSAGE} symbols`); const { table, total } = ArithmeticCoder.ranges(counts); if (message.length > 0 && total === 0) throw new RangeError("the model has no counts"); let index = 0; for (const range of table.values()) { // ▸ each symbol owns a slice of the interval, as wide as its share this.tracer?.emit("table", { index, symbol: range.symbol, count: range.count, from: range.before / total, to: (range.before + range.count) / total, total }); index += 1; } const scaleBy = BigInt(total); const totalCount = BigInt(total); let low = 0n; let width = 1n; let den = 1n; let denominator = 1n; for (let i = 0; i < message.length; i++) { const symbol = message[i]!; const range = table.get(symbol); if (!range || range.count === 0) throw new RangeError(`"${symbol}" has no count in the model`); low = low * scaleBy + width * BigInt(range.before); low = low * totalCount + width * BigInt(range.before); width = width * BigInt(range.count); den = den * scaleBy; denominator = denominator * totalCount; // ▸ keep only this symbol's slice of the current interval this.tracer?.emit("narrow", { index: i, symbol, from: range.before / total, to: (range.before + range.count) / total, low: ratio(low, den), high: ratio(low + width, den), information: -Math.log2(ratio(width, den)) }); this.tracer?.emit("narrow", { index: i, symbol, from: range.before / total, to: (range.before + range.count) / total, low: ratio(low, denominator), high: ratio(low + width, denominator), information: -Math.log2(ratio(width, denominator)) }); } // The shortest binary fraction m / 2^length with low <= m / 2^length < low + width. let length = 0; let numerator = 0n; if (message.length > 0) { for (length = 1; ; length++) { const scale = 1n << BigInt(length); numerator = ceilDiv(low * scale, den); numerator = ceilDiv(low * scale, denominator); if (numerator * den < (low + width) * scale) break; if (numerator * denominator < (low + width) * scale) break; } } const bits = length === 0 ? "" : numerator.toString(2).padStart(length, "0"); const information = -Math.log2(ratio(width, den)); const information = -Math.log2(ratio(width, denominator)); // ▸ the shortest binary fraction inside the interval is the code this.tracer?.emit("finish", { bits, length, low: ratio(low, den), high: ratio(low + width, den), information, slack: length - information }); this.tracer?.emit("finish", { bits, length, low: ratio(low, denominator), high: ratio(low + width, denominator), information, slack: length - information }); return { bits, low: ratio(low, den), high: ratio(low + width, den), information }; return { bits, low: ratio(low, denominator), high: ratio(low + width, denominator), information }; } /** Replays the narrowing from the code's fraction: at each step the slice the fraction falls in is the symbol. Untraced. */ static decode(bits: string, counts: ReadonlyMap<string, number>, length: number): string { const { table, total } = ArithmeticCoder.ranges(counts); const scaleBy = BigInt(total); const totalCount = BigInt(total); const numerator = bits === "" ? 0n : BigInt(`0b${bits}`); const scale = 1n << BigInt(bits.length); let low = 0n; let width = 1n; let den = 1n; let denominator = 1n; let out = ""; for (let i = 0; i < length; i++) { // The fraction's position inside the current interval, as counts out of the total. const value = numerator * den * scaleBy; const value = numerator * denominator * totalCount; for (const range of table.values()) { if (range.count === 0) continue; const from = (low * scaleBy + width * BigInt(range.before)) * scale; const from = (low * totalCount + width * BigInt(range.before)) * scale; const to = (low * scaleBy + width * BigInt(range.before + range.count)) * scale; const to = (low * totalCount + width * BigInt(range.before + range.count)) * scale; if (value >= from && value < to) { out += range.symbol; low = low * scaleBy + width * BigInt(range.before); low = low * totalCount + width * BigInt(range.before); width = width * BigInt(range.count); den = den * scaleBy; denominator = denominator * totalCount; break; } } } return out; }}