Narrow

A prefix code has to hand out a whole number of bits per symbol. That is the entire limitation and it is not a small one. A symbol that arrives 90% of the time carries −log₂(0.9) = 0.152 bits of information, and Huffman — which is provably the best prefix code that exists — still has to spend a whole bit on it, because half a bit is not a thing you can write down. Over a long message that rounding is not noise. It is a fixed tax on every symbol, and on a skewed source the tax is several times larger than the payload.

Arithmetic coding gets out of it by refusing to encode symbols at all. It encodes the whole message as a single number, and it finds that number by narrowing an interval:

Start with [0, 1). Subdivide it in proportion to the model. Keep the slice belonging to the symbol that actually arrived. Subdivide that slice by the same proportions. Keep the next symbol’s slice. Repeat.

After n symbols the surviving interval has width

w = p(s₁) · p(s₂) · … · p(sₙ) = P(message)

— that multiplication is the whole algorithm — and any number inside it names the message uniquely. Writing down a number inside an interval of width w costs about −log₂ w bits. So the code length is the message’s own information content, to within two bits total, not per symbol. The fractional bits are never rounded away. They accumulate inside the interval and get spent once enough of them have piled up.

That is what the piece is built to draw: the width of a bar and a number of bits are the same quantity on two scales.

What’s on screen

• The message, scrolling, with the symbol in hand ringed.
• The model — [0, 1) cut into slices in proportion to the coder’s beliefs, each slice carrying its cost in bits. That cost is the only number here that matters, and it is a fraction, which is the thing a prefix code cannot spend.
• The window, twice: as this step found it, and as it leaves it. A funnel runs between them. On a symbol step the funnel is straight-sided — a slice is kept, nothing is magnified. On a renormalisation it flares, and the label in the middle says by how much.
• The bit tape. Solid cells are bits written. Hollow ? cells are bits deferred — see below.
• The scoreboard: −log₂P(message), what arithmetic coding has actually emitted, and what Huffman would have spent, on one shared bit axis, with the source’s own entropy n·H as the amber line nothing can beat.

The four numbers, at 400 symbols

Every figure below is read off the running demo by scripts/screenshot-demo.mjs, which checks 47 claims on every build.

Three things fall out of that table.

The overhead is a constant, not a rate. Arithmetic never spends more than 2.00 bits over −log₂P — checked across all twelve source/model combinations, and the worst case is the fair coin, where the flush at the end is the entire cost. Huffman’s overhead is up to a bit per symbol, which is why its column never moves off 400 no matter how lopsided the source gets.

On a fair coin, arithmetic coding loses. 402 against 400. There is nothing fractional to recover when every symbol is worth exactly one bit, so the only thing left is the two-bit flush. Worth stating plainly, because the usual telling of this algorithm does not have a case where it comes second.

Huffman is not being sandbagged. Its tree is built from the actual symbol frequencies of the message — the optimal two-pass static prefix code, the best one that exists for this exact input — and it is not charged for transmitting the table it would need. The gap is not a bad tree. It is the whole-bit constraint, which no prefix code escapes.

The bits that are deferred

The register is finite, so the interval has to be renormalised as it shrinks. Two of the three rules are obvious: if the interval sits entirely below ½ the answer starts with 0, and if it sits entirely above ½ it starts with 1 — emit the bit and double what is left.

The third rule is the one that makes the algorithm work. An interval can straddle ½ while being narrower than the register can hold, and then the next bit is genuinely not decided yet while the precision is about to run out. The fix is to notice that whatever that bit turns out to be, the one after it is its opposite. So the coder counts a pending bit, expands around the midpoint, and carries on; when a real bit finally lands, the deferred ones follow it inverted.

Those are the hollow cells on the tape: bits whose count is known and whose value is not. Almost no explanation of arithmetic coding draws them, and they are the reason a fixed-width register can code an interval far narrower than itself. Set the register to 6 bits and the same 400-symbol message still comes out in 213 bits and still decodes exactly — a register that can hold 64 distinct values, addressing an interval 2⁻²¹³ wide.

Push it further and the point gets blunt. At 4000 symbols the interval width is 2⁻¹⁹²⁰, which underflows a double to exactly zero — the demo’s own realWidth readout goes to 0 and stays there — while the 16-bit coder produces 1922 bits and round-trips perfectly. The number being encoded is not a number any float can hold. The coder never holds it.

The model is the whole game

Switch the model to uniform on the 90/10 source and arithmetic coding spends 402 bits against Huffman’s 400. It loses. The bit tape gives away why: with a uniform model over two symbols each one costs exactly one bit, the low half is 0 and the high half is 1, and the “code” is just the message spelled out. Compression is not something the coder does. It is something the model knows, and the coder’s only job is to spend the model’s beliefs without rounding them.

Which makes the third setting the interesting one. Adaptive starts from one imaginary observation of each symbol — it has been told nothing about the source — and updates its counts as it codes. On 90/10 it lands on 217 bits, three bits behind the model that was handed the right answer, and 183 under Huffman. On 99/1 it reaches 52 against 400. On the four-symbol source it comes in at 768 against Huffman’s 783, and unlike Huffman it sends no table at all, because the decoder rebuilds the same counts from the symbols it has already decoded.

That is the practical form of the whole piece: the coder is within two bits of whatever its model believes, so all the engineering that is left is believing better things.

Notes

• src/narrow.js is framework-free and has no rendering in it: sources, Huffman, the integer encoder (Witten–Neal–Cleary), a decoder, and simulate, which runs the decoder over the encoder’s own output and reports whether the message came back. It does, in every configuration the demo offers — a coder that does not round-trip is a picture, not a coder.
• The slice a symbol receives is the difference of two floors, not the floor of a difference. Those are not the same number, and only the first is what the coder uses; getting it wrong hands a rare symbol an empty slice and the stream stops being decodable with nothing to show for it. The demo counts empty slices rather than crashing on them. The count is zero everywhere, including at 6 bits, where the standard total ≤ ¼·2ᴮ precondition is violated by a factor of 120 (2048 against an allowed 17) and nothing goes wrong anyway. The difference of floors is why: the last symbol in the alphabet can never be starved, because its upper boundary is the interval’s own top.
• Encoder and decoder subdivide on integer counts rather than floats, because they must cut at bit-identical boundaries. A float that rounds differently on the two sides desynchronises the stream, and there is no way to notice until the output is garbage.