PPM: Prediction by Partial Matching

Every compressor has to bet on what the next byte will be. Zip bets on repeated strings. PNG bets on adjacent pixels. PPM — Prediction by Partial Matching — bets on the next character after the longest matching context it has ever seen, and it does so well that it held the record for pure text compression for almost two decades.

The insight is simple but powerful: text is not random. After the letters $t$, $h$, $e$, the next character is probably a space. After $q$, it is almost certainly $u$. The longer the matching context, the stronger the prediction — and a strong prediction needs very few bits to encode the outcome.

PPM was introduced in 1984 by John Cleary and Ian Witten at the University of Waikato. They showed that blending predictions from contexts of length 0, 1, 2, 3 and beyond — and escaping gracefully when a long context has never been seen — lets a compressor outperform everything that had come before on natural language text.

The idea sits at the intersection of information theory, statistics, and algorithmic elegance: build a model of the source while you compress it, and always use the deepest context for which you have any evidence.

Type in the box below and watch PPM build its context model character by character. For each new symbol, the panel shows which context depth matched, the predicted probability of that symbol in that context, and the estimated bits needed to encode it (−$\log_{2}$ probability).

<div class="ppm-wrap">
  <div class="input-row">
    <label for="ppm-input" class="inp-label">{{label_type_text}}</label>
    <input id="ppm-input" type="text" autocomplete="off" spellcheck="false"
           placeholder='{{placeholder_eg}}' />
  </div>
  <div class="presets">
    <span class="preset-label">{{presets_label}}</span>
    <button class="preset" data-text="abracadabra">abracadabra</button>
    <button class="preset" data-text="the cat sat on the mat">the cat sat on the mat</button>
    <button class="preset" data-text="aaabbbaaabbb">aaabbbaaabbb</button>
    <button class="preset" data-text="hello world hello world hello">{{preset_hello_x2}}</button>
  </div>
  <div class="summary" id="summary" style="display:none">
    <span id="total-bits"></span>
    <span id="bpc"></span>
  </div>
  <div class="log-head" id="log-head" style="display:none">
    <span class="col-char">{{col_char}}</span>
    <span class="col-ctx">{{col_ctx}}</span>
    <span class="col-depth">{{col_depth}}</span>
    <span class="col-prob">{{col_prob}}</span>
    <span class="col-bits">{{col_bits}}</span>
    <span class="col-bar">{{col_bar}}</span>
  </div>
  <div id="log"></div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #1a2030; background: #f7f9fc; }
