Wavelet Tree - naoyaのはてなダイアリー

圧縮全文索引の実装などでしばしば利用される Rank/Select 辞書と呼ばれるデータ構造があります。詳しくは参考文献を参照していただくとして、今回は一般の文字列に対して効率的に Rank/Select を可能とするデータ構造である Wavelet Tree (ウェーブレット木) のライブラリを作りました。

http://github.com/naoya/perl-algorithm-wavelettree/tree/master

my $wt = Algorithm::WaveletTree->new("abccbbabca");

is $wt->rank(6, 'a'), 2;
is $wt->rank(6, 'b'), 3;
is $wt->rank(9, 'b'), 4;

is $wt->select(0, 'a'), 0;
is $wt->select(1, 'a'), 6;
is $wt->select(2, 'a'), 9;

Wavelet Tree の実装は『高速且つ省メモリで文字列を扱うデータ構造「wavelet tree」』を参考にしました。

Wavelet Tree は入力文字列から構築されたハフマン木の節に、簡潔データ構造 (Succinct Data Structure) のビットベクトルを付与したデータ構造です (ビットベクトルについては後述)。今回の自分の実装では、ハフマン木はオブジェクト同士のポインタでツリーを表現したものをヒープを使って構築しています。Wavelet Tree の性格からいくとオブジェクトやポインタのサイズは余計なので、配列などで工夫してより小さいツリーの表現を使うようにしたほうが良さそうです (そもそも実用性を考えるなら LL での実装は微妙ですけれど)。参考文献の実装はそのようになっています。

Wavelet Tree があると Burrows Wheeler Transform (id:naoya:20081016:1224173077) で変換したテキストを使って、圧縮全文索引 (FM-Index) などが実装できます。この辺りについてはまた折りを見て言及したいと思います。

Bit::Vector::Succinct

Wavelet Tree を実装するためにはビットベクトルの簡潔データ構造が必要でした。そこで、Perl の vec() 関数によるビットベクトルに対して Rank/Select を可能にする Bit::Vector::Succinct も作りました。

http://github.com/naoya/perl-bit-vector-succinct/tree/master

同パッケージにある Bit::Vector::Succinct::Raw が vec() 関数をオブジェクト指向で操作できるようラッピングしたクラスです。このビットベクタオブジェクトを Bit::Vector::Succinct に渡すと、Rank/Select 辞書が得られます。

my $vec = Bit::Vector::Succinct::Raw->new;
$vec->set(1);
$vec->set(2);
$vec->set(3);
 
my $sucbv = Bit::Vector::Succinct->new($vec);

## rank1
is $sucbv->rank(0, 1),   0;
is $sucbv->rank(1, 1),   1;
is $sucbv->rank(2, 1),   2;

## select1
is $sucbv->select(0, 1), 1;
is $sucbv->select(1, 1), 2;
is $sucbv->select(2, 1), 3;

rank メソッドの実装は『高速かつ省メモリなbit vector「sucBV」を作る』の実装を参考にしました。select はいまのところ簡単のため、rank の二分探索で実装しています。

参考文献

R. Grossi, A. Gupta, J.S. Vitter "High-Order Entropy-Compressed Text Indexes" SODA '03, 2003
定兼邦彦: 『圧縮データ構造とその最新動向』, RAMP2006, 2006
岡野原大輔: 『圧縮索引とその周辺』, 2005
岡野原大輔: 『現実的な圧縮付全文索引』, 夏のプログラミングシンポジウム 2005, 2005
岡野原大輔: 『高速かつ省メモリなbit vector「sucBV」を作る』, CodeZine, 翔泳社, 2006
岡野原大輔: 『高速且つ省メモリで文字列を扱うデータ構造「wavelet tree」』, CodeZine, 翔泳社, 2006
岡野原大輔: 『大規模データを高速・コンパクトに処理するデータ構造』 WEB+DB PRESS Vol.42, 技術評論社 2006
広井誠: 『Algorithms with Python / シャノン・ファノ符号とハフマン符号』, 2007

付録: Algorithm::Huffman 0.09 のパッチ

ハフマン木を構築するにあたって、結局はヒープから構築するコードを実装しましたが、途中 Algorithm::Huffman を試しました。Algorithm::Huffman 0.09 は Heap::Elem の最新版の実装と相性が悪く、Heap::Elem が新しいと正しく動作しません。Heap::Elem のオブジェクト表現がハッシュから配列に変更になったのが原因のようです。

この問題を修正するパッチは以下です。作者にメールしました。

diff -Nur Algorithm-Huffman-0.09.prev/Huffman.pm Algorithm-Huffman-0.09/Huffman.pm
--- Algorithm-Huffman-0.09.prev/Huffman.pm      2002-09-06 20:29:16.000000000 +0900
+++ Algorithm-Huffman-0.09/Huffman.pm   2008-11-14 17:13:41.000000000 +0900
@@ -189,31 +189,34 @@

 our @ISA = qw/Exporter Heap::Elem/;

+use constant KEY   => 2;
+use constant VALUE => 3;
+
 sub new {
    my ($proto, $key, $value) = @_;
    my $class = ref($proto) || $proto;

    my $self = $class->SUPER::new;

-   $self->{"KeyValuePair::key"}   = $key;
-   $self->{"KeyValuePair::value"} = $value;
+   $self->[ KEY ]   = $key;
+   $self->[ VALUE ] = $value;

    return $self;
 }

 sub cmp {
    my ($self, $other) = @_;
-   $self->{"KeyValuePair::value"} <=> $other->{"KeyValuePair::value"};
+   $self->[ VALUE ] <=> $other->[ VALUE ];
 }

 sub key {
     my $self = shift;
-    return $self->{"KeyValuePair::key"};
+    return $self->[ KEY ];
 }

 sub value {
     my $self = shift;
-    return $self->{"KeyValuePair::value"};
+    return $self->[ VALUE ];
 }

 1;