string - Ukkonen 后缀树 : procedure 'canonize' unclear

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函数的作用是在 this SA post 的最后描述的，我们考虑这样的情况:

情况是这样的:

1. 活跃点在(red,'d',3) ，即 defg 中的三个字符边从红色节点出去。

2. 现在我们跟随绿色节点的后缀链接。理论上，我们的事件节点现在是(green,'d',3) .

3. 不幸的是，那个点不存在，因为 de从绿色节点出来的边只有 2 个字符。 因此，我们应用 canonize功能。

它的工作原理是这样的:

1. 我们感兴趣的边的起始字符是d .此字符在 Ukkonen 的表示法中称为 t_k。因此，“找到 t_k-edge”意味着找到 de绿色节点处的边。

2. 这条边的长度只有两个字符。 IE。 (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 中使用的指针绿色节点处的边将引用一些 子串de t 的指针，以及 fg 中使用的指针蓝色节点处的边将引用一些 子串fg吨。尽管字符串 defg必须作为一个连续的字符串出现在 t 中的某处，子字符串 fg也可能出现在其他地方。所以，fg 的指针 k edge 不一定 de 的结束指针 p边加一。

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

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