我一直在阅读Ukkonen的Suffix树上的工作,并想确认以下是否属实 .
在Ukkonen后缀树中说这是正确的:
只有通向叶节点的边可以将多个连续字符压缩为其一部分 . 内部节点之间的边缘(例如,从根节点到内部节点)只能表示单个字符 .
我不认为这种说法是对的 . 我使用article实现了一个后缀树 . 您可以看到他们为示例构建的最终后缀树具有多于一个字母的边 .
声明不正确 . 后缀树是Patricia树,这意味着所有边都带有字符串标签(任何长度,而不是单个字符) . 但请注意,标签实现为(从,到)对输入文本的引用,因此边缘占用的内存空间为O(1),与标签的长度无关 .
2 回答
我不认为这种说法是对的 . 我使用article实现了一个后缀树 . 您可以看到他们为示例构建的最终后缀树具有多于一个字母的边 .
声明不正确 . 后缀树是Patricia树,这意味着所有边都带有字符串标签(任何长度,而不是单个字符) . 但请注意,标签实现为(从,到)对输入文本的引用,因此边缘占用的内存空间为O(1),与标签的长度无关 .