KMP — 字串搜尋演算法

KMP (Knuth-Morris-Pratt) 演算法是一個強力的字串搜尋演算法，能把原本暴力法的 O(m*n) 大刀一砍 [ 註1 ] 降成 O(m+n) !

字串搜尋，除了字面上的作用之外，在電腦科學中，還有各種應用，例如基因搜尋啦、圖像比對 [ 註2 ] 等等

回到我們的主題，每個演算法都有自己的精神，而 KMP 的精神則是 :「重複的比對不做第二次」，這也是為何 KMP 能夠將乘法時間變成加法時間的關鍵

怎麼說呢？先來看看暴力法是麼做的吧~

我們有待檢索的資料T(Text, 長度為n)，和要搜尋的花樣P(Pattern, 長度為m) :

設 T = abcabcabcabcacab , P = abcabcacab

a b c a b c a b c a b c a c a b
--------------------------------------
a b c a b c a C                
  A                            
    A                          
      a b c a b c a C          
        A                      
          A                    
            a b c a b c a c a b -> FIN
--------------------------------------
(大寫代表比對錯誤)

在這邊我們可以看到，暴力法會對每個字元進行一次比較，每次比較又會持續到比對錯誤，才換到下個字元進行比較

[這也是複雜度 O(m*n) 的由來 : n個比較 x m次比對]

如次一來，當資料重複性大的時候，一定會有已搜尋的資料被白白浪費掉(例如這裡的第一行跟第四行)，KMP 所作的就是「在比對錯誤時，尋找前面已搜尋的資料中，可以利用的部份」，來實際操作一遍吧 :

 a b c a b c a b c a b c a c a b
 --------------------------------------
[a b c(a]b c a)C 
      (a b c[a)b c a]C
            [a b c a]b c a c a b -> FIN
 --------------------------------------
（括弧代表以搜尋字串的，除了自己以外、長度最大的相同前後綴）

我們可以看到，在進行第二次比較的時候，由於開頭已搜尋的 abcabca，可以找到除了自己以外、長度最大的相同前後綴 : abca，因此能直接由此比較

Q : 為什麼找到長度最大的相同前後綴就能省略比較呢？

A : 當我們比對錯誤時，代表錯誤前的已比對字串都是正確的，因此，只要我們能將字串開頭的一段字元，對齊「正確的已比對字串末端」就能「將字串挪到對齊處比對」的效果

Q : 那我們要怎麼知道「應該挪去哪」呢？

A : 事實上，我們在進行比對之前，會先計算花樣(P)的「Faliure Function」，就是在比對錯誤時，用來計算該挪去哪的函式，故名為 Failure Function

[以下簡寫為 f()，f(x) 代表前 x-1 個字元中，是除了自己外、最長的相同前後綴長度，也是「如果在這邊比對錯誤，應該從哪邊開始比對」(因為前面已經比完了) ]

這個函式是 KMP 的核心，也有用到 DP 的概念，以範例為例 :

index 0 1 2 3 4 5 6 7 8 9
P   = a b c a b c a c a b
f() = 0 0 0 1 2 3 4 0 1 2
      -------------------
      a                    -> 第一個字元f(0)固定為0
      a b                  -> 與第一個字元不同，f(1) = 0
      a b c                -> 與第一個字元不同，f(2) = 0
     [a]b c[a]             -> 與第一個字元相同，f(3) = 1
     [a b]c[a b]           -> 能夠接上上個前綴，f(4) = 2
     [a b c|a b c]         -> 能夠接上上個前綴，f(5) = 3
     [a b c[a]b c a]       -> 能夠接上上個前綴，f(6) = 4
      a b c a b c a c      -> 不能接上上個前綴，嘗試接上前綴的前綴，直到找不到前綴為止
                           -> f(7-1) = 4 -> f(4-1) = 1 -> f(1-1) = 0，找不到相同前綴
                           -> f(7) = 0
     [a]b c a b c a c[a]   -> 與第一個字元相同，f(8) = 1
     [a b]c a b c a c[a b] -> 能夠接上上個前綴，f(9) = 2

看完 FailureFunction 後再看一遍 KMP 吧

index 0 1 2 3 4 5 6 7 8 9101112131415
T   = a b c a b c a b c a b c a c a b
      -------------------------------
      a b c a b c a C                 -> P[7]與T[7]比對錯誤，已比對字串省略至f(6)=4
                                      -> P[7]應與T[4]進行比較(將字串位移)
            a b c a b c a C           -> P[10]與T[7]比對錯誤，已比對字串省略至f(6)=4
                                      -> P[10]應與T[4]進行比較(將字串位移)
                  a b c a b c a c a b -> 比對完畢

相信看完了如何計算 Failure Function 之後，大家也能理解為何 KMP 可以利用 O(m+n) 的時間來搜尋字串了，不過，KMP 對於花樣(Pattern) 重複性低的搜尋就不會比暴力法快上多少，但遇到重複性大的情況 (搜尋基因之類) 還是能加快不少時間的

最後來總結下 KMP 吧 :

在長度n 的資料T(Text) 中搜尋長度m 的花樣P(Pattern)
計算出P的 Failure Function( f() )
對資料T(Text) 中的字依序進行比對，若比對錯誤，則將比對的字元切換到 P[ f(j-1) ] 去，直到沒有相同前後綴可以省略；如果比對正確，則比對下一個字元，直到P結尾為止

最後附上 Pseudo Code

/* FailureFunction */
f(){
    f(0) = 0, i = 0, j = 0
    while(i < m){
        /*能夠接上上個前綴*/
        if(P[i] == P[j]){
            f(i) = j+1
            i++, j++
        }
        /*不能接上上個前綴*/
        else{
            /*嘗試接上前綴的前綴*/
            if(j > 0) j = f(j-1)
            /*沒有前綴，放棄*/
            else f(i) = 0, i++
        }
    }
}

/* KMP */
i = 0, j = 0
while(i < n){
    /*字元相同*/
    if(T[i] == P[j]){
        if(j == m-1) -> FIN
        else i++, j++
    }
    /*字元不同*/
    else{
        /*找向上個最長相同前後綴*/
        if(j > 0) j = f(j-1)
        /*放棄，進行下一次比較*/
        else i++
    }
}

[ 註1 ] 我其實很想把標題改的聳動一點 : 「能讓乘法變加法的KMP！」但是這樣好像就完全看不出 KMP 是什麼鬼了 o.o

[ 註2 ] 圖像在電腦中也是以數字儲存的，最常見的就是 rgb編碼 : ＃FFFFFF(白色)，一種 16進位的表示法，將組成圖案的像素用紅/綠/藍光的三原色儲存，每2位 16進位碼是對應原色的參數，機器藉由參數來調整該像素原色的亮度，以發出特定顏色的光

Absnormal's Blog

KMP — 字串搜尋演算法

For now, just for having a blog