Prediction by Partial Matching

PPM (Prediction by Partial Matching) とは？

PPMは、1984年にJ.G. ClearyとI.H. Wittenによって開発された、優れたデータ圧縮アルゴリズムです。その高い圧縮率から、7-Zipなどの圧縮ソフトウェアで改良版が採用されています。しかし、その反面、圧縮速度が非常に遅く、多くのメモリを消費するという欠点も持ち合わせています。

PPMアルゴリズムは、データ列における文字の出現確率を統計的に予測することで圧縮を行います。例えば、`aabacaabba`というデータ列があった場合、次にどの文字が現れるかを予測します。この例では、`a`の後に`a`が現れる確率が高いと予測できます。このように、出現確率に偏りがある場合、ハフマン符号化や算術符号化などによって圧縮が可能になります。

ゼロ頻度問題とスムージング

しかし、単純に予測を行うだけでは問題が発生します。例えば、`a`を50%、`b`を40%、`c`を10%と予測した場合、それ以外の文字(`d`など)が出現した際に対応できなくなります。これをゼロ頻度問題と言います。

PPMはこの問題を解決するために、「エスケープ(escape)」という特別な記号を導入します。例えば、`a`を45%、`b`を35%、`c`を5%、エスケープを15%と割り当てることで、新しい文字(`d`)が出現した場合でも、まずエスケープ記号を出力し、その後`d`を出力することで対応できます。そして、`d`を統計情報に追加することで、次の予測に反映します。

このように、まだ出現していない文字に確率を割り当てることをスムージングと言います。エスケープはスムージング手法の一つです。

文脈の長さと次数

予測の精度を高めるために、PPMでは文脈の長さ(次数またはorder)という概念を用います。例えば、`a`の後に続く文字を予測する際に、直前の1文字だけを考慮するのか、直前の2文字を考慮するのかによって予測結果が変わります。次数が高いほど正確な予測が可能になりますが、高い次数の文脈では統計情報が不足しがちです。

そこで、PPMでは、まず最高次数から予測を行い、エスケープが発生したら1つ低い次数で予測し直すという方法を用いることで、適切な次数での予測を実現します。

エスケープ確率の推定

エスケープ記号の確率を適切に推定することは、圧縮効率に大きく影響します。符号化された文字が少ないうちはエスケープ確率が高く、符号化が進むにつれてエスケープ確率は低くなる傾向にあります。

エスケープ確率の推定方法(method)として、いくつか提案されていますが、Method CとMethod Dが特に優れた性能を示すとされています。それぞれの計算式は以下の通りです。

Method A: 1/(n+1)
Method B: u/n
Method C: u/(n+u)
Method D: u/(2n)

ここで、`n`は今までに出現した記号の総数、`u`はエスケープの総数です。

PPMの亜種

PPMには、PPMC、PPMd、PPMN、PPMY、PPMZなど、いくつかの亜種が存在し、それぞれ圧縮率や速度が異なります。

PPMd: RARや7-Zipなどで採用されている、PPMの中でも高速な方式です。場合によってはRange Coderに匹敵する速度を実現します。圧縮率も十分に高く、バランスに優れたアルゴリズムです。
PPMZ: PPM系列の中でもっとも高い圧縮率を実現する方式ですが、計算量が膨大で、速度が非常に遅いため、実用的なアプリケーションではあまり使われていません。PPMZ2という改良版も存在しますが、速度の改善は限定的です。

まとめ

PPMは、高い圧縮率を達成する強力なアルゴリズムですが、計算コストが高いというトレードオフが存在します。そのため、使用するアプリケーションやデータの種類に応じて、最適なPPMの亜種を選択する必要があります。 また、エスケープ確率の推定方法なども圧縮効率に影響するため、適切なパラメータ設定が重要になります。

もう一度検索