Prediction by Partial Matching (PPM) je adaptivní technika komprese statistických dat založená na kontextovém modelování a predikci. Modely PPM používají sadu předchozích symbolů v nekomprimovaném toku symbolů k predikci dalšího symbolu v toku.
Predikce jsou obvykle redukovány na pořadí symbolů. Počet předchozích symbolů n určuje pořadí modelu PPM, který je označen jako PPM(n). Neomezené varianty, kde kontext nemá omezení délky, také existují a jsou označeny jako PPM*. Pokud nelze provést predikci na základě všech n kontextových symbolů, je pokus o predikci se symboly n-1. Tento proces se opakuje, dokud není nalezena shoda nebo v kontextu nezůstanou žádné další symboly. V tomto okamžiku je provedena pevná predikce. Tento proces doplňuje proces, po kterém následuje Dynamická Markovova komprese (DMC), která vychází z modelu nulového pořadí.
Velkou část práce při optimalizaci modelu PPM je práce se vstupy, které se ještě neobjevily ve vstupním proudu. Zřejmý způsob, jak s nimi naložit, je vytvořit symbol „nikdy neviděný“, který spustí únikovou sekvenci. Ale jaká pravděpodobnost by měla být přiřazena symbolu, který nikdy nebyl viděn? Tomu se říká problém nulové frekvence. Jedna varianta přiřazuje symbolu „nikdy neviděný“ pevný pseudopočet jedna. Varianta s názvem PPMd zvyšuje pseudopočet symbolu „nikdy neviděný“ pokaždé, když je použit symbol „nikdy neviděný“. (Jinými slovy, PPM-D odhaduje pravděpodobnost nového symbolu jako poměr počtu jedinečných symbolů k celkovému počtu pozorovaných symbolů). PPMd je jedna z „nových“ kompresních metod používaných ve formátu ZIP souborů a ve formátu 7z souborů.
Implementace komprese PPM se velmi liší v dalších detailech. Vlastní výběr symbolů je obvykle zaznamenán pomocí aritmetického kódování, i když je také možné použít Huffmanovo kódování nebo dokonce nějaký typ slovníkové kódovací techniky. Základní model používaný ve většině algoritmů PPM může být také rozšířen pro predikci více symbolů. Je také možné použít jiné než Markovovo modelování buď nahradit nebo doplnit Markovovo modelování. Velikost symbolu je obvykle statická, typicky jeden byte, což usnadňuje obecné zacházení s jakýmkoliv formátem souboru.
Publikovaný výzkum této rodiny algoritmů lze nalézt již v polovině 80. let 20. století. Softwarové implementace nebyly až do začátku 90. let populární, protože algoritmy PPM vyžadují značné množství RAM. Nedávné implementace PPM patří mezi nejvýkonnější bezztrátové kompresní programy pro text v přirozeném jazyce.
Snaha o vylepšení PPM algoritmů vedla k sérii PAQ algoritmů pro kompresi dat.
Algoritmus PPM, spíše než aby byl použit pro kompresi, se používá ke zvýšení efektivity uživatelského vstupu v alternativním vstupním metodickém programu Dasher.
, IEEE Transactions on Communications, sv. 38 (11), s. 1917-1921, listopad 1990.