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

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されます。

これが理論上の上限であるだけでなく、一部のサフィックス ツリーが実際にこの上限に達していることを確認するには、例として、文字が 1 つだけ繰り返される文字列 'aaa$' を考えてみます。このサフィックス ツリーに 7 つのノード (ルートとリーフを含む) があることを確認します。

要約:明らかなように、実際の変数は内部ノードの数だけです。根と葉の数は1およびNすべてのサフィックス ツリーで一定ですが、内部ノードの数は と の間0で異なりN-2ます。