Skip to content

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.

Version
v1 · 2026-10-03 · History
Domain-specific #
13513
Domain group
Applied Sciences & Engineering
Origin domain
Computer Science & Software Engineering
Subdomains
Data Compression, Sequence Prediction → Computer Science & Software Engineering

Core Idea

Prediction by partial matching (PPM) estimates which discrete symbol comes next by consulting what followed similar recent symbol histories. It starts with the longest usable suffix context. When the actual continuation has not been observed after that context, classic probabilistic PPM assigns an escape route to a shorter suffix, repeating until the symbol can be represented. Observations then revise the context statistics. This is a variable-context, adaptive probability model, not merely the act of finding a repeated substring.[1]

The probability estimates may drive an arithmetic coder in lossless compression, as in the original compression lineage, but the coder is a consumer, not a necessary component of the predictor. Dasher used a PPM5D+ language model to size interactive character-selection regions; entered characters updated the model even though that use did not require PPM to produce a compressed file.[2][1][3] PPM denotes a family of implementations: maximum order, escape estimator, exclusion policy and terminal treatment of new symbols are not one universal recipe.[1]

Structural Signature

Sig role-phrases: observed symbol history — context-conditioned continuation statistics — longest informative suffix — unseen-continuation allocation and shorter-context fallback — adaptive update — next-symbol probabilities for a consumer.

  • Observed symbol history supplies an ordered discrete stream. Its recent suffixes form candidate contexts; an unordered bag of symbol frequencies cannot provide the same conditioning.[1]
  • Continuation statistics record or estimate which symbols followed each observed context. Implementations can differ in storage and count updates, but without context-specific continuation evidence the model has no adaptive prediction.[1]
  • Longest informative suffix starts with the most specific usable recent match, subject to a variant's maximum order and available observations. A single fixed-order table loses the hierarchy of partial matches.[1]
  • Unseen-continuation allocation and fallback reserve probability for a symbol not previously seen after the selected context, then pass its representation to a shorter suffix. The context itself need not be unseen. Escape probability and exclusion rules vary; a physical escape code is a compression implementation detail.[1]
  • Adaptive update and output incorporate newly observed symbols and provide next-symbol probabilities. In one setting these probabilities feed a lossless coder; in another they organize an interface. Requiring either consumer would misidentify the predictor.[1][3]

What It Is Not

PPM is not arithmetic coding. Arithmetic coding translates a supplied probability sequence into a code interval; PPM supplies context-dependent probabilities. It is not a dictionary compressor merely because it matches previous strings: the crucial object is the continuation distribution, including a route for unseen continuations. Nor is it a fixed-order Markov predictor with a single context length; the progressively shorter suffixes matter when longer-context evidence does not account for a symbol.[1]

The abbreviation does not force every variant to use Moffat's particular escape method, exclusion rule, memory bound or final raw-symbol convention. His paper explicitly compares methods A, B and C and implementation choices.[1] Kalamatianos and Kaeli named an indirect-branch target predictor after PPM, but their approximate tables and highest-valid-history target selection are an adaptation; the paper does not establish that this predictor calculates the same full novelty-escape distribution as classic compression PPM.[4]

Scope of Application

The literal core applies to ordered, discrete symbols with useful repeated suffix contexts. Cleary and Witten's original compression tests included a gray-scale image serialized in raster order: pixel-level values became symbols in the sequence rather than English letters. This is an input-stream use, not a claim that PPM itself performs a spatial image transform. Only the indexed original-paper sample description was accessible here; no image-specific performance number is inferred from it.[2] Text compression and Dasher's interactive text entry use character streams but send the modeled probabilities to different consumers.[1][3]

The model is not a universal solution for every sequence. Sparse long contexts create unreliable evidence; keeping richer context tables consumes memory and processing time; and a consumer may have response-latency or probability-floor needs beyond a compressor's needs. Dasher's original paper describes a low-probability floor followed by renormalization to keep characters selectable, an interface-specific adaptation rather than a defining rule of PPM.[1][3]

Clarity

The decisive distinction is unseen continuation versus unseen context. A familiar context may have been followed by several symbols yet never by the current one. Classic PPM cannot simply assign that symbol zero probability; it makes an escape allocation and consults a shorter suffix. This clarifies why an exact previous-string match is not enough and why the estimator is more than a set of context counts.[1]

Separating the predictor from its consumer also resolves a naming confusion. In compression the predictor and a coder form a pipeline. In Dasher the same family of next-character estimates organizes interactive display geometry. The latter does not retroactively make every display operation part of PPM, nor does it make coding irrelevant to the original compression research.[2][1][3]

