« 2008年4月 | トップページ | 2008年7月 »

IS法 その3

さて、今回はキャッシュ効率の改善のために induceSA を書き換えてみました。使用した方法は、itssort で用いられているものと基本的に同じです。

File: is3.zip
Size: 15,533 bytes
SHA1: 97d598e28651a6c5b5555ff405a0b530c0ae5b5e

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

  • DC - Difference-cover algorithm (v = 32)
  • DS - Deep-Shallow sorting algorithm
  • IS1 - ほぼオリジナルと同じ NZC Induced sorting algorithm
  • IS2 - 配列tを排除したIS法
  • IS3 - 今回の改良したIS法
  • KA - Ko-Aluru algorithm
  • LS - Larsson-Sadakane algorithm
FilesDCDSIS1IS2IS3KALS
totals722.19846.89435.07342.10266.99527.85510.05
chr22.dna19.987.0614.8612.1410.8317.329.35
etext9973.0832.4562.8147.8039.6374.7551.50
gcc-3.0.tar54.9634.1432.9826.5621.2141.6536.80
howto22.647.8216.7613.5811.4121.0314.81
jdk13c56.0828.0827.2522.4516.4334.4835.73
linux-2.4.5.tar74.1824.2446.5637.0930.0559.6049.05
rctail96110.3056.0558.4045.5133.5570.8463.63
rfc82.4427.9854.5341.4832.7665.4755.85
sprot34.dat85.7229.6958.4444.3534.5169.0451.63
w3c281.7548.6241.7034.1525.5053.3470.90
abac0.0626.480.020.000.000.020.02
abba9.8929.512.602.221.402.5112.48
book1x2013.0795.356.165.433.847.4418.68
fib_s1493035216.18177.075.564.242.553.8816.23
fss1013.4582.754.153.432.003.5313.06
fss91.444.820.500.360.280.582.50
houston1.81114.110.350.230.180.501.08
paper5x800.380.620.110.080.080.170.36
test10.948.060.250.190.150.332.04
test20.948.070.260.210.160.322.06
test31.021.340.260.200.150.390.77
test41.021.590.280.230.170.390.77
test50.860.990.280.170.150.270.75

普通のファイルでも Deep-Shallow sorting algorithm とほぼ互角なので、やっとそれなりの速度になったかな。しかし、上位のSACAにはまだ遠く及ばず・・。

| | コメント (0) | トラックバック (0)

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 から移行しようか。。

| | コメント (0) | トラックバック (0)

IS法 その1

IS法は非常にシンプルでそれなりに速いのだけど、論文のサンプルコードは s[n-1] 以外の場所に 0x00 が含まれているデータの接尾辞配列を構築することができない。(というか、s[n-1]が常にユニークでなければいけない)

もし、アルファベットサイズが256のデータを処理したいなら、入力文字列のデータタイプを unsigned char から int へ変更しないといけないわけだが、その場合メモリの消費量が 8n 以上になってしまう・・。というわけで、コードを少しいじって入力データに 0x00 が含まれていても処理できるようにしてみた。BWT/UnBWTがおまけとして入ってます。

File: is1.zip
Size: 11,402 bytes
SHA1: 153b4c3b35a30bea5d13113fde9f0183eb5ee1ef

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

  • DC - Difference-cover algorithm (v = 32)
  • DS - Deep-Shallow sorting algorithm
  • IS - NZC Induced sorting algorithm
  • KA - Ko-Aluru algorithm
  • LS - Larsson-Sadakane algorithm
FilesSize DC DS IS KA LS
totals968063446 722.66 846.87 434.59 526.96 508.98
chr22.dna34553758 19.97 7.07 14.82 17.25 9.4
etext99105277340 73.03 32.39 62.64 74.39 51.27
gcc-3.0.tar86630400 54.86 34.05 32.79 41.36 36.61
howto39422105 23.18 7.78 16.70 21.19 14.72
jdk13c69728899 56.03 28.03 27.14 34.68 35.56
linux-2.4.5.tar116254720 74.07 24.22 46.49 59.38 49.06
rctail96114711151 110.32 55.94 58.36 70.61 63.33
rfc116421901 82.52 27.98 54.51 65.34 55.77
sprot34.dat109617186 85.69 29.63 58.41 68.96 51.48
w3c2104201579 81.74 48.61 41.83 53.39 70.83
abac200000 0.06 26.48 0.02 0.01 0.02
abba10500600 9.89 29.53 2.61 2.51 12.48
book1x2015375420 13.10 95.40 6.19 7.45 18.7
fib_s1493035214930352 16.15 177.06 5.57 3.89 16.23
fss1012078908 13.45 82.89 4.16 3.54 13.08
fss92851443 1.45 4.84 0.51 0.59 2.51
houston3840000 1.82 114.28 0.35 0.51 1.08
paper5x80981924 0.38 0.62 0.12 0.18 0.37
test12097152 0.95 8.06 0.26 0.33 2.09
test22097152 1.05 8.07 0.27 0.33 2.10
test32097152 1.03 1.35 0.27 0.39 0.76
test42097152 1.06 1.60 0.29 0.40 0.77
test52097152 0.86 0.99 0.28 0.28 0.76

ISは、linear-algorithm なので DS のように特定のファイルで極端に遅くなったりはしないけど、キャッシュ効率があまり良くないため通常の(avg. lcp や max. lcp の低い)ファイルでは DS の倍程度の時間がかかるみたいですね。

その2へつづく・・・?

| | コメント (0) | トラックバック (0)

New Linear SACAs: IS and DS

まだdraftだけど、新しいSuffix Array構築法に関する論文が公開されています。

タイトル通り、Suffix Arrayを線形時間で構築できる新しい二つのアルゴリズムについて、サンプルコード付きで解説されています。どちらのアルゴリズムもKA法より高速に動作して、なおかつ extra working space が最悪の場合でもわずか? 2.25n + O(1) bytes となかなかの性能のようです。

それにしてもIS法はすごいなぁ。(L)S-substringのソートをここまでコンパクトにするとは。。

| | コメント (0) | トラックバック (0)

« 2008年4月 | トップページ | 2008年7月 »