PPMとは？

PPMというのは、既出したデータから次の文字を予測して、確率を変化させる
ことにより圧縮するものである。

例えば　abcdabcdabcdabc○

と来て○に入る文字は何だろうと考えてみたとき、dが出やすいというのは直感的に
わかる。そういう場合はdの確率を上げ、他の文字の出現確率を下げる。すると、圧縮
される。たぶんわからないと思うので、詳しく説明します。

確率を上げるとなぜ圧縮率が上がるか？

例えば８種類の文字 a,b,c,d,e,f,g,h　があって、それを0と1で表すのならば

a:000
b:001
c:010
d:011
e:100
f:101
g:110
h:111

（方法Ａ）

とそれぞれに3bit割り振ればよい。つまり一文字に付き3bit使う。
これに対し、もし８つの文字にばらつきがある、つまり出現確率が違う場合には
多く出てくる文字に対し小さい文字を割り当ててみる。

例としてa が 確率　1/2　で、　b,c,d,e,f,g,h が　確率　1/14 で出現するとする。
そのとき

a:0
b:1000
c:1001
d:1010
e:1011
f:1100
g:1101
h:1110

（方法Ｂ）

と割り当てを変えたとする。

方法Ａの場合　3 * 1/2 + 7 * 3 * 1/14 = 3
方法Ｂの場合　1 * 1/2 + 7 * 4 * 1/14 = 2.5

と小さくなる。

このとき出現確率pのものをどのくらいの長さのbit数で表せばもっとも小さくなるのか
これは、「-log2(p)」 という長さのビット数で表すと最も短いことがわかります。

直感的に　1/2で出現するものは1bitで表現したらよさそう　 確かに　-log2(1/2) = 1
　　　　　1/4　　　　　　　　2 　　　　-log2(1/4) = 2

これに対しaの出現確率がp = 99/100 bの出現確率がp = 1/100
の場合、aは-log2(99/100) = 0.014bit b は -log2(1/100) = 6.66bitで表せばよいことがわかる。

0.014bitで表現できるのか？0か1でないと表現できないんじゃないのか？
と思うかもしれませんが、これは算術圧縮（実用的にはrangecoder）によって実現できます。

PPMの詳細

では、実際にこのアイディアを使って圧縮してみます。

方法としては、実際にデータを一通り見てどの文字の次に何が来るかを統計をとり、
その統計の表を出力して、圧縮、復元の際はその表を見ながら圧縮、復元をする（方法１）
もしくは、表を出力せず、圧縮でも復元でも今まででてきた文字列のみから情報を
とりそれを利用して圧縮、復元するという方法（方法２）

の二種類があります。そして現時点では方法２が使われています。理由は方法１だと、表自体
の出力にものすごいコストがかかるからです。

というわけでPPMでは今までのデータからの情報を利用して圧縮します。

例として

・・・・・abcdefg

と今までデータを変換してきて、次のgの次の文字が何が出てくるかを予測するとします。
ここで問題になるのが

この場合だと abcdefg　という文字列が以前に出現している場合、abcdefgのあとに何が出てくる
かを統計として情報として持っていたとします。そしてその統計が文字列が２回出現しており、
二回ともaであったとします。

このときaの出現予想確率を100%としてよいのでしょうか？
もし100% つまり p = 1 としてしまった場合、他の文字の出現確率　p = 0 となります。すると、
他の文字が出てきてしまった場合に対処ができなくなります。（前の-log(p)で計算すると、
-log(p) = + ∞　というかエラー）そうすると他の文字が出てくる場合を想定して確率を確保
しておかなければなりません。

