Arithmetic Coding Questions

Question

I have been reading up on arithmetic coding and, while I understand how it works, all the guides and instructions I've read start with something like:

Set up your intervals based upon the frequency of symbols in your data; i.e., more likely symbols get proportionally larger intervals.

My main query is, once I have encoded my data, presumably I also need to include this statistical model with the encoding, otherwise the compressed data can't be decoded. Is that correct? I don't see this mentioned anywhere -- the most I've seen is that you need to include the number of iterations (i.e., encoded symbols) -- but unless I'm missing something, this also seems necessary to me.

If this is true, that will obviously add an overhead to the final output. At what point does this outweigh the benefits of compression (e.g., say if I'm trying to compress just a few thousand bits)? Will the choice of symbol size also make a significant difference (e.g., if I'm looking at 2-bit words, rather than full octets/whatever)?

Answer 1

Typically the overhead of including the statistical model is avoided by using an adaptive approach. The encoder and decoder begin in the same predefined state and adapt to the data. This allows the decoder to track the encode. An example would be starting with 128 uniform intervals for each ascii char in [0..127]. Then the encoder logic is:

 while (there is data)

      encode the char to a symbol

      increment that chars count

      update the model

 end while

The decoder follows the similar logic:

 while (there is data)

      decode the symbol to a char

      increment that chars count

      update the model

 end while

In practice arithmetic coding is highly time consuming for marginal gains in compression performance. An H.264 video decoder I worked on slowed down by about a third due to arithmetic coding.

Answer 2

I think the approach described by @CWallach is the most common way to handle this, but it has two potential downsides, since you're continually updating the model in during encoding and decoding:

1. It's somewhat slower.
2. It's (even more) difficult to do random access.

Some schemes do put the codebook at the front of the data file. This would add some overhead to very small files, though you could potentially do something clever like transmit the smaller of the compressed file + codebook or the original file.

Finally, a fixed codebook could work pretty well for some applications. English text, for example, has a pretty typical character structure, and a model trained on one large corpus would probably perform pretty well when applied to another large document. That said, small or atypical documents might not compress well.

I vaguely remember an old (BBS-era) compression program which had options to do all three of these options. I think it even had several built-in codebooks for different file types. Unfortunately, I can't remember what it was called, but I'll update if I do!