28

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

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

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

非常感谢。

4

1 回答 1

66

要理解这一点，首先回想一下后缀树中存在三种节点：

  • 根
  • 内部节点
  • 叶节点

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

有两件重要的事情需要注意：

  • 内部节点总是有超过 1 个出边。也就是说，内部节点标记了树中发生分支的那些部分。

  • 分支发生在涉及重复字符串的任何地方，并且仅存在于那里。对于任何内部节点 X，从根到 X 的字符串在输入字符串中出现的次数必须至少与来自 X的出边一样多。

示例：通向蓝色节点的字符串是ABAB. 实际上，这个字符串在输入字符串中出现了两次：位置 0 和位置 2。这就是蓝色节点存在的原因。

现在关于后缀链接：

  1. 如果通向某个内部节点 X的字符串s长于 1 个字符，则减去第一个字符的相同字符串 （称为s -1）也必须在树中（毕竟它是后缀树，所以后缀它的任何字符串也必须在树中）。

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

  2. 如果某个字符串s指向一个内部节点，那么它的缩短版本 s -1也 必须指向一个内部节点（称为 X -1）。为什么？因为s必须在输入字符串中至少出现两次，所以s -1必须至少出现多次（因为它是s 的一部分：在s出现的任何地方， s -1也必须出现）。但是如果s -1 在输入字符串中出现多次，那么它必须有一个内部节点。

  3. 在任何这种情况下，将 X 连接到 X -1的特殊链接是后缀链接。

注意：由于上面的 (1) 和 (2)，每个内部节点 X 如果从根到 X 的标签超过 1 个字符，则必须具有到另一个内部节点的后缀链接。

例子：

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

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

这就是为什么它们被称为后缀链接（整个序列称为后缀链）。

它们有什么用？

它们对许多事情都有好处。但是，它们在Ukkonen 的后缀树构造算法中扮演着特殊的角色，特别是在规则 3中描述的：在某个点 X 处插入某些后缀s的最后一个字符后，该算法需要插入后缀s的最后一个字符-1在 O(1) 时间内。为此，它使用后缀链接直接跳转到 X -1位置并进行插入。

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

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

于 2012-04-16T05:08:50.527 回答