問題タブ [suffix-tree]

Tries一般にプレフィックス ツリーおよび として知られているものについて読んでいSuffix Treesます。
のコードは見つかりましたがTrie、 の例が見つかりませんSuffix Tree。Trieまた、a を構築するコードは a のコードと同じであると感じますがSuffix Tree、前者の場合は接頭辞を格納し、後者の場合は接尾辞を格納するという唯一の違いがあります。
これは本当ですか？頭の中でこれをクリアするのを手伝ってくれる人はいますか? サンプルコードは非常に役立ちます!

簡単な質問：

接尾辞木（単語の接尾辞を格納する木）はbツリーの一種ですか？

2つの文字列間の最大の共通部分文字列の問題を解決しようとしています。問題を次のように減らします。一般的な接尾辞木を作成しました。私の理解では、最大の共通サブ文字列は、両方の文字列に属するノードで構成される最も深いパスです。

私のテスト入力は次のとおりです。

私が構築したツリーは正しいようですが、私の問題は次の方法です（最初にツリーのルートを渡します）。

私が目指していたのは、両方の文字列に属するノードを持つ最も深いパスを見つけるために、ツリーをトラバースし（事前注文）、リストに両方の文字列に属するノードを追加することです（current）。両方の一部ではないノードに入ると、大きいmax場合はリストを更新します。current

しかし、コードは誤りです。そして、私はこれを実装する方法について混乱しています。なぜなら、私は昔から一般的な（非バイナリ）ツリーのコードを書いていなかったからです。

これを理解するのを手伝ってくれませんか。

更新：
@templatetypedefに従って変更されました。これも動作させることができませんでした。

文字列 S を保持し、次のことを可能にするデータ構造を必要とする問題に遭遇しました。

1. 単語 W が S のサブワードかどうかを O(|W|) 時間でチェックする
2. 与えられた単語 U のプレフィックスでもある S の最長のサフィックスを O(|U|) 時間で見つけます
3. O(|K|) 時間で S の末尾に文字列 K を追加します

Ukkonen アルゴリズムによって構築された接尾辞ツリーが探しているものであることがわかりました。アルゴリズムは「接尾辞ツリーのオンライン構築」として説明されており、「オンライン」部分に問題があります。各文字アルゴリズムの挿入後、最終ステップで明示的に変換できる暗黙的な接尾辞ツリーを構築します。しかし、そのステップの前に暗黙的なツリーを検索に使用したい場合はどうすればよいでしょうか? 「オンライン」は、分析された文字列のプレフィックスを挿入した後に可能であることを示唆していますが、暗黙的なツリーで動作する最も単純なアルゴリズムの例さえ見つかりません。

私の質問は次のとおりです。暗黙の接尾辞ツリーで文字列を検索するにはどうすればよいですか?

編集:私は私の問題を解決する非常に良い答えを受け入れましたが、その間に私は2へのより簡単な解決策を見つけることができました:長さ|U|のSの接尾辞でUを検索するだけで十分です KMP アルゴリズムを使用し、最後に一致した文字数は文字列の重複になります。

入力: 2 つの文字列 A と B。

出力: 繰り返され、重複しない部分文字列のセット

繰り返されるすべての文字列を見つける必要があり、それぞれが両方の (!) 文字列に少なくとも 1 回出現する必要があります。たとえば、

A = "xyabcxeeeyabczeee" および B = "yxabcxabee".

この場合、有効な出力は {"abcx","ab","ee"} になりますが、文字列 A でのみ発生するため、"eee" ではありません。

この問題は、「超極大反復」の問題と非常に関連していると思います。定義は次のとおりです。

最大反復ペア : S 内の同一のサブストリング alpha と beta のペアで、alpha と beta をいずれかの方向に拡張すると 2 つの文字列の等価性が失われるようなものです。トリプレット (位置 1、位置 2、長さ) として表されます。

