私は接尾辞ツリーライブラリを探しています（それは線形時間構造を持っています）、見つかったのはPATLですが、PATLにはドキュメンテーションがありません。いずれかの例。 C++用のサフィックスツリーライブラリにはまともな文書がありますか？シンプルな例のあるC++の接尾辞ツリーライブラリ
PATLホーム： http://code.google.com/p/patl/
EDIT：
動機：私は、文字列の大規模な量を処理し、頻繁に共通のサブストリングを見つけ、任意の部分文字列以上のn個の出現は、t秒以内に発生した場合は報告する必要があります。私はツリーを実装しました（実際にはカウンターではありませんが、私は時間が必要だと言ったので、訪問時間の標準です）。しかし、それは非常に遅いです。 だから私は（文字列の間にいくつかのランダムなものと連結して、部分文字列が複数の文字列にまたがっていないように）一定量のメッセージ（30秒分のデータを考えましょう）を作成し、文字列。
Pizza&Chili projectの実装を見てみるとよいでしょう。接尾辞ツリーはありませんが、接尾辞配列とさまざまな圧縮インデックスがあります。プレーン（非圧縮）サフィックス配列は、サフィックスツリーではないにもかかわらず、あなたの目的には理想的です。
（あなたは「インデックスコレクション」リンクの下のダウンロードコードを見つけます。）
以前にP＆Cインデックスで働いていた人として、私はそれらをプロダクションコードで使用することに注意しました。彼らは研究品質のproof-of-conceptコードであり、私はそれらを使うときにさまざまなクラッシュを経験しました。 –
@Konrad Rudolph興味深く、知りたい。ありがとう。私はかなり前にいくつかの実験のためだけにそれらのいくつかだけを使用しました。私は将来、それらを推薦するときに、より慎重になるでしょう。 – jogojapan
ドキュメントと様々な検索アルゴリズムとデータ構造の高性能な実装を提供していますSeqAnライブラリを見てみましょう。
たとえば、suffix arrayクラスは、サフィックスツリーのドロップイン置換として使用できます。
あなたの問題は本質的に複雑なように聞こえますが、私はどれだけスピードアップできるかはわかりません。一般的な表現では、マルチアライメント問題はNPです。正確なサブミットにのみ関心があるが、まだ複雑なので、おそらくこれをより扱いやすいものに変えることができます。
は有望に見え、それを使用してもperfであっても、私の結果について報告しようとします。 – NoSenseEtAl
サフィックス*ツリー*が実際に必要ですか？またはトライやサフィックス配列も機能しますか？接尾辞配列はキャッシュの局所性のためにより良い性能を発揮するため、サフィックスツリーは通常は実装されません。 –
モチベーションを持ったtxtを編集 – NoSenseEtAl