Unbounded Length Contexts for PPM J OHN G C LEARY AND W J T EAHAN Department of Computer Science University of Waikato Hamilton New Zealand Email jcleary cs waikato ac nz wjt cs waikato ac nz The PPM data compression scheme has set the performance standard in lossless compression of text throughout the past decade PPM is a nite context statistical modelling technique that can be viewed as blending together several xed order context models to predict the next character in the input sequence This paper gives a brief introduction to PPM and describes a variant of the algorithm called PPM which exploits contexts of unbounded length Although requiring considerably greater computational resources in both time and space this reliably achieves compression superior to the benchmark PPMC version Its major contribution is that it shows that the full information available by considering all substrings of the input string can be used effectively to generate high quality predictions Hence it provides a useful tool for exploring the bounds of compression Received June 28 1996 revised July 25 1997 1 INTRODUCTION The prediction by partial matching PPM data compression scheme has set the performance standard in lossless compression of text throughout the past decade The original algorithm was rst published in 1984 by Cleary and Witten 1 and a series of improvements was described by Moffat culminating in a careful implementation called PPMC which has become the benchmark version 2 This still achieves results superior to virtually all other compression methods despite many attempts to better it Other methods such as those based on Ziv Lempel coding 3 4 are more commonly used in practice but their attractiveness lies in their relative speed rather than any superiority in compression indeed their compression performance generally falls distinctly below that of PPM in practical benchmark tests 5 Prediction by partial matching or PPM is a nite context statistical modelling technique that can be viewed as blending together several xed order context models to predict the next character in the input sequence Prediction probabilities for each context in the model are calculated from frequency counts which are updated adaptively and the symbol that actually occurs is encoded relative to its predicted distribution using arithmetic coding 6 7 The maximum context length is a xed constant and it has been found that increasing it beyond about 5 does not generally improve compression 1 2 8 The present paper1 describes an algorithm PPM which exploits contexts of unbounded length It reliably achieves compression superior to the benchmark PPMC version although our current implementation uses considerably greater computational resources in both time and space The next section describes the basic PPM compression scheme 1 A preliminary form of this paper 25 was presented at the 1995 IEEE Data Compression Conference T HE C OMPUTER J OURNAL Following that we give our motivation for the use of contexts of unbounded length introduce the new method and show how it can be implemented using a trie data structure Then we give some results that demonstrate an improvement of about 6 over the benchmark PPMC Finally other seemingly unrelated compression schemes are related to the unbounded context idea that forms the essential innovation of PPM This paper uses the compression achieved on the standard Calgary text compression corpus 5 as a measure of how good the PPM model is The importance of this goes beyond the incremental improvement in the size of the compressed text Having a computer model that achieves close to human performance is critical in areas such as speech recognition spell checking OCR and language identi cation Teahan and Cleary 9 show how the PPM scheme can be used to build a character based computer model that can predict English text almost as well as humans They performed experiments on the same text that Claude E Shannon used in a famous experiment to estimate the entropy of English 10 and found that performance was close to and in some cases superior to human based results It is also well known in cryptography that removing redundancy is important prior to encryption to prevent statistical attacks 11 It is important here that there are no models human or otherwise that are signi cantly better than the model used to remove the redundancy 2 PPM PREDICTION BY PARTIAL MATCH The basic idea of PPM is to use the last few characters in the input stream to predict the upcoming one Models that condition their predictions on a few immediately preceding symbols are called nite context models of order k where k is the number of preceding symbols used PPM employs a suite of xed order context models with different values of Vol 40 No 2 3 1997 68 J G C LEARY AND W J T EAHAN TABLE 1 PPMC model after processing the string abracadabra maximum order 2 Order k 2 Predictions ab ac Order k 1 c p Predictions 2 3 1 3 a r 2 Esc 1 a 1 Esc 1 1 2 1 2 b ad a 1 Esc 1 1 2 1 2 c br a 2 Esc 1 2 3 1 3 d ca d 1 Esc 1 1 2 1 2 r da ra b 1 Esc 1 c 1 Esc 1 1 2 1 2 b Order k 0 c p 2 2 7 1 7 1 7 3 7 c 1 d 1 Esc 3 r 2 Esc 1 a 1 Esc 1 a 1 Esc 1 a 2 Esc 1 2 3 1 3 Predictions Order k 1 c p 5 16 2 16 1 16 1 16 2 16 5 16 a 5 b 2 c 1 d 1 r 2 Esc 5 Predictions A c p 1 1 A 1 2 1 2 1 2 1 2 1 3 1 3 1 2 1 2 k from 0 up to some pre determined maximum to predict upcoming characters For each model a note is kept of all characters that have followed every length k subsequence observed so far in the input and the number of times that each has occurred Prediction probabilities are calculated from these counts The probabilities associated with each character that has followed the last k characters in the past are used to predict the upcoming character Thus from each model a separate predicted probability distribution is obtained These distributions are effectively combined into a single one and arithmetic coding is used to encode the character that actually occurs relative to that distribution The combination is achieved through the use of escape probabilities Recall that each model has a different value of k The model with the largest k is by default the one used for coding However if a novel character is encountered in this context which means that the context cannot be used to encode it an escape symbol is transmitted to signal the decoder to switch to the model with the next smaller value of k The process continues until a model is reached in which the character