第3回目 MG勉強会

Managing Gigabytesの3回目です。本日の内容は算術符号とブロックソーティングです。ここは結構目から鱗的な、おもしろいアルゴリズム連発です。

算術符号

まずは算術符号です。前回出てきたハフマンコーディングは、1パス目で各語の出現頻度を求めて、2パス目で符号化するという方法でしたが、これは1パスで出現頻度を求めつつ、同時に符号化を行っていく方法になります。それでいて、ハフマンコーディングより圧縮率が高いという方法になります。


算術符号では、実数の「範囲」をうまく使って、出現頻度の高い語には広い範囲、出現頻度の低い語には狭い範囲を割り当てることで、圧縮を効率よく行う方法です。ちゃんと説明すると長そうなので、いずれまたちゃんとした説明を試みます。

ブロックソーティング

もう一つがブロックソーティングです。この方法は、文章を「文脈」により並べ替える方法です。
ここで言う文脈とは、簡単に言うと前の語のことです。

この方法自体は並べ替えるだけの方法ですが、ほかの圧縮技法と組み合わせることで大きな効果が得られます。自然言語というのは、だいたいにおいて同じ文脈だと同じ語が使われることになります。そのため、文脈ごとに並べ替えると、同じ語が連続して並ぶことになり、圧縮しやすい形になる、ということです。



今回は数式はあまり出てこないのですが、アルゴリズムが結構複雑で、難しい部分でした。次回までにちゃんと復習しとかねば。