データ圧縮手法の応用

PPM (Prediction by Partial Matching)というデータ圧縮アルゴリズムがある。 一般に、あるデータ列が与えられているとき、次に来るデータを予測することができればデータ圧縮を行なうことができる。 データ列から判断して次に来るデータが「a」だと確実に判断できるときは「a」を記述する必要が無いからである。 PPM法では、既存のデータ列中の文字列出現頻度を計算することによってこのような予測を行なう。 たとえば「abracadab」というデータの次にどの文字が来るか予測する場合、

1. 「a」は4回、「b」は2回出現している
2. 「b」の後に「r」が続いたことがある
3. 「ab」の後に「r」が続いたことがある
4. ...

といった情報を累積して確率を推定する。 この場合、 (3)から考えて次の文字は「r」である確率が高いが、 (1)も考慮すると「a」の確率もある、という風に計算を行なう。

PPM法は圧縮方法として優れた性能を持っているが、 これは予測手法としても優れているということなので、 予測式文字入力などに応用することができる。 また、じゃんけんのような勝負において相手の次の手を予測するのにも利用できるはずである。 ちょっと作って実験してみたところ、 長く勝負すると必ず負けてしまうので、確かに効果的な予測が行なわれているのだろうと思う。

Association for Computing Machineryの機関誌Communication of the ACMの2月号で spam判定手法が特集されており、 PPM法をspam判定に使う手法が紹介されていた。 PPM法でspam圧縮を学習させると別のspamも効率よく圧縮できるため、圧縮効率でspamかどうかを判断できるらしい。 spamもいろいろ種類が多いはずだが、 単純な予測手法で判定できてしまうというのはなかなか興味深い。