« IS法 その1 | トップページ | IS法 その3 »

IS法 その2

さて今回は、IS法のほぼ全体で使用されている配列tを排除してみた。これは、それぞれのサフィックスのタイプを O(1) time で求めるのに使われているのだが、そのほとんどは配列sで置換が可能である。例えば、 induceSAl と induceSAs は以下のように変更できる。

 // compute SAl
-static void induceSAl(const unsigned char *t, int *SA, const unsigned char *s, int *bkt,
+static void induceSAl(int *SA, const unsigned char *s, int *bkt,
                       int n, int K, int cs, bool end) {
   int i, j;
   getBuckets(s, bkt, n, K, cs, end); // find starts of buckets
   SA[bkt[chr(n-1)]++]=n-1;
   for(i=0; i<n; i++) {
     j=SA[i]-1;
-    if(j>=0 && !tget(j)) SA[bkt[chr(j)]++]=j;
+    if(j>=0 && chr(j)>=chr(j+1)) SA[bkt[chr(j)]++]=j;
   }
}
// compute SAs
-static void induceSAs(const unsigned char *t, int *SA, const unsigned char *s, int *bkt,
+static void induceSAs(int *SA, const unsigned char *s, int *bkt,
                       int n, int K, int cs, bool end) {
   int i, j;
   getBuckets(s, bkt, n, K, cs, end); // find ends of buckets
   for(i=n-1; i>=0; i--) {
     j=SA[i]-1;
-    if(j>=0 && tget(j)) SA[--bkt[chr(j)]]=j;
+    if(j>=0 && chr(j)<=chr(j+1)) SA[--bkt[chr(j)]]=j;
   }
}

あと、二つの LMS-substring を比較する箇所ですが、これはあらかじめ全ての LMS-substring の長さを順位が格納されるところに保存しておいて、あとはその長さを使って比較を行うだけで良い。(is2.c の 71-86 lines)

上記以外にも多少いじってますが、詳しくはソースコードを読んでくだされ。

File: is2.zip
Size: 13,707 bytes
SHA1: 912bd1db943669aa798040b0e30cc1f97800f4d9

IS1とIS2を使って Suffix array の構築時間を測定した結果が以下になります。

  • DC - Difference-cover algorithm (v = 32)
  • DS - Deep-Shallow sorting algorithm
  • IS1 - ほぼオリジナルと同じ NZC Induced sorting algorithm
  • IS2 - 今回の改良したIS法
  • KA - Ko-Aluru algorithm
  • LS - Larsson-Sadakane algorithm
FilesDC DS IS1 IS2 KA LS
totals722.19 846.89 435.07 342.10 527.85 510.05
chr22.dna19.98 7.06 14.86 12.14 17.32 9.35
etext9973.08 32.45 62.81 47.80 74.75 51.50
gcc-3.0.tar54.96 34.14 32.98 26.56 41.65 36.80
howto22.64 7.82 16.76 13.58 21.03 14.81
jdk13c56.08 28.08 27.25 22.45 34.48 35.73
linux-2.4.5.tar74.18 24.24 46.56 37.09 59.60 49.05
rctail96110.30 56.05 58.40 45.51 70.84 63.63
rfc82.44 27.98 54.53 41.48 65.47 55.85
sprot34.dat85.72 29.69 58.44 44.35 69.04 51.63
w3c281.75 48.62 41.70 34.15 53.34 70.90
abac0.06 26.48 0.02 0.00 0.02 0.02
abba9.89 29.51 2.60 2.22 2.51 12.48
book1x2013.07 95.35 6.16 5.43 7.44 18.68
fib_s1493035216.18 177.07 5.56 4.24 3.88 16.23
fss1013.45 82.75 4.15 3.43 3.53 13.06
fss91.44 4.82 0.50 0.36 0.58 2.50
houston1.81 114.11 0.35 0.23 0.50 1.08
paper5x800.38 0.62 0.11 0.08 0.17 0.36
test10.94 8.06 0.25 0.19 0.33 2.04
test20.94 8.07 0.26 0.21 0.32 2.06
test31.02 1.34 0.26 0.20 0.39 0.77
test41.02 1.59 0.28 0.23 0.39 0.77
test50.86 0.99 0.28 0.17 0.27 0.75

IS1よりはほんの少し速いくらいのようですね。まあ今回はメモリ使用量の削減が目的なのでこんなものでしょうか。

ところで、CMakeっていいですねえ。Makefileだけじゃなく、VC++やCodeblocksのプロジェクトも簡単に生成できる。Autotools から移行しようか。。

|

« IS法 その1 | トップページ | IS法 その3 »

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/154471/41619481

この記事へのトラックバック一覧です: IS法 その2:

« IS法 その1 | トップページ | IS法 その3 »