SA-IS: C++版

以前common lispで実装したSA-ISアルゴリズムを、C++でも実装したのでその計時結果など。
ソースコード(github): sais-0.0.1

計時

対象データには以下のサイズのテキストファイル群を使用。

$ ls sa.txt.*
-rw-r--r-- 1 user user     10000 2010-12-23 19:25 sa.txt.10000     # 約10KB
-rw-r--r-- 1 user user    100000 2010-12-23 19:25 sa.txt.100000    # 約100KB
-rw-r--r-- 1 user user   1000000 2010-12-23 19:25 sa.txt.1000000   # 約1MB
-rw-r--r-- 1 user user  10000000 2010-12-23 19:25 sa.txt.10000000  # 約10MB
-rw-r--r-- 1 user user 100000000 2010-12-23 19:25 sa.txt.100000000 # 約100MB


計時結果.
表の二番目のSA-ISの実装には『Two Efficient Algorithms for Linear Suffix Array Construction』に載っているC++ソースコードを使用。
※ 末尾の計時用プログラムも参照

構築時間/最大使用メモリsa.txt.10000sa.txt.100000sa.txt.1000000sa.txt.10000000sa.txt.100000000
std::sort関数0.007秒/49KB0.094秒/488KB4.246秒/4883KB394.3秒/48828KB計測不能*1
SA-IS(論文の実装)0.002秒/57KB0.020秒/543KB0.215秒/5382KB3.542秒/53010KB40.34秒/530268KB
SA-IS(sais-0.0.1)0.002秒/90KB0.019秒/781KB0.192秒/7035KB3.406秒/65036KB38.31秒/644434KB
やっぱりデータ量が多くなってくると汎用ソートとの処理時間の差が顕著。
SuffixArrayの構築に必要なメモリは、std::sort関数を用いた場合が一番少なく「入力データ分 + SuffixArray分(対象データ x sizeof(int))」のバイト数となっている。
SA-ISアルゴリズムの場合は、構築時にさらに余分な領域が必要になるが、(論文の実装の場合は)一割程度の増分で済んでいる。

メモリ使用量

今回作成したsais-0.0.1でのメモリ使用量の概略。

  • 1) 入力データ用のメモリ
  • 2) SuffixArray用のメモリ: 入力データサイズ x sizeof(int) バイト
    • この領域はinduced-sortで使用するバケツの領域としても利用される
    • SA-ISの再帰的な呼び出し時には、一つ上のレベルのSuffixArray用のメモリ領域が共有されるため追加で確保されることはない
  • 3) 入力データの各文字(or suffix)のタイプを保持する配列用のメモリ: 入力データサイズ x 1 ビット
    • SA-ISの(再帰)呼び出しのたびに、新たに確保
  • 4) induced-sort時に用いる各文字用のバケツのインデックスを保持する配列用のメモリ: (入力データ中の最大要素の値+1) x 3xsizeof(unsigned) バイト
    • SA-ISの(再帰)呼び出しのたびに、新たに確保

この内で3と4は、SA-ISの再帰的呼び出しの回数とその際の入力データによって変動する。
SA-IS再帰呼び出しの際の入力データのサイズは、一つ上のレベルでのそれの半分以下となることが保証されているので、3用のメモリ使用量は多くても、入力データサイズ*2 ビット == 入力データサイズ/4 バイト、となる(おそらく)

4の方は、一番最初の(もともとの入力データに対する)SA-IS呼び出し時には、256 x 12 バイト*2 *3、必要となる。そして残りの各SA-IS再帰呼び出しでは最大で、入力データサイズ x 12 バイト*4、の領域が消費されるので、最悪の場合の使用メモリ量はだいたい、(100 + 入力データサイズ) x 12 バイト、となる(おそらく)


論文にある実装では、よりメモリ使用量が少ないので、もっと節約できる箇所がある*5のだろうけど、特に差し迫って何かに使いたいということもないので、当面は改良の予定はなし。

計時プログラム

計時に用いたプログラムのソースコード


