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
Limitations
- PPM names a modelling family, not an interchangeable archive format. The example omits bitstream coding, framing and finite-precision arithmetic. [3]
Citations
- Moffat: Implementing the PPM Data Compression Scheme, IEEE Transactions on Communications 38(11), 1917-1921 (1990), sections II-III
- Cleary and Teahan: Unbounded Length Contexts for PPM, The Computer Journal 40(2/3), 67-75 (1997), sections 2-3 and 5
- Hesela: PPM coding and update exclusion, exact executable example and tests
- 7-Zip: 7z Format, integrated compression methods
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.