この今までの統計で見られない文字をescape（エスケープ）といいます。
そして、今まで出現してきた文字の確率を(1 - エスケープの確率）* 想定されていた確率
として、(1 - エスケープの確率）のところで確率を小さくして、エスケープのために確率の
スペースをあけてあげます。

ではこのescapeの確率（この場合だとa以外の文字が出現する確率）はどのようにすればよいので
しょうか？実はこの問題に対する決定的な答えはありません。予想の方法にはいろいろな方法が
あります。

現在までに次のような方法が提案されています。

エスケープの確率
A 1/(n + 1)
B (u-t1)/n
C u/(n + u)
D (u/2)/n
P t1/n - t2/n^2 - t3/n^3 - ・・・
X t1/n

（nは今まで合計文字出現数　uはescapeが出現した回数　tiはi回出現した文字の個数)

などです。例としてAの場合だと、上の例では予想出現確率は、aが2/3 エスケープが1/3
となります。

このエスケープ確率の予想が、PPMの圧縮率に一番かかわる要素です。

escapeの役目

では、これで予想ができるかといえばまだ不十分です。

それは本当に一番長い文字列一致の部分だけで考えてよいのかという話です。上の例ではabcdefg
という文字列だけを見てみましたが、bcdefg、cdefg、defg、efg、fg、g、条件無しの場合、のように
他に７種類の文字列を使った予想の仕方があります。

わかりやすくするために、何文字で予想するかをN文字で予想する場合order-N（オーダーN)という
書き方をします。この場合、order-7がabcdefgで予想する場合であり条件無しの場合がorder-0です。

確かにオーダーが高ければ予想は正確になりそうですが、低いorderで予想したほうがいい場合も
あるし、すべてのオーダーを考慮に入れたいです。すべてのオーダーに重み付けをして計算すれば
いいかもしれませんが、もっといい方法があります。

エスケープを使えばエスケープになった場合に一つ下のオーダーで予想するということにすれば
すっきりします。そのオーダーで見つからなければどんどん下のオーダーに移っていき、最後
は条件無しの場合によって、すべての文字がキャッチされるということです。
オーダー１の予想で出現文字がでてきた場合だと、エスケープ文字が６回出現するということに
なります。

注意してほしいのは上のオーダーで予想した文字が出現したら、下のオーダーで確率を計算しなくて
よいということです。escapeの導入により、高速化されます。（実際にテストによるとほとんどの
文字が高いオーダーで変換される）

また、上のオーダーで出現しなかった場合の確率を下のオーダーでも考慮にいれるのは無駄になります。
例えばorder-7でaを考慮に入れた上で、エスケープがでているのにorder-6以下でaの文字用に確率を
保持しておくのは無駄です。その分を他の文字の確率に与えたほうがいいです。
これをexclusion（日本語だと除外ということがあるそうです。）といいます。

今パソコンで使われているデータは１バイト単位、つまり２５６種類あります。このexclusionは
この２５６個の配列を用意しておいて上のオーダーで使われたら、その配列の部分に使われたという
記号（マスクという）を入れておけば簡単に実装できます。

LOE SEE PPM�U

で、実際ここまでの知識を使って実装してみようとすると、すぐに問題が発生します。
それは高いオーダーでの予想が非常に信頼性が無いということです。

一般的に高いオーダーであればあるほど、今までの出現回数（サンプル数）が少なく、次の文字
の予想がしづらく、圧縮率向上のネックになります。PPMZで使われているLOE(Local Order Estimation)
ではどのオーダーでの予想が良さそうなのかを推定する方法です。

PPMZの論文ではいろいろな方法が提案されていますが、その中の一つに、もっとも出現確率が高い
文字の確率を基準にその確率が高い順にオーダーを決めるというのがあります。

また、PPMZでは、パラメータを決め、それによる評価関数によりオーダーを決める場合がありますが
ファイルによってパラメータを調整しなければなりません。（圧縮率はいいが）

また、エスケープの予想でもSEE(Secondary Escape Estimation)という方法が使われています。
これは、オーダー、エスケープの回数、マッチした回数によってハッシュキーをつくりそれにより、
似たようなものを集めてエスケープの予想をしてしまおうというものです。エスケープの回数が
多い場合は普通のPPMの予想を使うので、これは、サンプル数が少ない場合のエスケープの予想に
役立ちます。

他にppmdは今までより長いオーダーのコンテキストがでてきた場合に、コンテキストを木として
持っている場合ならば、親の情報を子に遺伝させることにより、はじめから、かなり高い予想性能
を持たせるという方法があります。

具体的には abcdという文字列がはじめて出てきた場合、bcdは今までたくさんでてきていて、次の
文字の予測に信頼性がある場合、abcdでの予測の初期値にbcdの今まで集めた統計情報を入れると
いうことです。これは子をつけるときだけにしか必要ないので非常に高速に、かつ非常によい性能を
みせています。