サフィックスツリー内のノードの最大数と最小数

Question

サフィックスツリー内のノードの最大数と最小数はいくらですか？そして私はそれをどのように証明できますか？

Answer 1

入力テキストの長さがNであると仮定すると、ルートノードとすべてのリーフノードを含むノードの最小数はN+1であり、ルートとリーフを含むノードの最大数は2N-1です。

最小限の保証：接尾辞ごとに少なくとも1つのリーフノードがあり、接尾辞はNです。例は、任意の内部ノードとすることがない必要がありますテキストはユニークシンボルのシーケンス、abc$されている場合、分岐は、得られた接尾辞木には内部ノードが故に、存在しない：

従って最小でありますN葉、0内部ノード、1ルートノード、合計N+1ノード。最大の

証明：サフィックスが終わるところリーフノードであり、あなたは長さNの文字列内に複数Nの異なるサフィックスを持つことができないので、葉ノードの数が、Nより大きくなることはありません。実際には、常に正確にNという別個の接尾辞があります。したがって、Nのリーフノードです。）ルートノードは常に正確に1であるため、問題は内部ノードの最大数です。すべての内部ノードはツリー内に分岐を導入します（サフィックスツリーの内部ノードには少なくとも2つの子があるため）。新しいブランチはそれぞれ少なくとも1つの余分なリーフノードにつながる必要がありますので、Kの内部ノードがある場合は少なくともK+1のリーフノードが必要です。ルートノードの存在には少なくとも1つの追加リーフが必要です（ツリーが空でない限り）。しかし、葉ノードの数はNによって制限されているので、内部ノードの最大数はN-2で制限されています。これにより、正確にNの葉、1のルート、および最大でN-2の内部ノード、2N-1が得られます。

これは理論上の上限であるだけでなく、いくつかの接尾辞ツリーが実際にこの最大値に達していることを確認するには、例として、「aaa $」という文字を繰り返した文字列を考えてみましょう。

概要：明らかなように、唯一の真の変数は内部ノードの数であり、このための接尾辞木は（根および葉を含む）7のノードを有していることを確認根と葉の数は、すべての接尾辞木に対して、1とNで一定ですが、内部ノードの数は0とN-2の間で変わります。