現在の最先端のサフィックスアレイ構築アルゴリズムは何ですか？

Question

私は高速のsuffix-arrayの構築アルゴリズムを探しています。私は実装の容易さと素早い速度に懐疑的な複雑さよりも興味があります（サフィックス配列はO（n）時間にサフィックスツリーを使って構築できますが、それには多くのスペースが必要です。 bad-worst-case big-Oの複雑さですが、実際にはかなり高速に実行されます）。とにかく自分の目的のために必要なので、私は副産物としてLCP配列を生成するアルゴリズムは気にしません。

taxonomy of various suffix array construction algorithmsが見つかりましたが、期限が切れています。私はSA-IS、qsufsort、およびBPRについて聞いたことがありますが、私はそれらがお互いにどう比較されているのか、より良いアルゴリズムがあるのか​​本当に分かりません。サフィックス配列のフィールドがどれほど熱くなっているかを考えると、他のアルゴリズムが公開されて以来そのアルゴリズムに取って代わっていると思います。私は「スプリット」と呼ばれる高速アルゴリズムを記述した論文を思い出しているように思いますが、私の人生のためには今見つけられません。

だから、現在の状態は何ですか？理想的には、現時点でのベスト・アルゴリズムのリスト（可能であれば、リンクあり）とその相対的な長所と短所の概要をお伝えしたいと思います。

Answer 1

現在、最良のSuffix-Arrayコンストラクタ知らLibDivSufSortは雄太森で、次のとおりです。 http://code.google.com/p/libdivsufsort/

それが誘発ソート方法（基本的には、「A *」で始まるすべての文字列をソートした後、あなたは「BA *を」文字列のソーティングを誘導することができる「CA *」「DAを使用しています*等）

それはeffiのためにどこでも賞賛されています退化した症例の効率および良好な取扱い。また、最も高速で、最適なメモリ量（5N）を使用します。ライセンスは邪魔にならないので、このアルゴリズムはIlya Grebnovによるlibbsc圧縮ライブラリなどの他のいくつかのプログラムに統合されています。比較のために http://libbsc.com/default.aspx

、このページにリンクされ接尾辞配列の圧縮ベンチマークを見つける： http://code.google.com/p/libdivsufsort/wiki/SACA_Benchmarks と、このページ http://homepage3.nifty.com/wpage/benchmark/index.html

ベンチマークは、他の多くの価値があるSACAの実装を示しています。 しかし、ライセンスと効率の両方の理由から、私はそれらの中でlibdivsufsortをお勧めします。

編集：明らかに、MSufsortはすぐにバージョン4に向かっていると言われ、Divsufsortよりもかなり速くなるはずです。それが正しいとすれば、それは新しいSACAチャンピオンになるでしょう。しかしまだ、リリース日はまだありません。これはアルファ版です。したがって、実績のある実装が必要な場合は、libdivsufsortが最良の選択です。

これらの「最良のSACA実装」では、「1つの構築アルゴリズム」は使用されず、複数の最適化トリックが組み合わされて集計が困難になることにも注意してください。

Answer 2

あなたはで見ることができる：接尾辞配列と圧縮接尾辞配列 Rグロッシ上

クイックツアー - 2011

おそらく新しい接尾辞配列アルゴリズムは、もはやペースで開発されている理論計算機科学、あなたは想像しています。最先端を行くには、suffiix配列と一緒に使用されるデータ構造を見て、接尾辞配列関連の数学についての論文を見てください：Schürmann、Munro、He等

Answer 3

http://code.google.com/p/libdivsufsort/source/browse/wiki/SACA_Benchmarks.wikiは、必要な最速アルゴリズムのリストを提供します。

kvarkの実装は、上記ベンチマークのほとんどのケースで最も高速です。コードはhttp://www.kvatom.com/archonにあります。

libdivsufsortは、ITのアルゴリズムと誘導ソートの後処理の組み合わせです。サフィックスのサブセットは、誘導ソートアルゴリズムと同様に選択されますが、誘導ソートによって再帰的に解決するのではなく、ITのアルゴリズムによってソートされます。

libdivsufsortとkvarkの実装はどちらもITのアルゴリズムに基づいています。

KAのアルゴリズムは、99に現れるITのアルゴリズムに似ています。接尾辞は、タイプSまたはタイプLの2つのカテゴリに分割されます.i番目の接尾辞が（i + 1）接尾辞、それはタイプSです。それ以外の場合はL型です。すべてのタイプS接尾辞をソートした後、すべてのタイプL接尾辞の順序を推論することができます。

KAのアルゴリズムとITのアルゴリズムの違いは、KAは再帰を使用して部分文字列をソートし、ITのアルゴリズムはマルチキークイックソート/ MSD /挿入ソートに訴えます。