Manages Complexity

PPM avoids committing to one context length for an entire stream. It uses specific long-history evidence where available and degrades through shorter suffixes when a continuation is not represented. That organizes many possible local histories into a hierarchy rather than requiring an independent, fully populated table for every long history.[1]

The hierarchy transfers, rather than abolishes, complexity. It needs context storage, count updates, an escape allocation and often many successive lookups. Moffat discusses choices that alter memory and coding behavior; Dasher requires repeated fast estimates during interaction. Neither result licenses a universal compression rate, universal speed advantage or exact context bound.[1][3]

Abstract Reasoning

For a given next-symbol query, identify a recent suffix and examine its continuation evidence at the longest usable order. If the desired symbol is represented, assign its conditional mass under the variant's estimate. If it is not, allocate escape mass, shorten the context and continue under the variant's lower-order rules. After observing the symbol, update the relevant statistics. This describes the conditional reasoning shared by classic PPM variants without choosing a single numerical escape formula.[1]

A diagnostic failure is assigning zero mass to a merely unobserved continuation, which would make lossless encoding impossible for that event and interactive selection brittle. Another is treating every shorter-context consultation as evidence that the longer context never occurred; only the continuation may be novel there. A third is calling an approximate branch-target cache a proof that all PPM implementations return calibrated full symbol distributions.[1][4]

Knowledge Transfer

The same predictor organization can operate over gray-level samples from a serialized image and over characters in an interactive text-entry system: both have prior symbols, context-conditioned continuations, a more-specific-first search, novel continuations and updates. What changes is the alphabet and the destination of the probabilities. Cleary and Witten's image was a compression input; Dasher's estimates set visible character regions.[2][1][3]

An even broader intuition—consult specific evidence, then fall back to broader evidence—is portable, but that alone is not literally PPM. Without a discrete symbol stream, context-conditioned continuation probabilities and a defensible new-symbol route, the analogy has crossed out of the named method. Any abstraction of that portable backoff shape belongs to a separate future-prime inquiry.[1]

Examples

Canonical — rasterized gray-scale image as a source stream

Cleary and Witten's original test suite describes a gray-scale image supplied in raster order, with its sample levels treated as symbols. A classic PPM encoder can model the sequence of preceding sample values and transmit the current value using the resulting probability estimate. This example rests on the original paper's indexed sample description and Moffat's full original exposition of the PPM mechanism; the directly opened Cleary–Witten PDF was unavailable. No particular prediction accuracy or image-specific model table is claimed.[2][1]

Mapped back: Observed symbol history is the raster-ordered gray-level sequence; continuation statistics concern gray levels after previously seen sample-value suffixes; longest informative suffix starts with a usable recent sample sequence; unseen-continuation allocation shifts to shorter suffixes when a gray level has not followed the current context; adaptive update incorporates each sample; and next-symbol probabilities feed the source-coding consumer rather than an interactive display.[2][1]

Applied — Dasher interactive character entry

Ward, Blackwell and MacKay's original Dasher paper identifies a PPM5D+ language model. It uses matching character histories to predict next-character probabilities, makes interactive regions proportional to those probabilities and updates the model from entered text. The paper does not publish every internal PPM5D+ escape or exclusion formula, so this is an evidenced PPM-family use, not a claim that Dasher duplicates Moffat's coding implementation. Dasher also adds a small probability floor and renormalizes to preserve a route to low-probability characters.[3]

Mapped back: Observed symbol history is the user's already-entered text; continuation statistics estimate characters after matching strings; longest informative suffix is governed by the PPM5D+ variant rather than a universal order; unseen-continuation allocation is the model's probability route for characters not well represented by the chosen context, with the interface-specific floor kept distinct; adaptive update follows each entered character; and next-symbol probabilities resize selection regions, not a compressed output file.[3][1]

Structural Tensions

Specific-context discrimination versus sparse evidence. Longer suffixes can distinguish local patterns, but each has fewer continuations and may not yet contain the next symbol. Shortening the context supplies more evidence while losing distinctions. Escape/backoff manages this cost but cannot make both extremes simultaneously optimal. Diagnostic: when the current long suffix is thinly supported, how much probability should move to shorter contexts?[1]

Novel-symbol allowance versus concentration on known continuations. More escape mass gives a newly observed continuation a route, but removes mass from symbols already observed after that context. Moffat's escape estimators embody different choices rather than one universally dominant estimate. Diagnostic: is the local context producing enough new continuations to justify its current novelty allocation?[1]

