关于Ukkonen的后缀树的澄清

Question

我一直在阅读Ukkonen后缀树上的工作，并想确认以下内容是否属实。

难道是正确地说，在Ukkonen后缀树：

---

，导致叶节点可以有多个连续 字符压缩为它的一部分，只有边缘。而内部节点之间的边缘（比如说，从根节点到内部节点）只能代表 单个字符。

---

Answer 1

我不认为这种说法是正确的。我已使用此article实施了后缀树。您可以看到他们为示例构建的最终后缀树具有多于一个字母的边缘。

Answer 2

该声明不正确。后缀树是帕特里夏树，意思是所有的边都带有字符串标签（任意长度，而不是单个字符）。但请注意，标签实现为（从，到）对输入文本的引用，因此无论标签的长度如何，边缘占用的内存空间都是O（1）。