low が 31 ビットの Range Coder

先日実装した Range Coder (id:naoya:20090724:1248433187) は Perl が use integer すると整数を signed int で扱う関係から low を 24 ビットで妥協し、整数32ビットの上位1バイトを使わない実装を行っていましが、signed int の場合でも 32 ビットの最上位ビットを使わない、すなわち 31 ビットで計算すると良いということ、またその実装方法を広井さん (参考にさせていただいた Algorithms with Python の広井さんです) に教えていだだきました。ありがとうございます!

github のレポジトリに 31 ビット版の実装を追加しました。

の、lib/RangeCoder.pm が 24 ビット版、lib/RangeCoder/Wide.pm が 31 ビット版です。

24 ビット版との diff は以下になりました。

--- lib/RangeCoder.pm	2009-07-22 22:24:15.000000000 +0900
+++ lib/RangeCoder/Wide.pm	2009-07-26 04:57:07.000000000 +0900
@@ -1,4 +1,5 @@
-package RangeCoder;
+## 31 bit low
+package RangeCoder::Wide;
 use strict;
 use warnings;
 
@@ -6,22 +7,21 @@
 use List::Util qw/max/;
 
 use constant UCHAR_MAX => 256;
-use constant MAX_RANGE => 0x1000000;
-use constant MIN_RANGE => 0x10000;
-use constant MASK      => 0xffffff;
-use constant SHIFT     => 16;
+use constant MAX_RANGE => 0x7fffffff; # 31 bit
+use constant MIN_RANGE => 0x800000;
+use constant MASK      => 0x7fffffff;
+use constant SHIFT     => 23;         # 31 bit の上位 8 bit を取り出したい
 
 sub new {
     my ($class, $count) = @_;
     my $self = bless { count => $count }, $class;
 
     ## Smoothing (奥村さんの方式)
-    ## 655355 を越えないように
-    ## 度数の最大値が 255 になるように調節
-    if ((my $m = max(@$count)) >= 256) {
+    ## 度数の最大値が 0x7fff になるように調節
+    if ((my $m = max(@$count)) >= 0x7fff) {
        use integer;
        for my $v (@$count) {
-           $v = ($v * 255 + $m - 1) / $m;
+           $v = ($v * 0x7fff + $m - 1) / $m;
        }
     }
 
@@ -111,9 +111,12 @@
     for (my $i = $self->{n_carry}; $i > 0; $i--) {
         putc($out, 0xff);
     }
-    putc($out, ($self->{low} >> 16) & 0xff);
-    putc($out, ($self->{low} >> 8)  & 0xff);
-    putc($out, $self->{low} & 0xff);
+
+    ## 31 bit 書き出し
+    putc($out, ($self->{low} >> 23) & 0xff);
+    putc($out, ($self->{low} >> 15) & 0xff);
+    putc($out, ($self->{low} >> 7)  & 0xff);
+    putc($out, ($self->{low} & 0x7f) << 1);
 }
 
 sub decode {
@@ -131,9 +134,13 @@
     &getc($in);
 
     my $self = $class->new(\@count);
+
+    ## 31 bit 読み込み、最後の 1 ビットは buff に保存
     $self->{low} = &getc($in);
     $self->{low} = ($self->{low} << 8) + &getc($in);
     $self->{low} = ($self->{low} << 8) + &getc($in);
+    $self->{buff} = &getc($in);
+    $self->{low} = ($self->{low} << 7) + ($self->{buff} >> 1);
 
     ## cumfreq[c]/total <= low/range < cumfreq[c + 1]/total な c を探す
     ## 探し当てたら low と range を更新して同様に繰り返す
@@ -157,8 +164,12 @@
 sub decode_normalize {
     my ($self, $in) = @_;
     while ($self->{range} < MIN_RANGE) {
+        # buff の 1 ビット挿入
+        $self->{low} = ($self->{low} << 1) + ($self->{buff} & 1); 
+        # 読み出したデータから上位 7 ビットを挿入。残り1ビットは buff に残して次回に
+        $self->{buff} = &getc($in);
+        $self->{low} = (($self->{low} << 7) + ($self->{buff} >> 1)) & MASK; 
         $self->{range} <<= 8;
-        $self->{low} = (($self->{low} << 8) + &getc($in)) & MASK;
     }
 }

ポイントは

  • 32 ビット整数で最上位ビットを使わないのでレンジは 0x7FFF_FFFF から始める。またマスクが 31 ビット で 0x7FFF_FFFF になる
  • 31 ビットの上位 8 ビットを符号化時に取り出すので、SHIFT は 23 ビットになる
  • 桁上がりで 32 ビット目が有効になっても、それが必ず負数であることを使えば桁上がり処理も記述できる
  • データの読み込みにあたっては、バッファをうまく使って半端な 1 ビットを調整する
    • low にはまずバッファの 1 ビットを挿入してから、データの上位 7 ビットを挿入する

という所でした。なるほどー。特に最後の箇所がなかなか思いつきませんでした。

なお、広井さん曰く、"同様な方法は Michael Schindler さんや Yuta Mori さんの rangecoder で使われていたと記憶しています。" とのことです。

さて、31 ビット化したことにより圧縮サイズが改善されるか、前回同様 Canterbury Corpus の alice29.txt (0-order で 86,837 バイトが下界)で試してみました。

実装 24ビット 31ビット
静的 Range Coder 87,383 (87,110) 87,119 (86,886)
適応型 Range Coder 88,896 (88,892) 87,158 (87,154)

となりました。括弧内の数字はファイルサイズや頻度表など先頭に埋め込んでいるメタデータを除いたサイズです。31 ビット版の静的 Range Coderでは圧縮下界にかなり近づいています。これは楽しい。広井さんに感謝です。