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

Question

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

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

希望能给出一些图片来说明每一步.

非常感谢.

Answer 1

要理解这一点,首先回想一下后缀树中有三种节点:

• 根
• 内部节点
• 叶节点

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

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

• 内部节点始终具有多个传出边缘.也就是说,内部节点标记树的那些发生分支的部分.

• 分支发生在涉及重复字符串的任何地方,并且仅在那里.对于任何内部节点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的标签超过1个字符的内部节点X 必须具有到其他内部节点的后缀链接.

例:

这是与以前相同的后缀树; 虚线表示后缀链接.如果从蓝色节点开始并按照后面的链接(从蓝色,绿色,到第一个灰色,再到第二个灰色),并查看从根到每个节点的字符串,您将看到:

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

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

它们有什么用？

他们对许多事情都有好处.然而,它们在一个特定的角色Ukkonen算法为后缀树建设,特别是在第3条中描述有:插入的一些后缀的最后一个字符后小号在某些点X,算法需要加后缀的最后一个字符小号_-1在O(1)时间.为了做到这一点,它使用后缀链接向右跳到X _-1并进行插入.

但是,请注意,没有必要在后缀树中添加后缀链接.它们不是后缀树定义的一部分 - 它们只是构造或使用后缀树的一些算法所使用的特殊链接.

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