ウェーブレット木のライブラリshellinfordを作ったので公開しておく

計算機科学

ついかっとなってウェーブレット木のライブラリを作ってみた。せっかくなので公開しておく。LOUDSはerika-trieを作ったので今度はウェーブレット木を作りたかった。
ライブラリ名はおおかたの予想を裏切りshellinford。かびーん。
なお、ウェーブレット木で用いている簡潔ビットベクトルは前回のDSIRNLPで発表したものの公開していなかった「少ない労力でそこそこいけてるビットベクトル」を使っている。

shellinford - shellinford: succinct document retrieval library - Google Project Hosting
DSIRNLP#2で発表しました「作ろう！簡潔ビットベクトル」 - EchizenBlog-Zwei


まずソースコードを取ってきてインスト。

$$ svn checkout https://shellinford.googlecode.com/svn/trunk/ shellinford
$$ cd shellinford/src
$$ make
$$ make install
$$ cd ..

サンプルとしてBWT(Burrows-Wheeler Transform, BW変換)のコードが付属している。

$$ cd sample
$$ make
$$ ./bwt
mississippi    # 変換前
ipssm$pissii  # 変換後

$$ ./rbwt
ipssm$pissii  # 逆変換前
mississippi    # 逆変換後

というわけで今後はこのshellinfordを使ってFM-Indexとか2D-Searchとかを実装していく予定。