問題タブ [suffix-tree]

http://marknelson.us/1996/08/01/suffix-trees/のサイトに基づいてJavaでサフィックスツリーを構築しましたが、問題が発生しました。接尾辞ツリーをうまく構築することはできますが、ツリーからすべての接尾辞のセットを構築しようとすることはできます。基本的にすべての「エンドノード」を見つけて、その「エンドノード」で表される文字列を返します

そのアルゴリズムは「簿記係」のような単語に対して機能します

接尾辞：

でも「ATATATATATA」みたいなものを使うと失敗します

接尾辞：

ただし、適切なサフィックスは次のようになります。

各「エンドノード」文字列のすべてのサフィックスを見つけることで答えを見つけることができますが、それは正しいアプローチのようには思えません。他に何か提案はありますか？

編集：izomorphiusに感謝します！元の文字列にEND_CHARを追加すると、非常に役立ちました。

接尾辞：

私はPythonに比較的慣れておらず、接尾辞木を使い始めています。それらを構築することはできますが、文字列が大きくなるとメモリの問題が発生します。サイズが4^10または4^12のDNAストリングを処理するために使用できることは知っていますが、メソッドを実装しようとすると、メモリの問題が発生します。

文字列と接尾辞木を生成するための私のコードは次のとおりです。

4 ** 8前後になると、深刻なメモリの問題が発生します。私はこれにかなり慣れていないので、これらのものを保存することで何かが欠けていると確信しています。アドバイスをいただければ幸いです。

注：非常に大きな文字列で一致する文字列を探すために文字列検索を実行したいと思います。検索文字列の一致サイズは16です。したがって、これは大きな文字列内でサイズ16の文字列を検索し、次の文字列に移動して別の検索を実行します。非常に多くの検索を行うので、接尾辞木が提案されました。

どうもありがとう

「canonize」関数 (Ukkonen の論文から以下に示す) はどのように機能し、特に while ループはいつ終了するのでしょうか? p' - k' の値は常に p - k の値よりも小さいままになると思います。私は正しいですか、それとも間違っていますか？

現在、2 つのネストされたforループを使用して、文字列のすべての部分文字列を生成しています。聞いたことSuffix Treeがありますが、AFAIKSuffix Treeは部分文字列ではなく接尾辞を生成します。以下は、現在私が使用しているコードです-

未満のすべての部分文字列を生成できる方法が必要ですO(n^2)。私のコードを見ると、すべての部分文字列をリストに追加しているので、誰でも不可能だと示唆することができます。しかし、私の目的はすべての部分文字列を保存することではなく、辞書編集的に i 番目に小さい文字列を見つけることです。

接尾辞ツリーで接尾辞リンクを作成する方法と時期について、誰かに例を教えてもらえますか?

私の文字列がABABABCの場合、それがより良い場合は別の例を使用してください。

すべてのステップを説明するためにいくつかの写真を提供したいと考えています。

とても感謝しています。

この問題を解決するための(パフォーマンス面での)最善のアプローチは何でしょうか? サフィックスツリーを使用することをお勧めしました。これは最善のアプローチですか？

文字列「ABAB」のサフィックス ツリーを作成すると、2 つのノードしか得られません。

ABABとBAB

最長の repeatead 部分文字列 ("AB") は、「少なくとも k 個の子孫を持つ最も深いノード」に配置する必要がありますが、これは私の文字列には当てはまりません。何が問題なのですか?

ありがとう

文字列 ' ' に対してアルゴリズムを実行してAEKEAAEKEAAEKEA$、少なくとも 3 回出現する最長の部分文字列を探している場合、サフィックス ツリーのすべてのノードに最大 2 つの分岐があるとしたら、どうすればよいでしょうか?

正しい結果は部分文字列 ' AEKEA' です。

ツリーは、オンラインのサフィックス ツリー ビルダーで簡単に確認できます。

ウィキペディの説明に従っただけです：

「少なくともk回出現する最長の部分文字列を見つける問題は、最初にツリーを前処理して各内部ノードの葉の子孫の数を数え、次に少なくともk回の子孫を持つ最も深いノードを見つけることによって見つけることができます。」

ここで何が欠けていますか？

ありがとうございました。