Ukkonen后缀树相关澄清

3
我一直在为我的工作阅读Ukkonen后缀树,并想确认以下内容是否正确。
可以说在Ukkonen的后缀树中:
只有指向叶节点的边可以将多个连续字符压缩为一个整体。而内部节点之间(例如从根节点到内部节点)的边只能表示单个字符。
2个回答

4

我不认为这个说法是正确的。我使用了这篇文章来实现后缀树。你可以看到他们为这个例子建立的最终后缀树有边缘带有多个字母。


2
该语句是不正确的。后缀树是一种 Patricia 树,这意味着所有边都带有字符串标签(可以是任意长度,而不仅仅是单个字符)。但请注意,这些标签是实现为对输入文本的(起始,结束)引用,因此边所占用的内存空间是 O(1),无论标签的长度如何。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接