Ukkonen后缀树：'canonize'过程不清楚

Question

'规范化'函数（来自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).

- Abhishek

---

我认为加上论文的确切参考资料会更好。这是指1995年发表在《Algorithmica》上的那篇论文吗？如果是的话，参考资料应该是DOI 10.1007/BF01206331。 - jogojapan

该论文可以在http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf找到。 - Abhishek

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. 那条边只有两个字符的长度。即在Ukkonen的符号中，(p' - k') == 2。但原始边有三个字符：(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。因此循环条件

   while (p' - k') <= (p - k) do

不再成立，因此循环结束，实际上新的（正确的）活动点是(blue,'f',1)。

[实际上，在Ukkonen的符号中，边的结束指针p指向边的最后一个字符的位置，而不是紧随其后的位置。因此，严格来说，（p - k）为0，而不是1，（p' - k'）为1，而不是2。但重要的不是长度的绝对值，而是两个不同长度的相对比较。]

最后几点说明：

• 指针（如 p 和 k）引用原始输入文本 t 中的位置。这可能会让人感到困惑。例如，绿色节点处使用的边缘中使用的指针将引用 t 的某个子字符串 de，蓝色节点处 fg 边缘使用的指针将引用 t 的某些子字符串 fg。虽然字符串 defg 必须以某种连续的方式出现在 t 中，但子字符串 fg 也可能出现在其他地方。因此，fg 边缘的指针 k 不一定是 de 边缘的结束指针 p 加一。

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

• 在您的问题中，代码片段的第四行存在拼写错误：应该是 k' 而不是 k;。

- jogojapan

---

谢谢你的回答，它澄清了规范化的每个方面。如果您可以为更新、测试和拆分以及特别是算法2的最后一行提供类似于此的解释，并调用更新后调用规范化，那么对于我和所有其他有理解后缀树问题的人来说，这将非常有帮助。再次感谢你。 - Abhishek

我同意，将这些不同函数的原始名称放在我上面提到的算法的全面SA帖子中确实是一个好主意。我很快就会做到这一点。但如果还有进一步的问题（这是非常可能的），我们应该在单独的SA帖子中处理它们。 - jogojapan

Answer 2

我不得不更改canonize函数，因为它没有正确处理辅助状态。在“p < k”之后，我添加了以下代码：

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

现在看起来好像可以工作了 :)

- Kris De Greve