« New Linear SACAs: IS and DS | トップページ | IS法 その2 »

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へつづく・・・?

|

« New Linear SACAs: IS and DS | トップページ | IS法 その2 »

コメント

コメントを書く



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


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



トラックバック

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

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

« New Linear SACAs: IS and DS | トップページ | IS法 その2 »