2018年4月24日星期二

KMP(Knuth-Morris-Pratt)

前言

下面我将按这个目录来介绍 KMP 算法:

  • 字符串『前綴』|『後綴』
  • PMT(Partial Match Table)『最長公共前後綴』
  • Next 表
  • KMP 算法描述
  • KMP 程式

一、字符串『前綴』|『後綴』

KPM 其實是一種字符串匹配的算法,也就是說檢索字符串,那麼在學習它之前先了解一下『前綴』和『後綴』這 2 個概念。

1. 字符串『前綴』

a. 简单的解释
聲明 2 個字符串: A 和 B
定義它們的關係: A = BS (S 为任意的非空字符)
那麼就稱: B 是 A 的前缀

b. 舉例來看
現在有一個字符串:Hello
那麼它的前綴有:H, He, Hel, Hell

那麼把這個結果更結構化的表達一下:
"Hello" = { "H", "He", "Hel", "Hell" }

{} 這裡我們稱它為集合 => 字符串前綴集合

2. 字符串『后綴』

a. 简单的解释
聲明 2 個字符串: A 和 B
定義它們的關係: A = SB (S 为任意的非空字符)
那麼就稱: B 是 A 的后缀

b. 舉例來看
現在有一個字符串:Hello
那麼它的后綴有:ello, llo, lo, o

那麼把這個結果更結構化的表達一下:
"Hello" = { "ello", "llo", "lo", "o" }

{} 這裡我們稱它為集合 => 字符串后綴集合

其实这个概念还是挺简单的,我这里参考的是知乎的一个回答来解释一些概念,也许不严谨,但是我认为是易懂的。

不過按我查詢資料來理解 KMP 的時候,有外鏈最先不要跳躍出去,這樣保持一個思維來理解。

接下來將再看一個概念『最長公共前綴』,這個概念才是真正我們編程的時候需要尋找的部分。

二、PMT(Partial Match Table)『最長公共前後綴』

a. 解释和推导

這個概念用文字其實不是那麼好理解,如果硬要用漢字理解的話,就用拆字的方式:最長、公共、前綴、後綴,就是首先要找前綴和後綴,並且要是公共的,並且公共字符串的長度要是最長。

其實我覺得這個漢字解釋是錯的,既然那麼不好解釋,我們就用數學的方式來解釋看看,比較代數式的抽象度更高,更容易看懂。


前提:有一個字符串 \( P_j \)
目的:查找 \( P_j \) 中最長且相等的 k 前缀和 k 後綴

即:滿足條件的最大 k 值,使得,

\( P_0P_1P_2...P_{k-1}P_k = P_{j-k}P_{j-k+1}...P_{j-2}P_{j-1}P{j} \)


这样解释应该比较清晰了,当然这个东西也不是我自己写的,来自于算法老师 July CSDN 中的推导简化的。

b. 实例

模式串: abaabcaba

字符串 前綴 後綴 最长公共字符串 最長公共字符串長度
a 0
ab a b 0
aba ab ba a 1
abaab abaa baab ab 2
abaabc abaab baabc 0
abaabca abaabc baabca a 1
abaabcab abaabca baabcab ab 2
abaabcaba abaabcab baabcaba aba 3

根据上面的分析表,得出最终的表:

模式串 a b a a b c a b a
最大前缀后缀公共元素长度 0 0 1 1 2 0 1 2 3

c. 为什么需要 PMT?

看完這裡應該有個疑問:為什麼是這個步驟找出這樣一張表出來?這個就需要先了解一下由 PMT 表產生的 Next 表。下面我們先來看看 Next 表的相關東西。

三、Next 表

Next 表是由 PMT 表得到的,做到就是將 PMT 表中的每一個值向后移动 1 位,第一位賦值為 -1,為什麼是這樣得到 Next 表呢?接著看下去吧。

先按結論補充一下之前的表格,添加 Next 表

模式串 a b a a b c a b a
最大前缀后缀公共元素长度 0 0 1 1 2 0 1 2 3
Next -1 0 0 1 1 2 0 1 2

下面這張圖能很好的解釋為什麼我們需要 PMT 得到的 Next 表,這個表意味著我們能夠跳過一些不必要的字符,通過推斷的結構根據 Next 表的數據跳到已經確定的下一個比較位置,這里的 k 就是最長公共子綴的位置。

