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