私は仕事のためにUkkonenの接尾辞ツリーを読んでいて、次のことが真であるかどうかを確認したいと思っていました。Ukkonenの接尾辞ツリーに関する解説
Ukkonenサフィックスツリーにそれを言うことが正しいだろう。
のみリーフノードにつながるエッジはその一部として、圧縮された複数の連続 文字を持つことができます。内部の ノードの間のエッジ(ルートから内部ノードまで)は、 という単一の文字しか表現できません。
私は仕事のためにUkkonenの接尾辞ツリーを読んでいて、次のことが真であるかどうかを確認したいと思っていました。Ukkonenの接尾辞ツリーに関する解説
Ukkonenサフィックスツリーにそれを言うことが正しいだろう。
のみリーフノードにつながるエッジはその一部として、圧縮された複数の連続 文字を持つことができます。内部の ノードの間のエッジ(ルートから内部ノードまで)は、 という単一の文字しか表現できません。
私はこの文が真であるとは思いません。私はこのarticleを使ってサフィックスツリーを実装しました。例のために構築した最後の接尾辞ツリーは、より多くの文字を含むエッジがあることがわかります。
ステートメントが正しくありません。サフィックスツリーはパトリシアツリーであり、すべてのエッジが(単一の文字ではなく任意の長さの)文字列ラベルを保持することを意味します。しかし、ラベルは入力テキストへの(から、への)参照として実装されるので、ラベルの長さに関係なく、エッジによって取られるメモリ空間はO(1)です。
すばらしいリンク、ありがとう –