接尾辞ツリーで接尾辞リンクを作成する方法と時期について、誰かに例を教えてもらえますか?
私の文字列がABABABCの場合、それがより良い場合は別の例を使用してください。
すべてのステップを説明するためにいくつかの写真を提供したいと考えています。
とても感謝しています。
質問する
9536 次
1 に答える
66
これを理解するには、まずサフィックス ツリーに 3 種類のノードがあることを思い出してください。
- 根っ子
- 内部ノード
- 葉ノード
のサフィックス ツリーである下のグラフではABABABC、黄色の円はルート、灰色、青、緑の円は内部ノード、小さな黒い円は葉です。
注意すべき重要な点が 2 つあります。
内部ノードには、常に複数の出力エッジがあります。つまり、内部ノードは、分岐が発生するツリーの部分をマークします。
分岐は、繰り返される文字列が関係する場所でのみ発生します。任意の内部ノード X の場合、ルートから X につながる文字列は、少なくともX からの出力エッジと同じ回数、入力文字列で発生している必要があります。
例:青いノードにつながる文字列はABABです。実際、この文字列は入力文字列に 2 回表示されます: 位置 0 と位置 2 です。これが青いノードが存在する理由です。
サフィックスリンクについて：
内部ノード X に至る文字列sが 1 文字よりも長い場合、同じ文字列から最初の文字を除いたもの(これをs -1 と呼びます) もツリーに含まれている必要があります (結局のところ、これは接尾辞ツリーなので、接尾辞はその文字列のいずれかもツリー内にある必要があります)。
例:
ABAB青のノードにつながる文字列をs=とします。次に、最初の文字を削除した後、s -1はBABです。実際、その文字列はツリーにもあります。緑のノードにつながります。一部の文字列sが内部ノードにつながる場合、その短縮バージョン s -1も内部ノード ( X -1と呼びます) につながる必要があります。なんで？sは入力文字列に少なくとも 2 回出現する必要があるため、s -1は少なくとも同じ回数出現する必要があります (これはs の一部であるため、 sが出現する 場所には常にs -1も出現する必要があります)。ただし、入力文字列にs -1 が複数回出現する場合は、その内部ノードが必要です。
このような状況では、X を X -1に接続する特別なリンクがサフィックス リンクです。
注:上記の (1) および (2) のため、ルートから X までの 1 文字を超えるラベルを持つすべての内部ノード X には、正確に 1 つの他の内部ノードへの接尾辞リンクが必要です。
例：
これは前と同じサフィックス ツリーです。点線はサフィックス リンクを示します。青のノードから始めて、そこから接尾辞のリンク (青から緑、最初の灰色、2 番目の灰色) をたどり、ルートから各ノードに至る文字列を見ると、次のようになります。
ABAB -> BAB -> AB -> B
(blue) (green) (gray1) (gray2)
これがサフィックスリンクと呼ばれる理由です(シーケンス全体はサフィックスチェーンと呼ばれます)。
彼らは何のために良いですか？
驚くほど多くのことに適しています。ただし、接尾辞ツリー構築のための Ukkonen のアルゴリズム、特にそこで説明されているルール 3で特定の役割を果たします:ある点 X でいくつかの接尾辞s の最後の文字を挿入した後、アルゴリズムは接尾辞s -1の最後の文字を挿入する必要があります。 O(1)時間で。そのために、接尾辞リンクを使用して X -1の場所にジャンプし、挿入を行います。
ただし、サフィックス ツリーにサフィックス リンクを配置する必要はないことに注意してください。これらはサフィックス ツリーの定義の一部ではありません。サフィックス ツリーを構築または使用する一部のアルゴリズムで使用される特別なリンクにすぎません。
単一文字ノードについて:文字列 (つまり、ルートから X へのパス上の文字列) が 1 文字のみで構成される内部ノード X がある場合はどうなりますか? 上記の定義により、X には接尾辞リンクがありません。ただし、接尾辞リンクがある場合は、ルート ノードを指すと想定できます。さらに、上記の定義により、内部ノードに接尾辞リンクがない場合、それは単一文字ノードである必要があるため、内部ノードに接尾辞リンクが存在しない場合は、単一文字ノードである必要があると常に想定できます。したがって、接尾辞 s -1を表すノードがルート ノードです。(一部のアルゴリズムは、この場合、ルート ノードを指す明示的な接尾辞リンクを実際に追加する場合があります。)これに関するコメントについて j_random_hacker に感謝します。
于 2012-04-16T05:08:50.527 に答える