らこらこらこ～ｗ で学ぶ圧縮講座

Kazuya Gokita @kazoo04

このように、各文字の出現確率に応じて異なる長さの符号を割り当てて圧縮するものを、エントロピー符号といいます。昨日のハフマン符号のように、一旦決めたたら符号語を変えないものを静的符号化といい、圧縮しながら適時符号語を変化させるものを動的符号化などと言ったりします。

Kazuya Gokita @kazoo04

このツイート、すばらしい指摘ですね。 http://t.co/KiuKDAkTAC ここからわかるように、事前情報は非常に重要です。予めデータの性質がわかっていたらより圧縮することができるからです。わかる→ウケる→ときて、次に来る文字が予想できるかどうかで圧縮率がかわるのです。

Kazuya Gokita @kazoo04

次に来る文字を予測するというコンセプトを全面に押し出したアルゴリズムがPrediction by Partial Matching (PPM)です。PPMはいくつかのテクニックを使って効率よく、また高い確率で次の文字を予測しようとします。アルゴリズムは複雑なのでここでは割愛します

Kazuya Gokita @kazoo04

いま、「ウケる」という文字だけ与えられたとします。次に来る文字（単語）はなんでしょう？難しいですね。ところが「わかるウケる」だったらどうでしょう？たぶん「神」かな？と予想できます。参照する文字数は多いほど高精度で予測できそうですね。ところがそうはいかないのです。

Kazuya Gokita @kazoo04

なぜなら、確率を推定できるほどのサンプルが得られないからです。ファイルサイズは有限ですから、確率を推定するための情報が少なすぎて、むしろ圧縮率は悪くなってしまいます。一方で、参照する文字数を少なくすると文脈情報が活かせません。どうすればよいでしょうか？

Kazuya Gokita @kazoo04

PPMでは、この問題に対して優れた方法で対応しています。まず可能な限り長い文字数で予測しようとし、その精度が悪そうだったら1文字ずつ参照する文字数を減らすという方法です。これなら両者のいいとこ取りが可能ですね。

Kazuya Gokita @kazoo04

PPMは過去にどんな文脈でどんな文字が出現したのかを保存しておいたり更新したりしなければならないので、圧縮に時間がかかるしメモリもたくさん使います。一方で高い圧縮率を誇るアルゴリズムのひとつです。