2

最近、ツリーを使用して最長共通部分文字列の問題を解決する方法を学んでいます。Wiki やその他のオンライン リソースから学んだ後、サフィックス ツリーを使用して最長の共通部分文字列を見つける必要があることがわかりました。

ウィキが言ったように：

文字列の集合の最も長い共通部分文字列は、文字列の一般化されたサフィックス ツリーを構築し、その下のサブツリー内のすべての文字列から葉ノードを持つ最も深い内部ノードを見つけることによって見つけることができます。

ジャスティンが言ったように：

String = ABCDE$XABCZ$
    End of word character 1 = $
    └── (0)
        ├── (20) $
        ├── (22) ABC
        │   ├── (15) DE$
        │   └── (23) Z$
        ├── (24) BC
        │   ├── (16) DE$
        │   └── (25) Z$
        ├── (26) C
        │   ├── (17) DE$
        │   └── (27) Z$
        ├── (18) DE$
        ├── (19) E$
        ├── (21) XABCZ$
        └── (28) Z$

(コンパクトな) サフィックス ツリーでは、すべての文字列からリーフ ノードを持つ最も深い内部ノードを見つける必要があります。同じ深さに複数のノードがある場合は、そのノードが表す文字列の長さを比較する必要があります。つまり、ABC、BC、C の深さはすべて同じなので、ABC、BC、C の文字列の長さを比較して、どちらが長いかを確認する必要があります。これは明らかにABCです。

ここで、すべての文字列から葉ノードを持つ最も深い内部ノードを見つけるプロセスは、実際にはすべての文字列からすべての接尾辞の中で最も長い共通の接頭辞を見つけるプロセスだと思いました。

ここで質問があります: すべての文字列のすべてのサフィックスを格納するプレフィックス ツリーを構築しないのはなぜですか? 次に、接頭辞ツリーを検索して、これらの接尾辞の最も長い共通接頭辞を見つけることができます。この2つの違いはわかりません。この問題を解決するためにプレフィックス ツリーの代わりにサフィックス ツリーを使用する理由を誰かに教えてもらえますか?

4

2 に答える 2

3

サフィックス ツリーはO(N)、長さの文字列に対して時間とスペースのみを必要としますN。これが、それを使用して線形時間で最長共通部分文字列問題を解くことができる理由です。
文字列のすべてのサフィックスをトライに追加するO(N^2)には、最悪の場合、時間とスペースが必要になります。

したがって、すべての文字列のすべての接尾辞をトライに追加するという考えは実際には正しいですが、接尾辞ツリーを使用したソリューションと比較すると非効率的です。

于 2014-09-23T19:14:53.900 に答える
0

辞書にはトライを使用します。接尾辞は保存されません。

于 2014-09-23T18:20:55.320 に答える