Prediction by Partial Matching (PPM) is a lossless compression method built around context modelling: predict the next symbol from the longest useful history, but back off intelligently when that context has too little evidence or has never seen the answer.
PPM compression connects variable-order Markov models, conditional probability, escape symbols, exclusion, arithmetic coding and entropy coding. Instead of treating text or bytes as independent symbols, it asks what followed the same recent context before. Longer contexts can make predictions sharper; shorter contexts provide broader evidence when the long context fails.
The central theory question is how Prediction by Partial Matching compresses data and why context can make a lossless message smaller. PPM does not remove information. It makes expected symbols cheaper by transferring repeated history into a shared probabilistic model that encoder and decoder update together.
Quick Read
- PPM predicts from recent symbol contexts.
- It tries specific long contexts before backing off to shorter suffixes.
- Escape probability reserves coding mass for unseen continuations.
- Exclusion prevents already-rejected symbols from consuming probability again during backoff.
- Arithmetic or range coding converts PPM probabilities into bits.
- Memory, maximum order and sparse contexts determine practical cost.
1. Diagnose the Failure: Global Frequency Is Not Enough
In English, a global letter table knows that e is common. It does not know that after q, u becomes extraordinarily likely. It does not know that after “compress”, particular suffixes become plausible. Context changes probability. PPM exists to exploit that change.
A zero-order model asks how often each symbol appeared. An order-one model conditions on one previous symbol. Order two conditions on two, and so on. If the source contains real sequential dependencies, conditional entropy can fall as relevant context is added.
2. Longest Context First
Suppose the recent history is “tion”. A PPM model may consult the longest stored suffix first. If that context has useful counts, it assigns probabilities from those counts. If the next symbol has never appeared there, the model emits an escape and backs off to a shorter suffix, continuing until the symbol can be represented.
This creates a hierarchy of evidence. Specific contexts get first opportunity because they may be highly predictive. General contexts remain available because they have more observations.
3. Why Backoff Is a Feature
A long context can be statistically fragile. If it occurred once, a single continuation should not become certainty. Backoff is disciplined humility: use specific evidence when it exists, but do not pretend sparse evidence is complete knowledge.
This is the same bias–variance tension encountered in Context Tree Weighting, but the mechanism is different. PPM owns explicit longest-context prediction, escape and backoff; CTW owns recursive weighting over context-tree models.
4. Escape Probability
Every context model must reserve probability for novelty. If a context has observed A, B and C but the next symbol is D, assigning D probability zero would make lossless coding impossible under that context. An escape event says: the answer is not represented here; move to a shorter context.
PPM variants differ substantially in how they estimate escape probability. The choice matters because escapes dominate sparse contexts and become rarer in mature contexts.
5. Exclusion
After escaping, symbols already seen and rejected at a longer context can often be excluded from the shorter model for the current prediction. The escape path itself provides side information: we know the next symbol was not one of those higher-context candidates.
6. Worked Example
Imagine context “ab” appeared five times: three followed by c and two by d. If c occurs next, the order-two model can encode it cheaply. If e occurs, the model escapes, excludes c and d where the variant permits, and consults context “b”. If b has often been followed by e, the backed-off prediction can still be strong.
The decoder follows the identical path because it has the same history and deterministic update rules.
7. Arithmetic Coding Is the Cashier
PPM produces probabilities. Arithmetic or range coding turns those probabilities into a reversible bitstream. If PPM assigns probability p to the observed symbol, the ideal incremental cost is approximately -log₂p bits. Good predictions are cheap; surprises are expensive.
8. Maximum Order and Memory
Higher maximum order exposes longer dependencies but grows context storage. Rare contexts consume memory. Searches and updates cost time. Practical PPM implementations cap order, prune models, bound memory or use compact structures.
The correct question is not “how much history can we store?” but “how much history still changes the distribution enough to earn its cost?”
9. PPM Versus LZ
LZ methods usually replace exact repeated substrings with references or dictionary codes. PPM can benefit without an exact long match because it predicts the next symbol statistically. LZ asks whether this sequence occurred; PPM asks what tends to follow this history.
10. PPM Versus CTW
CTW mixes candidate context-tree structures recursively. PPM follows a backoff hierarchy with explicit escapes. Both address variable memory, but they represent uncertainty about context depth differently.
11. Text Compression
Text is natural PPM territory because local character contexts contain strong dependencies. Spelling, morphology, punctuation and recurring fragments sharpen conditional probabilities. PPM-family compressors have historically achieved strong text ratios, often by spending substantial computation and memory on modelling.
12. Distribution Shift and Forgetting
A model trained on prose can become stale when the stream becomes code or binary data. Counts accumulated under the old regime can slow adaptation. Bounded memory, rescaling and model resets are therefore not merely implementation details; they decide how quickly the compressor can stop believing yesterday.
13. The Clementi Mechanism Pattern
The diagnostic is fixed-order failure. The mechanism is longest-context prediction with escape and backoff. The practice is to compare code cost across context depths. The transfer is recognising when specificity helps and when sparse evidence hurts. The independence test is whether the reader can explain why more context can make prediction worse.
14. Primary to Advanced Route
A Primary learner can begin with “what letter usually comes after q?” A Secondary learner can build conditional frequency tables. A JC learner can connect conditional probability to logarithmic code length. An advanced reader can study escape estimators, exclusion, redundancy bounds and arithmetic coding.
15. Practical Checklist
- What alphabet is modelled?
- What maximum order is allowed?
- How are escape probabilities estimated?
- Is exclusion used?
- How are contexts stored and pruned?
- How are counts rescaled?
- Which entropy coder consumes the probabilities?
- What is the memory ceiling?
16. FAQ
Is PPM lossless? Yes, when encoder and decoder share deterministic model rules and the probability stream is coded losslessly.
Does PPM always trust the longest context? No. It escapes or backs off when the needed continuation is not represented under the current context.
Why can PPM outperform simple frequency coding? Because conditional distributions can be much sharper than global distributions.
Is PPM universally best? No. Its modelling strength can cost substantial memory and CPU, and other source families may suit dictionary or transform methods better.
17. Deeper Point
PPM teaches that memory is not valuable merely because it is long. Memory is valuable when it changes what comes next.
A good compressor does not ask only what happened before. It asks how much of what happened before still deserves to speak.