Integer::Elias - Elias gamma/delta coder

Perl でγ符号、δ符号で整数を符号化するためのモジュールを作りました。(ω符号はまだサポートしていませんが) Elias 整数符号のモジュールなので Integer::Elias という名前にしています。

γ符号、δ符号は整数の可変長符号です。バイト単位での可変長符号は ASN.1 BER (id:naoya:20080906:1220685978 参照) がありますが、γ符号、δ符号はビット単位での可変長符号で、より短いビット数で小さな整数を符号化することができます。

例えば 6 という数字があったとします。

6 の二進数での表現は 110 で 3 ビットです。110 の先頭ビットを除いたビット 10 で 2ビットあります。このビット数 2 を α符号 (Unary code) で表現すると 01 になります。α符号 は 0 の数で数字を表す符号です。例えば 2 は 01, 3 は 001, 4 は 0001, 5 は 00001 ... です。

  • 6 = 110 の先頭ビットを除いた 2ビットは 10
  • 2 を α符号化 => 01
  • α符号と先頭を除いたビットをくっつけて 01 10 → 0110

これがγ符号です。int の場合 6 を表現するのに 32 ビットが必要、char でも 8 ビットです。γ符号であれば 4 ビットで表現できます。このように小さな整数はビット単位の符号化でより短く表現することができます。なお、γ符号で α符号を使っているところを γ符号に変更したものがδ符号です。

検索エンジンの転置インデックスなどでは大量の整数を管理することになりますが、このとき Array::Gap での実装のように整数を小さく持つ工夫をした上でγ符号、δ符号で圧縮する手法が有効です。

Integer::Elias を使うと正の整数をγ符号化、δ符号化したバイナリが得られます。なお、Integer::Elias は 0 も符号化できるようにしているので、符号化のルールが少し異なります。

my $encoder = Integer::Elias::Encoder->new;

$encoder->gamma_encode(5);
$encoder->gamma_encode(10);
$encoder->gamma_encode(256);
$encoder->finish;

say $encoder->as_string; # 2進の文字列表現

my $decoder = Integer::Elias::Decoder->new( $encoder->binary );

say $decoder->gamma_decode; # 5;
say $decoder->gamma_decode; # 10;
say $decoder->gamma_decode; # 256;

実装にあたっては ホームページ移転のお知らせ - Yahoo!ジオシティーズ が大変参考になりました。

参考文献