41

高速な接尾辞配列構築アルゴリズムを探しています。私は、漸近的な複雑さよりも、実装の容易さと生の速度に関心があります (O(n) 時間で接尾辞ツリーを使用して接尾辞配列を構築できることは知っていますが、それには多くのスペースが必要です。明らかに他のアルゴリズムには悪い最悪の場合の Big-O の複雑さですが、実際には非常に高速に実行されます)。副産物として LCP 配列を生成するアルゴリズムは気にしません。自分の目的のためにとにかく必要だからです。

さまざまなサフィックス配列構築アルゴリズムの分類法を見つけましたが、古くなっています。SA-IS、qsufsort、およびBPRについて聞いたことがありますが、それらが互いにどのように比較されるか、さらに優れたアルゴリズムがあるかどうかはよくわかりません。suffix-array フィールドが現在どれほど注目されているかを考えると、他のアルゴリズムが公開されて以来、それらに取って代わっていると思います。「分割」と呼ばれる高速なアルゴリズムを記述した論文に出くわしたことを思い出すようですが、今では一生見つけることができません。

では、現在の最先端技術はどのようなものでしょうか。理想的には、現在の最良のアルゴリズムの短いリスト (可能であればリンク付き) と、それらの相対的な長所と短所の概要を示してください。

4

3 に答える 3

43

現在知られている最適な Suffix-Array コンストラクターは、森裕太による LibDivSufSort です: http://code.google.com/p/libdivsufsort/

Induced Sorting 手法を使用します (基本的に、「A*」で始まるすべての文字列を並べ替えた後、文字列「BA*」「CA*」「DA*」などの並べ替えを誘導できます)。

その効率性と劣化したケースの優れた処理は、どこでも称賛されています。また、最速であり、最適な量のメモリ (5N) を使用します。ライセンスは目立たないため、このアルゴリズムは、Ilya Grebnov による libbsc 圧縮ライブラリなど、他のいくつかのプログラムに統合されています。 http://libbsc.com/default.aspx

比較のために、このページにリンクされている Suffix Array Compression ベンチマークを見つけることができます: 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 つの構築アルゴリズム」を使用するのではなく、いくつかの最適化のトリックを組み合わせているため、要約が難しくなっていることに注意してください。

于 2011-10-26T15:28:43.710 に答える
10

https://github.com/y-256/libdivsufsort/blob/wiki/SACA_Benchmarks.mdは、必要な最速のアルゴリズムのリストを提供します。

kvark の実装は、ほとんどの場合、上記のベンチマークで最速です。コードはhttps://github.com/kvark/dark-archonにあります。

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

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

Ko-Aluru のアルゴリズムは、99 に登場する IT のアルゴリズムに似ています。どちらも接尾辞をタイプ S またはタイプ L の 2 つのカテゴリに分けます。i 番目の接尾辞が (i+1) 番目の接尾辞よりも小さい場合、それはタイプ S です。それ以外の場合は L 型です。すべての S 型接尾辞を並べ替えた後、すべての L 型接尾辞の順序を推測できれば完了です。

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

于 2012-11-04T03:32:06.993 に答える
2

あなたは見ることができます：

サフィックス配列と圧縮サフィックス配列のクイック ツアー R Grossi - Theoretical Computer Science、2011

おそらく、新しい接尾辞配列アルゴリズムは、もはやあなたが想像するペースで開発されていません。最先端にいるために、接尾辞配列と一緒に使用されるデータ構造を調べ、接尾辞配列関連の数学に関する論文を見ることをお勧めします: Schürmann、Munro、He など

于 2011-10-25T00:55:57.367 に答える