PAQ

A sample session of PAQ8O

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.[1] PAQ is free software distributed under the GNU General Public License.[2]

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 weighed 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:

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:

PAQ1SSE and later versions postprocess the prediction using secondary symbol estimation (SSE). The combined prediction and a small context are used to look up a new prediction in a table. After the bit is encoded, the table entry is adjusted to reduce the prediction error. SSE stages can be pipelined with different contexts or computed in parallel with the outputs averaged.

Arithmetic coding

A string s is compressed to the shortest byte string representing a base 256 big-endian number x in the range [0, 1] such that P(r < s) ≤ x < P(rs), where P(r < s) is the probability that a random string r with the same length as s will be lexicographically less than s. It is always possible to find an x such that the length of x is at most one byte longer than the Shannon limit, −log2P(r = s) bits. The length of s is stored in the archive header.

The arithmetic coder in PAQ is implemented by maintaining for each prediction a lower and upper bound on x, initially [0, 1]. After each prediction, the current range is split into two parts in proportion to P(0) and P(1), the probability that the next bit of s will be a 0 or 1 respectively, given the previous bits of s. The next bit is then encoded by selecting the corresponding subrange to be the new range.

The number x is decompressed back to string s by making an identical series of bit predictions (since the previous bits of s are known). The range is split as with compression. The portion containing x becomes the new range, and the corresponding bit is appended to s.

In PAQ, the lower and upper bounds of the range are represented in 3 parts. The most significant base-256 digits are identical, so they can be written as the leading bytes of x. The next 4 bytes are kept in memory, such that the leading byte is different. The trailing bits are assumed to be all zeros for the lower bound and all ones for the upper bound. Compression is terminated by writing one more byte from the lower bound.

Adaptive model weighting

In PAQ versions through PAQ6, each model maps a set of distinct contexts to a pair of counts, , a count of zero bits, and , a count of 1 bits. In order to favor recent history, half of the count over 2 is discarded when the opposite bit is observed. For example, if the current state associated with a context is and a 1 is observed, then the counts are updated to (7, 4).

A bit is arithmetically coded with space proportional to its probability, either P(1) or P(0) = 1 − P(1). The probabilities are computed by weighted addition of the 0 and 1 counts:

where wi is the weight of the i-th model. Through PAQ3, the weights were fixed and set in an ad-hoc manner. (Order-n contexts had a weight of n2.) Beginning with PAQ4, the weights were adjusted adaptively in the direction that would reduce future errors in the same context set. If the bit to be coded is y, then the weight adjustment is:

Neural-network mixing

Beginning with PAQ7, each model outputs a prediction (instead of a pair of counts). These predictions are averaged in the logistic domain:

where P(1) is the probability that the next bit will be a 1, Pi(1) is the probability estimated by the i-th model, and

After each prediction, the model is updated by adjusting the weights to minimize coding cost:

where η is the learning rate (typically 0.002 to 0.01), y is the predicted bit, and (y − P(1)) is the prediction error. The weight update algorithm differs from backpropagation in that the terms P(1)P(0) are dropped. This is because the goal of the neural network is to minimize coding cost, not root mean square error.

Most versions of PAQ use a small context to select among sets of weights for the neural network. Some versions use multiple networks whose outputs are combined with one more network prior to the SSE stages. Furthermore, for each input prediction there may be several inputs which are nonlinear functions of Pi(1) in addition to stretch(P(1)).

Context modeling

Each model partitions the known bits of s into a set of contexts and maps each context to a bit history represented by an 8-bit state. In versions through PAQ6, the state represents a pair of counters (n0, n1). In PAQ7 and later versions under certain conditions, the state also represents the value of the last bit or the entire sequence. The states are mapped to probabilities using a 256-entry table for each model. After a prediction by the model, the table entry is adjusted slightly (typically by 0.4%) to reduce the prediction error.

In all PAQ8 versions, the representable states are as follows:

To keep the number of states to 256, the following limits are placed on the representable counts: (41, 0), (40, 1), (12, 2), (5, 3), (4, 4), (3, 5), (2, 12), (1, 40), (0, 41). If a count exceeds this limit, then the next state is one chosen to have a similar ratio of n0 to n1. Thus, if the current state is (n0 = 4, n1 = 4, last bit = 0) and a 1 is observed, then the new state is not (n0 = 4, n1 = 5, last bit = 1). Rather, it is (n0 = 3, n1 = 4, last bit = 1).

