KNUTH, MORRIS, PRATT (KMP) PATTERN MATCHING ALGORITHM

Gary Gong

5 minute read

OVERVIEW - A BASIC PATTERN MATCHING

字串是一個由字元所組成的有限集合，字串的比對有許多方法，其中最簡單的是選定一個起始點向下比對，若是遇到不符合 Pattern 的字串，即起始點向下挪動一格再重新啟動 Pattern 比對，其程式方法如下：

int findString(char *string, char *pattern) {
    int i, j = 0;
    int startStringPos = 0, endStringPos = strlen(string)-1;
    int endPatternPos = strlen(pattern)-1;
    int endMatchingPos = endPatternPos;
    for (i = startStringPos; endMatchingPos <= endStringPos; ) {
        if (string[endMatchingPos] == pattern[endPatternPos]) {
            for (j = 0, i = startStringPos; j < endPatternPos && string[i] == pattern[j]; i++, j++);
        }
        if (j == endPatternPos) {
            return startStringPos;
        }
        endMatchingPos++;
        startStringPos++;
    }
    return -1;
}

這個程式主要運作起來長這樣：

初始化（2~5 行地方）：

首先把定位（i）定在字串初始位置（startStringPos = 0）的地方，然後推移endMatchingPos個長度當作該字串比對結束位置（endMatchingPos）。

第一個if：

我們有字串比對結束位置（endMatchingPos）之後，先行檢查是否與欲比對的 Pattern 最尾端（endPatternPos）是否有同樣的字元，如果不一樣，前面就都不用對了。

第一個if裡面的for：

如果發現我們要比對的字串尾巴與 Pattern 尾巴字元相符，那麼我們就檢查要比對的字串字元是否跟 Pattern 完全相符。

第二個if：

如果皆相符，j理應會被計數器加到跟endMatchingPos一樣，那就代表找到相符的樣式字串。

之後（12, 13 行地方）：

把字串比對的初始位置（startStringPos）往後調一個，endMatchingPos也是。

這是 PATTERN 與變數的關係：

pattern:
(  a  a  b  \0  )
   ^j    ^endPatternPos
   _______
   endMatchingPos

這是 STRING 比較的經過：

第一層 FOR 迴圈，第 1 輪

-------------------------------------------
(  a  b  a  b  b  a  a  b  a  a  \0)
   ^startStringPos            ^endStringPos
   ^i    ^endMatchingPos
-------------------------------------------
(*) i = startStringPos
(1) 比較 pattern[endPatternPos] 是否等於 string[endMatchingPos]：YES
(2) 比較 string[i] 是否等於 pattern[j]：NO
(3) endMatchingPos++; startStringPos++;

第一層 FOR 迴圈，第 2 輪

-------------------------------------------
(  a  b  a  b  b  a  a  b  a  a  \0)
      ^startStringPos         ^endStringPos
      ^i    ^endMatchingPos
-------------------------------------------
(*) i = startStringPos
(1) 比較 pattern[endPatternPos] 是否等於 string[endMatchingPos]：NO
(2) 比較 string[i] 是否等於 pattern[j]：NO
(3) endMatchingPos++; startStringPos++;

第一層 FOR 迴圈，第 3 輪

-------------------------------------------
(  a  b  a  b  b  a  a  b  a  a  \0)
         ^startStringPos      ^endStringPos
         ^i    ^endMatchingPos
-------------------------------------------
(*) i = startStringPos
(1) 比較 pattern[endPatternPos] 是否等於 string[endMatchingPos]：NO
(2) 比較 string[i] 是否等於 pattern[j]：NO
(3) endMatchingPos++; startStringPos++;

第一層 FOR 迴圈，第 4 輪

-------------------------------------------
(  a  b  a  b  b  a  a  b  a  a  \0)
            ^startStringPos   ^endStringPos
            ^i    ^endMatchingPos
-------------------------------------------
(*) i = startStringPos
(1) 比較 pattern[endPatternPos] 是否等於 string[endMatchingPos]：NO
(2) 比較 string[i] 是否等於 pattern[j]：NO
(3) endMatchingPos++; startStringPos++;

第一層 FOR 迴圈，第 5 輪

-------------------------------------------
(  a  b  a  b  b  a  a  b  a  a  \0)
               ^startStringPos^endStringPos
               ^i    ^endMatchingPos
