white page

もう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)]

  File: blocksort.c.diff.gz
  Size: 16231 bytes
   MD5: cc5677ffec496c55bc0bfd91ea2f8788

こっそりと公開してみる。一応、簡単なテストはしたけど、まだバグがあるかもしれないのでご注意を・・。ちなみに、ソートアルゴリズムには、bzip2用のdivsufsort-1.2.1を使用しております。

追記: パッチファイルを少し修正しました。

libdivsufsort-1.2.1 をリリースしました。今回の変更点は、バグ修正と簡易検索機能の追加だけです。

links の Suffix Arrays に "In-Place Suffix Sorting" を追加しました。面白いアルゴリズムではあるけど、実装するのは非常に難しい・・。まあ出来てもあまり速くは無さそうだが。

• Gianni Francheschini and S. Muthukrishnan, In-Place Suffix Sorting, Proceedings of the 34th International Colloquium on Automata, Languages and Programming, 2007.
  [.pdf (www.cs.rutgers.edu)]