prediction-by-partial-matching · shipping · also PPM

Prediction by partial matching

Prediction by partial matching models symbols from preceding contexts, escaping to shorter contexts when the current model cannot encode a symbol.

Coding: PPM predicts probabilities; an arithmetic coder represents the events. An escape is a model event, not necessarily a reserved input byte. Encoder and decoder must agree on model updates. [2]

Two exclusions: Coding exclusion removes symbols already ruled out by a higher-context escape. Update exclusion instead omits counter increments below the context that successfully predicted the symbol. They affect different stages. [1]

Example: For context a with counts a:3,b:1, and an empty-context model a:5,b:2,c:1, method-C escape counts are 2 and 3. Coding c has path probability (2/6)*(1/4)=1/12 with coding exclusion, versus (2/6)*(1/11)=1/33 without it. These are model probabilities, not measured file sizes. [3]

Longer contexts: More history can mean more escapes, not better compression. PPM* removes a fixed order limit but still needs a context-selection policy; the 1997 paper uses the shortest deterministic context when one exists. [2]

Implementation: Moffat uses move-to-front lists to search context statistics, a different role from emitting MTF ranks. The 7z format documents a PPMdH-derived coding method. [1] [4]

Relations

related
Lossless compression, Burrows-Wheeler transform, Move-to-front transform

Limitations

  • PPM names a modelling family, not an interchangeable archive format. The example omits bitstream coding, framing and finite-precision arithmetic. [3]

Citations

  1. Moffat: Implementing the PPM Data Compression Scheme, IEEE Transactions on Communications 38(11), 1917-1921 (1990), sections II-III (accessed 2026-11-18)
  2. Cleary and Teahan: Unbounded Length Contexts for PPM, The Computer Journal 40(2/3), 67-75 (1997), sections 2-3 and 5 (accessed 2026-11-18)
  3. Hesela: PPM coding and update exclusion, exact executable example and tests (accessed 2026-11-18)
  4. 7-Zip: 7z Format, integrated compression methods (accessed 2026-11-18)
Sources & caveats
  • Source synthesis and an original hypothetical count example; not a compressor benchmark or replication of a paper's measurements.
  • The 1990 and 1997 papers were read. Full-text retrieval of the 1984 paper failed; no claim depends on its abstract alone.

JSON: /data/terms/prediction-by-partial-matching.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Prediction by partial matching. Hesela. 2026-11-18. https://hesela.dev/terms/prediction-by-partial-matching/