簡潔データ構造を使った全文検索アルゴリズム、FM-Indexのライブラリを作りました

計算機科学

先日公開したウェーブレット木のライブラリshellinfordにFM-Indexの機能を追加した。
まだ基本的な機能しか実装していないけれど、とりいそぎ公開しておく。おいおい機能は追加していく予定。


ちなみにウェーブレット木はちょっと高速化したので一つ前の記事のパフォーマンス測定結果が改善されて

rank_wavelet_tree: 14.71s
select_wavelet_tree: 460.34s

となった。これについては機会があったら記事を書く。

サンプルは以下のような感じ。

#include <iostream>
#include "shellinford_fm_index.h"

using namespace std;
using namespace shellinford;
int main() {
  try {
    string s = "mississippi";
    cout << "text: " << s << endl;

    fm_index fm;
    fm.build(s.c_str());

    string key = "";
    while (cin >> key) {
      uint64_t first, last;
      uint64_t rows = fm.get_rows(key.c_str(), first, last);
      cout << rows << " hits." << endl;
      if (rows > 0) {
        for (uint64_t i = first; i <= last; i++) {
          uint64_t pos = fm.get_position(i);
          cout << fm.get_substring(pos, fm.size()) << endl;
        }
      }
    }
  } catch (const char *err) {
    cerr << "ERR: " << err << endl;
    return 1;
  }
  return 0;
}

これをsample.ccなどどして保存し以下のように使う。

$$ g++ -lshellinford sample.cc
$$ ./a.out
text: mississippi
ssi
2 hits.
ssippi
ssissippi

テキストmississippiから検索キーssiで始まるsuffixが2件検索された。