Compressed Suffix ArrayとFM-Indexの性能を比較してみた

せっかくFM-Indexを実装したので、以前作ったCompressed Suffix Arrayとの性能比較をしてみた。
私の実装の比較なので本来の手法の良し悪しとは必ずしも一致しない可能性がある。あくまで参考程度に。

データにはいつもの住所データ(http://jusyo.jp/)を用いた。

$$ mkdir var
$$ cd var
$$ wget http://jusyo.jp/downloads/new/csv/csv_zenkoku.zip
$$ unzip csv_zenkoku.zip

$$ nkf -w zenkoku.txt > zenkoku.txt.utf8
$$ perl -ne '@a=split(/\t/);$s="$a[7]$a[9]$a[11]";
     $s=~s/"//g;print "$s\n"' zenkoku.txt.utf8 > zenkoku.key
$$ sort -u zenkoku.key -o zenkoku.key
$$ cd ..

とりあえず比較したのはデータサイズと、get_rows(検索キーに何件ヒットしたかを返す)という操作。以下の操作はshellinford/で行った。
まずデータをつくる。

$$ tsubomi_mkary var/zenkoku.key
$$ tsubomi_mkcsa var/zenkoku.key
$$ sample/make_fm_index var/zenkoku.key.fm < var/zenkoku.key

するとデータサイズは以下のようになった。

元テキスト: 3,872,813 byte
Suffix Array: 19,364,065 byte
Compressed Suffix Array: 6,093,288 byte
FM-Index: 5, 709, 560 byte

そしてget_rowsの比較には以下のコードを用いた。

#include "shellinford_fm_index.h"
#include "tsubomi_basic_searcher.h"
#include "tsubomi_compressor.h"
#include <iostream>
#include <ctime>

using namespace std;
int main(int argc, char **argv) {
  try {
    vector<string> v;
    string s;
    while (cin >> s) { v.push_back(s); }
    vector<string>::iterator i;
    clock_t tmp;
    double  sec;

    // tsubomi::basic_searcher
    tsubomi::basic_searcher bs(argv[1]);
    tmp = clock();
    for (i = v.begin(); i != v.end(); i++) {
      bs.search(i->c_str());
    }
    sec = double(clock() - tmp) / CLOCKS_PER_SEC;
    cout << sec << "s" << endl;

    // tsubomi::compressor
    tsubomi::compressor c(argv[1]);
    tmp = clock();
    for (i = v.begin(); i != v.end(); i++) {
      c.search(i->c_str());
    }
    sec = double(clock() - tmp) / CLOCKS_PER_SEC;
    cout << sec << "s" << endl;

    // shellinford::fm_index
    string fn = argv[1];
    fn += ".fm";
    shellinford::fm_index fm;
    fm.read(fn.c_str());
    tmp = clock();
    for (i = v.begin(); i != v.end(); i++) {
      fm.get_rows(*i);
    }
    sec = double(clock() - tmp) / CLOCKS_PER_SEC;
    cout << sec << "s" << endl;

  } catch (const char *err) {
    cerr << "ERROR: " << err << endl;
  }
  return 0;
}

これをeval.ccとして保存する。元データをシャッフルしたデータを入力として評価すると以下のようになった。

$$ shuf var/zenkoku.key > var/zenkoku.shuf
$$ g++ -O2 eval.cc -ltsubomi -lshellinford
$$ ./a.out var/zenkoku.key < var/zenkoku.shuf
0.128185s  # Suffix Array
8.26793s  # Compressed Suffix Array
4.56001s  # FM-Index

というわけで一応、(私の実装では)FM-IndexがCompressed Suffix Arrayよりもデータサイズ、get_rowsどちらも良い結果になった。