首页 文章

关于Ukkonen的后缀树的澄清

提问于
浏览
3

我一直在阅读Ukkonen的Suffix树上的工作,并想确认以下是否属实 .

在Ukkonen后缀树中说这是正确的:


只有通向叶节点的边可以将多个连续字符压缩为其一部分 . 内部节点之间的边缘(例如,从根节点到内部节点)只能表示单个字符 .


2 回答

  • 2

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

  • 4

    声明不正确 . 后缀树是Patricia树,这意味着所有边都带有字符串标签(任何长度,而不是单个字符) . 但请注意,标签实现为(从,到)对输入文本的引用,因此边缘占用的内存空间为O(1),与标签的长度无关 .

相关问题