Prediction by Partial Matching
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/04/13 17:16 UTC 版)
Prediction by Partial Matching（PPM）は1984年にJ.G.ClearyとI.H.Wittenによって考案されたデータ圧縮アルゴリズムの1つ。 この改良版が7-zip等に用いられている。非常に高い圧縮率の反面、圧縮速度はかなり遅くメモリも多く消費するアルゴリズムである。
符号化の原理
aabacaabbaとデータを符号化したとして、次にどの記号が出現するかを統計的に予測する。この場合、統計的にaの次にはaが出現する可能性が高い。逆にcが出現する可能性は低いであろう。このように出現確率に偏りがあるとハフマン符号や算術符号で圧縮することができる。しかし、上記の場合に次に出現する符号をaを50%、bを40%、cを10%と予測したとすると、他の記号は絶対に現れないということになり、新たな記号（dとする）が出現したときに対応できなくなってしまう。これをゼロ頻度問題という。
そこで、PPMでは「今までに出現していない文字」として「エスケープ」（英語: escape）という記号を加える。上記の例であれば、aを45%、bを35%、cを5%などとして、エスケープには残りの15%を割り当てておく。これならば先ほどのように新しい記号dが出現したとしても、まずエスケープ記号を出力し、その後dを出力すればよい。更にこのとき、dを既知の記号として統計情報に加える。このように、まだ現れていない記号に他の記号の確率を配分し、ゼロ頻度問題を回避することをスムージングという。エスケープはスムージングの１つである。
また、エスケープには次のような役割もある。先ほどの文字列の統計情報を利用するとき、aの次にはaが出現しやすいが、baの次にはcが出現しやすい。このように、予測に用いる文脈の長さ（次数〈英語: order〉という）によって予想の結果は異なってしまう。次数は高いほうが正確な予想が出来ると思われるが、高い次数の文脈は統計情報が不足している場合が多い。この解決策として、まず一番高い次数から予想をし、エスケープであれば1つ低い次数で予想しなおすという案があり、これによって適切な次数による予想が可能となる。
エスケープの確率
先ほどの例ではエスケープには適当に15%を割り当てたが、実際にエスケープがどれくらいの確率であるかを推定することは重要である。符号化した記号が少なければエスケープの確率は高くなるだろう。逆に符号化が進み、多くの記号を符号化したころにはエスケープはあまり出現しないと考えられる。 エスケープ確率の推定方法はmethodと呼ばれいくつか提案されているが、中でもmethod Cとmethod Dは良い性能をみせる。
method A
PPMd
RARや7zなどに採用されている、PPMの中で最も速い方式。場合によってはRange Coderに匹敵するほど速い。それでも圧縮率はそこそこで、十分な圧縮率がある。
オリジナルのプログラムには様々なバージョンが存在する。
PPMN
 | この節の加筆が望まれています。 |
PPMY
| この節の加筆が望まれています。 |
PPMZ
PPM系列の中でもっとも圧縮率が高くなる方式。しかし、その分計算量は莫大に増え、実用にならないほど速度が遅い。
その為、改良しても速度が改善されにくく、サンプルプログラム以外に採用された例は無い。
亜種で圧縮率と速度を多少改善したPPMZ2が存在する。
関連項目
 | この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。 |
「Prediction by Partial Matching」の例文・使い方・用例・文例
- Colby KentがHeidi Petersに連絡をした理由
- goodbyはgoodbyeの異綴りである。
- 受身の動作主 《受身の by 以下に示されて動作を引き起こすもの》.
- タクシーで行く 《by cab は無冠詞》.
- 『rubber baby buggy bumper』は早口言葉である
- ｢Ruby(ルビー)｣と呼ばれる新しいコンピュータプログラミング言語を開発。
- Rubyはプログラム作成を楽しく手軽なものにし，世界中で広く使われている。
- Rubyはウェブサイト作成にも利用できる。
- この言語はRubyとはかなり違っていました。
- 1993年にRubyの開発を始めました。
- Rubyを使って最も簡単なプログラムを動かすのに半年近くかかりました。
- でも，私は進み続け，ついにRubyを完成させました。
- 1995年，Rubyは一般に公開されました。
- 現在はフェローの肩書きをもらい，Rubyに関する開発や講演，執筆に専念しています。
- ７月１日，ウォルマートNWアーカンソー選手権 by P&G の最終ラウンドが米国アーカンソー州のピナクルカントリークラブで行われた。
- Prediction_by_Partial_Matchingのページへのリンク
