PAQ
From Wikipedia, the free encyclopedia
PAQ is a series of data compression archivers that have evolved through collaborative development to top rankings on several benchmarks measuring compression ratio (although at the expense of speed and memory usage). PWCM (PAQ weighted context mixing) is an independently developed closed source implementation of the PAQ algorithm. 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]
Contents |
[edit] 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:
- 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, or 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 (n0,n1). These counts are combined by weighted summation, with greater weights given to longer contexts.
- In PAQ4 through PAQ6, the predictions are combined as before, but the weights assigned to each model are adjusted to favor the more accurate models.
- In PAQ7 and later, each model outputs a probability rather than a pair of counts. The probabilities are combined using an artificial neural network.
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.
[edit] 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(r ≤ s), 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, -log2 P(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.
[edit] Adaptive Model Weighting
In PAQ versions through PAQ6, each model maps a set of distinct contexts to a pair of counts, n0, a count of zero bits, and n1, 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 (n0,n1) = (12,3) and a 1 is observed, then the counts are updated to (7,4).
A bit is arithmetic 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:
- S0 = Σi wi n0i
- S1 = Σi wi n1i
- S = S0 + S1
- P(0) = S0 / S
- P(1) = S1 / S
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 n².) 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:
- ni = n0i + n1i
- error = y – P(1)
- wi ← wi + [(S n1i - S1 ni) / (S0 S1)] error
[edit] 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:
- xi = stretch(Pi(1))
- P(1) = squash(Σi wi xi)
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
- stretch(x) = ln(x / (1 - x))
- squash(x) = 1 / (1 + e-x) (inverse of stretch).
After each prediction, the model is updated by adjusting the weights to minimize coding cost.
- wi ← wi + η xi (y - P(1))
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))
[edit] 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:
- The exact bit sequence for up to 4 bits.
- A pair of counts and an indicator of the most recent bit for sequences of 5 to 15 bits.
- A pair of counts for sequences of 16 to 41 bits.
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.
[edit] 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-3 byte codes. In addition, uppercase letters are encoded with a special character followed by the lower case letter. In the PAQ8HP series, the dictionary is organized by grouping syntactically and semantically related words together. This allows models that use just the most significant bits of the dictionary codes as context.
[edit] 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.
- PAQ1 was released on January 6, 2002 by Matt Mahoney. It used fixed weights and did not include an analog or sparse model.
- PAQ1SSE/PAQ2 was released on May 11, 2003 by Serge Osnach. It significantly improved compression by adding a SSE stage between the predictor and encoder. SSE (secondary symbol estimation) inputs a short context and the current prediction and outputs a new prediction from a table. The table entry is then adjusted to reflect the actual bit value.
- PAQ4, released November 15, 2003 by Matt Mahoney used adaptive weighting. PAQ5 (December 18, 2003) and PAQ6 (December 30, 2003) were minor improvements, including a new analog model. At this point, PAQ was competitive with the best PPM compressors and attracted the attention of the data compression community, which resulted in a large number of incremental improvements through April 2004. Berto Destasio tuned the models and adjusted the bit count discounting schedule. Johan de Bock made improvements to the user interface. David A. Scott made improvements to the arithmetic coder. Fabio Buffoni made speed improvements.
- During the period May 20, 2004 through July 27, 2004, Alexander Ratushnyak released seven versions of PAQAR, which made significant compression improvements by adding many new models, multiple mixers with weights selected by context, adding an SSE stage to each mixer output, and adding a preprocessor to improve the compression of Intel executable files. PAQAR stood as the top ranked compressor through the end of 2004 but was significantly slower than prior PAQ versions.
- During the period January 18, 2005 through February 7, 2005, Przemyslaw Skibinski released four versions of PASqDa, based on PAQ6 and PAQAR with the addition of an English dictionary preprocessor. It achieved the top ranking on the Calgary corpus but not on most other benchmarks.
- A modified version of PAQ6 won the Calgary Challenge on January 10, 2004 by Matt Mahoney. This was bettered by ten subsequent versions of PAQAR by Alexander Ratushnyak. The most recent was submitted on June 5, 2006, consisting of compressed data and program source code totaling 589,862 bytes.
- PAQ7 was released December 2005 by Matt Mahoney. PAQ7 is a complete rewrite of PAQ6 and variants (PAQAR, PAsQDa). Compression ratio was similar to PAQAR but 3 times faster. However it lacked x86 and a dictionary, so it did not compress Windows executables and English text files as well as PAsQDa. It does include models for color .bmp, .tiff, and .jpeg files, so compresses these files better. The primary difference from PAQ6 is it uses a neural network to combine models rather than a gradient descent mixer. Another feature is PAQ7's ability to compress embedded jpeg and bitmap images in Excel-, Word- and pdf-files.
- PAQ8A was released on January 27, 2006, PAQ8C on February 13, 2006. These were experimental pre-release of anticipated PAQ8. It fixed several issues in PAQ7 (poor compression in some cases). PAQ8A also included model for compressing (x86) executables.
- PAQ8F was released on February 28, 2006. PAQ8F had 3 improvements over PAQ8A: a more memory efficient context model, a new indirect context model to improve compression, and a new user interface to support drag and drop in Windows. It does not use an English dictionary like the PAQ8B/C/D/E variants.
- PAQ8G was released March 3, 2006 by Przemyslaw Skibinski. PAQ8G is PAQ8F with dictionaries added and some other improvements as a redesigned TextFilter (which does not decrease compression performance on non-textual files)
- PAQ8H was released on March 22, 2006 by Alexander Ratushnyak and updated on March 24, 2006. PAQ8H is based on PAQ8G with some improvements to the model.
- PAQ8I was released on August 18, 2006 by Pavel L. Holoborodko, with bug fixes on August 24, September 4, and September 13. It added a grayscale image model for PGM files.
- PAQ8J was released on November 13, 2006 by Bill Pettis. It was based on PAQ8F with some text model improvements taken from PAQ8HP5. Thus, it did not include the text dictionaries from PAQ8G or PGM model from PAQ8I.
- Serge Osnach released a series of modeling improvements: PAQ8JA on November 16, 2006, PAQ8JB on November 21, and PAQ8JC on November 28.
- PAQ8JD was released on December 30, 2006 by Bill Pettis. This version has since been ported to 32 bit Windows for several processors, and 32 and 64 bit Linux.
- PAQ8K was released on February 13, 2007 by Bill Pettis. It includes additional models for binary files.
- PAQ8O was released on August 24, 2007 by Andreas Morphis. Contains improved bmp and jpg models over PAQ8L. Can be optionally compiled with SSE2 support and for 64-bit Linux. The algorithm has notable performance benefits under 64-bit OS.
- PAQ9A was released on December 31, 2007 by Matt Mahoney. A new experimental version.It does not include models for specific file types and has an LZP preprocessor.
[edit] 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[3] that PAQ8HP5 won a Hutter Prize for Lossless Compression of Human Knowledge of 3,416 euro.
On June 30, 2007, Ratushnyak's paq8hp12 was awarded a second Hutter prize of 1732 euro, improving upon his previous record by 3.46%.
[edit] Benchmark Results
[edit] Maximum Compression
The Maximum Compression benchmark is maintained by Werner Bergmans. It uses two data sets, one public and one private. The public set consists of about 55 MiB in 10 files with a variety of types: text in various formats, executable data, and images. Programs are run with settings selecting maximum compression at the expense of speed and memory. It uses two scoring criteria: a point system based on rank on each file, and overall compressed size. As of February 10, 2007 it ranked the latest versions of 169 compression programs. Using the point system, PAQ8JD was ranked second after WinRK 3.0.3. On overall size, PAQ8JD was ranked first.
The second data set is private. It consists of 316,355,757 bytes in 510 files of various types. Programs are ranked by total compressed size, by compression time, and by a formula combining size and time. There were 200 tests, which include some older versions and some runs of the same program with different options. By overall size, WinRK 3.0.3 was ranked first, followed by PAQ8JC, then PAQ8JD. PAQ ranks near the bottom for compression time. PAQ8JD takes 47,558 seconds to compress the data (196'th place) compared to 4 seconds for the fastest program and 70,444 for the slowest.
[edit] Squeeze Chart
The Squeeze Chart by Stephen Busch ranks programs by total compressed size of 16 unpublished data sets totaling 3,271,105,873 bytes. As of January 20, 2007, it ranked PAQ8JC first out of 201 tests. PAQ8JD was not ranked.
[edit] Black Fox
The Black Fox Benchmark ranked 111 versions of 69 programs on 12 unpublished files totaling 30,309,194 bytes as of February 4, 2007. PAQ8JD was ranked first.
[edit] Large Text Benchmark
The Large Text Compression Benchmark by Matt Mahoney ranks programs by compressed size of a published file consisting of 109 bytes of Wikipedia English text. Unlike the other benchmarks, the compressed size includes the size of the decompressor and any associated files needed for decompression, as a zip archive. As of February 9, 2007, it ranked PAQ8HP8 first out of 62 programs.
PAQ is extremely CPU and memory intensive. The following table compares output size, compression time (on a 2.2 GHz Athlon-64) and memory usage (in MiB) for some popular programs on this benchmark.
| Rank | Program | Compressed size | Compression time | Memory |
|---|---|---|---|---|
| 1 | PAQ8HP8 | 133,423,109 | 64,639 sec. | 1849 MiB |
| 18 | PPMd | 183,976,014 | 880 sec. | 256 MiB |
| 44 | bzip2 | 254,007,875 | 379 sec. | 8 MiB |
| 49 | InfoZIP | 322,649,703 | 104 sec. | 0.1 MiB |
[edit] PAQ derivations
Being free software, the software 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). The most notable PAQ-clones are:
- WinUDA 0.291, based on PAQ6 but faster[4]
- UDA 0.301, based on PAQ8I algorithm[4]
- KGB, is basically PAQ6v2 with a GUI[5] (beta version supports PAQ7 compression algorithms)
- Emilcont based on PAQ6[6]
- Peazip GUI frontend (for Windows and Linux) for LPAQ and various PAQ8* algorithms[7]
[edit] See also
[edit] References
- ^ The Compression/SHA-1 Challenge
- ^ Homepage of the PAQ compressors. Retrieved on 2007-07-10. “You may download, use, copy, modify, and distribute these programs under the terms of the GNU general public license”
- ^ James Bowery. Alexander Ratushnyak Wins First Hutter Prize Payout. Published October 27, 2006, retrieved October 30, 2006.
- ^ a b dwing's homepage
- ^ KGB Archiver homepage
- ^ EmilCont Ultracompression
- ^ SourceForge.net: PeaZip
[edit] External links
- Project website - includes sources and windows command-line executables download.
- Compiled linux binaries - Linux command-line executables download.
- MaximumCompression.com, a site providing test results from compression of various file types using different compression tools.
|
||||||||||||||||||||||||||||||||||||||||||||
