Arithmetic coding, the termination symbol, and the empty string

Question

Suppose the source alphabet is $a, b, c$ with $a$ as the termination symbol and so the unit interval is correspondingly divided as $[0, P(a), P(a)+P(b), 1]$.

Strings consisting of a bunch of $b$'s and $c$'s ending with an $a$ (the termination symbol) are valid for encoding. Strings with an $a$ in middle are considered invalid for encoding.

So its easy to construct strings with encodings lying in the interval $[P(a), 1)$. But does arithmetic coding assign any string an encoding in the interval $[0, P(a))$? Would the empty string qualify as being encoded to a bitstring lying in $[0, P(a))$? Since the empty string can be thought of as the string "$a$" or as just the termination symbol.

Since devoting space to encoding the empty string would seem pointless why not have the first division of the unit interval be $[0, (P(b)-P(a))/(1-P(a)), 1]$ which corresponds to mapping $[P(a), P(a)+P(b), 1]$ to fill up the unit interval. Then subsequent refining divisions would use $[0, P(a), P(a)+P(b), 1]$ as usual.

Answer 1

Why shouldn't you be able to send the empty string? Shouldn't it be considered a valid message?

But if you don't allow the empty string as a message, then your modified protocol will work fine, and will save you on average a small fraction of a bit per message.

Is this tweak worth putting into your implementation so as to improve the performance? Let's work out how much it saves you. Suppose you're using a binary alphabet, and your average message is around 100 bits in length. You then want the termination symbol to have probability 1/100. By not allowing the possibility of the termination symbol being the first bit, you save on the order of 1/100 bits^* per message. If you assume a compression ratio of 2, the total improvement in performance is 0.02%. Since 100 bits is a smaller average message length than I expect you would see anywhere, the actual performance improvement would probably be even smaller. I thus suspect that this variant would not actually be used in practice.

^* 1/100 nats, or 0.014 bits, to be more precise.

Answer 2

You are right that in many real-world applications, we never need to transmit an empty string.

You are right that in those applications, we could divide the unit interval into only two pieces, [0,(P(b)−P(a))/(1−P(a)),1] when encoding the first bit, which corresponds to mapping [P(a),P(a)+P(b),1] to fill up the unit interval.

However, arithmetic coding already does that, so there is no need to add special case code to handle that, much like there is no need to add special-case hardware to zero the AX register in the special case of XOR AX, AX.

details

At any time during sequentially encoding or decoding, the P(a) is the probability that the message ends at that time.

If you know for a fact that P(a) is zero at one or more times during sequential decoding -- if you know that you will never need to transmit the empty string, or you know for a fact that you will always transmit a multiple of 8 bits -- then the compression implementation and decompression implementation should set P(a) to zero at those one or more times.

Then the normal [0,P(a),P(a)+P(b),1] intervals becomes [0, 0, P(b), 1], giving effectively only two intervals of non-zero measure -- [0, P(b), 1]. Your suggestion of [0,(P(b)−P(a))/(1−P(a)),1], when you know P(a) is zero, becomes the same two intervals [0, P(b), 1].

does arithmetic coding assign any string an encoding in the interval [0,P(a))?

Yes, the encoder assigns the empty string an encoding in that interval -- but only if that interval exists.

However, in the special case where P(a) is zero, the interval [0,P(a)) becomes [0, 0), which is empty (not even a single point).

In that special case where you know we will never need to transmit an empty string, then P(a) is zero while encoding that first bit, and so arithmetic coding does not assign any string a finite-length encoding in the interval [0,P(a)).

And so, in that special case where P(a) is zero during the first bit, a arithmetic decoder will never emit an empty string, no matter what compressed representation it is given. Even if the range of some symbol did include exactly one single point -- such as, for example, [0,0] -- the decompressor would never emit that symbol. Even the decompressor is given the sequence of decimal digits (or whatever other base the corresponding arithmetic compressor uses) 00000000000.... , each "0" of which narrows the range down more and more but never enough to put the range of that value as exactly equal to or inside the [0,0] range. As more and more "0" symbols in the compressed representation is fed to the decoder, the midpoint of the current range keeps getting closer to, but never actually enters into the single-point range [0,0].

This is related to the zero-frequency problem.