汎用ソート用:
※ util.hhファイルに関してはsais-0.0.1を参照

/***
 * ファイル名: sa-sort.cc
 * コンパイル: g++ -O3 -o sa-sort sa-sort.cc
 * 使用方法: sa-sort <対象ファイル> 
 */
#include <iostream>
#include <algorithm>
#include <cstring>
#include "util.hh"

struct SAcmp {
  SAcmp(const char* s) : s(s) {}

  bool operator()(const int i1, const int i2) const {
    return strcmp(s+i1, s+i2) < 0;
  }

  const char* s;
};

void sa_sort(const char* s, unsigned length, int* sa) {
  for(unsigned i=0; i < length; i++)
    sa[i] = i;
  
  SAcmp cmp(s);
  std::sort(sa, sa+length, cmp);
}

int main(int argc, char** argv) {
  if(argc != 2) {
    std::cerr << "Usage: sa-sort FILEPATH" << std::endl;
    return 1;
  }
  
  double beg_t = gettime();
  FileData fd(argv[1]);
  if(!fd) {
    std::cerr << "Can't open file: " << argv[1] << std::endl;
    return 1;
  }
  std::cerr << "Read file data:\t\t took " << gettime()-beg_t << " sec" << std::endl;
  
  beg_t = gettime();
  const char* text = fd.c_str();
  int* sa = new int[fd.size()+1];
  sa_sort(text, fd.size()+1, sa);
  std::cerr << "Construct Suffix-Array:\t took " << gettime()-beg_t << " sec" << std::endl;

  beg_t = gettime();
  for(unsigned i=1; i <= fd.size(); i++)
    std::cout << sa[i] << std::endl;
  std::cerr << "Print SA elements:\t took " << gettime()-beg_t << " sec" << std::endl;
  
  return 0;
}


SA-IS(論文の実装):

/***
 * ファイル名: sais-orig.cc
 * コンパイル: g++ -O3 -o sais-orig sais-orig.cc
 * 使用方法: sais-orig <対象ファイル> 
 */

#include <iostream>
#include <cstdlib>
#include "util.hh"

// ※ 'sais-orig.hh'の中身は『Two Efficient Algorithms for Linear Suffix Array Construction』に載っているC++のソースコード
#include "sais-orig.hh"

int main(int argc, char** argv) {
  if(argc != 2) {
    std::cerr << "Usage: sa FILEPATH" << std::endl;
    return 1;
  }
  
  double beg_t = gettime();
  FileData fd(argv[1]);
  if(!fd) {
    std::cerr << "Can't open file: " << argv[1] << std::endl;
    return 1;
  }
  std::cerr << "Read file data:\t\t took " << gettime()-beg_t << " sec" << std::endl;
  
  beg_t = gettime();
  const char* text = fd.c_str();
  int* SA = new int[fd.size()+1];
  SA_IS((unsigned char*)text, SA, fd.size()+1, 0x100, sizeof(char));
  std::cerr << "Construct Suffix-Array:\t took " << gettime()-beg_t << " sec" << std::endl;

  beg_t = gettime();
  for(unsigned i=1; i <= fd.size(); i++)
    std::cout << SA[i] << std::endl;
  std::cerr << "Print SA elements:\t took " << gettime()-beg_t << " sec" << std::endl;
  
  return 0;
}

*1:処理終了までの時間が長すぎるため

*2:'256'は、char型で表現可能な文字の数

*3:2010/12/25: コメントにて指摘を受けたため修正。もともとは「256 x 3バイト」と記載していたが掛けるバイト数は、3 x sizeof(unsigned)バイト == 12バイト、が正しい。

*4:SA-ISの再帰呼び出し時には、一つ上のレベルの各LMS部分文字列(の最初の要素)の先頭からの順番(ソート順)が、入力として用いられる。そのため新たな入力データ中の要素の最大の値は'入力データサイズ-1'(添字の最大値)となる※ 簡略化し過ぎで若干不正確だけど、大きくは間違ってはいない

*5:バケツの表現方法に工夫がある?