Array::Gap

明日は一ヶ月ぶりのIIR輪読会です。主催のたつをさんから「教科書の話題から何か適当に実装せよ」という課題が出ていたので、5章のインデックスの圧縮の所で見た Variable byte codes (以下 VB code) を使った圧縮の実装を作ってみました。

整列済みの整数を圧縮する手法

ここでの圧縮のポイントは二つ。

昇順に並べられた整数を、整数そのままの数で扱うのではなく、一つ前の要素との差で扱う。差で扱うと 21,314,156 → 21,314,157 という数は "1" というより小さい数で表現することができる。(整列済みなので、差が分かれば逆の操作で復元が可能)
32 ビット int の整数を固定長 32 ビットで表現するのではなく可変長バイトで表現する。(これが VB code) VB code なら小さな数字は 32ビット = 4バイトよりも小さなビット数で表現できる

この二つの手法を組み合わせると、大きな整数を差分で小さい数字として表現し、その小さい数字を可変長整数で小さなビット数で表現することができるので、圧縮効果が得られます。

整数を可変長なエンコーディングで圧縮するアルゴリズムは、より圧縮率の高いγコードやδコードなども有名です。VB code は実装が簡単なのが利点です。VB code はバイトレベルでの圧縮、γコード/δコードはビットレベルでの圧縮になります。

ASN.1 Basic Encoding Rules / perl の pack('w', ...)

IIR で解説されている VB code は、ほぼ同じ変換規則で ASN.1 BER (Basic Encoding Rules) という仕様で標準化されているようです。(IIR での VB code と ASN.1 BER は先頭ビットの解釈が異なる。)

Perl の場合、pack() が整数を BER でエンコーディングする機能を提供しています。数値の 5 を 00000101 に変換するには

pack('w', 5) # 00000101

で ok です。

整列済みの整数リストを、pack() を利用した圧縮済みの配列として BER で保持しつつ、普通のリスト同様に扱えるよう操作を加えたクラスが今回作った Array::Gap です。

#!/usr/bin/env perl
use strict;
use warnings;

use FindBin::libs;
use Perl6::Say;
use Array::Gap;

my $array = Array::Gap->new;
$array->push(824);
$array->push(829);
$array->push(830);
$array->push(1024);
$array->push(215406);

my $it = $array->iterator;
while ($it->has_next) {
    say $it->next;
}

というコードの出力は

となります。一見すると Array::Gap 内部で配列を持っているだけのように見えますが、実際には内部で整数の配列は保持しておらず、隣り合う整数の差分をBER によるバイナリ表現、つまりスカラーで保持するようになっています。

ソースコードを以下に置いておきます。

http://github.com/naoya/perl-array-gap/tree/master

以上、夏休みの宿題でした。

追記

say $array

で、二進数の文字列表現を表示することができます。

my $array = Array::Gap->new;
$array->push(824);
$array->push(829);
$array->push(830);
$array->push(1024);
$array->push(215406);

say $array

ですと

100001100011100000000101000000011000000101000010100011011000101001101110

となります。72ビットです。工夫せずに実装すると、32ビット x 5 = 160 ビット*1になるところ、72 ビットで済んでいます。

*1:実際には 32ビット x 5 ではなく「Perl のスカラーのサイズ」 x 5 です。