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})} . 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.
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, −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 three 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, n 0 {\displaystyle n_{0}} , a count of zero bits, and n 1 {\displaystyle n_{1}} , 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 ( n 0 , n 1 ) = ( 12 , 3 ) {\displaystyle (n_{0},n_{1})=(12,3)} 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:
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 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:
ni = n0i + n1i, error = y – P(1), wi ← wi + [(S n1i − S1 ni) / (S0 S1)] error.
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:
… excerpt ends here. Continue reading the full article.