最大繰り返し : 「S の最大ペアで発生する S の部分文字列」。例: S の abc = xabcyiiizabcqabcyrxar。注: 多数の最大反復ペアが存在する可能性がありますが、最大反復の限られた数しか存在できません。

超極大反復 「他の極大反復の部分文字列として決して発生しない極大反復」 例: abcy in S = xabcyiiizabcqabcyrxar.

すべての超極大反復を見つけるためのアルゴリズムは、「文字列、ツリー、およびシーケンスのアルゴリズム」で説明されていますが、接尾辞ツリーについてのみです。

1.) DFS を使用してすべての左多様なノードを見つける

S の各位置 i に対して、S(i-1) は左文字 i と呼ばれます。T(S) の葉の左文字は、その葉が表すサフィックス位置の左文字です。T(S) の内部ノード v は、v のサブツリー内の少なくとも 2 つの葉が異なる左文字を持つ場合、左多様化と呼ばれます。

2.) これらのノードに定理 7.12.4 を適用する:

左多様な内部ノード v は、v のすべての子が葉であり、それぞれが別個の左文字を持っている場合に限り、超最大反復 a を表します

文字列 A と B の両方を連結する必要があり、ステップ 2 で v の葉をチェックするときに、文字列 A と B から少なくとも 1 つの別個の左側の文字が必要であるという追加の制約も課す必要があります。これは、それらの位置を A の長さと比較します。位置 (左の文字) > 長さ (A) の場合、左の文字は A にあり、そうでない場合は B にあります。

サフィックス + lcp 配列でこの問題を解決するのを手伝ってくれませんか?

文字列Sのプレフィックスであるように、テキストTで最長のサブストリングを見つけています。より複雑でないソリューションを提供するサフィックスツリーを使用してアルゴリズムを作成しましたが、Matlabはポインターやその他の参照を使用しないため、実装。

誰かがこの問題の解決策または代替方法を提案してください。Matlabで可能です。

文字列 S[1..m] の接尾辞ツリーから文字列 S[2..m]の接尾辞ツリーを生成する高速 (O(1) 時間の計算量) の方法はありますか?

私は Ukkonen に精通しているので、文字列 S[1..m] のサフィックス ツリーから文字列 S[1..m+1] のサフィックス ツリーを高速に作成する方法は知っていますが、逆の状況にアルゴリズムを適用することはできませんでした。 .

多くの文献を調べましたが、部分文字列のサフィックス ツリーへの削除または挿入に関する情報は見つかりませんでした。ツリーを構築するためのアルゴリズムは Ukkonen または McCreight のみです。
最も貧弱な方法は、部分文字列を削除または挿入した後にツリーを再構築することです。しかし、それが最善の方法だと思います。
例 (位置は 0 からカウントされます):
"abcdef" のサフィックス ツリーがあり、1 から 3 までのシンボルを削除する必要があります。次に、"aef" のサフィックス ツリーがあります。そして、位置 1 の文字列「as」から追加する必要があります。そして、この後、「aasef」の接尾辞ツリーができます。手伝って頂けますか？

ウッコネンのアルゴリズムを理解しています。複数の文字列を含むように拡張する方法に興味があるだけです（特殊文字「$」で終わります）。

文字列 s1(たとえば "abcddefx$") と s2(たとえば "abddefgh$") が与えられた場合、ukkonen のアルゴリズムで通常どおり s1 を挿入する必要があることをどこかで読みました。次に、s2 でツリーをたどります。つまり、ツリーで s2 を検索する必要があります。検索が終了するノード (「ab」、「b」の後) に到達したら、そこからウッコネンのアルゴリズムを再開する必要があります。

この背後にある基本的なロジックを理解しています。しかし、私が興味を持っているのは、古いサフィックス リンクがどうなるのかということです。それらはまだ有効ですか？また、新しいパスを開始するときに、トリプル (active_node,active_length,remainder) が ("ab",0,0 を表すノード) である必要があることについて混乱していますか???