Introduction

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 tt, hh, ee, the next character is probably a space. After qq, it is almost certainly uu. 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.

Try It

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\log_{2} probability).

<div class="ppm-wrap">
  <div class="input-row">
    <label for="ppm-input" class="inp-label">Type text here:</label>
    <input id="ppm-input" type="text" autocomplete="off" spellcheck="false"
           placeholder='e.g. "abracadabra" or "the cat sat on the mat"' />
  </div>
  <div class="presets">
    <span class="preset-label">Presets:</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">hello world ×2</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">Char</span>
    <span class="col-ctx">Context used</span>
    <span class="col-depth">Order</span>
    <span class="col-prob">Prob</span>
    <span class="col-bits">Bits</span>
    <span class="col-bar">Compression saving</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// PPM (Prediction by Partial Matching) — simplified PPM-A variant
// We maintain a context trie of order up to MAX_ORDER.
// For each new symbol, we find the longest suffix context that has seen at least one symbol, read the count of the new symbol in that context, compute a probability using Method A escape, and fall back to shorter orders until found.
// Bits = -log2(probability).  Total bits approximates PPM compressed size.

const MAX_ORDER = 4;
const ESC_DENOM_EXTRA = 1; // Method A: escape count = 1, total = count_sum + 1

// Trie node: Map<char, {count, children: Map<char, node>}>
// We represent the model as a map from context-string to frequency tables.
// context '' = order-0, 'a' = order-1 with context 'a', etc.
const model = new Map(); // context string -> Map<char, count>

function getCtx(s) {
  if (!model.has(s)) model.set(s, new Map());
  return model.get(s);
}

function totalCount(freq) {
  let t = 0; freq.forEach(v => t += v); return t;
}

// Encode symbol c with current context suffix of length up to MAX_ORDER.
// Returns { prob, bitsStr, depth, ctxUsed }
function encode(c, history) {
  // Try contexts from longest to shortest, then order-(-1) = uniform
  let probProduct = 1.0; // accumulated escape probabilities
  for (let order = Math.min(MAX_ORDER, history.length); order >= 0; order--) {
    const ctx = history.slice(history.length - order);
    const freq = getCtx(ctx);
    const total = totalCount(freq);
    const count = freq.get(c) || 0;

    if (order === 0 && count === 0) {
      // Order-(-1) fallback: uniform over 95 printable ASCII
      const p = probProduct / 95;
      return { prob: p, bits: -Math.log2(p), depth: -1, ctxUsed: '(uniform)' };
    }

    if (count > 0) {
      // Method A: p(c|ctx) = count / (total + 1)
      const escDenom = total + ESC_DENOM_EXTRA;
      const p = probProduct * (count / escDenom);
      return { prob: p, bits: -Math.log2(p), depth: order, ctxUsed: JSON.stringify(ctx) };
    }

    // escape: p_esc = 1 / (total + 1)
    if (total > 0) {
      const escDenom = total + ESC_DENOM_EXTRA;
      probProduct *= ESC_DENOM_EXTRA / escDenom;
    }
  }
  const p = probProduct / 95;
  return { prob: p, bits: -Math.log2(p), depth: -1, ctxUsed: '(uniform)' };
}

// Update model: add c to all suffix contexts up to MAX_ORDER
function update(c, history) {
  for (let order = 0; order <= Math.min(MAX_ORDER, history.length); order++) {
    const ctx = history.slice(history.length - order);
    const freq = getCtx(ctx);
    freq.set(c, (freq.get(c) || 0) + 1);
  }
}

// Badge HTML for depth
function depthBadge(d) {
  if (d < 0) return '<span class="badge badge-d0">∅</span>';
  if (d === 0) return '<span class="badge badge-d0">0</span>';
  if (d === 1) return '<span class="badge badge-d1">1</span>';
  if (d === 2) return '<span class="badge badge-d2">2</span>';
  if (d === 3) return '<span class="badge badge-d3">3</span>';
  return '<span class="badge badge-d4p">' + d + '</span>';
}

let lastText = '';

function process(text) {
  // Reset model for fresh run
  model.clear();
  const log = document.getElementById('log');
  const logHead = document.getElementById('log-head');
  const summary = document.getElementById('summary');
  log.innerHTML = '';

  if (!text) { logHead.style.display = 'none'; summary.style.display = 'none'; return; }

  let totalBits = 0;
  let rows = '';
  let history = '';

  for (let i = 0; i < text.length; i++) {
    const c = text[i];
    const res = encode(c, history);
    update(c, history);
    history += c;
    totalBits += res.bits;

    // Saving bar: max 8 bits baseline (uniform 256), show how much better we did
    const baseline = 8;
    const saving = Math.max(0, Math.min(1, (baseline - res.bits) / baseline));

    const displayChar = c === ' ' ? '·' : c;
    const displayCtx = res.depth <= 0 ? '—' :
      (JSON.parse(res.ctxUsed) || '').replace(/ /g, '·');

    rows += `<div class="log-row">
      <span class="col-char">${displayChar}</span>
      <span class="col-ctx">${displayCtx || '""'}</span>
      <span class="col-depth">${depthBadge(res.depth)}</span>
      <span class="col-prob">${(res.prob * 100).toFixed(1)}%</span>
      <span class="col-bits">${res.bits.toFixed(2)}</span>
      <span class="col-bar"><div class="bar-wrap"><div class="bar-fill" style="width:${(saving*100).toFixed(1)}%"></div></div></span>
    </div>`;
  }

  log.innerHTML = rows;
  logHead.style.display = '';
  summary.style.display = '';
  document.getElementById('total-bits').textContent =
    fmt('Total: %totalBits% bits', { totalBits: totalBits.toFixed(1) });
  document.getElementById('bpc').textContent =
    fmt('Avg: %v% bits/char', { v: (totalBits / text.length).toFixed(2) });

  // Scroll to bottom to show latest
  log.scrollTop = log.scrollHeight;
}

const input = document.getElementById('ppm-input');
input.addEventListener('input', () => {
  lastText = input.value;
  process(lastText);
});

document.querySelectorAll('.preset').forEach(btn => {
  btn.addEventListener('click', () => {
    input.value = btn.dataset.text;
    lastText = input.value;
    process(lastText);
  });
});

// Kick off with a starter
input.value = 'abracadabra';
process(input.value);
Result
Console

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.

The Real Complexity

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∗⋅∗k∗)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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/ppm/Content licensed under CC BY-NC 4.0.