white page

とつぜんですが、ここのmemoはココログへ移転しました。あと、libdivsufsortはGoogle codeの方へ移転中です。

• http://wpage.cocolog-nifty.com/wp/
• http://code.google.com/p/libdivsufsort/

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

• Ge Nong, Sen Zhang and Wai Hong Chan, Two Efficient Algorithms for Linear Suffix Array Construction, 2008?.
  [.pdf (http://www.cs.sysu.edu.cn)]

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

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

こっそり更新・・。さて、ようやく新しい 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