Ukkonen后缀树:程序'canonize'不清楚

Question

"canonize"函数(如下所示,来自Ukkonen的论文)是如何工作的,特别是while循环何时完成？我认为p' - k'的值总是小于p - k的值.我是对还是错？

procedure canonize(s, (k, p)):
1. if p < k then return (s, k)
2. else
3. find the tk–transition g'(s, (k', p')) = s' from s;
4. while p' ? k' <= p ? k do
5.     k  = k + p' ? k' + 1;
6.     s  = s';
7.     if k <= p then find the tk–transition g'(s, (k', p')) = s' from s;
8. return (s, k).

Answer 1

该canonize功能的作用是在这篇SA帖子的最后描述的内容,我们考虑这样的情况:

情况是这样的:

1. 活动点位于(red,'d',3),即defg从红色节点出来的边缘中的三个字符.

2. 现在我们按照绿色节点的后缀链接.理论上,我们的主动节点现在(green,'d',3).

3. 不幸的是,这一点并不存在,因为de从绿色节点出来的边缘只有2个字符.因此,我们应用该canonize功能.

它的工作原理如下:

1. 我们感兴趣的边缘的起始特征是d.这个字符在Ukkonen的符号中被称为t _k.因此,"找到t _k -edge"意味着de在绿色节点处找到边缘.

2. 该边缘长度只有两个字符.即(p' - k') == 2在Ukkonen的符号.但原始边缘有三个字符:(p - k) == 3.这<=是真的,我们进入循环.

3. 我们缩短我们正在寻找从边缘def到f.这就是这p := p + (k' - p') + 1一步.

4. 我们前进到de边缘指向的状态,即蓝色状态.这是做什么的s := s'.

5. 由于f边缘的剩余部分不是空的(k <= p),我们识别相关的外出边缘(即fg从蓝色节点出来的边缘).此步骤将k'和p'设置为全新值,因为它们现在引用字符串fg,其长度(p' - k')现在为2.

6. 剩余边缘的长度f(p-k)现在为1,fg新活动点(p' - k')的候选边长度为2.因此循环条件

   而(p' - k')<=(p - k)

不再是真的,所以循环结束,实际上新的(和正确的)活动点是(blue,'f',1).

[实际上,在Ukkonen的表示法中,边缘的结束指针p指向边缘的最终字符的位置,而不是跟随它的位置.因此,严格来说,(p - k)是0,而不是1,而(p' - k')是1,而不是2.但重要的不是长度的绝对值,而是两者的相对比较长度.]

最后几点说明:

• 像p和k这样的指针指的是原始输入文本t中的位置.这可能会令人困惑.例如,de绿色节点边缘中使用的指针将引用t的某个子字符串de,而fg蓝色节点边缘中使用的指针将引用t的某些子字符串fg.尽管字符串defg必须在t中的某处显示为一个连续字符串,但子字符串fg也可能出现在其他位置.所以,的指针ķ fg边缘是不一定的的端指针p de边加一.

• 因此,当我们决定是否结束循环时,重要的不是绝对位置k或p,而是剩余边缘的长度(p-k)与当前候选边缘的长度(p'-k')相比较.

• 在你的问题,代码片段的第4行,有一个错字:它应该是k'而不是k;.