Most context models are implemented as hash tables. Some small contexts are implemented as direct lookup tables.

Text preprocessing

Some versions of PAQ, in particular PAsQDa, PAQAR (both PAQ6 derivatives), and PAQ8HP1 through PAQ8HP8 (PAQ8 derivatives and Hutter prize recipients) preprocess text files by looking up words in an external dictionary and replacing them with 1- to 3-byte codes. In addition, uppercase letters are encoded with a special character followed by the lowercase letter. In the PAQ8HP series, the dictionary is organized by grouping syntactically and semantically related words together. This allows models to use just the most significant bits of the dictionary codes as context.

Comparison

The following table is a sample from the Large Text Compression Benchmark by Matt Mahoney that consists of a file consisting of 109 bytes (1 GB, or 0.931 GiB) of English Wikipedia text.

Program Compressed size (bytes) % of original size Compression time (s) Memory (MiB)
PAQ8HP8 133,423,109 13.34 64 639 1849
PPMd 183,976,014 18.4 880 256
bzip2 254,007,875 25.4 379 8
InfoZIP 322,649,703 32.26 104 0.1

See Comparison of file archivers for a list of file compression benchmarks.

History

The following lists the major enhancements to the PAQ algorithm. In addition, there have been a large number of incremental improvements, which are omitted.

Hutter Prizes

The series PAQ8HP1 through PAQ8HP8 were released by Alexander Ratushnyak from August 21, 2006 through January 18, 2007 as Hutter Prize submissions. The Hutter Prize is a text compression contest using a 100 MB English and XML data set derived from Wikipedia's source. The PAQ8HP series was forked from PAQ8H. The programs include text preprocessing dictionaries and models tuned specifically to the benchmark. All non-text models were removed. The dictionaries were organized to group syntactically and semantically related words and to group words by common suffix. The former strategy improves compression because related words (which are likely to appear in similar context) can be modeled on the high order bits of their dictionary codes. The latter strategy makes the dictionary easier to compress. The size of the decompression program and compressed dictionary is included in the contest ranking.

On October 27, 2006, it was announced[5] that PAQ8HP5 won a Hutter Prize for Lossless Compression of Human Knowledge of 3,416.

On June 30, 2007, Ratushnyak's paq8hp12 was awarded a second Hutter prize of €1732,[6] improving upon his previous record by 3.46%.

PAQ derivations

Being free software, PAQ can be modified and redistributed by anyone who has a copy. This has allowed other authors to fork the PAQ compression engine and add new features such as a graphical user interface or better speed (at the expense of compression ratio). Notable PAQ derivatives include:

See also

References

  1. "The Compression/SHA-1 Challenge". Mailcom.com. Retrieved 2010-05-19.
  2. "Homepage of the PAQ compressors". Retrieved 2007-07-10. You may download, use, copy, modify, and distribute these programs under the terms of the GNU general public license
  3. "Ubuntu zpaq(1) man page".
  4. "ZPAQ Level 1 Specification" (PDF). Retrieved 2010-09-03.
  5. James Bowery. Alexander Ratushnyak Wins First Hutter Prize Payout. Published October 27, 2006. Retrieved October 30, 2006.
  6. http://prize.hutter1.net/award2.gif
  7. 1 2 dwing's homepage Archived February 24, 2007, at the Wayback Machine.
  8. "KGB Archiver homepage". Kgbarchiver.net. Retrieved 2010-05-19.
  9. "EmilCont Ultracompression". Freewebs.com. Retrieved 2010-05-19.
  10. Matt Mahoney (2007). "LPAQ". Retrieved 2013-12-29.
  11. "PeaZip". PeaZip. Retrieved 2013-10-06.
  12. "Single file data compression benchmark, sorted on compression ratio". Maximumcompression.com. 2007-04-14. Retrieved 2010-05-19.
  13. "PerfectCompress Official Website". Moises-studios.110mb.com. 2010-04-03. Retrieved 2010-05-19.
  14. "PerfectCompress Official Facebook Page". Facebook.com. Retrieved 2010-05-19.

Further reading

This article is issued from Wikipedia - version of the 11/15/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.