Simple implementation of PAQ1 compression algorithm

I wrote a simplified version of PAQ1 compression algorithm in C#.

You can check the source code at github.

PAQ1 is context mixing compression algorithm, written by Matt Mahoney in 2002. It is similar to very popular in academic papers PPM. But the differences are interesting.

First, PAQ1 works at bit level instead of byte level of PPM. Just like DMC. It's known that PPM performs poorly when applied on a bit level. Why PAQ1 works good then?

The reason for this can be its blending strategy and fast non-stationary adaptation.

Blending strategy

PAQ1 does not apply complicated schemes of context selection PPM uses. Also it does not predict escape probabilities. It just blends all predictions in weighted average. Weight for specific model is just square of its order:

int n0 = 1;
int n1 = 1;
for (var i = 0; i < N; i++) {
  var w = (i + 1) * (i + 1);
  var n = m[i].predict();
  n0 += w * n[0];
  n1 += w * n[1];
}

Non-stationary adaptation

It can surprise one, but instead of usual counters division on overflow, PAQ1 aggressively divides counter of opposite bit on each encoding step. This keeps counters from growing. Also PAQ1 limits all counters to 255. So instead of keeping as much of frequency information as it can, it courageously forgets it.

if (el[a] < 255) el[a]++;
if (el[b] > 0) {
  el[b] = el[b] / 2 + 1;
}

Sample of compressed data

The figure below shows compression of individual symbols:

White symbols require about one bit to encode. Other colors towards black require more than 1 bit to encode.

Conclusion

PAQ1 also has several additional models. But I like the general one only. The simplicity of algorithm without additional models is similar to DMC but compression ratio is still very good.

PAQ1 was a base for further PAQ-family algorithms reaching top places on many compression benchmarks (for example, on Hutter Prize). So as for today PAQ-related algorthms are among the most powerful ones in data compression.

 

shitpoet@gmail.com