Is PPM itself arithmetic coding?

No. PPM supplies a probability model; arithmetic coding is commonly used to encode symbols using those probabilities.

Why are escape events needed?

They tell the decoder to move to a shorter context when the next symbol cannot be represented at the current one.

Must the decoder receive the whole model separately?

In an adaptive setup, it can rebuild the model through identical updates, provided initialization and all coding rules agree.

AI Glossary / MLOps and deployment / Intermediate

Prediction by partial matching

Definition

Prediction by partial matching, or PPM, is an adaptive statistical approach to lossless compression that predicts the next symbol from preceding symbols. It uses contexts of different lengths, backing off to shorter ones when a longer context cannot encode the next symbol directly. An entropy coder then converts these probability estimates into a compressed stream.

What it means

Local patterns make sequences predictable. Characters following a familiar prefix may differ in frequency from characters across the whole document. A context model records these patterns.

Longer contexts provide more specific but less frequently observed patterns. PPM maintains several context lengths, using a shorter suffix of recent history when a longer match is insufficient.

PPM predicts symbols statistically; it does not need to understand their meaning. It is also distinct from replacing long repeated strings with dictionary references. Its model supplies probabilities, and the associated coding machinery represents the actual symbols without losing information.

How it works

The encoder and decoder begin with compatible model states and rules. For each symbol, the encoder consults the longest permitted relevant context. If the symbol is represented there, it is encoded using that distribution.

If not, an escape event signals a move to a shorter context when needed. This continues until the symbol can be represented, with a fallback rule for symbols not encountered before. An entirely unseen context can sometimes be skipped without explicit signaling because both sides already know it has no predictions.

After the symbol is encoded or decoded, both sides update their statistics identically. This synchronized adaptation avoids transmitting the complete changing model after each step.

PPM variants differ in escape probabilities, exclusions, context limits, and update rules. Exclusion can remove symbols already ruled out at a longer context from shorter-context distributions. Those details affect both compression and decoder compatibility; PPM is a family of methods rather than one interchangeable file format.

Three practical examples

1. A compression experiment models a stream of text characters using their recent context. Repeated spelling patterns can receive higher probability than they would under a model that ignores preceding characters.

2. A researcher studies structured log data whose local syntax repeats. PPM provides a context-based baseline, while measurements reveal whether variable identifiers and unpredictable fields limit compression.

3. A language-processing study uses a PPM model to score alternative symbol sequences. The probability model can inform such analysis even when the immediate goal is not storing the final compressed bitstream.

Think of it this way

Think of guessing the next word fragment from a phrase you have seen before. If the full phrase is unfamiliar, you fall back to its last few characters, then to more general frequencies.

PPM must assign usable probabilities and synchronize encoder and decoder. A plausible guess is insufficient: every actual symbol, including an unexpected one, needs a defined lossless representation.

Worked example

Consider a toy PPM-style model with maximum context length two. After the context “ab,” suppose its agreed distribution assigns probability 0.6 to c, 0.2 to d, and 0.2 to escape. These are illustrative probabilities, not a claim about one standard escape estimator.

If the next symbol is c, the ideal information cost is −log2(0.6), approximately 0.737 bits. An arithmetic coder realizes such fractional average costs across a stream; it does not literally store a standalone fraction of a bit for this one symbol.

If the next symbol is e, the encoder signals escape with probability 0.2. It then consults the shorter context “b.” Suppose the applicable shorter-context distribution assigns e probability 0.25. The combined path probability is 0.2×0.25=0.05, with ideal cost −log2(0.05), approximately 4.322 bits.

After e is decoded, both sides update the relevant contexts. A future “ab” followed by e can then be treated differently. Actual size also depends on coder precision, initialization, termination, and the exact exclusion and update conventions. The example isolates backoff accounting rather than specifying a complete compressor.

Illustrative case study

Fictional case: LogWeave evaluates a context compressor for exported machine logs. Its test files compress differently because some contain repeated message templates while others are dominated by changing identifiers.

The team measures compression ratio, encoding time, decoding time, and peak memory on both kinds. It also finds that changing an escape rule in the encoder without updating the decoder breaks round-trip recovery.

The specification identifies the variant and model settings. This hypothetical case illustrates workload evaluation and compatibility, not superiority over other compressors or a measured saving.

Common misconceptions and mistakes

A longer maximum context does not automatically improve every practical outcome. Sparse context statistics can require frequent escapes, while storing more contexts consumes memory and computation.

Lossless prediction does not mean predictions must always be correct. An unlikely symbol can still be encoded exactly, usually at a greater information cost. Confusing prediction accuracy with exact recoverability obscures how statistical compression works.

Also, model probability is not a statement that a text is true or meaningful. It measures compatibility with the model's learned symbol patterns. Highly predictable false statements and repetitive noise-like labels can still be treated according to their statistical structure.

Business use

PPM demonstrates how local context can support exact-data compression. Its practical appeal depends on the workload and model-maintenance cost.

Compare representative files, including short records and already compressed inputs. Report complete file size rather than ideal probability costs alone. Define memory limits, stream framing, and exact decoder rules, and verify recovery against the original bytes. If random access matters, consider how adaptive history affects the ability to decode from the middle of a stream.

Check your understanding

Why is the toy escape path's probability 0.05 rather than 0.25?

Answer: Encoding e requires both the escape event and the shorter-context symbol event, so their conditional probabilities multiply: 0.2×0.25.

Related terms

Learn next

Trace a short symbol stream through two context lengths, recording counts and escape events after every symbol. Check that a decoder reconstructing the same history always reaches the same probability distribution before the next event.

Probability distribution

Sources

Primary reference consulted: W. J. Teahan and colleagues, A Compression-based Algorithm for Chinese Word Segmentation, Section 3, Language Modeling using PPM, https://aclanthology.org/J00-3004.pdf . This research paper describes its PPM model and backoff rules. The numerical probabilities and fictional log example are original teaching illustrations.

Previous: Prediction bias Next: Prediction interval