話題のウェーブレット行列を組み込んだ検索ライブラリShellinfordのPerlモジュールを作った
ごく一部で話題沸騰中のまじぱないデータ構造、ウェーブレット行列を用いた検索アルゴリズムであるFM-Index。このFM-Indexは以前私が実装したShellinfordというライブラリから利用可能になっている。さらにここで用いたウェーブレット行列にはオリジナルにはない高速化を加えている。
とはいえC++からしか使えなくて少々不便だったのでPerlモジュールを用意してみた。
ライブラリのインストール方法は以下を参照。
サンプルを示す。
use strict; use warnings; use Shellinford; my @docs = ("apple", "orange", "remon", "application"); my $fm = Shellinford->new; for my $doc (@docs) { $fm->push_back($doc); } $fm->build(); while (my $key = <>) { chomp($key); my $res = $fm->search($key); for my $did (keys %$res) { my $doc = $fm->get_document($did); print "$did : $doc\n"; } }
これをtest.plとして保存して実行すると以下のようになる。
$$ perl test.pl apple 0 : apple app 3 : application 0 : apple
ファイルの読み書きは以下のとおり。
ただしbuild後のデータしか読み書きできず、build後にpush_backはできないので注意。
$fm->write("temp"); $fm->read("temp");