演算法 - KMP

Posted on | Edited on | In

KMP(Knuth–Morris–Pratt algorithm)演算法

String Searching 運用位移來處理字串搜尋問題

中譯”字串搜尋”:
兩個字串 T 和 P 找出 T 當中是否有一段字串正好是 P 並且找出位置

註：字串搜尋當中，我們通常將兩字串的象徵符號取做 T 和 P ， T 意指 text ， P 意指 pattern 。可以想作是從長篇文字 T 之中搜索小段文字 P 。

T:  ababcabc
P: abc

ababcabc    ababcabc
|||            |||
abc            abc

T中有兩個地方出現P
最直覺的演算法就是窮舉法：
挪動 P 對準 T 的各個位置 逐一比對字元 判斷是否相等
–> 時間複雜度為 O(TP) 。

T: ababcabc
P: abc

0.         1.         2.         3.         4.         5.
ababcabc   ababcabc   ababcabc   ababcabc   ababcabc   ababcabc
|||         |||         |||         |||         |||         |||
abc         abc         abc         abc         abc         abc
(X)         (X)         (O)         (X)         (X)         (O)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void string_searching()
{
string t = "ababcabc", p = "abc";

// 採用窮舉法，讓P對準T的各個位置
for (int i=0; i<t.size(); ++i)
{
// P不會超出T右端
if (i + p.size() > t.size()) break;

// 逐一比對每個字元、判斷一不一樣
bool find = true;
for (int j=0; j<p.size(); ++j)
if (t[i+j] != p[j])
{
find = false;
break;
}

if (find)
cout << "T的第" << i << "個字元開始為P";
}
}

failure function 窮舉法 (prefix function/ border function )–>

窮舉法的過程當中，當前比對成功的字串片段，是 P 的前綴。因為我們無法預測是 P 的哪幾個前綴，
所以我們可以預先計算 P 的每一個前綴的「次長的相同前綴後綴」，以備不時之需

failure function 是一個字串函數：輸入字串的其中一個前綴，則輸出該前綴的「次長的相同前綴後綴」。

012345
abzabc

prefix | border |failure function| implementation
-------|--------|----------------|----------------
Ø      | Ø      | f(Ø)      = Ø  |
a      | Ø      | f(a)      = Ø  | failure[0] = -1
ab     | Ø      | f(ab)     = Ø  | failure[1] = -1
abz    | Ø      | f(abz)    = Ø  | failure[2] = -1
abza   | a      | f(abza)   = a  | failure[3] =  0
abzab  | ab     | f(abzab)  = ab | failure[4] =  1
abzabc | Ø      | f(abzabc) = Ø  | failure[5] = -1

計算 failure function ，一般是利用 Dynamic Programming 。
分割問題的方式，是 P[0…i] 拿掉尾端字元 P[i] ，利用已知的「次長的相同前綴後綴」，得到 P[0…i] 的「次長的相同前綴後綴」。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// p[0...i] 的「次長的相同前綴後綴」是 p[0...failure[i]]。
// failure[] 值為 -1 時，代表「次長的相同前綴後綴」為空字串。
int failure[100];

void failure(string& p)
{
// iterative, bottom-up DP
    for (int i=1, j=failure[0]=-1; i<p.size(); ++i)
    {
    // 先試 p[0...i-1] 的「次長的相同前綴後綴」，
    // 也就是 p[0...failure[i-1]] = p[0...j]。
    // 再試 p[0...j] 的「次長的相同前綴後綴」，
    // 也就是 p[0...failure[j]]。
    // 再試 p[0...failure[j]] 的「次長的相同前綴後綴」……
        // 直到試成功為止。
        while (j >= 0 && p[j+1] != p[i])
        j = failure[j];

        // p[i] 終於有用處了，終於可以加長！
        if (p[j+1] == p[i]) j++;

// 得到了 failure[i] 的值！
failure[i] = j;
}
}

