# Arithmetic coding, the termination symbol, and the empty string

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.

• Can someone explain what this question is about? What are the intervals you speak of? Are they the lexicographic order of word on three symbols? What is $P(a)$? – Andrej Bauer Mar 27 '12 at 5:11
• Ok, I educated myself and provided a link in the question for other ignorant people. – Andrej Bauer Mar 27 '12 at 6:24

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.

• In the context of using arithmetic coding for real world compression when would it make sense to encode the empty string. Maybe a better way to phrase the question is what do real world uses of arithmetic coding do about the empty string? Maybe someone who is an expert at the various codecs can answer? – user782220 Mar 27 '12 at 5:07
• You save a small fraction of a bit per message if you don't allow encoding the empty string. You have to add a special case to your code so that it does something different on the first encoded symbol than on the others. Furthermore, you end up with a program that will break if somebody feeds it the empty string. Is it really worth it? – Peter Shor Mar 27 '12 at 13:19

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.

• What do you mean by "the arithmetic encoder" here? Maybe some ideal arithmetic encoder does, but I don't expect that any actual implementations of arithmetic coding do this. – Peter Shor Apr 7 '12 at 14:37
• @PeterShor: you're right, this is for an ideal arithmetic encoder that uses only the "a" symbol as a stop symbol, rather than real arithmetic encoders which often store the "uncompressed length" in a header somewhere, or at least peek ahead at the actual "compressed length". – David Cary Apr 8 '12 at 23:06