algorithm - 如何以及何时在后缀树中创建后缀链接？

Question

谁能给我一个关于如何以及何时在后缀树中创建后缀链接的例子？

如果我的字符串是 ABABABC ，但如果更好，请使用不同的示例。

希望给一些图片来说明每一步。

非常欣赏。

Answer 1

要理解这一点，首先记忆一下有三种节点
在后缀树中:

根

内部节点

叶节点

在下图中，这是 ABABABC 的后缀树，黄色
圆圈是 根 ，灰色、蓝色和绿色分别是 内部的
节点 ，小黑的是 树叶。



有两个重要的事情需要注意:

内部节点总是有 1 个以上的出边 .那是，
内部节点标记发生分支的树的那些部分。

分支发生在 的任何地方重复字符串 涉及，而且只有
那里。对于任何内部节点 X，从
root 到 X 必须至少在输入字符串中出现过多次
因为有 出边来自 X。

示例:通向蓝色节点的字符串是 ABAB .的确，
此字符串在输入字符串中出现两次:在位置 0 和在
位置 2。这就是蓝色节点存在的原因。

现在关于后缀链接:

如果字符串 s 通向某个内部节点 X 的时间更长
超过 1 个字符，相同的字符串减去第一个字符
(称之为 s-1 )也必须在树中(这是一个
毕竟是后缀树，所以它的任何字符串的后缀都必须是
也在树上)。

示例:让 s= ABAB ，通向蓝色节点的字符串。然后
删除第一个字符后，s-1 是 BAB .和
确实，在树中也可以找到该字符串。它通向绿色
节点。

如果某个字符串 s 导致内部节点，其缩短
版本 s-1 必须通向内部节点(调用
X-1) 也是如此。为什么？因为 s 必须至少出现两次
输入字符串，所以 s-1 必须至少出现多次
(因为它是 s 的一部分:无论 s 出现在哪里，
s-1 也必须出现)。但如果 s-1
在输入字符串中出现多次，那么一定有一个
它的内部节点。

在任何此类情况下，将 X 连接到 X-1 的特殊链接是
后缀链接。

注:由于上述(1)和(2)， 每内部节点 X
有一个从 root 到 X 超过 1 个字符的标签 必须有一个
后缀链接到另一个内部节点。

示例:



这是和以前一样的后缀树；虚线表示
后缀链接。如果从蓝色节点开始，按照后缀
从那里链接(从蓝色，到绿色，到第一个灰色，到第二个灰色)，
并查看从根到每个节点的字符串，您将
看到这个:

 ABAB   ->    BAB    ->    AB    ->    B
(blue)      (green)     (gray1)     (gray2)

这就是为什么它们被称为 后缀链接 (整个序列是
叫 后缀链 )。

它们有什么用？

它们适用于许多令人惊讶的事情。然而，他们玩
在 Ukkonen's algorithm for suffix treeconstruction 中的特殊作用， 具体来说
在 规则 3 在那里描述:插入最后一个字符后
一些后缀 s 在某个点 X，算法需要插入
后缀的最后一个字符 s-1 在 O(1) 时间内。在
为了做到这一点，它使用后缀链接直接跳转到该位置
X-1 并插入。

但是，请注意 没有必要将后缀链接放在后缀树中。它们不是后缀树定义的一部分——它们只是一些构建或使用后缀树的算法所使用的特殊链接。

关于单字符节点:如果有一个内部节点 X 的字符串(即从根到 X 的路径上的字符串)只包含一个字符怎么办？根据上面的定义，X 没有后缀链接。但是，您可以假设如果它有后缀链接，它将指向根节点。此外:如果根据上面的定义，内部节点没有后缀链接，则它必须是单字符节点，因此您始终可以假设，如果内部节点不存在后缀链接，则它必须是单字符节点。字符节点，因此，代表s-1后缀的节点就是根节点。 (在这种情况下，某些算法实际上可能会添加指向根节点的显式后缀链接。)感谢 j_random_hacker 对此的评论。