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;

[tuhuteap]

圧縮全文索引の実装などでしばしば利用される Rank/Select 辞書と呼ばれるデータ構造　Wavelet Tree (ウェーブレット木)：）

[teddy-g]

ウェーブレット木のPERL実装

[taki0313]

うぇーぶれっと

[odessa_mydns_jp]

圧縮

[ajapo]

文字列のRank/Select辞書のためのデータ構造Wavelet Treeの実装

[sshi]

だれかRuby実装つくらんかな

[AK78]

データ構造 ウェーブレット木

[hiromark]

WaveletTree のライブラリ。

[ototoi]

僕も書いてみたよ。というか書いてあったんだけど、いい機会だからさらしてみるよ。