white page

こっそり更新・・。さて、ようやく新しい itssort が完成したので公開しました。これで特に問題がなければ、次のバージョンの divsufsort (たぶん1.4.0) に適用されるでしょう。

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

• ライセンスを GNU Lesser General Public License から MIT/X11 License に変更。
• サンプルプログラム bwt と unbwt の追加。
• OpenMP用コードの追加。
• construct_SA と construct_BWT の最適化。
• 常に先頭に配置される終端記号のインデックスを Suffixarray から除外。
• qsortを簡単なMultikey Quicksortに置換。

File: itssort_0080412.tar.gz
Size: 13,603 bytes
 MD5: d512939ce50af8494440274c9221ad39

--------------------

links を更新。(ページの構築に使用しているスクリプトを変更したので、ちょっとだけ見た目が変わりました。) DCCで、新しい Linear-time SACA が2つほど出てましたねえ。 2分割 + Shannon-Fano-Elias符号 と KA法 + KS法 かぁ。。

久々に SACA のベンチマークを更新。 Core 2 Duo の結果を追加しました。

テストに使用したファイルの合計サイズは 約 1.2 Gb なのですが、上位 3 つのプログラムは 3 ～ 5 分くらいで処理できてしまうようですね。。もうこれ以上の高速化はあまり意味がないのかもしれません。

divsufsortxx-r3 を公開しました。今回の変更点は以下のとおりです。

• STL の vector が使用できない問題を修正。
• 4つのBW逆変換アルゴリズムを実装。 .. PSI, LF, MergedTLF, コンパクトなLF(3.65n)

File: divsufsortxx-r3.zip
Size: 30,836 bytes
 MD5: ed22b7a13dd64d6a51e98784b858446e

もう1月末ですが。。。あけましておめでとうございます。

さて、今回はサフィックスソートアルゴリズムのテスト用ファイルを新たに2つほど作ってみました。 test4.bz2, test5.bz2, generator2.c.bz2

Thinkpad X31 (Pentium M) での結果は以下のとおりです。相変わらず、linear/loglinear系のアルゴリズムは結果が安定してます。MSufSort-3.1.1b と Archon4r0 は test4 が少し苦手なようですね。

                              Running times (in sec)
Programs             test1     test2     test3     test4     test5    totals
-------           --------  --------  --------  --------  --------  --------
Archon4r0            3.940     8.498     6.393    19.740    11.096    49.667
BPR                  6.541     1.871   810.399     2.496   128.451   949.758
DC32                 7.094     7.238     8.216     8.066     5.794    36.408
Deep-Shallow        20.363    20.337    11.370    12.314     8.594    72.979
KA                   2.261     2.249     1.955     1.945     0.923     9.334
KS                   5.017     5.053     5.051     5.111     2.910    23.143
MSufSort-3.1.1b      2.614     6.083     2.412    78.244     7.409    96.761
qsufsort             7.571     7.769     9.742     9.524     9.295    43.901

--------------------

そしてようやく新しいPCを買ったので、その結果も一応のせてみる。スペックは CPU: Intel Core 2 Duo E6750、Phys. Memory: 2048MB です。

                              Running times (in sec)
Programs             test1     test2     test3     test4     test5    totals
-------           --------  --------  --------  --------  --------  --------
Archon4r0            0.316     0.628     0.481     1.609     0.925     3.959
BPR                  1.931     0.587   169.828     0.737    26.881   199.965
DC32                 1.228     1.187     1.275     1.275     1.072     6.037
Deep-Shallow         8.469     8.459     1.316     1.569     0.978    20.791
KA                   0.350     0.322     0.409     0.381     0.262     1.725
KS                   1.072     1.078     1.097     1.097     0.722     5.066
MSufSort-3.1.1b      1.325     3.375     0.925    33.325     3.231    42.181
qsufsort             2.375     2.381     2.856     2.872     2.503    12.988

Suffix array を構築するためのライブラリ divsufsort の C++ 版を公開しました。テンプレートになっているので、libdivsufsortよりは使いやすいかもしれません。

  File: divsufsortxx-r1.zip
  Size: 17,462 bytes
   MD5: b762a9552ac869a30181952637975559

--------------------

links を更新。"Move-to-Front, ..." の二つ目のpdfはスライドです。

• Burrows-Wheeler Transform:
  • Peter Fenwick, Burrows-Wheeler compression : Principles and reflections, Theoretical Computer Science, 387, pp. 200-219, 2007.
    [.pdf (www.cs.auckland.ac.nz)]
  • Travis Gagie and Giovanni Manzini, Move-to-Front, Distance Coding, and Inversion Frequencies Revisited, Proceedings of the 18th Symposium on Combinatorial Pattern Matching, LNCS 4580, Springer-Verlag, pp. 71-82, 2007.
    [.pdf (www.mfn.unipmn.it)] [.pdf (www.csd.uwo.ca)]
  • Haim Kaplan and Elad Verbin, Most Burrows-Wheeler Based Compressors are Not Optimal, Proceedings of the 18th Annual Symposium on Combinatorial Pattern Matching, LNCS 4580, Springer-Verlag, pp. 107-118, 2007.
    [.ps (www.math.tau.ac.il)] [.ps (www.cs.tau.ac.il)]
• Suffix Arrays:
  • Klaus-Bernd Schurmann, Suffix Arrays in Theory and Practice, 2007.
    [.pdf (bieson.ub.uni-bielefeld.de)]