2

密接に関連する 2 つのデータ構造は、接尾辞ツリーと接尾辞配列です。私が読んだことによると、サフィックス ツリーは、サフィックス配列よりも高速で、強力で、柔軟性があり、メモリ効率も優れています。ただし、この以前の質問では、サフィックス配列が実際にはより広く使用されているとの回答が最も多くありました。私はこれらの構造のいずれも使用した経験がありませんが、現在のところ、提供される機能 (高速な部分文字列チェックなど) が必要な問題については、常に接尾辞配列よりも接尾辞ツリーを好むようです。

接尾辞ツリーよりも接尾辞配列の方が適しているのはどのような場合ですか?

（ちなみに、この質問は私がリンクしたものに関連していますが、接尾辞配列と接尾辞ツリーの比較にのみ興味があり、試行を完全に除外しているため、正確な重複ではないと思います. ただし、同意しない場合は、この質問を終了するかどうかは理解できます。)

4

2 に答える 2

3

http://www.youtube.com/watch?v=1DGZxd-PP7Uからの引用

Suffix Arrays と Suffix Trees は以前は異なっていました。しかし最近では、サフィックス配列はサフィックス ツリーを実装する方法にすぎません (またはその逆)。参照: キム、キム、およびパーク。線形化されたサフィックス ツリー: サフィックス ツリーとサフィックス配列の機能を備えた効率的なインデックス データ構造。アルゴリズム、2007年。

キムらの論文はよく書かれており、アクセスしやすく、アボエルホーダらによるものなど、他の重要な論文への参照があります。

于 2011-08-21T18:00:11.853 に答える
2

ほとんどの場合、サフィックス配列が推奨されますが、次の場合を除きます。

  • 少量のデータのインデックスを作成する場合。
  • タンパク質の一致や DNA の突然変異に関する研究を行っていて、非常に高価なコンピューターにアクセスできる場合。
  • どうしても必要な場合は、ワイルドカードを使用したエラー検索を使用してください。

サフィックス配列を使用して、サフィックス ツリーを実装できます。つまり、サフィックス ツリーは、サフィックス アレイと、サフィックス ツリーの機能をシミュレートするためのいくつかの追加データ構造にすることができます。

したがって：

  • 接尾辞配列が使用するスペースが少ない (はるかに少ない)
  • サフィックス ツリーの構築が遅い
  • サフィックス ツリーは、パターン マッチング操作の実行が高速です
  • サフィックス ツリーはより多くの操作を実行できます。最善の方法は、ワイルドカードを使用したエラー パターン マッチングです (サフィックス配列もパターン マッチングを行いますが、ワイルドカードを使用しません)。

50 メガバイトを超えるような大量のデータにインデックスを付けたい場合。サフィックス ツリーは非常に多くのスペースを使用するため、コンピューターには中央メモリに保持するための十分な RAM がありません。そのため、セカンダリ メモリの使用が開始され、速度が大幅に低下します。(たとえば、人間の DNA は 700 メガバイトを使用し、そのデータの接尾辞ツリーは 40 ギガバイトを「使用できます」 -> * 実装に応じて「可能です * 」)

このため、接尾辞ツリーが実際に使用されることはほとんどありません。実際には、接尾辞配列が使用され、小さな追加のデータ構造により、いくつかの追加機能が提供されます (完全な接尾辞ツリーではありません)。

しかし、それらは異なります。効率的な速度、高速な構築速度、および少ないスペースの使用により、パターン マッチングに純粋な接尾辞配列が適している場合が多くあります。

于 2012-06-19T17:16:27.123 に答える