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!ジオシティーズ が大変参考になりました。
参考文献
- ホームページ移転のお知らせ - Yahoo!ジオシティーズ - 整数の符号化について詳しく解説されています。Python による実装もあります。0を符号化するにあたっての解説もあります
- Universal code (data compression) - Wikipedia - Universal code の解説。Elias 符号の位置づけについてなど
- Gamma codes - Introduction to Information Retrieval 5章。転置インデックスの圧縮法についての解説の中でγ符号について触れられています