私は自分の仕事のためにウッコネンの接尾辞ツリーを読んでいて、次のことが正しいかどうかを確認したかった.
Ukkonen Suffix Tree で次のように言うのは正しいでしょうか?
リーフ ノードにつながるエッジのみが、複数の連続した文字をその一部として圧縮できます。また、内部ノード間のエッジ (たとえば、ルートから内部ノードまで) は、1 つの文字のみを表すことができます。
2 に答える
4
この発言は真実ではないと思います。この記事を使用してサフィックス ツリーを実装しました。彼らがこの例のために構築した最終的なサフィックス ツリーには、1 文字以上のエッジがあることがわかります。
于 2012-02-16T08:32:24.677 に答える
2
ステートメントは正しくありません。サフィックス ツリーはパトリシア ツリーです。これは、すべてのエッジが文字列ラベル (単一の文字ではなく任意の長さ) を持つことを意味します。ただし、ラベルは入力テキストへの (from,to) 参照として実装されるため、ラベルの長さに関係なくエッジが使用するメモリ空間は O(1) であることに注意してください。
于 2012-02-17T02:34:34.540 に答える