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. 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. See Lossless compression benchmarks 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. PAQ1 was released on January 6, 2002 by Matt Mahoney. It used fixed weights and did not include