Perl で Range Coder

練習がてら、圧縮符号化の手法のひとつである Range Coder を Perl で実装してみました。

Range Coder は算術符号を実数ではなく整数で実現した手法です。高速な算術圧縮を実現する「Range Coder」 (1/2)：CodeZine（コードジン） に詳しい解説があります。今回の実装も、この記事にあるソースコードを参考に実装しました。参考、というか結局ほとんど移植に近くなってしまいました。

インタフェースは以下のようになっています。入力文字列における各記号の出現頻度、累積出現頻度をあらかじめ算出して RangeCoder オブジェクトにセットしてから、encode することで圧縮結果が得られます。(出現頻度表をバイナリに添加する実装は行っていません。)

use Algorithm::RangeCoder;

use constant UCHAR_MAX => 0xff;

my $text = shift or die "usage: $0 <text>";

## 記号の出現頻度を求める
my @freq;
for (my $i = 0; $i < UCHAR_MAX; $i++) {
    $freq[$i] = 0;
}

for my $c ( unpack('C*', $text) ) {
    $freq[$c]++;
}

## 記号の累積出現頻度を求める
my @cum = (0);
for (my $i = 0; $i < UCHAR_MAX; $i++) {
    $cum[$i + 1] = $cum[$i] + $freq[$i];
}

my $rc = Algorithm::RangeCoder->new;
$rc->freq    = \@freq;
$rc->cumfreq = \@cum;

$rc->encode($text);

この RangeCoder 実装で、実際に符号化してみます。算術符号の例で良くでてくる "aaaaaaaaa...b" で 100 文字という、偏った出現確率を持つ文字列を与えてみます。

% perl sample.pl aaaaa(略)b
origin:  aaaaa(略)b
decoded: aaaaa(略)b
100 bytes => 5 bytes (95.0%)

と、正しく符号化/復号できています。また、100バイトの文字列が 5 バイトまで縮まりました。記号一文字に対して最低でも1ビットを割り当てるハフマン符号ではここまで縮めることはできませんが、算術符号法なら可能です。

Perl で Range Coder を実装するにあたって一つ困ったのは、整数の扱いでした。Perl のスカラーは数値を内部的に浮動小数点として扱うようですが、Range Coder では符号化処理を整数で実装します。Perl でも integer プラグマを利用することでコンパイラに整数を利用することを指示できますが、integer プラグマはこのとき int を unsigned ではなく signed int として扱います。一方、Range Coder の実装では unsigned int を使った方が効率的にも実装的にも良さそうでした。

Perl で unsigned int をうまく、あるいは上手にごまかして扱う方法はないものかと調べていたところ CPAN にある Data::Integer の実装が参考になりました。最初は Data::Integer を参考に整数周りの処理を記述していましたが、参考箇所が多くなったので結局 Data::Integer をそのまま利用することにしました。

普段 Perl で数値の型を意識してプログラムを書くことは希だったので、その取り扱いについての知識が曖昧でしたが、今回の実装をきっかけに Perl の理解も深めることができて良かったです。

圧縮符号プログラムを LL で書く、というのは実用的には微妙なところですが、アルゴリズムの理解のためということでひとつご容赦ください。

追記

本エントリの実装は、あまり速度などを気にせず参考文献の実装を移植した感じの実装でした。その後理解が深まったので改めて実装したものを以下の URL にアップロードしています。

参考文献