cyclic suffix array

cyclic-sais-1.0を公開〜。cyclic stringのsuffix arrayを構築できるsaisです。終端記号'$'を使用しない接尾辞?ソートといった方がわかりやすいかな。これでBW変換を行うと、オリジナルのBWT(BW94)やbzip2のソートとほぼ同じ結果が得られます。

File: cyclic-sais-1.0.zip
Size: 12,090 bytes
 MD5: acd653afbe8b6b6bf1a47f1787926f7d
SHA1: 5fb5bc7eabb04ffd157538f763e32bf84054a510

一応、bzip2-1.0.6のソートをcyclic-saisへ変更できるパッチが入っています。適用(blocksort.cとcyclic-sais.[c,h]をbzip2のフォルダへコピー)すると、ソート処理が入力されるデータによっては極端に遅くなる…などということは無くなりますが、通常のデータに対してはあまり効果がなかったり、逆に少し遅くなったりもするのでご注意を。

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

sais-java & C#

ようやく、saisのJava版を更新しました。LMSsort2などは面倒なので実装していませんが、以前のバージョンよりは速くなっています。それとついでにC#版も公開。C#のコードを書いたのは初めてなので色々と適当なところはありますが、一応ちゃんと動作はするはず。

File: SAIS-CSharp.zip
Size: 29,875 bytes
SHA1: e1d52fb74c8551cb2881fc2ff3d92ad19a86db22
File: sais-java.zip
Size: 19,603 bytes
SHA1: 79828ab134408a8b414aa517a1885cebf43418fe

接尾辞配列の構築にかかる時間は、Windows上ではJavaよりC#の方がほんの少し速いです。まあどちらもC/C++と比べると倍近く遅いわけですが…。

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

sais-2.4.1

この間更新したばかりですが、新しいsais-2.4.1とsais-lite-2.4.1を公開しました。今回の変更点は、バグ修正・examplesのLFS対応・CMake周りの修正です。ついでに向こうのサイトも更新〜。

File: sais-lite-2.4.1.zip
Size: 17,097 bytes
SHA1: b3b7396da40022ed7dd7c19ffba81587020750c2
File: sais-2.4.1.zip
Size: 46,304 bytes
SHA1: cccf8d8bd18a893c58527d16ce6613923e22b411

これで暫くは更新しないと思います。Java版は…まあそのうちってことで。

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

sais-2.4.0

新しいsaisのcmake版を公開〜。むこうは8月中には更新したいのぅ。

File: sais-2.4.0.zip
Size: 45,671 bytes
SHA1: e0e5ad859c7a4936bcd454dc5e3142de92eaaeb7

続きを読む "sais-2.4.0"

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

sais-lite-2.4.0

sais-lite-2.4.0をこっそり公開〜。バグが無ければ向こうのもそのうち更新します。

File: sais-lite-2.4.0.zip
Size: 17,096 bytes
SHA1: 7b7677b02ca9e65bac8b8295c35bf387856814ff

今回はstage1の処理などを大幅に書き変えたので、接尾辞配列の構築にかかる時間が少し短縮されています。 あと、ほとんど意味の無かったOpenMP関連のコードを削除しました。parallel suffix sortingにはdcsを使った方が良さげ。

続きを読む "sais-lite-2.4.0"

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

libdcs

Wafというビルドシステムを試すついでに、かなり前のDifference Cover法のコードを書き直したのでちょっとだけ公開してみる。今回も適当に書いたものなのでバグがあると思います…。

追記: READMEやINSTALLを入れ忘れたが…まあいいか

File: libdcs-0.0.1.zip
Size: 126,129 bytes
SHA1: fd261e36be48e0ebe582e20cd9bc80cf9ab46c62

他のSACAsとは違い、DC法なら任意のインデックスポイントからなる接尾辞配列を少ないメモリで構築可能なので意外と便利だったりします。例えば、UTF-8の先頭オクテットの位置や行頭の位置を事前に用意して、それらを接尾辞ソート…なんてこともできたりする。

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

IS法 その5

saisとsais-liteを更新。BWTとOpenMP用のコードを追加しました。これでマルチCPUやマルチコアCPUを搭載したマシンならSuffix arrayの構築時間が少し短縮できる・・かもしれません。

CMake version

File: sais-lite.zip
Size: 13,154 bytes
SHA1: 904f22769fbc974f6b49c9f38d0cb38b9091cb89

CMake version

File: sais.zip
Size: 26,620 bytes
SHA1: c21bc6f1d3ece5485fb05604ca4bfaee388a73ab

あと、Java言語版を作ってみました。さすがにC言語版より遅いけど、とりあえずちゃんと動作します。