稱作 failure function ，是因為比對失敗時，就會使用它。
稱作 prefix function ，是因為此函數的定義域是 prefix 。稱作 border function ，是因為此函數的值域是 border 。

Morris-Pratt Algorithm

1.
T: aabzabzabcz
P:abzabc

2.
窮舉法，從左往右逐步挪動P。

aabzabzabcz   aabzabzabcz   aabzabzabcz
||||||         ||||||         ||||||      ......
abzabc         abzabc         abzabc
(X)            (X)            (X)

2.
仔細看窮舉法 是從左往右一一比對字元 一旦發現字元不同 就馬上往右挪動P

V              V            V              V
aabzabzabcz   aabzabzabcz  aabzabzabcz   aabzabzabcz
|             |X            |             ||
abzabc        abzabc        abzabc        abzabc

V             V               V             V
aabzabzabcz  aabzabzabcz   aabzabzabcz   aabzabzabcz
 |||          ||||          |||||         |||||X
 abzabc       abzabc        abzabc        abzabc

V             V              V              V
aabzabzabcz  aabzabzabcz   aabzabzabcz   aabzabzabcz
  X             X              |             ||       ......
  abzabc        abzabc         abzabc        abzabc

3.
往右挪動P之前 當下比對成功的字串片段 abzab 其實可以好好利用

V
aabzabzabcz    -abzab-----
 |||||X         |||||
 abzabc         abzab-

4.
觀察窮舉法的步驟順序 繼續往右挪動P 挪動一個位置、挪動兩個位置、……

-abzab-----   -abzab-----   -abzab-----
  ||||           |||            ||
  abzab-         abzab-         abzab-

-abzab-----   -abzab-----
     |
     abzab-         abzab-

5.
換個角度觀察上述行為
挪動一個位置：看看abzab的後四個字元 是不是前四個字元
挪動兩個位置：看看abzab的後三個字元 是不是前三個字元

6.
如果我們預先知道abzab的「次長的相同前綴後綴」是ab 就可以一口氣大幅挪動P 略過許多步驟：

V                 V
aabzabzabcz        aabzabzabcz
 |||||X      --->      ||
 abzabc                abzabc

7.
從「V」處繼續向右一一比對字元 每當比對失敗、遇到相異字元 就故技重施
從當前比對成功的字串片段 取其「次長的相同前綴後綴」大幅挪動P

Knuth-Morris-Pratt Algorithm

          v
T: aaaabcacab
P:    abcabcacab
          ^

Morris-Pratt Algorithm 當中，當比對到上圖之處， c != b ，所以需要向右挪動 P 。
找到 abca 的「次長的相同前綴後綴」，也就是 a 。然後向右挪動 P ，最後左端凸出一段 a ，如下圖所示。

          v
T: aaaabcacab
P:       abcabcacab
          ^

接下來就繼續比對字元。在這裡 c != b ，所以又要挪動 P 了。

Knuth 則是多想了一步：連續挪動 P ，能不能預先偵測呢？
Knuth 發現，找到 abca 的「次長的相同前綴後綴」 a 之後，看看 a 的下一個字元（是 b ），是否仍是 abca 的下一個字元（也是 b ）。
如果兩個字元一樣的話，那就表示 P 鐵定會連續挪動兩次，兩次比較都是 c != b 。

既然鐵定會挪動兩次，那乾脆直接移到定位不就好了？
於是 Knuth 在計算 failure function 的時候，就額外加了一個判斷：
找到 abca 的相同前綴後綴 f(abca) = a 之後，如果 f(abca) 的下一個字元恰巧仍是 abca 的下一個字元，
那麼就令 f(abca) = f(a) ，也就是再多找一次 a 的相同前綴後綴。
如此一來， P 只要移一次就行了。

由於是用遞迴定義 failure function ，所以連續挪動三次、四次、五次的情況，
經過遞迴計算，最後都會變成一次移到定位。

引用 http://www.csie.ntnu.edu.tw/~u91029/StringSearching.html#3