.ppm-wrap { padding: .6rem .2rem; }
.inp-label { font-size: .85rem; font-weight: 600; color: #445; margin-bottom: .3rem; display: block; }
#ppm-input {
  width: 100%; padding: .5rem .7rem; font-size: 1rem; border: 1.5px solid #b0bec5;
  border-radius: 8px; outline: none; background: #fff;
}
#ppm-input:focus { border-color: #4a7fc1; }
.presets { display: flex; flex-wrap: wrap; gap: .35rem; margin: .5rem 0 .6rem; align-items: center; }
.preset-label { font-size: .8rem; color: #667; }
.preset {
  font-size: .78rem; padding: .25rem .55rem; border: 1px solid #aab8cc; background: #fff;
  border-radius: 20px; cursor: pointer; color: #2a4a7a; transition: background .1s;
}
.preset:hover { background: #dce8f5; }
.summary {
  display: flex; gap: 1.2rem; font-size: .9rem; font-weight: 600; color: #2a4a7a;
  background: #dce8f5; border-radius: 8px; padding: .4rem .7rem; margin-bottom: .4rem;
}
.log-head, .log-row {
  display: grid;
  grid-template-columns: 2.2rem 5.5rem 3.2rem 4.2rem 3.5rem 1fr;
  gap: 0 .3rem; align-items: center;
  font-size: .78rem; padding: .18rem .3rem;
}
.log-head {
  font-weight: 700; color: #445; border-bottom: 1px solid #c0ccd8;
  background: #eef2f7; border-radius: 6px 6px 0 0;
}
.log-row { border-bottom: 1px solid #e4eaf1; }
.log-row:last-child { border-bottom: none; }
.log-row:hover { background: #f0f5fa; }
.col-char { font-weight: 700; font-family: ui-monospace, monospace; color: #1a3a6a; }
.col-ctx { font-family: ui-monospace, monospace; color: #3a5a8a; font-size: .75rem; }
.col-depth { text-align: center; }
.col-prob { text-align: right; color: #2a6a3a; }
.col-bits { text-align: right; color: #7a3a1a; font-weight: 600; }
.bar-wrap { height: 7px; background: #dce8f5; border-radius: 4px; overflow: hidden; }
.bar-fill { height: 100%; background: linear-gradient(90deg,#4a7fc1,#2ecc71); border-radius: 4px; }
.badge {
  display: inline-block; font-size: .65rem; padding: .1rem .3rem;
  border-radius: 4px; font-weight: 700; margin-right: .1rem;
}
.badge-d0 { background: #f3e8ff; color: #6a0dad; }
.badge-d1 { background: #e0f0ff; color: #0a4fa0; }
.badge-d2 { background: #e0fff0; color: #0a6a30; }
.badge-d3 { background: #fff5e0; color: #8a5000; }
.badge-d4p { background: #ffe0e0; color: #8a0000; }
#log { max-height: 260px; overflow-y: auto; border: 1px solid #c0ccd8; border-radius: 0 0 8px 8px; background: #fff; }

// Code not found

Notice how the bits per character drop as PPM accumulates more context. The first few characters cost almost 8 bits each (the model knows nothing); after a dozen characters, common continuations cost 2–4 bits. That gap is the compression gain — and it grows the more the text follows patterns PPM has seen before.

PPM is not a puzzle in computational complexity — it is an algorithmic achievement in information theory. Its status: solved, in the sense of approaching the entropy of natural language, achieved by Cleary and Witten (1984) and refined through PPM*, PPMD and PPMA variants.

• Shannon entropy is the theoretical minimum bits-per-symbol for a source with known statistics. For English text this is roughly 1 to 1.5 bits per character. PPM approaches this limit from above.
• Context depth vs. model size: a context of order k stores frequency tables for every k-character string seen. Order 5 (PPMD) gives near-optimal compression but the table can grow large. A context of order 0 is just a global symbol frequency — cheap but weak. PPM blends all depths via the escape mechanism.
• The escape probability: when the current context has never seen symbol s, PPM "escapes" to a shorter context that might have. Choosing the right escape probability (methods A, B, C, D…) has occupied researchers for decades and is where most of the practical gains come from.
• Time and space: building and querying the trie of context counts takes $O(*n* \cdot *k*)$ time and O(alphabet · k · n) space in the worst case. In practice, PPMD and its successors bound context depth and prune rare entries, keeping memory manageable.
• Why it dominated: before neural language models, nothing captured the long-range statistical structure of English text as cleanly. PPM implicitly builds a variable-order Markov model tuned to the specific text it sees.

PPM is not the answer to P vs NP — it is not even in that category. It is a beautiful example of an algorithm that is provably efficient yet pushes against an information-theoretic wall that no algorithm, however clever, can break.

The context-blending idea at the heart of PPM has spread far beyond text files:

• Archival compression: 7-Zip's PPMd mode (Igor Pavlov, 2002) uses a refined PPM with a fixed-order context and is still competitive with modern general-purpose compressors on natural language text.
• Source-code and document compression: text with rich structure (HTML, LaTeX, source code) has longer repetitions that PPM's deep contexts capture cleanly.
• Bioinformatics: DNA and protein sequences are near-alphabet text. Context models detect statistical regularities that reflect biological structure, and compression ratio doubles as a similarity measure for phylogenetics.
• Anomaly detection and intrusion detection: a system call sequence that costs many bits under a PPM model trained on normal behavior is a statistical outlier — and therefore suspicious.
• Language modelling precursor: before transformers, n-gram language models with Kneser-Ney smoothing (used in speech recognition and machine translation) are a close cousin of PPM's escape mechanism, interpolating shorter contexts when longer ones fail.

The core lesson — condition on the longest matching context, fall back gracefully when evidence is thin — echoes through every modern probabilistic model of sequential data. Even large language models implicitly learn which context length matters for each prediction. PPM just made the mechanism explicit and provably near-optimal for the sources it was designed for. For a deeper look at how compression relates to information limits, see the related article.

Prediction by Partial Matching is a lesson in the power of knowing your history. By conditioning every prediction on the longest suffix of past text for which evidence exists, and escaping gracefully to shallower contexts when evidence runs out, PPM approaches the information-theoretic floor for natural language — and held the record for pure text compression ratios for almost twenty years.

It is not magic: it is careful statistics applied character by character, building a model of the source at the same time as it encodes the output. The deeper the matching context, the sharper the prediction, and the fewer bits the arithmetic coder needs.

The next time a compressor squeezes a novel down to a third of its original size, somewhere inside there is almost certainly an idea descended from the elegant blend of context depths that Cleary and Witten put on paper in 1984.