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向量构造算法，似乎只有T[i] 对于索引 i = 0 小于零。在那种情况下，可以在索引上执行更快的 "check"（数组访问是一项额外的指令，特别是如果考虑到可能的 cache-faults），赋值 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 数组中吗？

Answer 1

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

的字符的情况

我不认为维基百科中的算法是 "official" 或超优化的；它的目的是说教。

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 上找到）提出了以下简单算法： <pre>(* Note: here, m is the length of pattern and n is the length of the input *) j := k := 1; while j ≤ m and k ≤ n do begin while j > 0 and text[k] ≠ pattern[j] do j := next[j]; k := k + l; j := j + l; end; </pre>

然而，作者抱怨上面的简单算法不必要地低效，并用了几页来探索优化。

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

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

Redundant instruction in Knuth-Morris-Pratt algorithm

algorithm

optimization

knuth-morris-pratt