Loading article…
部分一致予測（PPM）は、コンテキストモデリングと予測に基づく適応型統計的データ圧縮技術です。PPMモデルは、圧縮されていないシンボルストリーム内の過去のシンボルセットを使用して、ストリーム内の次のシンボルを予測します。PPMアルゴリズムは、クラスタ分析においてデータを予測されたグループにクラスタリングするためにも使用できます。
予測は通常、シンボルの順位付けに還元されます。各シンボル（文字、ビット、またはその他のデータ量）は圧縮前に順位付けされ、順位付けシステムによって対応する符号語（したがって圧縮率）が決定されます。多くの圧縮アルゴリズムでは、順位付けは確率質量関数の推定に相当します。前の文字（またはコンテキスト）が与えられた場合、各シンボルには確率が割り当てられます。たとえば、算術符号化では、シンボルは前のシンボルの後に現れる確率によって順位付けされ、シーケンス全体がこれらの確率に基づいて計算された単一の分数に圧縮されます。
前のシンボルの数nによって、PPM モデルの次数が決定され、PPM( n ) と表記されます。コンテキストに長さの制限がない無制限のバリアントも存在し、PPM*と表記されます。すべてのn 個のコンテキストシンボルに基づいて予測ができない場合は、 n − 1 個のシンボルを使用して予測が試みられます 。このプロセスは、一致するシンボルが見つかるか、コンテキストにシンボルがなくなるまで繰り返されます。その時点で、固定の予測が行われます。
PPMモデルの最適化作業の大部分は、入力ストリームにまだ出現していない入力の処理です。これらを処理する明白な方法は、エスケープシーケンスをトリガーする「未出現」シンボルを作成することです。しかし、未出現のシンボルにはどのような確率を割り当てるべきでしょうか？これはゼロ頻度問題と呼ばれます。1つのバリアントでは、ラプラス推定器を使用して、「未出現」シンボルに固定の擬似カウント1を割り当てます。PPMdと呼ばれるバリアントでは、「未出現」シンボルが使用されるたびに、その擬似カウントをインクリメントします。（言い換えれば、PPMdは、ユニークシンボルの数と観測されたシンボルの総数の比率として、新しいシンボルの確率を推定します。）
PPM圧縮の実装は、その他の詳細において大きく異なります。実際のシンボル選択は通常、算術符号化を使用して記録されますが、ハフマン符号化や何らかの辞書符号化技術を使用することも可能です。ほとんどのPPMアルゴリズムで使用される基盤となるモデルは、複数のシンボルを予測するように拡張することもできます。また、マルコフモデルを置き換える、または補完するために、非マルコフモデルを使用することも可能です。シンボルサイズは通常静的で、一般的には1バイトであるため、あらゆるファイル形式を汎用的に処理することが容易です。
このアルゴリズム群に関する研究論文は、1980年代半ばまで遡ることができます。PPMアルゴリズムは大量のRAMを必要とするため、ソフトウェアによる実装は1990年代初頭まで普及しませんでした。最近のPPM実装は、自然言語テキスト向けのロスレス圧縮プログラムの中でも最高レベルの性能を誇ります。
PPMd は、Dmitry Shkarin による PPMII (情報継承付き PPM) のパブリック ドメイン実装で、互換性のない改訂が何度か行われています。[ 1 ]デフォルトではRARファイル形式で使用されます。7zおよびzipファイル形式でも利用可能です。
PPMアルゴリズムの改良の試みは、PAQシリーズのデータ圧縮アルゴリズムの開発につながった。
PPMアルゴリズムは、圧縮に使用されるのではなく、代替入力方法プログラムDasherにおけるユーザー入力の効率を高めるために使用されます。