我一直在为我的工作阅读 Ukkonen 的后缀树，并想确认以下内容是否属实。
在 Ukkonen 后缀树中这样说是否正确：
只有通向叶节点的边才能将多个连续字符压缩为其中的一部分。并且内部节点之间的边（例如，从根到内部节点）只能代表一个字符。
问问题
253 次
2 回答
4
我不认为这种说法是正确的。我已经使用这篇文章实现了一个后缀树。您可以看到他们为示例构建的最终后缀树的边多于一个字母。
于 2012-02-16T08:32:24.677 回答
2
该说法不正确。后缀树是 Patricia 树，这意味着所有边都带有字符串标签（任何长度，而不是单个字符）。但请注意，标签被实现为对输入文本的 (from,to) 引用，因此无论标签的长度如何，一条边占用的内存空间都是 O(1)。
于 2012-02-17T02:34:34.540 回答