Java language version

File: sais-java.zip
Size: 9,955 bytes
SHA1: b5b88324eabf5f308abd5704309ce981c5bc081f

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

TXTCache

なにやらTXTCacheというJava言語で書かれた圧縮インデックスライブラリがリリースされている。中身は・・、Pizza&Chili Corpusのソースコードを移植したものみたいですね。

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

2.0.0

libdivsufsort-2.0.0 とその簡易版 libdivsufsort-lite を公開しました。

version 1.2.3 からの変更点は以下のとおりです。

  • ベースを itssort_0080412 に変更。
    • 一部OpenMPに対応。
    • 常に先頭に配置される終端記号のインデックスを Suffixarray から除外。
  • 64ビットのインデックスに対応。(CMakeのみ)
  • 性能がほんの少し向上。
 
File: libdivsufsort-2.0.0.tar.bz2
Size: 252,912 bytes
SHA1: 168bac570726619409d05814ac1c9ab14a248dc4
 
File: libdivsufsort-lite.zip
Size:  21,348 bytes
SHA1: 6068f9571a9b15831082b8dccfc005cee7b47956

2.0.0は、SVNのものと違って configure などのファイルも含まれているので、CMakeが無い環境でもビルドは可能です。簡易版は、ライブラリのビルドが面倒な人向けのパッケージです。divsufsort.cと.hをそのままコピーして使っちゃって下さい。

追記: divbwtのバグと ChangeLog を修正するのを忘れてました・・。そのうち直します。

追記そのに: こっそり修正しました。

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

IS法 その4

そろそろ改良できる箇所が少なくなってきたと思うので、ソースコードを全面的に(といっても100行程度だけど・・)書き直して、プロジェクト名を「sais」に変更しました。 サイス・・古代エジプトの都市の名前だっけ?  他の変更点は、配列SAの未使用領域をなるべくバケット配列として利用させるようにしました。これで少しメモリ使用量が削減されます。あとは・・C++版の追加くらいかな。

CMake versionは少し複雑になってきたので、シンプルな GNU Make versionを作ってみました。

File: sais-lite.zip
Size: 13,154 bytes
SHA1: 904f22769fbc974f6b49c9f38d0cb38b9091cb89
Last update: 2008/12/25

CMake version

File: sais.zip
Size: 26,620 bytes
SHA1: c21bc6f1d3ece5485fb05604ca4bfaee388a73ab
Last update: 2008/12/25

Java language version

File: sais-java.zip
Size: 9,955 bytes
SHA1: b5b88324eabf5f308abd5704309ce981c5bc081f
Last update: 2009/01/10

追記 (2008/07/14): Makefile と suftest.c の誤りを修正。

追記 (2009/01/10): BWTとOpenMP用のコードを追加。Java言語版を追加。

IS1-3 & SAISなどの Suffix array 構築時間を測定した結果が以下になります。

  • DC - Difference-cover algorithm (v = 32)
  • DS - Deep-Shallow sorting algorithm
  • IS1 - ほぼオリジナルと同じ NZC Induced sorting algorithm
  • IS2 - 配列tを排除したIS法
  • IS3 - IS2のincudeSAを改良したIS法
  • SAIS - 今回のIS法
  • KA - Ko-Aluru algorithm
  • LS - Larsson-Sadakane algorithm
Time (in secs)
FilesSize DC DS IS1 IS2 IS3 SAIS KA LS
totals968,063,446 722.19 846.89 426.18 347.94 263.93 257.80 527.85 510.05
chr22.dna34,553,758 19.98 7.06 14.62 12.62 10.87 10.68 17.32 9.35
etext99105,277,340 73.08 32.45 62.05 48.96 39.54 38.26 74.75 51.50
gcc-3.0.tar86,630,400 54.96 34.14 32.06 26.76 20.77 20.31 41.65 36.80
howto39,422,105 22.64 7.82 16.47 13.81 11.27 11.08 21.03 14.81
jdk13c69,728,899 56.08 28.08 26.58 22.66 16.06 15.83 34.48 35.73
linux-2.4.5.tar116,254,720 74.18 24.24 45.51 37.62 29.69 28.88 59.60 49.05
rctail96114,711,151 110.30 56.05 57.23 46.19 33.13 32.52 70.84 63.63
rfc116,421,901 82.44 27.98 53.49 42.14 32.29 31.51 65.47 55.85
sprot34.dat109,617,186 85.72 29.69 57.52 45.21 34.25 33.19 69.04 51.63
w3c2104,201,579 81.75 48.62 40.88 34.68 25.01 24.57 53.34 70.90
abac200,000 0.06 26.48 0.01 0.00 0.00 0.00 0.02 0.02
abba10,500,600 9.89 29.51 2.47 2.25 1.39 1.38 2.51 12.48
book1x2015,375,420 13.07 95.35 6.03 5.53 3.84 3.79 7.44 18.68
fib_s1493035214,930,352 16.18 177.07 5.28 4.31 2.51 2.50 3.88 16.23
fss1012,078,908 13.45 82.75 3.94 3.53 2.02 1.98 3.53 13.06
fss92,851,443 1.44 4.82 0.44 0.38 0.28 0.28 0.58 2.50
houston3,840,000 1.81 114.11 0.30 0.22 0.18 0.18 0.50 1.08
paper5x80981,924 0.38 0.62 0.10 0.08 0.07 0.07 0.17 0.36
test12,097,152 0.94 8.06 0.24 0.18 0.15 0.16 0.33 2.04
test22,097,152 0.94 8.07 0.24 0.21 0.16 0.16 0.32 2.06
test32,097,152 1.02 1.34 0.23 0.20 0.14 0.16 0.39 0.77
test42,097,152 1.02 1.59 0.26 0.22 0.16 0.17 0.39 0.77
test52,097,152 0.86 0.99 0.23 0.18 0.15 0.14 0.27 0.75