Predictive detail versus memory and latency. Richer context tables can discriminate more histories but demand storage and update/lookup work. Moffat's implementation discusses model-space choices; Dasher must compute frequent probability estimates quickly enough for an interface. Diagnostic: what context detail is worth retaining for this consumer's memory and response-time limits?[1][3]

Structural–Framed Character

PPM lies toward the structural side of the structural–framed spectrum, though its discrete-symbol, learned-statistics setting remains a domain-specific frame. Evaluative weight: the method defines a probability-estimation organization; whether its compression ratio or interaction speed is good is an empirical comparison, not part of its identity. Human-practice dependence: human choices of alphabet, context cap, escape estimator and consumer affect an implementation, but the conditional-statistics and fallback relationship remains testable across those choices. Institutional origin: a named research lineage does not make a paper's laboratory or interface the authority that defines all possible instances. Vocabulary travel: “prediction” and “matching” are broad words, while PPM denotes this narrower symbol-context family. Import versus recognition: one can recognize the method in a source coder or Dasher's language model from its roles; importing the method into an arbitrary system requires establishing ordered symbols and continuation statistics rather than merely labeling a lookup “PPM.”[2][1][3]

Its character: a strongly structural but domain-specific adaptive symbol-prediction method; it travels between symbol-stream consumers without becoming a universal pattern of all prediction or all backoff.

Structural Core vs. Domain Accent

The core is an ordered discrete-symbol history, continuation estimates at multiple suffix orders, more-specific-first use, an allocation for unseen continuations and adaptive updates. The original compression experiments and Dasher differ in alphabet, output consumer, time constraints and interface adaptations; those are accents, not reasons to collapse two implementations into one artifact.[1][3]

A more portable principle—favor specific evidence, then fall back when support fails—might warrant a future prime, but PPM's named identity still requires symbol-conditioned probability estimates. Live Compression covers reduction of redundancy, not the Dasher predictor's necessary genus; live Predictive Coding describes a different prediction/error-coding arrangement. Thus neither supplies a verified strict parent, and the named method does not clear the prime bar simply because its evidence hierarchy is suggestive elsewhere.[1][3]

No strict typed parent is proposed pending independent DAG review. Compression is an important application neighbor; the entropy coder consumes PPM probabilities in a compressor but is not necessary to PPM's Dasher use. Predictive Coding is a distinct neighboring architecture, not an asserted genus. Factored Language Model conditions next words on factors that need not be a variable suffix hierarchy with novelty escape. Model Compression reduces a model's resource footprint, not the symbol stream that PPM models. The similarity to Set Redundancy Compression or signal-residual coding is topical rather than an established is-a relation.[1][3]

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

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With

  • Partial-string retrieval: a repeated substring is a context cue; PPM needs continuation statistics and an unseen-symbol route.[1]
  • Arithmetic coding: an optional downstream coding mechanism that can use PPM probabilities.[1]
  • One fixed-order Markov table: classic PPM uses a suffix-context hierarchy and falls back when a continuation is unrepresented.[1]
  • A universal method A/B/C formula: escape estimators, exclusion and terminal treatment vary among implementations.[1]
  • All self-described PPM descendants: the original indirect-branch predictor borrows context-history selection with approximate target tables; it does not document the full classic novelty-escape distribution.[4]

References

[1] Alistair Moffat, “Implementing the PPM Data Compression Scheme”, IEEE Transactions on Communications 38(11), 1917–1921 (1990), original full paper, §§II–III, pp.1917–1919 inspected 2026-10-01. It directly supports longest-context selection, unseen-continuation escape, method A/B/C and implementation tradeoffs. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u ↩v ↩w ↩x ↩y ↩z ↩27 ↩28 ↩29 ↩30 ↩31 ↩32 ↩33 ↩34

[2] 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-description excerpt inspected 2026-10-01. Direct PDF opening failed; the indexed sample passage supports the gray-scale raster input only, not an image performance or formula claim. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g

[3] 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, particularly §4.5, inspected 2026-10-01; publisher DOI. The article identifies PPM5D+ but does not enumerate every internal escape-estimator detail. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n

[4] John Kalamatianos and David R. Kaeli, “Predicting Indirect Branches via Data Compression”, original MICRO 1998 author-hosted paper, §§3–4, inspected 2026-10-01. Used only for the named-adaptation boundary, not to assert equivalence with classic PPM probability coding. registry ↩a ↩b ↩c