Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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)?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
Thank you :) However, I'm confused how your pseudocode maps to my understanding of arithmetic coding; whereby you narrow down an interval in [0,1) such that it is the intersection of successive applications of the model at different "zoom levels", then you pick a point within that interval. I'm very much a novice, so if you could share any useful references (beyond Wikipedia) that would be very helpful... –  Xophmeister Dec 17 '12 at 21:56

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!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.