-------------------------------------------
(*) i = startStringPos
(1) 比較 pattern[endPatternPos] 是否等於 string[endMatchingPos]：NO
(2) 比較 string[i] 是否等於 pattern[j]：NO
(3) endMatchingPos++; startStringPos++;

第一層 FOR 迴圈，第 6 輪

-------------------------------------------
                              ˇendStringPos
(  a  b  a  b  b  a  a  b  a  a  \0)
                  ^startStringPos
                  ^i    ^endMatchingPos
-------------------------------------------
(*) i = startStringPos
(1) 比較 pattern[endPatternPos] 是否等於 string[endMatchingPos]：YES

    第一層 for 迴圈，第 6 輪 - 第二層 for 迴圈，第 1 輪
    -------------------------------------------
                                  ˇendStringPos
    (  a  b  a  b  b  a  a  b  a  a  \0)
                      ^startStringPos
                      ^i    ^endMatchingPos
    -------------------------------------------
    (  a  a  b  \0  )
       ^j    ^endPatternPos
    -------------------------------------------
    (*) i = startStringPos
    (1) 比較 pattern[endPatternPos] 是否等於 string[endMatchingPos]：YES
    (1-1) 比較 pattern[j] 是否等於 string[i]：YES -> i++; j++;

    第一層 for 迴圈，第 6 輪 - 第二層 for 迴圈，第 2 輪
    -------------------------------------------
                                  ˇendStringPos
    (  a  b  a  b  b  a  a  b  a  a  \0)
                      ^startStringPos
                         ^i ^endMatchingPos
    -------------------------------------------
    (  a  a  b  \0  )
          ^j ^endPatternPos
    -------------------------------------------
    (1-2) 比較 pattern[j] 是否等於 string[i]：YES -> i++; j++;

    第一層 for 迴圈，第 6 輪 - 第二層 for 迴圈，第 3 輪
    -------------------------------------------
                                  ˇendStringPos
    (  a  b  a  b  b  a  a  b  a  a  \0)
                      ^startStringPos
                            ^i 
                            ^endMatchingPos
    -------------------------------------------
    (  a  a  b  \0  )
             ^j 
             ^endPatternPos
    -------------------------------------------
    (1-3) j == endMatchingPos，不符合第二個 for 迴圈執行要件，跳出此 for 迴圈

(2) j == endMatchingPos 故找到 String 的 Pattern，返回結果

TIME COMPLEXITY

如果最糟最糟的情況是我們必須要把字串比到最後的話，那時間複雜度將會是 Pattern 字串的長度$n$以及拿來比較的 String 字串長度$m$的乘積，亦即： $$ O(mn) $$

KNUTH, MORRIS, PRATT (KMP) PATTERN MATCHING ALGORITHM

KMP ALG. OVERVIEW

這個演算法基本上就是不要重複比那麼多次已經確定知道的事實，假若給定欲比較的字串$s$ ABCCABABCACBABCACB以及 Pattern $p$ ABCACBABCACB，如果是上述的演算法，$s_1$ 與 $p_1$ 會先比較，再來比較 $s_2$ 與 $p_2$，再來是 $s_3$ 與 $p_3$，但是比到 $s_4$ 與 $p_4$ 時卻發現不同了，這時，上述演算法就會從 $s_2$ 開始再跟 $p_1$ 重新開始比。

如果 Pattern 裡面有很多 Sub-Patterns，例如給定一個 $p’ = ABCACBABCACB$ ，這個 $p’$ 有重複兩次的 ABCACB，假若今天給定一個欲比較的字串 $s’ = ABCACBABCABCACBABCACB$ 比到 $p’_{11}$ 時，發現與 $s’_{11}$ 不一樣，如果我再從 $s’_2$ 開始跟 $p’_{1}$ 比其實很耗時間；我們發現到，在 $s’_{11}$ 的時候我們已經比完了 $p’_1$ ～ $p’_{10}$ 了，再仔細觀察一下，我們又發現 $p’_1$ ～ $p’_4$ 以及 $p’_7$ ～ $p’_{10}$ 根本都是一樣的（都是ABCA）；也就是說，當我的 $s’_7$ ～ $s’_{10}$ 跟 $ p’_7$ ～ $p’_{10}$ 一樣就等同於$s’_7$ ～ $s’_{10}$ 跟$ p’_1$ ～ $p’_4$ 也一樣的意思，那我就直接把 $ p’_1$ ～ $p’_4$ 對齊 $ s’_7$ ～ $s’_{10}$ 不就好了呢？

註：我這裡的 $s_1$ 等等那些 1 就是從字串第一個字開始。

