Stream Codes

What if we allow arbitrary intervals? For recording a sequence of moves in rock-paper-scissors, assuming a uniform distribution, it would be optimal to use base 3, namely divide the unit interval into thirds, then divide each of those into thirds, and so on.

More generally, the probability distribution of an information source would describe exactly how to partition the unit interval, and lead to an optimal encoding.

We represent probabilities with arbitrary precision rationals.

We represent an interval with its lower endpoint and its length. The following converts probabilities to intervals.

Let’s code! Roughly speaking, we start with the unit interval, and as we encode symbols, we zoom in on sub-intervals of our current interval.

Mission accomplished? No, it’s hardly a stream code if we analyze the entire message to encode it. Also, for practical reasons, we wish to output 0s and 1s (though see range encoding).

Since we ought to produce output as we go, we convert what we can to binary on the fly. When both endpoints lie in the same half of the interval, we output one bit then double everything.

We finish by sending enough bits to describe a Huffman interval lying within the final interval.

Decoding inverts this process.

This seems to be an elegant generalization of symbol codes, but on closer inspection, there is cause for concern:

Let’s start with the good news. Let \(I\) be the interval \([0, m)\). Then \(I\) contains \([0, 1/2^n)\) where \(n = \lceil \lg 1/m \rceil\). If we translate \(I\), sometimes we find it contains a Huffman interval of the form \([k/2^n, (k+1)/2^n)\) which only takes \(n\) bits to represent.

But sometimes not, because it straddles a point \(j/2^n\) for some \(j\). Still, at least one of the half-intervals on either side lies in \(I\), that is, the interval \(I\) contains at least one of \([2j / 2^{n+1}, (2j + 1) / 2^{n+1})\) or \([(2j - 1)/2^{n+1}, 2j / 2^{n+1})\), otherwise \(1/2^n\) would exceed \(m\), a contradiction.

In other words, for any interval of length \(m\), we can find a Huffman interval within that we can represent with at most \(\lceil \lg 1/m \rceil + 1\) bits. Thus, the entire encoded message has under 2 bits of overhead.

Now the bad news. In general, our decoder cannot determine when to stop decoding. Consider a biased coin that shows heads 9 times out of 10. We encode heads with [0, 9/10) and tails with [9/10,1), which is optimal. But what do we make of the encoded message "0"? It means \([0,1/2)\), which is contained within:

…​

There is no way to recover the original message. We must send its length separately, or add a special end-of-message symbol and assign it some probability.

Our decoder above always chooses the longest possibility.

Let’s tackle arbitrary precision. We pick some power of two \(w\), and round our probabilities to the nearest rational whose denominator is \(w\). This is harmless for sufficiently large \(w\), as a tiny difference in probabilities has a negligible effect on compression, and we can now represent endpoints with integers. They are the numerators of fractions with denominator \(w\).

We’ve been sending off the most-significant bits when we can. What if we also lop off least-significant bits? That is, during encoding, we simply drop the low bits so that numbers representing the endpoints stay under \(w\)?

This amounts to perturbing the probability distribution as we go; we can view fixed precision as nudging probabilities so numbers happen to line up with certain powers of two, so we only ever drop zero bits. Again, for large enough \(w\), the tiny changes to the probabilities have a negligible effect on compression.

Changing probabilities on the fly is known as adaptive encoding. Apart from letting us get away with fixed precision, adaptive encoding can also improve compression by incorporating more facts about our information source.

For example, in English,"q" is almost always followed by "u", so after encoding a "q" we ought to give "u" a heavy weight in our probability distribution for the next letter. Naturally, the decoder must make the same assumptions.

We can also apply adaptive encoding to symbol codes, but the gains are more modest.

However, fixed precision raises a new concern. When dropping the least-significant bits, can we drop too much and lose information?

Unfortunately, we can. Consider the stream code:

A long string of "B"s leads to an interval that shrinks around 1/2. If eventually followed by an "A", then the encoding should be 0111…​, that is, something just below 1/2. On the other hand, if eventually followed by a "C", then the encoding should be 1000…​, that is, something just above 1/2. Until then, a naive encoder must stay silent, and if there are too many "B"s, something will go wrong. See the table-maker’s dilemma, a related problem.

Hugging 1/2 is the sole pitfall, for whenever the interval lies to one side, we can send off the most significant bit. Fortunately there is a simple fix. If the interval lies in [1/4, 3/4), we double it (more precisely, we widen it by doubling each endpoint’s distance from 1/2) and increment a counter. When the interval finally chooses a side, we output 011..1 or 100..0 accordingly, where the number of bits is equal to the counter. We then reset the counter.

Thus the interval is always greater than 1/4 in size, and we avoid underflow if we compute with just 2 more bits than the precision used to describe probabilities in the distribution.

(Symbol codes sidestep this problem by construction: their intervals never straddle 1/2.)

We demonstrate with 16-bit precision, though for clarity we use mathematical operations rather than bitwise operations. Our implementation actually involves 32-bit operations.

We define constants representing the points that divide the unit interval into quarters:

We convert the probability intervals to the form \([a/2^{16}, b/2^{16})\). As above, we store them as the lower endpoint and interval size. Since the denominator is always q4, we just store \((a, b - a)\).

We’ve conservatively taken the floor to approximate rationals, which means we may leave a sliver of the unit interval unused, and the approximations may be a touch worse than they ought to be. We could do better by calling round instead of floor and forcing the last interval to (a, q4 - a).

The encoder resembles our arbitrary precision version, except for a counter and an extra case for intervals contained in [1/4, 3/4):

We take pains to ensure the decoder recreates the encoder’s state of mind exactly, changing the probability distribution in lockstep.

The tuple (a, p) represents the interval [a, a + 2^p) and the lower p bits of a are always zero.

Thus arithmetic coding attains the optimal expected length \(H N\) save for under 2 bits of overhead for binary encoding and the cost of either transmitting the message length or adding an end-of-message symbol with a nonzero probability.

We reuse examples and code from our notes on symbol codes.