Ukkonen后缀树：过程“册封”不明(Ukkonen suffix tree: procedure

如何（如下，从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 。 此字符称为T在Ukkonen的符号_ķ。 所以，“寻找吨_{ķ_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 ，并且其长度（对“ - K”）现在将是2。

6. 其余边缘的长度f ，（对- k）时，现在是1，和候选边缘的长度fg为新的活性点，（对“ - K”），是2。因此循环条件

   而（对 ' - K'）<=（P - K）做

不再是真实的，所以循环结束，确实是新的（正确的）活动点为(blue,'f',1)

[实际上，在Ukkonen的符号，一个边缘点到边缘，而不是它后面的位置的最后一个字符的位置的端指针p。 因此，严格来说，（对- k）为0，而不是1，和（p“ - K”）为1，而不是2。但重要的是不长度的绝对值，但是两个不同的相对比较长度。]

最后几点注意事项：

• 像P，K的指针指向在原始输入文本吨位置。 这可以是相当混乱。 例如，在所使用的指针de在绿节点边缘将参考一些子de在所使用的吨，并且所述指针fg在蓝色节点边缘将参考一些子fg吨的。 虽然字符串defg必须在T某处显示为一个连续字符串，则子fg可能出现在其他地方，太。 所以，的指针ķ fg边缘并不一定是的结束指针p de边缘加一 。

• 因此，当我们终于决定是否要结束循环计数不是绝对位置K或P，但长度（P - K） - 当前候选边缘的剩余边缘相比，长度（P“K”） 。

• 在你的问题，代码段第4行，有一个错字：它应该是k' ，而不是k; 。

Answer 2:

我不得不改变推崇的功能，因为它没有正确处理辅助状态。 添加以下代码的“P <K”后，如果：

if (s == auxiliary)
{
    s = root;
    k++;
    if (p < k)
        return;
}

似乎现在的工作:)

文章来源: Ukkonen suffix tree: procedure 'canonize' unclear