Prediction by Partial Matching¶
Estimate the next symbol from adaptive continuation statistics at the longest informative recent context, backing off to shorter contexts when the continuation is unseen.
Core Idea¶
Prediction by partial matching (PPM) estimates the next discrete symbol from observed continuations of recent symbol histories. It first uses the longest informative suffix context; when a symbol has not previously followed that context, classic PPM reserves escape probability and falls back to a shorter suffix. The model updates as new symbols arrive. Escape is about an unseen continuation, not necessarily an entirely unseen context.[^ref-d7677555697b]
The probabilities can feed a coder for lossless compression, but coding is not part of the predictor's necessary identity. Dasher uses a PPM5D+ character model to organize an interactive text-entry display. Maximum order, escape estimate, exclusion policy and treatment of novel symbols vary across implementations.[ref-d7677555697b][ref-1aef978cf1e2]
Scope of Application¶
Cleary and Witten's original compression experiments included a gray-scale image serialized in raster order, so previous sample values rather than English letters formed the symbol context. The original paper's indexed sample statement supports this input example; its full PDF could not be opened here, and no image-specific performance result is claimed.[^ref-048aae63de08] In Dasher, previously entered characters provide context; PPM5D+ next-character probabilities size interactive regions, and entered characters update the model. Dasher's probability floor is an interface adaptation, not a universal PPM rule.[^ref-1aef978cf1e2]
Both settings share ordered symbols, learned context-conditioned continuations, more-specific-first use, a route for low- or unseen-probability symbols, and adaptive updates. The consumers differ: a compressed representation in one, an interface display in the other. An indirect-branch target predictor also calls itself PPM, but uses approximate history tables and highest-valid-history selection; it is an adaptation, not evidence that all variants perform classic novelty-escape probability coding.[ref-d7677555697b][ref-1aef978cf1e2][^ref-1392d64fdf08]
Clarity¶
PPM is neither a repeated-string dictionary nor arithmetic coding. The string match selects a context and its continuation statistics; the coder, when present, consumes probabilities. A fixed-order Markov table likewise omits the shorter-suffix fallback that distinguishes classic PPM. It would be wrong to assert one universal order −1 fallback or one escape formula from Moffat's particular variants.[^ref-d7677555697b]
Manages Complexity¶
The context hierarchy lets a predictor exploit specific histories without requiring every long history to have seen every possible next symbol. When long contexts are sparse, shorter contexts provide a route for a continuation. The cost moves to maintaining context data, estimating escape probability and conducting multiple lookups. Moffat discusses memory/coding tradeoffs; Dasher needs repeated estimates fast enough for interaction.[ref-d7677555697b][ref-1aef978cf1e2]
Abstract Reasoning¶
Given a recent symbol suffix, consult the longest usable context's observed continuations. If the target symbol is represented, estimate its mass under the chosen variant; otherwise allocate escape mass and consult a shorter suffix. After the symbol is observed, update the statistics. More escape mass protects novel continuations but takes mass from known ones; more context detail may sharpen estimates but costs memory and time. These are diagnostic tensions, not promises of one optimal PPM variant.[^ref-d7677555697b]
Knowledge Transfer¶
The same conditional-probability organization transfers from a raster-ordered image-symbol stream to Dasher's interactive character stream. Only the alphabet, output consumer and implementation constraints change. The broader maxim “use specific evidence, then fall back” is not itself PPM without ordered symbols and continuation probabilities. Accordingly this remains a domain-specific method. Live Compression is related but not a strict parent, because Dasher's predictor need not compress; Predictive Coding is also a distinct neighbor.
[^ref-048aae63de08]: John G. Cleary and Ian H. Witten, “Data Compression Using Adaptive Coding and Partial String Matching”, IEEE Transactions on Communications 32(4), 396–402 (1984), original-paper indexed abstract and §III sample excerpt inspected 2026-10-01; direct PDF opening failed, so no sample-specific results are inferred. [^ref-d7677555697b]: Alistair Moffat, “Implementing the PPM Data Compression Scheme”, IEEE Transactions on Communications 38(11), 1917–1921 (1990), original full paper §§II–III inspected 2026-10-01. [^ref-1aef978cf1e2]: David J. Ward, Alan F. Blackwell and David J. C. MacKay, “Dasher—a data entry interface using continuous gestures and language models”, original UIST 2000 author manuscript §§4.1–4.5 inspected 2026-10-01; publisher DOI. [^ref-1392d64fdf08]: John Kalamatianos and David R. Kaeli, “Predicting Indirect Branches via Data Compression”, original MICRO 1998 author-hosted paper §§3–4 inspected 2026-10-01; cited as an adaptation boundary only.
Neighborhood in Abstraction Space¶
Prediction by Partial Matching sits in a sparse region of the domain-specific corpus (74th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Scaling Laws & Growth Patterns (12 abstractions)
Nearest neighbors
- Kneser–Ney Smoothing — 0.87
- Factored Language Model — 0.83
- Elapsed-Time Memory Decay — 0.83
- Locally catenative sequence — 0.83
- Suffix Tree — 0.82
Computed from structural-signature embeddings · 2026-10-08