我一直在为我的工作阅读Ukkonen后缀树,并想确认以下内容是否正确。可以说在Ukkonen的后缀树中:只有指向叶节点的边可以将多个连续字符压缩为一个整体。而内部节点之间(例如从根节点到内部节点)的边只能表示单个字符。
该语句是不正确的。后缀树是一种 Patricia 树,这意味着所有边都带有字符串标签(可以是任意长度,而不仅仅是单个字符)。但请注意,这些标签是实现为对输入文本的(起始,结束)引用,因此边所占用的内存空间是 O(1),无论标签的长度如何。