algorithm - Knuth-Morris-Pratt 算法中的冗余指令

Question

Knuth-Morris-Pratt algorithm旨在找到字符串中子字符串的第一次(可能是下一次)出现。由于 substring 可以包含重复部分，因此它使用了某种回溯机制。这是伪代码中的算法:

let m ← 0, i ← 0
while m + i < length(S) do
        if W[i] = S[m + i] then
            if i = length(W) - 1 then
                return m
            let i ← i + 1
        else
            if T[i] > -1 then
                let m ← m + i - T[i], i ← T[i]
            else
                let i ← 0, m ← m + 1

(来自维基百科)。使用 W 子字符串和 S 要搜索的字符串，都是从零开始的数组。

我对算法中的最后一个 if 子句有疑问:if T[i] > -1 then，基于 T-向量构造算法，对于索引 i = 0，T[i] 似乎只可能小于零。在那种情况下，我们可以对索引执行更快的“检查”(数组访问是一项额外的指令，特别是如果考虑到可能的缓存错误)，就像赋值 i ← 0 。

T 的构造是通过以下算法完成的:

let pos ← 2, cmd ← 0
let T[0] ← -1, T[1] ← 0
while pos < length(W) do
    if W[pos-1] = W[cnd] then
        let cnd ← cnd + 1, T[pos] ← cnd, pos ← pos + 1
    else if cnd > 0 then    // (*)
        let cnd ← T[cnd]
    else
        let T[pos] ← 0, pos ← pos + 1

(来自维基百科)

现在可以看到算法只将0 或cnd 的值写入T。对于第一种类型的赋值，该陈述是平凡的。对于第二种情况，它取决于cmd的值。

现在cmd唯一可以减少的方法是第二种情况(*)，在那种情况下，cmd会变得越来越小，直到它的值为零或较少的。但由于 cmd 从数组的已初始化部分获取值，因此它可以是 0 或 -1。如果 cmd 确实是 -1，这会导致 T[pos] 被设置为 0，因为有设置值之前的增量。如果 cmd 为零，则完全没有问题。

因此，更高效的算法是:

let m ← 0, i ← 0
while m + i < length(S) do
    if W[i] = S[m + i] then
        if i = length(W) - 1 then
            return m
        let i ← i + 1
    else
        if i > 0 then
            let m ← m + i - T[i], i ← T[i]
        else
            let m ← m + 1

这个说法对吗？如果不是，您能否给出一个子字符串，其中两个或多个 -1 出现在 T-array 中？

Answer 1

这对我来说很好，虽然我不知道它在实践中会有多大的不同。的确，在常见情况下，大多数循环恰恰是 i 为 0 且位置 S[m] ≠ W 的字符[0].

我不认为维基百科中的算法是“官方的”或超优化的；它的目的是说教。

if 的第二个分支发生在遇到不能扩展任何候选匹配的字符时，并且不是要搜索的单词的第一个字符；在这种情况下，有必要移动该字符。 (这是前面提到的常见情况。)

在进入失败分支的所有其他情况下，m+i 保持不变。在成功案例和最终失败案例中，m+i 恰好递增 1。

由于 min 和 max 是许多 CPU 上的无分支操作码，另一个优化是将 T[0] 设置为 0 而不是 -1，并将循环更改为:

let m ← 0, i ← 0
while m + i < length(S) do
    if W[i] = S[m + i] then
        if i = length(W) - 1 then
            return m
        let i ← i + 1
    else
        let m ← m + max(1, i - T[i]), i ← T[i]

但是更好的优化是使用三个不同的循环:一个用于常见情况(i = 0 和 S[m] 不匹配 W[0]);一种用于字符匹配的情况；一个用于失败案例。 (失败案例不需要将m + i与输入长度进行比较；它只需要检查i是否为0。)

作为引用，原始论文(可在 citeseer 上找到)提出了以下简单算法:

<em>(* Note: here, m is the length of pattern and n is the length of the input *)</em>
j := k := 1;
<strong>while</strong> j ≤ m <strong>and</strong> k ≤ n <strong>do</strong>
    <strong>begin</strong>
        <strong>while</strong> j > 0 <strong>and</strong> text[k] ≠ pattern[j]
            <strong>do</strong> j := next[j];
        k := k + l; j := j + l;
    <strong>end</strong>;

然而，作者提示上述简单算法的效率低得不必要，并用了几页来探索优化。

参见 Fast Matching in Strings, 1974, Knuth, Morris & Pratt