Ukkonenの接尾辞ツリーに関する解説

Question

私は仕事のためにUkkonenの接尾辞ツリーを読んでいて、次のことが真であるかどうかを確認したいと思っていました。

Ukkonenサフィックスツリーにそれを言うことが正しいだろう。

---

のみリーフノードにつながるエッジはその一部として、圧縮された複数の連続 文字を持つことができます。内部の ノードの間のエッジ（ルートから内部ノードまで）は、 という単一の文字しか表現できません。

---

Answer 1

私はこの文が真であるとは思いません。私はこのarticleを使ってサフィックスツリーを実装しました。例のために構築した最後の接尾辞ツリーは、より多くの文字を含むエッジがあることがわかります。

Answer 2

ステートメントが正しくありません。サフィックスツリーはパトリシアツリーであり、すべてのエッジが（単一の文字ではなく任意の長さの）文字列ラベルを保持することを意味します。しかし、ラベルは入力テキストへの（から、への）参照として実装されるので、ラベルの長さに関係なく、エッジによって取られるメモリ空間はO（1）です。