4

'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).
4

2 回答 2

8

该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的边中使用的指针将指向 t 的某个子串。尽管字符串必须在 t 的某处出现为一个连续的字符串，但子串也可能出现在其他地方。所以，边的指针 k不一定是边的结束指针 p加一。fgfgdefgfgfgde

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

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

于 2012-04-11T02:00:51.667 回答
0

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

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

它现在似乎工作了:)

于 2014-10-17T13:04:17.383 回答