s' = ABCACBABCABCACBABCACB
p' = ABCACBABCACB
               ^比到這裡錯了
笨：
s' = ABCACBABCABCACBABCACB
p' =  ABCACBABCACB

讚：
s' = ABCACBABCABCACBABCACB
p' =       ABCACBABCACB

因為 Pattern 如果有字樣重複問題（如上面重複兩次的ABCACB）很容易在比較的時候重複比對，造成不必要的運算，為了解決這個問題，我們於是有了Failure表，讓我們知道在比對的時候如果發現錯了，我們要該從哪裡重新比對，而非一直從頭開始慢慢比對。

以下是 $p’ = ABCACBABCACB​$ 的 Failure Table：

A B C A C B A B C A C B
When failure, goto? -1 -1 -1 0 -1 -1 0 1 2 3 4 5
index 0 1 2 3 4 5 6 7 8 9 10 11

再給定 $s’ = ABCACBABCABCACBABCACB$

很顯而易見的，如果 Pattern 比對到 index 10 (C) 的地方發現爛掉了，那我就依循 index 10 的 failure index 看看要從哪裡開始重新比較，此時是 4 ，所以欲比較的字串目前比對的字就回到 index 4 的地方從這裡開始比，就不重複比 index 0 ~ 3的地方了。

FAILURE FUNCTION RECURSION

如何創造出一個 Failure Table，若給定相關的遞迴式（From Horowitz et al.）：

$$ f(j) = \begin{cases} -1 & \quad \text{if } j \text{ is 0} \newline f^m(j-1)+1 & \quad \text{where } m \text{ is the least integer } k \text{ for which } p_{f^k(j-1)+1}=p_j \newline -1 & \quad \text{if there is no } k \text{ satisfying the above} \end{cases} $$

可求得以下程式，Horowitz et al. 的 Fundamental of Data Structures in C 給出初始值為-1而在 CLRS 的 Introduction to Algorithm 給出初始值為0，這其實大同小異，程式微調而已，演算法本質不變。

void failureFunction (char *pattern) {
    int n = strlen(pattern);
    failure[0] = -1;
    for (int j = 1; j < n; j++) {
        i = failure[j-1];
        while ((pattern[j] != pattern[i+1]) && (i >= 0)) {
            i = failure[i];
        }
        if (pattern[j] == pattern[i+1]) {
            failure[j] = i + 1;
        } else {
            failure[j] = -1;
        }
    }
}

EXPLANATION

這個 failureFunction主要是建構failure表供 KMP 演算法使用，其最重要的精神是在

初始化

failure[0] = -1

比對過程

  1. 先賦予前一次 Pattern 字元的編號（i = failure[j-1];）
  2. 比對本次字元是否與子 Pattern 字元是否*不*相符（pattern[j] != pattern[i+1]）以及編號必須大於等於 0（i >= 0）
    1. 若不相符，把i當failure索引，找到前一次的編號當作新的i
  3. 如果本次的字元與子 Pattern 字元相符（pattern[j] == pattern[i+1]），則賦予failure本次 Pattern 字元相對應的編號。
  4. 若以上都不符合，直接賦予failure本次 Pattern 字元-1的編號。

KMP MATCHING PROCEDURE

有了 Failure Table 可供使用之後，就可以建立起比較的模式，程式如下：

int kmpMatching(char *string, char *pattern) {
    int i = 0, j = 0;
    int stringLen = strlen(string);
    int patternLen = strlen(pattern);
    while (i < stringLen && j < patternLen) {
        if (string[i] == pattern[j]) {
            i++;
            j++;
        } else if (j == 0) {
            i++;
        } else {
            j = failure[j-1] + 1;
        }
    }
    return ((j == patternLen) ? (i - patternLen) : -1);
}

後記： 這篇打得有點虛虛的，感覺論述還不是很齊全，日後再慢慢補上。

也看看

Weather Research and Forecasting Model (WRF) Installation Guide on Ubuntu 16.04

Compiling TensorFlow-GPU on Ubuntu 16.04 with CUDA 9.1(9.2) and Python3

SPARSE MATRIX MULTIPICATION

Sparse Matrix Fast Transpose

Julia Triple-Quoted String Literals Alignment

NGINX, MYSQL, PHP INSTALLATION (UBUNTU 16.04)

Cannot Use pip3 in macOS (zlib Dependency Problem)

ZZZ我終於把 MATHJAX 弄進去了

comments powered by Disqus