algorithm - Ukkonen 的后缀树算法 : procedure 'test and split' unclear

Question

ukkonen's on line construction algorithm

我在尝试理解“测试和拆分”过程时遇到了问题，具体如下:程序 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)

我的问题是，第二行到底是什么意思，如果 g'(s,(k',p')) 从 s 开始然后是 t(k') 而不是，它怎么可能仍然是一个 tk-transition的 t(k)??

Answer 1

可能你已经弄明白了，你不再需要答案了，但由于我在试图理解它时遇到了同样的问题，也许它将来对其他人有用，我认为的答案是下面的。

在Ukkonen's on line construction algorithm ，在第 7 页，您可以阅读到:

...
The string w spelled out by the transition path in STrie(T) between two explicit states s and r is represented in STree(T) as generalized transition g′(s,w) = r. To save space the string w is actually represented as a pair (k,p) of pointers (the left pointer k and the right pointer p) to T such that t_k . . . t_p = w. In this way the generalized transition gets form g′(s, (k, p)) = r.
Such pointers exist because there must be a suffix T_i such that the transition path for T_i in STrie(T) goes through s and r. We could select the smallest such i, and let k and p point to the substring of this T_i that is spelled out by the transition path from s to r. A transition g′(s, (k, p)) = r is called an a–transition if t_k = a. Each s can have at most one a–transition for each a ∈ Σ.
...

这意味着我们正在寻找满足 t_k 的最小索引 k 和 p 。 . . t_p = w T
=> 如果 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 行我们要找到从 s 开始的转换，该转换以我们在 T 的 k 位置找到的字符开始>(即 t_k)。请注意，t_k 必须等于 t_k' 但索引 k 和k' 可以不同，因为我们总是指向字符串 w 在 T 中的第一次出现(还请记住，从一个状态可以有最多有一个以字符 t_k => 开头的转换，所以这是正确的，也是唯一的)。

然后在第 3 行，我们检查规范引用对 (s,(k,p)) 引用的状态是否为端点，即它是否具有 t_i - 过渡。状态 (s,(k,p)) 是我们可以从状态 s 到达的状态(隐式或非隐式)，紧随 t _k' -transition(即 t_k-transition 因为 k' = k)对于 (p - k) 个字符。这解释了 t_k′+p−k+1，其中 +1 代表下一个字符，即我们要检查的字符如果它等于 t(其中 t = t_i)。在那种情况下，我们到达终点并返回 true。

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