話題のウェーブレット行列を組み込んだ検索ライブラリShellinfordのPerlモジュールを作った

ごく一部で話題沸騰中のまじぱないデータ構造、ウェーブレット行列を用いた検索アルゴリズムであるFM-Index。このFM-Indexは以前私が実装したShellinfordというライブラリから利用可能になっている。さらにここで用いたウェーブレット行列にはオリジナルにはない高速化を加えている。

ウェーブレット行列を用いたFM-Indexを大幅に高速化した - EchizenBlog-Zwei

とはいえC++からしか使えなくて少々不便だったのでPerlモジュールを用意してみた。


ライブラリのインストール方法は以下を参照。

http://code.google.com/p/shellinford/

サンプルを示す。

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");