next

當我們在進行比較的時候,其實最後的『失配字符』(匹配失敗的字符)是 \( P_k \),所以真正相同的字符串是 \( P_0P_1...P_{k-1} \),那么我们能得到下面这个公式:

模式串向右移動的位數 := 已匹配字符數 - 失配字符的上一位字符所對應的最大長度值

模式串向右移動的位數 := j - next[j]

这个公式的解释依然出自于 July 的 CSDN 博客

以下是文字版公式:

\( S_0S_1 \qquad\qquad\qquad\qquad S_{i-k}S_{i-k+1}...S_{i-1} \quad S_i \\\)
\( \qquad P_0P_1...P_{k-1}P_k...P_{j-k}P_{j-k+1}...P_{j-1} \quad P_j \\\)
\( \qquad\qquad\qquad\qquad\qquad P_0 \quad P_1 \quad\ ...P_{k-1} \quad\ P_kP_{j-k}P_{j-k+1}...P_{j-1}P_j \)

這裡就能看出 KMP 的优势的,比如暴力的字符串匹配过程是需要每个字符都循环遍历进行比较的,如果遇到不匹配的时候总是移动一位然后再进行比较的过程。而 KMP 是可以跳跃一些不必要的匹配步骤的,时间就节约在这个地方,等會兒後面會分析一下最差情況的時間複雜度。

那么这里描述一下暴力匹配字符串的过程,有這麼 2 個字符串:

匹配串T: ababababab abaabcaba
模式串P: abaabcaba

1

這個很簡單,直接上代碼吧~因為要對比理解才能看出 KMP 節約的地方:

def index(source_string, type_string, pos):
    i = pos 
    j = 0

    while i <= len(source_string) - 1 and j <= len(type_string) - 1:
        if source_string[i] == type_string[j]:
            i += 1
            j += 1
        else:
            i = i - j + 1
            j = 0

    if j == len(type_string):
        return i - len(type_string)
    else:
        return -1

" output: 8 "
print index('abababababca', 'abca', 0)

這個代碼也是參考的博客python 的程式很直觀,就不翻譯成 JavaScript了。

四、KMP 算法描述

上面的準備工作已經差不多了,現在我們根據上面的 Next 表來描述一下算法過程:

  1. 如果 j = -1, 或者當前字符匹配成功(即S[i] == P[j]),都令 i++, j++,继续依次进行比较;
  2. 如果 j != -1, 且当前字符匹配失败(即S[i] != P[j]),令 i 不变,j = Next[j]。这个时候就要涉及到按照之前的公式进行移动,移动的位数为:j - Next[j]。

从上面的过程可以看出,我们算法是在解决 \( P_j \) 失配时候的问题。那麼這裡就是我們推斷算法複雜度的地方,算法最差的情況是模式串(P)在 i - j 的位置匹配完成,那么按匹配串(S)來看複雜度就是 O(n),如果算上 Next 表的過程 O(m),最後整體的算法複雜度為:O(n+m)。

五、KMP 程式

經過前面那麼多文字和公式的鋪墊,其實實現最後的程式并不複雜,程式包括 2 部分:

  1. 總的 KMP 算法實現過程
  2. Next 表的收集

Next 表的收集是有優化的地方的,優化點將以後再分享,這裡先實現它。

下面的 i 表示後綴索引,j 表示前綴索引。

def get_next_table(P):
    i = 0
    j = -1
    next_table = [-1]

    while i < len(P) - 1:
        if j == -1 or P[i] == P[j]:
            i += 1
            j += 1
            next_table.insert(i, j)
        else:
            j = next_table[j]

    return next_table

def index_kmp(S, P, pos):
    next_table = get_next_table(P)
    print next_table
    i = pos
    j = 0

    while i <= len(S) -1 and j <= len(P) - 1:
        if j == -1 or S[i] == P[j]:
            i += 1
            j += 1
        else:
            j = next_table[j]

    if j == len(P):
        return i - j
    else:
        return -1

"""
next_table: [-1, 0, 0, 1, 2, 3, 4, 0]
return: 2
"""
print index_kmp('ababababca', 'abababca', 0)

這裡的程式也是參考的網上的一篇文章

参考的太多了,贴一些列表吧:

這篇先這樣吧,之後再寫一些優化和自動機相關的內容呢。