接尾辞木を作成するには、最悪の場合、文字列のすべての文字が異なる場合、複雑さは次のようになります。
n + (n-1) + (n-2) ... 1 = n*(n+1)/2
これはO（n ^ 2）です。
ただし、 http：//en.wikipedia.org/wiki/Suffix_treeによると、サフィックスツリーの構築にはO（n）時間がかかります。ここで何が欠けていますか？
13146 次
1 に答える
42
アルゴリズムがΘ（n2）である理由の背後にある直感は良いものですが、ほとんどの接尾辞木は、この時間計算量の必要性を排除するように設計されています。直感的には、n +（n --1）+ ... + 1の異なるノードが必要になるため、すべての異なるサフィックスを保持するには、 Θ（n 2 ）の異なるノードが必要であるように思われます。ただし、接尾辞ツリーは通常、接尾辞の文字ごとに1つのノードが存在しないように設計されています。代わりに、各エッジは通常、元の文字列のサブ文字列である文字のシーケンスでラベル付けされます。それでも、Θ（n 2）サブストリングをこれらのエッジにコピーする必要があるため、このツリーを構築する時間ですが、通常、これはかわいいトリックによって回避されます-すべてのエッジが入力のサブストリングであるストリングでラベル付けされているため、エッジは代わりに開始位置と終了位置のラベルが付いています。これは、Θ（n）文字にまたがるエッジをO（1）時間で、O（1）空間を使用して構築できることを意味します。
とはいえ、接尾辞木を構築することはまだ本当に難しいです。ウィキペディアで参照されているΘ（n）アルゴリズムは簡単ではありません。線形時間で機能することがわかった最初のアルゴリズムの1つは、Ukkonenのアルゴリズムです。これは、文字列アルゴリズム（文字列、ツリー、シーケンスのアルゴリズムなど）に関する教科書で一般的に説明されています。元の論文はウィキペディアにリンクされています。より現代的なアプローチは、最初に接尾辞配列を構築し、それを使用して接尾辞ツリーを構築することによって機能します。
お役に立てれば！
于 2011-09-17T02:12:45.770 に答える