perlで整数列圧縮(Unary符号化)

はじめに

ハッシュのkeyにID、valueにソート済み整数列を持つようなデータに対して、valueの整数列を圧縮したい。
perlで簡単なUnary符号化を書いてみた。転置インデックス圧縮などに。

コードについて

• Unary符号とは、1を区切りとして連続する0の個数で数字を表す符号化
  • たとえば「1,2,3」ならば「010010001」になる
• ファイルへの出力は以下の形式で入出力してみた
  • [ keyのバイトサイズ ][ key ][ valueのバイト列のサイズ ][ valueのバイト列 ]...
• サイズはそれぞれint(4byte)分だけ取って、そのサイズ分だけ後ろのバイトを入出力
• ビットを扱うのに、操作はvec、表示はunpackを使う

コード

モジュール Unary.pm

package Unary;
use strict;
use warnings;

#コンストラクタ
sub new {
    my $class = shift;
    #my ($a, $b) = @_;

    my $self = {
	HashTable => undef,
    };

    return bless($self, $class);
}

#テーブルのクリア
sub clear($){
    my ($self) = @_;
    undef($self->{HashTable});
}

#配列からバイト列に直す
sub encode($$){
    my ($self,@arr) = @_;

    my $ret = '';
    my $idx = 0;
    foreach my $val( @arr ){
	my $cnt = $val;
	while($cnt--){
	    vec($ret, $idx, 1) = 0;
	    $idx++;
	}
	vec($ret, $idx, 1) = 1;
	$idx++;
    }
    return $ret;
}

#バイト列から配列に直す
sub decode($$){
    my ($self,$bin) = @_;

    my @ret;
    my $tmp = 0;
    my $idx = 0;
    my $len = length($bin) * 8;
    while($idx < $len){
	if(vec($bin, $idx, 1)){
	    push(@ret, $tmp);
	    $tmp = 0;
	}else{
	    $tmp++;
	}
	$idx++;
    }

    return @ret;
}


#配列をセットする
sub set($$$){
    my ($self,$key,@value) = @_;

    if( defined($self->{HashTable}->{$key}) ){
	warn "error: Table already had key $key.";
	return 0;
    }
    
    $self->{HashTable}->{$key} = $self->encode(@value);
    return 1;
}

#配列を取り出す
sub get($$){
    my ($self,$key) = @_;
    
    if( !defined($self->{HashTable}->{$key}) ){
	warn "error: Table do not have key $key.";
	return ();
    }

    return $self->decode($self->{HashTable}->{$key});
}

#ファイルへ出力
sub save($$){
    my ($self,$filename) = @_;

    open(OUT, "> $filename") or die "error:$!";
    binmode(OUT);
    foreach my $key ( keys %{$self->{HashTable}} ){
	#ファイルに出力
	print OUT pack('i',length($key));
	print OUT $key;
	print OUT pack('i',length($self->{HashTable}->{$key}));
	print OUT $self->{HashTable}->{$key};
    }
    close(OUT);
}

#ファイルからロード
sub load($$){
    my ($self, $filename) = @_;
    
    open(IN, $filename);
    binmode(IN);
    my ($keylen, $key, $vallen, $value);
    while(read(IN, $keylen, 4)){
	$keylen = unpack('i',$keylen);
	read(IN, $key, $keylen);
	read(IN, $vallen, 4);
	$vallen = unpack('i',$vallen);
	read(IN, $value, $vallen);

	$self->{HashTable}->{$key} = $value;
   }
}
1;

テスト用コード Unary.pl

use lib qw(.);
use strict;
use warnings;
use Unary;

my $unary = new Unary();

#セットしてファイルに出力
$unary->set('ほげほげ', (1,2,3) );
$unary->set('ほげ', (1,3,5) );
$unary->set('ほげげ', (2,4,6) );
$unary->save('data.dat');

#一度消す
$unary->clear();

#ロードして読み込む
$unary->load('data.dat');
foreach my $v ($unary->get('ほげほげ')){
    print $v," ";
}
print "\n";
foreach my $v ($unary->get('ほげ')){
    print $v," ";
}
print "\n";
foreach my $v ($unary->get('ほげげ')){
    print $v," ";
}
print "\n";

修正すべき点

• encodeで0を代入している部分は$idx+=$cntにすべき
• ファイル保存時に、整数列の最初の数字はそのまま0の個数で保持してしまっているが、この数字が大きい場合、大変なことになるので、普通に最初の数字は別にintなどで出力すべき
  • [ keyのサイズ ][ key ][ 最初の数字 ][ valueのサイズ ][ value ]など