構築にかかる時間は多少短くなっていますが・・、今までのような劇的な改善は難しいですねえ。

さて、今回はIS法のメモリ使用量がどれくらい改善したかを確認するために、memusage を使って各プログラムのピーク時のメモリ使用量を測定しました。結果は見ての通り。普通のデータなら、SAIS は Deep-Shallow よりもメモリ使用量が少なくすみます。しかし、最悪時のメモリ使用量は相変わらず 5n+max(2n,4k) bytes なので一長一短か。。

Space (in MiBytes)
FilesSize DC32 DS IS1 IS2 IS3 SAIS KA LS
totals968,063,446 5,423.92 4,630.57 4,890.55 4,691.51 4,691.51 4,616.34 8,226.06 7,385.76
mean- 5.88 5.02 5.30 5.08 5.08 5.00 8.91 8.00
chr22.dna34,553,758 193.60 165.18 178.09 170.40 170.40 164.77 289.97 263.62
etext99105,277,340 589.85 503.23 542.17 514.65 514.65 502.00 907.34 803.20
gcc-3.0.tar86,630,400 485.38 415.87 438.44 420.14 420.14 413.09 709.50 660.94
howto39,422,105 220.88 188.45 203.16 193.03 193.03 187.98 331.54 300.77
jdk13c69,728,899 390.68 333.40 347.01 334.57 334.57 332.49 609.71 531.99
linux-2.4.5.tar116,254,720 651.36 555.76 590.55 565.98 565.98 554.35 977.81 886.95
rctail96114,711,151 642.71 548.32 575.46 553.45 553.45 546.99 1,004.98 875.18
rfc116,421,901 652.29 556.53 588.69 564.35 564.35 555.14 956.52 888.23
sprot34.dat109,617,186 614.17 524.03 554.58 534.37 534.37 522.70 930.06 836.31
w3c2104,201,579 583.82 498.09 519.41 500.36 500.36 496.87 912.00 795.00
abac200,000 1.12 0.98 0.99 0.95 0.95 0.95 1.75 1.53
abba10,500,600 58.83 50.21 51.83 50.09 50.09 50.07 86.20 80.11
book1x2015,375,420 86.15 73.52 76.23 73.51 73.51 73.32 132.42 117.31
fib_s1493035214,930,352 83.65 71.71 74.07 71.19 71.19 71.19 117.16 113.91
fss1012,078,908 67.68 58.05 59.86 57.60 57.60 57.60 107.05 92.16
fss92,851,443 15.98 13.71 14.13 13.60 13.60 13.60 25.27 21.76
houston3,840,000 21.52 18.46 18.88 18.33 18.33 18.31 28.79 29.30
paper5x80981,924 5.50 4.72 4.85 4.69 4.69 4.68 8.59 7.49
test12,097,152 11.75 10.10 10.38 10.00 10.00 10.00 18.34 16.00
test22,097,152 11.75 10.10 10.38 10.00 10.00 10.00 18.34 16.00
test32,097,152 11.75 10.05 10.50 10.12 10.12 10.12 18.34 16.00
test42,097,152 11.75 10.05 10.50 10.12 10.12 10.12 18.34 16.00
test52,097,152 11.75 10.05 10.39 10.01 10.01 10.00 16.04 16.00

とりあえず、IS法の改良はこれにて終了。しばらくは更新しないと思います。

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

より以前の記事一覧