Prediction by Partial Matching Algorithm

Prediction by partial matching, known as PPM, is an adaptive statistical algorithm for lossless data compression that predicts the next symbol in a stream of data from the context of symbols that immediately preceded it, then hands that prediction to an entropy coder, typically an arithmetic coder, to actually produce the compressed output. For each symbol it tries to find a match using the longest available context, a fixed number of preceding symbols, and falls back to progressively shorter contexts, down to no context at all, whenever the current context has never been followed by that symbol before, a fallback mechanism that also solves the zero-frequency problem of assigning a sensible probability to a symbol the model has never seen in that context; because the model updates its statistics as it processes the data, both the compressor and the decompressor stay synchronized without needing to transmit a separate statistical table. John Cleary and Ian Witten introduced prediction by partial matching in a paper published in April 1984, reporting that adaptive coding based on this kind of partial string matching could compress ordinary mixed-case English text to roughly 2.2 bits per character.