PAQ

PAQ is a series of lossless data compression archivers that have gone through collaborative development to top rankings on several benchmarks measuring compression ratio (although at the expense of speed and memory usage). Specialized versions of PAQ have won the Hutter Prize and the Calgary Challenge. PAQ is free software distributed under the GNU General Public License.

Algorithm

PAQ uses a context mixing algorithm. Context mixing is related to prediction by partial matching (PPM) in that the compressor is divided into a predictor and an arithmetic coder, but differs in that the next-symbol prediction is computed using a weighted combination of probability estimates from a large number of models conditioned on different contexts. Unlike PPM, a context doesn't need to be contiguous. Most PAQ versions collect next-symbol statistics for the following contexts:

n-grams; the context is the last n bytes before the predicted symbol (as in PPM);

whole-word n-grams, ignoring case and nonalphabetic characters (useful in text files);

"sparse" contexts, for example, the second and fourth bytes preceding the predicted symbol (useful in some binary formats);

"analog" contexts, consisting of the high-order bits of previous 8- or 16-bit words (useful for multimedia files);

two-dimensional contexts (useful for images, tables, and spreadsheets); the row length is determined by finding the stride length of repeating byte patterns;

specialized models, such as x86 executables, BMP, TIFF, or JPEG images; these models are active only when the particular file type is detected.

All PAQ versions predict and compress one bit at a time, but differ in the details of the models and how the predictions are combined and postprocessed. Once the next-bit probability is determined, it is encoded by arithmetic coding. There are three methods for combining predictions, depending on the version:

In PAQ1 through PAQ3, each prediction is represented as a pair of bit counts

(

n

0

,

n

1

)

{\displaystyle (n_{0},n_{1})}

.