Prediction by Partial Matching
Prediction by Partial Matching(PPM)は1984年にJ.G.ClearyとI.H.Wittenによって考案されたデータ圧縮アルゴリズムの1つ。 この改良版が7-zip等に用いられている。非常に高い圧縮率の反面、圧縮速度はかなり遅くメモリも多く消費するアルゴリズムである。
この亜種としてPPMC、PPMd、PPMZ等がある。
aabacaabbaとデータを符号化したとして、次にどの記号が出現するかを統計的に予測する。 この場合、統計的にaの次にはaが出現する可能性が高い。逆にcが出現する可能性は低いであろう。このように出現確率に偏りがあるとハフマン符号や算術符号で圧縮することが出来る。 しかし、上記の場合に次に出現する符号をaを50%、bを40%、cを10%と予測したとすると、他の記号は絶対に現れないということになり、新たな記号(dとする)が出現したときに対応できなくなってしまう。これをゼロ頻度問題という。
そこで、PPMでは「今までに出現していない文字」として「エスケープ(escape)」という記号を加える。 上記の例であれば、aを45%、bを35%、cを5%などとして、エスケープには残りの15%を割り当てておく。