Perl で Range Coder (再挑戦)

以前にも Perl で Range Coder を実装した (http://d.hatena.ne.jp/naoya/20080927/1222512024) のですが、当時は理解も曖昧なまま速度にも気を遣わずに実装していました。

再度改めて、Range Coder を実装してみました。

• http://github.com/naoya/perl-RangeCoder/tree/master

README に記載した通り、静的 Range Coder*1、Binary Indexed Tree を用いた適応型 Range Coder、それからついでに 1-order の有限文脈モデルをもちいたものを作ってみました。いずれも Algorithms with Python の情報 (1, 2, 3)を参考に実装しています。

Canterbury Corpus の alice29.txt は 0-order エントロピーが 4.57 ビット、圧縮の下界が 86,837 バイトです。これを Core 2 Duo T7200 を載せた coLinux 上で、拙作 Range Coder でそれぞれ圧縮してみたところ

% perl rc_sample.pl ~/cantrbry/alice29.txt > /dev/null
152089 bytes => 87383 bytes at rc_sample.pl line 30.
1 trial of encoding (2.260s total)
1 trial of decoding (3.090s total)

% perl adaptive_rc.pl ~/cantrbry/alice29.txt > /dev/null
152089 bytes => 88896 bytes at adaptive_rc.pl line 30.
1 trial of encoding (6.640s total)
1 trial of decoding (7.020s total)

% perl finite_context.pl ~/cantrbry/alice29.txt > /dev/null
152089 bytes => 74182 bytes at finite_context.pl line 30.
1 trial of encoding (8.740s total)
1 trial of decoding (8.980s total)

という結果になりました。速度、圧縮率共にもう少しチューニングできそうです。

おそらく圧縮率は、Range Coder の下限 (low) を 24 ビットで扱っていて、レンジの最大値が 0x1000000 なのをもっと大きくすることで改善すると思います。low を 32 ビット、レンジの最大値を 0xFFFFFFFF などにすると良いのでしょうが、Perl は use integer すると整数を signed int で扱います。その都合で今は 24 ビットでとりあえず実装しています。0xFFFFFFFE からはじめて云々でうまくいくのかなと思ったのですが、実装がまだうまくできません。アドバイス求む･･･! 広井さんから 31 ビットでの実装を教えていただきました (id:naoya:20090725:1248554486)

8月に発売の WEB+DB PRESS の次号 Vol.52 でデータ圧縮について書きました。分量的に1回では終らない内容でしたので、2 ~ 3 回に分ける予定です。2回目に、この Range Coder も含めて解説したいと思っています。

*1:頻度表は可変長バイト符号で pack して添付しています