サフィックス ツリーを実装するときに、元の文字列に "$" を追加する必要があるのはなぜですか?
user1819636
質問する
1801 次
3 に答える
5
接尾辞ツリーと接尾辞配列の両方の場合、特定の構築アルゴリズムが使用されている場合、文字列の最後に1つ（またはそれ以上）の特殊文字を追加する特別な理由があります。
ただし、接尾辞木の場合の最も基本的な根本的な理由は、接尾辞木の2つのプロパティの組み合わせです。
- 接尾辞木はPATRICIAツリーです。つまり、エッジラベルは、試行のエッジラベルとは異なり、1つ以上の文字で構成される文字列です。
- 内部ノードは分岐点にのみ存在します
これは、あるエッジラベルが別のエッジラベルのプレフィックスである可能性があることを意味します。
ここでの考え方は、右側の黒いノードが葉のノードであるということです。つまり、接尾辞はここで終わります。ただし、テキストに接尾辞が付いている場合はaa、1文字aも接尾辞である必要があります。ただし、接尾辞が最初のの後に終了するという情報を保存する方法はありません。これは、ツリーの1つの連続したエッジを形成するaためaaです（上記のプロパティ1）。次のように、情報を格納できる中間ノードを導入する必要があります。
ただし、プロパティ2のため、これは違法です。分岐点がない限り、内部ノードは存在してはなりません。
テキストの最後の文字が文字列全体のどこにも出現しない文字であることを保証できれば、問題は解決します。ドル記号は通常、その記号として使用されます。
明らかに、最後の文字が他のどこにも出現しない場合、文字列の最後で繰り返し（などaa、またはのようなより複雑なabcabc文字）が発生する可能性はないため、内部ノードが分岐しないという問題は発生しません。$上記の例では、文字列の最後に置くことの効果は次のとおりです。
現在、、、、の3つの接尾辞がありますが、aa$いずれも別の接頭辞ではありません。明らかに、これは結局、内部ノードを導入する必要があることを意味し、現在、合計3つのリーフがあります。したがって、確かに、これの利点は、スペースを節約したり、何かがより効率的になることではありません。これは、上記の2つのプロパティを保証する方法にすぎません。これらのプロパティは、内部ノードの数が文字列の長さで線形であるという事実など、接尾辞木の特定の有用な特性を証明するときに重要です（非分岐内部ノードが許可されている場合はこれを証明できませんでした）。a$$
これは、実際には、他のサフィックスのプレフィックスであるサフィックスと、非分岐内部ノードを処理するさまざまな方法を使用する可能性があることも意味します。たとえば、よく知られているUkkonenアルゴリズムを使用してツリーを構築する場合、末尾に一意の文字を追加せずにそれを行うことができます。最後に、最後の反復の後、すべての暗黙の接尾辞（つまり、エッジの中央で終了するすべての接尾辞）の最後に非分岐内部ノードを配置することを確認する必要があります。
繰り返しになりますが、接尾辞ツリーまたは配列を作成する前にテキストの最後に配置することには、さらに具体的な理由があります。$たとえば、DC（差分カバー）の原則に基づく接尾辞配列の構築アルゴリズムで$は、文字列の最後の文字でさえ完全な文字トリグラムの一部になるように、文字列の最後に2つの記号を付ける必要があります。アルゴリズムはトリグラムソートに基づいているためです。さらに、ユニークな$キャラクターを特別な方法で解釈しなければならない特定の状況があります。$Ukkonen構築アルゴリズムの場合、一意であるだけで十分です。DC接尾辞配列アルゴリズムの場合、一意性に加えて、次のことが必要です。$は辞書式に他のすべての文字よりも小さく、接尾辞木ベースの円形文字列切断アルゴリズム（最近ここで説明）では、実際に$は辞書式に最大の文字として解釈する必要があります。
于 2012-11-19T08:32:24.280 に答える
1
トラバース目的だと思います。サフィックス ツリーから何かを生成する場合、文字列が終了するノードにいるかどうかを知る必要があります。接尾辞ツリーが線形時間の解決策を提供する最長の共通部分文字列を見ると$、文字列が終了するノードに到達したことを判断するためにセンチネルが必要です。の後に終了することはできませんA-NA。
ウィキペディアより
于 2012-11-16T18:56:10.457 に答える