Ukkonen的后缀树算法：'test and split'过程不清楚。

Question

Ukkonen的后缀树算法：'test and split'过程不清楚。

3

我在尝试理解“测试和分裂”过程时遇到了问题，该过程如下：

过程test-and-split(s, (k, p), t):

>1. if k ≤ p then
>2. let g'(s,(k',p'))=s' be the tk-transition from s
>3. if t=t(k'+p-k+1) then return (true,s)

我的问题是第二行到底是什么意思，如果从s开始并跟随t(k')而不是t(k)，那么g'(s,(k',p'))如何仍然是一个tk转换？

- schmidt lee

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tommy · Accepted Answer

Probably you already figured it out and you don't need an answer anymore, but since I had the same problem in trying to understand it, and maybe it'll be useful for someone else in the future, the answer I think is the following one.

在 Ukkonen's on line construction algorithm 中的第7页可以看到：

...
在STrie(T)中，两个明确的状态s和r之间的转换路径所拼写出的字符串w在STree(T)中被表示为广义转移g′(s,w) = r。为了节省空间，字符串w实际上被表示为指向T的一对指针（左指针k和右指针p），使得t_k . . . t_p = w。通过这种方式，广义转移变成了g′(s, (k, p)) = r。
这样的指针是存在的，因为必须有一个后缀T_i，使得T_i在STrie(T)中的转换路径经过s和r。我们可以选择最小的这样的i，并让k和p指向从s到r的转换路径所拼写出的此T_i的子字符串。如果t_k = a，则转换g′(s, (k, p)) = r称为a–转换。每个s最多可以有一个a–转换，对于每个a ∈ Σ。
...

这意味着我们正在寻找最小的索引k和p，使得在T中t_k...t_p=w
=>如果T中有多个w的出现，我们总是使用k和p来引用第一个。

现在，过程test–and–split(s,(k,p),t)测试具有规范参考对(s,(k,p))的状态是否为终点，即在STrie(Tⁱ⁻¹)中将具有t_i–转换的状态。符号t_i作为输入参数t给出。

算法的前几行如下：

   procedure test–and–split(s,(k,p),t):
1.   if k ≤ p then
2.     let g′(s,(k′,p′)) = s′ be the t(k)–transition from s;
3.     if t = t(k′+p−k+1) then return(true,s)
4.     else ...

第1行，我们检查状态是否为隐式状态（即当 k <= p 时）。

如果是这样，在第2行，我们希望找到从字符 T 的位置 k 开始的转移（也就是 t_k）。注意，t_k 必须等于 t_k'，但是索引 k 和 k' 可以不同，因为我们总是指向 T 中字符串 w 的第一个出现位置（还要记住，从一个状态到另一个状态最多只能有一个以字符 t_k 开头的转移，因此这是正确且唯一的方式）。

然后，在第3行，我们检查规范引用对(s，（k，p）)所引用的状态是否为终点，即它是否具有t_i -转换。状态(s，（k，p）)是从状态s开始，沿着t_k' -转换（即t_k -转换，因为k' = k）可以到达的状态（隐式或非隐式），并且可以沿着(p - k)个字符进行。这就解释了t_k′+p−k+1，其中+1是下一个字符，即我们正在检查它是否等于t（其中t = t_i）。在这种情况下，我们到达了终点并返回true。

否则，从第4行开始，我们拆分转换g′(s，（k′，p′）) = s′以明确状态(s，（k，p）)并返回新的显式状态。