How does an arithmetic coder turn a whole message into a single subinterval of [0,1)?
answer
- one number, not one codeword each
- start from [0,1)
- each symbol keeps its own probability slice
- slice of the current interval, not of [0,1)
- final width equals the message probability
basics
~20 sAn arithmetic coder starts with [0,1) and narrows it once per symbol, keeping the slice whose width is that symbol's probability. The final interval's width is the message's probability, and a number inside it identifies the whole message.
solid answer
~40 sThe coder holds a half-open interval, initially `[0,1)`. The model lays the alphabet along that line, giving each symbol a slice whose width is its probability, so each symbol has a cumulative range. Coding a symbol replaces the current interval with that symbol's slice *of itself*: `range = high - low`, then `high = low + range * cum_high(s)` and `low = low + range * cum_low(s)`. The interval only shrinks, by a factor of exactly `p(s)` per symbol, so after n symbols its width equals the product of the coded symbols' probabilities — the model's probability for that exact message. The output is then enough binary digits to name a fraction inside the surviving interval, plus a length or an end-of-message symbol so the decoder knows where to stop.
code
pseudocode · 10 lineslow = 0.0
high = 1.0
for each symbol s in message:
range = high - low
high = low + range * cumulative_high(s) # compute high first
low = low + range * cumulative_low(s) # low is overwritten last
# name a binary fraction whose own dyadic interval lies inside [low, high)
emit_digits_of_a_point_inside(low, high)go deeper
Recall the shape: one interval for the whole message, narrowed once per symbol, and a single number written out at the end rather than a codeword per symbol.
Be able to run the arithmetic on a whiteboard: cumulative ranges, the slice-of-the-current-interval update, and why the final width equals the product of the coded symbols' probabilities.
Explain what the format must carry beyond the digits — termination and the model — and why the output can be streamed before the message ends once leading bits have settled.
Frame the trade this representation imposes: no codeword boundaries means no random access and no resync point, which is a framing and blast-radius decision rather than a coding one.
## One number instead of one codeword per symbol A symbol code answers the question "what bits do I write for this symbol?". An arithmetic coder answers a different one: "which numbers between 0 and 1 could this message be?" It keeps a half-open interval `[low, high)`, starts at `[0, 1)`, narrows it once per symbol, and at the end writes down enough binary digits to pin a number inside whatever interval survived. That number **is** the message. There is no per-symbol codeword you can point at in the output, and no table of codewords anywhere in the design. The narrowing rule needs the **model** — the thing that supplies symbol probabilities — to lay the alphabet out along the unit line. Each symbol `s` gets a slice whose width is its probability `p(s)`, the slices are stacked in a fixed order, and so each symbol has a **cumulative range** `[cum_low(s), cum_high(s))` with `cum_high(s) - cum_low(s) = p(s)`. Coding `s` replaces the current interval with the corresponding slice of *that interval*, not of `[0,1)`: ``` range = high - low high = low + range * cum_high(s) low = low + range * cum_low(s) ``` Two consequences fall straight out: - The interval never widens. Each symbol multiplies its width by exactly `p(s)`. - After n symbols the width is `p(s1) * p(s2) * ... * p(sn)` — precisely the probability the model assigned to the exact sequence that was coded. ## A worked example Take an archival text encoder whose model, at this point in the stream, gives `A = 0.8`, `B = 0.15`, `C = 0.05`, laid out as `A = [0, 0.8)`, `B = [0.8, 0.95)`, `C = [0.95, 1)`. 1. Start: `[0, 1)`, width 1. 2. Code `A`: keep the first 80 per cent of the interval, giving `[0, 0.8)`, width 0.8. 3. Code `B`: take the B slice **of that**. `range = 0.8`, so `high = 0 + 0.8 * 0.95 = 0.76` and `low = 0 + 0.8 * 0.8 = 0.64`. The interval is `[0.64, 0.76)`, width 0.12. And 0.12 is exactly `0.8 * 0.15`, the model's probability for the message `AB`. Every number in `[0.64, 0.76)` names that message and nothing else. ## Turning the interval into bits The encoder now writes a binary fraction that lands inside `[0.64, 0.76)`. The digits `1011` mean `0.1011` in binary = 0.6875. Because anything appended after four digits can add less than `1/16`, those four digits actually stand for the sub-interval `[0.6875, 0.75)` — and that sub-interval sits wholly inside `[0.64, 0.76)`, so a decoder reading them cannot be misled by whatever follows. That containment requirement is the honest version of "any point inside will do". The two digits `11` denote 0.75, which does lie inside the interval, but they stand for `[0.75, 1)`, which does not — so they are only usable if the decoder is told exactly how many digits to read. A self-delimiting arithmetic code needs about `log2(1/width)` digits plus a small constant: here `log2(1/0.12)` is about 3.06, so four digits. **The rounding to a whole number of bits is paid once for the message, not once per symbol.** In a practical coder the digits do not wait for the end. As soon as `low` and `high` agree on a leading bit, that bit can never change again and is streamed out immediately, and the interval is doubled to recover precision — so the output flows while the message is still being read. ## What the decoder does The decoder runs the identical model and mirrors the narrowing. Given the received fraction `v`: 1. Find which cumulative slice of the current interval contains `v`; that slice's symbol is the next output. 2. Narrow the interval exactly as the encoder did for that symbol. 3. Repeat. Because step 2 is the encoder's own arithmetic, the two stay on the same interval throughout. What the decoder cannot work out for itself is **where to stop**: the digit string does not announce the end, and trailing digits will happily decode into extra symbols. So the format must carry either the symbol count or a reserved end-of-message symbol given its own small slice of the line. ## The shape of the difference | | code that emits a codeword per symbol | interval coder | |---|---|---| | unit of output | one whole codeword per symbol | one number per message | | cost of a symbol | an integer number of bits | a multiplicative narrowing by `p(s)` | | where rounding happens | at every symbol | once, at the end of the message | | decoding a symbol | match a codeword | locate a value within a cumulative range | | random access | resume at any codeword boundary | decode from the start of the stream |
- What does the width of the final interval equal, and why does that matter?It equals the product of the coded symbols' probabilities under the model — the model's probability for that exact message. It matters because the number of digits needed to name a point inside an interval of width `w` is about `log2(1/w)`, so the output length is driven directly by how probable the model thought the message was.
- Why must the symbol's slice be taken of the current interval rather than of [0,1)?Because the interval already encodes everything coded so far. Slicing `[0,1)` again would discard that history and make the message ambiguous. Slicing the current interval composes the probabilities multiplicatively, which is what makes the final width equal the whole message's probability.
- How does the decoder know the message has ended?It cannot tell from the digits alone — trailing digits decode into spurious symbols. The format must supply the symbol count out of band, or the alphabet must include a reserved end-of-message symbol with its own slice, which costs a few bits but makes the stream self-terminating.
saying these in an interview costs you the question
- Thinks each symbol produces its own codeword in the output
- Slices [0,1) again per symbol instead of the current interval
- Believes the interval can widen again for a likely symbol
- Says the decoder needs the encoder's final low and high values
- Assumes the digit string announces where the message ends
- Confuses the interval's width with the number of symbols coded