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

Question

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

algorithmsuffix-tree

28

能否给我一个关于如何在后缀树中创建后缀链接的例子，以及何时创建后缀链接？如果可以，请使用字符串ABABABC进行示例，或者选择更好的示例。

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

非常感谢。

- lingguang1997

请参考以下链接：https://dev59.com/1mox5IYBdhLWcg3wFAU1#22126672 - Suchit Puri

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jogojapan · Accepted Answer

为了理解这个，首先需要回想一下后缀树中的三种节点：

- 根节点 - 内部节点 - 叶子节点

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

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

内部节点始终具有多于1个的传出边。也就是说，内部节点标记了树中发生分支的部分。
只有在涉及到重复字符串时才会发生分支，而且仅在那里。对于任何内部节点X，从根到X的字符串必须至少在输入字符串中出现与X的传出边一样多的次数。

例如：导致蓝色节点的字符串是ABAB。确实，在输入字符串中这个字符串出现了两次：在位置0和位置2。这就是为什么存在蓝色节点的原因。

现在来谈谈后缀链接：

如果导致某个内部节点 X 的字符串 s 长度大于 1，则该树中也必须存在相同的字符串去掉第一个字符后的版本（称为 s_-1），因为它是后缀树，所以任何字符串的后缀也必须在树中。
如果某个字符串 s 导致一个内部节点，那么它的缩短版本 s_-1 必须也导致一个内部节点（称之为 X_-1）。为什么？因为 s 必须至少在输入字符串中出现两次，所以 s_-1 至少也要出现同样的次数（因为它是 s 的一部分，无论 s 出现在哪里，s_-1 也必须出现）。但如果 s_-1 在输入字符串中出现多次，那么必须有一个内部节点与之对应。
在任何这种情况下，连接 X 和 X_-1 的特殊链接都是一个后缀链接。

注意：由于上述(1)和(2)的原因，每个从根节点到X标记大于1个字符的内部节点X必须有一个后缀链接指向另一个内部节点。

例子：

这是之前相同的后缀树；虚线表示后缀链接。如果你从蓝色节点开始，沿着后缀链接走（从蓝色到绿色，再到第一个灰色，最后到第二个灰色），并查看从根节点到每个节点的字符串，你会看到这样：

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

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

它们有什么用处？

它们有很多出人意料的用途。然而，在Ukkonen算法中用于后缀树构建的规则3中，它们发挥了特殊作用：在某个点X插入某个后缀s的最后一个字符后，算法需要在O(1)时间内插入后缀s_-1的最后一个字符。为了做到这一点，它使用后缀链接跳转到位置X_-1并进行插入。

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

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