 |
部分マッチングによる予測（PPM ）は、コンテキストモデリングと予測に基づく適応型統計データ圧縮技術です。PPMモデルは、圧縮されていないシンボルストリーム内の以前のシンボルセットを使用して、ストリーム内の次のシンボルを予測します。PPMアルゴリズムは、クラスター分析においてデータを予測されたグループにクラスタリングするためにも使用できます。
理論
予測は通常、シンボルのランキングに還元されます。各シンボル（文字、ビット、またはその他のデータ量）は圧縮前にランキング付けされ、ランキングシステムによって対応するコードワード（ひいては圧縮率）が決定されます。多くの圧縮アルゴリズムにおいて、このランキングは確率質量関数推定と同等です。前の文字（またはコンテキスト）が与えられた場合、各シンボルには確率が割り当てられます。例えば、算術符号化では、シンボルは前のシンボルの後に出現する確率によってランキング付けされ、シーケンス全体がこれらの確率に基づいて計算された単一の分数に圧縮されます。
前のシンボルの数nはPPMモデルの次数を決定します。これはPPM( n )と表記されます。コンテキストの長さに制限がない、無制限のバリエーションも存在し、PPM*と表記されます。n個のコンテキストシンボルすべてを用いて予測できない場合は、 n − 1個のシンボルを用いて予測を試みます 。このプロセスは、一致するシンボルが見つかるか、コンテキストにシンボルがなくなるまで繰り返されます。その時点で、固定された予測が行われます。
PPMモデルの最適化作業の多くは、入力ストリームにまだ出現していない入力を処理することです。これらを処理する明白な方法は、エスケープシーケンスをトリガーする「未出現」シンボルを作成することです。しかし、未出現シンボルにはどのような確率を割り当てるべきでしょうか？これはゼロ頻度問題と呼ばれます。一つの変種はラプラス推定量を使用し、「未出現」シンボルに固定の擬似カウント1を割り当てます。PPMdと呼ばれる変種は、「未出現」シンボルが使用されるたびに、その擬似カウントを増加します。（言い換えれば、PPMdは新しいシンボルの確率を、観測されたシンボルの総数に対する固有のシンボルの数の比として推定します）。
実装
PPM圧縮の実装は、その他の細部において大きく異なります。実際のシンボル選択は通常、算術符号化を用いて記録されますが、ハフマン符号化や辞書符号化技術を用いることも可能です。ほとんどのPPMアルゴリズムで使用される基礎モデルは、複数のシンボルを予測するように拡張することも可能です。また、非マルコフモデリングを用いてマルコフモデリングを置き換えたり、補完したりすることも可能です。シンボルサイズは通常固定で、通常は1バイトであるため、あらゆるファイル形式の汎用的な処理が容易になります。
このアルゴリズム群に関する研究発表は、1980年代半ばにまで遡ります。PPMアルゴリズムは大量のRAMを必要とするため、ソフトウェア実装は1990年代初頭まで普及しませんでした。最近のPPM実装は、自然言語テキスト用のロスレス圧縮プログラムとして最も優れた性能を持つものの1つです。
PPMdは、ドミトリー・シュカリンによるPPMII（情報継承型PPM）のパブリックドメイン実装であり、互換性のない改訂が何度か行われてきました。[ 1 ] RARファイル形式ではデフォルトで使用されています。また、 7zおよびzipファイル形式でも利用可能です。
PPM アルゴリズムを改良する試みにより、PAQシリーズのデータ圧縮アルゴリズムが生まれました。
PPM アルゴリズムは、圧縮用としてではなく、代替入力方式プログラムDasherでのユーザー入力の効率を高めるために使用されます。
参照
出典
- Cleary, J.; Witten, I. (1984年4月). 「適応型符号化と部分文字列マッチングを用いたデータ圧縮」. IEEE Trans. Commun. 32 (4): 396– 402. CiteSeerX 10.1.1.14.4305 . doi : 10.1109/TCOM.1984.1096090 .
- Moffat, A. (1990年11月). 「PPMデータ圧縮方式の実装」. IEEE Trans. Commun. 38 (11): 1917– 1921. CiteSeerX 10.1.1.120.8728 . doi : 10.1109/26.61469 .
- Cleary, JG; Teahan, WJ; Witten, IH (1997). 「PPMのための無制限長コンテキスト」 .コンピュータジャーナル. 40 (2_and_3). オックスフォード（イギリス）: オックスフォード大学出版局: 67– 75. doi : 10.1093/comjnl/40.2_and_3.67 . ISSN 0010-4620 .
- C. Bloom、「コンテキスト モデリングの問題の解決」。
- WJ Teahan、PPM の確率推定、元のソースは archive.org です。
- シュールマン、T.グラスバーガー、P. (1996 年 9 月)。 「シンボルシーケンスのエントロピー推定」。カオス。6 (3): 414–427。arXiv : cond-mat / 0203436 。Bibcode : 1996Chaos...6..414S。土井: 10.1063/1.166191。PMID 12780271。S2CID 10090433。
参考文献
- ^ "BMF、PPMd Всё о сжатии данных, изображений и видео" . Compression.ru (ロシア語)。注意: ブラウザで「キリル文字 (Windows)」エンコードを手動で設定する必要があります。
外部リンク
 |
