サフィックスツリーのサフィックスリンクは、aho-corasickオートマトンの障害エッジと同じですか？

Question

もしそうなら、誰かが正確な文字列照合のためにサフィックスツリーのサフィックスリンクの目的を説明することができますか？

Answer 1

ありません。接尾辞リンクは、接尾辞ツリー内の特定の遷移です。サブストリングを表すツリーで状態（S _I）、0 < I < nは、この状態から接尾辞木は0 < Iで、（S _{I + 1}）サブストリングを表す状態につながる与え<（n-1）。

これらの特定のトランジションは、新しい文字を追加している間にツリーのブランチをすばやく更新するためにツリーの構築中に使用されます。その名前が示すように、文字列Sを表す開始状態が指定されているの場合、接尾辞リンクに従うと、接尾辞Sが列挙されます。

...それだけです。その情報を使用していくつかのクエリをすばやく実行できますが、正確な文字列のマッチングには関連性はありません。

接尾辞ツリーで正確な文字列のマッチングはどのように機能しますか？あなたはあなたの木を歩いています。ノードにいる場合は、文字列に一致する文字から始まる適切なトランジションを選択する必要があります。不一致がなければ、明示的な状態（ノード）または暗黙の状態（遷移の途中）になる可能性があります。この時点で、入力文字列は接尾辞によって表される文字列の部分文字列です木。