Stream Codes

What if we generalize to arbitrary intervals? Then we get arithmetic coding, which turns out to yield (near-)optimal stream codes for any probability distribution.

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.

This time, 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. See the Dasher zooming interface for a visualization.

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.

Mission accomplished for real? Almost. There are a few loose ends:

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 around this. We must send the message 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 the third concern: 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 endpoints are harmless provided the interval isn’t too small.

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.

The last of our loose ends has a loose end. We said that we’re fine so long as "the interval isn’t too small". But just how small can intervals get? Do they get so small that dropping the least-significant bits would cause disaster?

Unfortunately, yes. 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, the encoder must stay silent, yet as the run of "B"s grows, the straddling interval shrinks, seemingly dooming us to arbitrary precision. See the table-maker’s dilemma, a related problem.

Fortunately, hugging 1/2 is the sole pitfall, for whenever the interval lies to one side, we can send off the most significant bit. Even more fortunately, there is a simple fix. If a straddling interval lies in [1/4, 3/4), 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 because 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 quantize 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. An earlier version confused a strict inequality for one that wasn’t, resulting in erroneous decodings, but only rarely!

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

Mission accomplished. Our arithmetic coding demo 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 explore a stream code of a different nature.

We need a function that splits a list into two in all possible ways:

We chunk the input by repeatedly breaking off the shortest prefix we haven’t seen yet.

We index these unique prefixes:

How does this help? If we replace each chunk with its index, we get [0,1,2,…​], which is clearly impossible to decode!

But what if for each chunk, we drop the last symbol before looking up its index, and also send the symbol that was dropped?

The first chunk is always empty so we skip it.

This works! A decoder can build the same table as it proceeds: by inductive assumption our table contains all chunks seen so far, thus we can always correctly update the table from an index and a new symbol.

It remains to specify how the indexes are encoded in binary. Since the sender and receiver have the same table, they both know the minimum number of bits \(m\) required to represent the current largest index. Altogether, we have:

The examples are chosen so the last string is absent from the table. We can force this to happen by using a special symbol to mark the end of the message. Or we can finish with the index of some string whose prefix matches the final string. Our code does the latter.

Lempel-Ziv compression is asymptotically optimal but only on a galactic scale (for any ergodic source, we eventually approach the entropy of the source, but typically not before we run out of space and time). Indeed, we see the Lempel-Ziv compression often produces output longer than the input for small examples, though we can easily optimize slightly:

Nonetheless, in practice, Lempel-Ziv is effective, because real data often contains many copies of the same sequence. Also, Lempel-Ziv is easy to implement it just works. There’s no need to model the data; no need for finding relative symbol frequencies; no need for thinking about how earlier symbols affect the probabilities of future symbols. Fire and forget.

With Huffman or arithmetic coding, we can automate modeling by, say, updating a probability distribution as we encode. But it’s more work.

In my younger days, Lempel-Ziv dominated compression. Many DOS executables I ran were compressed with LZEXE, so they’d decompress themselves in memory before running. GIF files and other widespread media formats relied on a variant of Lempel-Ziv. So did ZIP archives, and its competitors like ARC. On Unix, the compress and gzip tools also use Lempel-Ziv.

Then in the 1990s, the the Burrows-Wheeler transform was discovered, which can be viewed a stream code if we think of the alphabet as consisting of giant blocks. As the popularity of bzip2 attests, this algorithm seems as good as Lempel-Ziv for detecting patterns like the same string appearing several times in a block, though other algorithms such as arithmetic coding are required to actually compress the data.

We reuse code from previous pages:

Huffman coding already works well on our running english example, and beats arithmetic coding on particular strings by chance. For the latter, we show the decoding, as it may show too many symbols because we have not correctly handled the end of the message.

Lempel-Ziv does poorly because repeated substrings are unlikely, and because we replace each letter with 5 bits (like a Baudot code, or Bacon’s cipher) to imitate how compression tools are often run on ASCII files. But we would see savings on realistic text, and we stress that we can do without a model of the data source.

Arithmetic coding shines with lopsided distributions, as any symbol code requires 1 bit per symbol at minimum. Lempel-Ziv also usually beats symbol codes, because it can take advantage of repetitions.

Again, the comparison is a little unfair because our arithmetic coding implementation may mess up the end of the message. But the longer the message, the less this matters.