PPMd

PPMd is a data compression algorithm in the Prediction by Partial Matching (PPM) family. It models the probability distribution of the next symbol conditioned on a context formed by preceding symbols, organizing these statistics in a context tree. Each node in the tree stores counts for possible following symbols. When encoding, PPMd uses an escape mechanism: if the current context has no observed count for the next symbol, an escape symbol is emitted and the model backs off to shorter contexts until a symbol with a known probability is found. The resulting probabilities are encoded with an arithmetic or range coder to produce the compressed bitstream.

The strength of PPMd lies in its use of high-order contexts while maintaining practical decoding for data with less repetition. By backing off when needed, it can adapt to different data regions and prevent explosion of the model size. Implementations typically include optimizations for memory layout and updating the context counts as data is processed, enabling efficient compression on large inputs. PPMd is known for strong performance on natural language text and other data with long-range dependencies, though this comes with higher computational overhead and greater memory usage compared with some block-based schemes.

Historically, PPMd is one of the practical realizations of the PPM concept and has been implemented in various software packages, including some archivers. Its design emphasizes adaptive context modeling and efficient escape handling, making it a reference point in studies of statistical data compression and in applications that prioritize compression effectiveness for text and similar data.