Basic Version: 

The Arithmetic Coder is a fairly complex compression algorithm that allows us to compress at a relatively high ratio.  It does this by compressing several bits that are the same into one bit.  It again relies on the fact that there is a very high correlation between neighboring pixels in an image.

 

We first calculate the frequency of the values in the image.  This way we can compress the values that show up the most frequently with the highest compression ratio.  We essentially can encode several of these values as one single value.  Using this method, the values with a small frequency will get compressed poorly, but it doesn't matter because they occur so infrequently. 

 

---

Adaptive Arithmetic Coder: 

This is a variation on the arithmetic coder that it most cases turns out to be more efficient.  Instead of calculating the frequencies of the values at the beginning, we assume every value has a frequency of 1.  Then as we go along, if we hit the value, then we increase its frequency as well as the total cumulative frequency by 1.  We go through the bits in a wave-like fashion in order to get a higher correlation between pixels.

 

---