第3回目 MG勉強会
Managing Gigabytesの3回目です。本日の内容は算術符号とブロックソーティングです。ここは結構目から鱗的な、おもしろいアルゴリズム連発です。
算術符号
まずは算術符号です。前回出てきたハフマンコーディングは、1パス目で各語の出現頻度を求めて、2パス目で符号化するという方法でしたが、これは1パスで出現頻度を求めつつ、同時に符号化を行っていく方法になります。それでいて、ハフマンコーディングより圧縮率が高いという方法になります。
算術符号では、実数の「範囲」をうまく使って、出現頻度の高い語には広い範囲、出現頻度の低い語には狭い範囲を割り当てることで、圧縮を効率よく行う方法です。ちゃんと説明すると長そうなので、いずれまたちゃんとした説明を試みます。