克努斯-莫里斯-普拉特算法

维基百科,自由的百科全书
跳转至: 导航搜索

Knuth-Morris-Pratt 字符串查找算法(常简称为 “KMP算法”)是在一个“主文本字符串” S 内查找一个“词” W 的出现,通过观察发现,在不匹配发生的时候这个词自身包含足够的信息来确定下一个匹配将在哪里开始,以此避免对以前匹配过的字符重新检查。

这个算法是由高德纳(Donald Ervin Knuth)和 沃恩·普拉特英语Vaughan Pratt 在1977年合作发明的,同年詹姆斯·H·莫里斯英语James H. Morris也独立地设计出该算法,但是最终由三人联合发表。

注意: 在本文中,我们将使用始于零的数组来表示我们的字符串。所以在下面例子中,我们用W[2] 来表示字符串 W 中的字符 'C'。这种表示遵从 C语言 的语法。

算法说明[编辑]

查找算法实例[编辑]

让我们用一个实例来演示这个算法。在任意给定时间,本算法被两个整数 mi 所决定: m 代表主文字符串S 内匹配字符串 W 的当前查找位置;i 代表匹配字符串W当前做比较的字符位置。图示如下:

m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123456

我們從 WS 的開頭比較起。我們比對到 S[3](=' ') 時,發現 W[3](='D') 與其不符。接著並不是從S[1]比較下去。我們已經知道 S[1]~S[3] 不與 W[0] 相合。因此,略過這些字元,令 m = 4 以及 i = 0。

m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:     ABCDABD
i:     0123456

如上所示,我們檢核了 "ABCDAB" 這個字串。然而,這與目標仍有些差異。我們可以注意到,"AB"在字串頭尾處出現了兩次。這意味著尾端的 "AB" 可以作為下次比較的起始點。因此,我們令 m = 8, i = 0,繼續比較。圖示如下:

m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:         ABCDABD
i:         0123456

m = 10, i = 2 的地方,又出現不相符的情況。類似地,令 m = 11, i = 0 繼續比較:

m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:            ABCDABD
i:            0123456

這時,S[17](='C') 不與 W[6]相同,但是亦出現了兩次 "AB",我們採取一貫的作法,令 m = 15i = 2 ,繼續搜尋。

m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:                ABCDABD
i:                0123456

我們找到完全匹配的字串了,其起始位置於 S[15] 的地方。

“部分匹配”表(又叫做“失配函数”)[编辑]

表的作用是让算法无需多次匹配S中的任何字符。能够实现线性时间搜索的关键是在主串的一些字段中检查模式串的初始字段,我们可以确切地知道在当前位置之前的一个潜在匹配的位置。换句话说,在不错过任何潜在匹配的情况下,我们"预搜索"这个模式串本身并将其译成一个包含所有可能失配的位置对应可以绕过最多无效字符的列表。

对于W中的任何位置,我们都希望能够查询那个位置前(不包括那个位置)有可能的 W 的最长初始字段的长度,而不是从W[0]开始失配的整个字段,这长度就是我们查找下一个匹配时回退的距离。因此T[i]W的可能的适当初始字段同时也是结束于W[i - 1]的子串的最大长度。我们使空串长度是0。当一个失配出现在模式串的最开始,这是特殊情况(无法回退),我们设置T[0] = -1,在下面讨论。

建立表算法示例[编辑]

我们首先考虑例子 W = "ABCDABD"。使用这个大致相同的模式串作为主搜索,我们将会看到它高效的原因。

首先,我们设定 T[0] = -1。为了找到T[1],我们必须找到一个"A"适当后缀 同时也是W的前缀。但 "A" 没有后缀,所以我们设定T[1] = 0。类似地,T[2] = 0

继续到 T[3],我们注意到检查所有后缀有一个捷径:让我们说我们发现了一个适当后缀,结束于 W[2]、长度为2(最大可能)的后缀,那么它的第一个字符是W的一个适当前缀。因此一个结束于W[1]的适当前缀,我们已经确定了不可能出现在T[2]。因此在每一层递推中,这个规则是只有在上一层找到一个长度为m的有效后缀时,才需要需要检查给定长度为m+1的后缀(例如,T[x]=m)。

那么我们甚至不需要关心具有长度为2的子串,由于上一个情况因长度为1而失配,所以T[3] = 0

我们继续遍历到W[4]子序列,'A'。同样的逻辑说明我们需要考虑的最长子串的长度是1,并且在'A'这个情况中有效,回退到我们寻找的当前字符之前的字段,因此T[4] = 0

现在考虑下一个字符W[5]'B',我们使用这样的逻辑:如果我们曾发现一个子模式在上一个字符W[4]之前出现,继续到当前字符W[5],那么在它之前它本身会拥有一个结束于W[4]合适的初始段,与事实相反的是我们已经找到'A'是最早出现在结束于W[4]的合适字段。因此为了找到W[5]的终止串,我们不需要查看W[4]。因此T[5] = 1

最后,我们看到W[4] = 'A'下一个字符是'B',并且这也确实是W[5]。此外,上面的相同参数说明为了查找W[6]的字段,我们不需要向前查看W[4],所以我们得出T[6] = 2

于是我们得到下面的表:

i 0 1 2 3 4 5 6
W[i] A B C D A B D
T[i] -1 0 0 0 0 1 2

另一个更复杂和有趣的例子:

i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
W[i] P A R T I C I P A T E I N P A R A C H U T E
T[i] -1 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 1 2 3 0 0 0 0 0

建立表算法的伪代码的解释[编辑]

上面的例子以最少的复杂步骤展示了组织这个表格的一般性方法。这么做的原理是对整体的搜索:大多数工作已经在检测到当前位置的时候做完了,剩下需要做的很少。略微复杂的一点是找到一个共同前后缀。这就需要有一些初始化的代码。

algorithm kmp_table:
    input:
        an array of characters, W (the word to be analyzed)
        an array of integers, T (the table to be filled)
    output:
        nothing (but during operation, it populates the table)

    define variables:
        an integer, pos ← 2 (the current position we are computing in T)
        an integer, cnd ← 0 (the zero-based index in W of the next 
character of the current candidate substring) (the first few values are fixed but different from what the algorithm
might suggest) let T[0] ← -1, T[1] ← 0 while pos < length(W) do (first case: the substring continues) if W[pos - 1] = W[cnd] then let cnd ← cnd + 1, T[pos] ← cnd, pos ← pos + 1 (second case: it doesn't, but we can fall back) else if cnd > 0 then let cnd ← T[cnd] (third case: we have run out of candidates. Note cnd = 0) else let T[pos] ← 0, pos ← pos + 1

建立表的算法的效率[编辑]

建立表的算法的复杂度是 O(n), 其中 nW 的长度. 出去一些初始化的工作,所有工作都是在 while 循环中完成的, 足够说明这个循环执行用了 O(n) 的时间, 同时还会检查 pospos - cnd 的大小. 在第一个分支里, pos - cnd is preserved, as both pos and cnd are incremented simultaneously, but naturally, pos is increased. In the second branch, cnd is replaced by T[cnd], which we saw above is always strictly less than cnd, thus increasing pos - cnd. In the third branch, pos is incremented and cnd is not, so both pos and pos - cnd increase. Since pos ≥ pos - cnd, this means that at each stage either pos or a lower bound for pos increases; therefore since the algorithm terminates once pos = n, 这个循环最多在t must terminate after at most 2n 次迭代后终止, 因为 pos - cnd1 开始. 那么建立表的算法的复杂度是 O(n).

另见[编辑]

外部連結[编辑]

引用[编辑]