Prediction by Partial Matching

Prediction by Partial Matching(PPM)は1984年に J.G.Clearyと I.H.Wittenによって考案された データ圧縮アルゴリズムの1つ。 この改良版が 7-zip等に用いられている。非常に高い圧縮率の反面、圧縮速度はかなり遅くメモリも多く消費するアルゴリズムである。

この亜種として PPMCPPMdPPMZ等がある。

符号化の原理

aabacaabbaとデータを符号化したとして、次にどの記号が出現するかを 統計的に 予測する。 この場合、統計的にaの次にはaが出現する可能性が高い。逆にcが出現する可能性は低いであろう。このように出現 確率に偏りがあると ハフマン符号算術符号で圧縮することが出来る。 しかし、上記の場合に次に出現する符号をaを50%、bを40%、cを10%と予測したとすると、他の記号は絶対に現れないということになり、新たな記号(dとする)が出現したときに対応できなくなってしまう。これをゼロ頻度問題という。

そこで、PPMでは「今までに出現していない文字」として「エスケープ(escape)」という記号を加える。 上記の例であれば、aを45%、bを35%、cを5%などとして、エスケープには残りの15%を割り当てておく。これならば先ほどのように新しい記号dが出現したとしても、まずエスケープ記号を出力し、その後dを出力すればよい。更にこのとき、dを既知の記号として統計情報に加える。 このように、まだ現れていない記号に他の記号の確率を配分し、ゼロ頻度問題を回避することをスムージングという。 エスケープはスムージングの1つである。

また、エスケープには次のような役割もある。 先ほどの文字列の統計情報を利用するとき、aの次にはaが出現しやすいが、baの次にはcが出現しやすい。このように、予測に用いる 文脈の長さ(次数またはorderという)によって予想の結果は異なってしまう。次数は高いほうが正確な予想が出来ると思われるが、高い次数の文脈は統計情報が不足している場合が多い。 この解決策として、まず一番高い次数から予想をし、エスケープであれば1つ低い次数で予想しなおすという案があり、これによって適切な次数による予想が可能となる。