克努斯-莫里斯-普拉特演算法(KMP Algorithm)


「克努斯-莫里斯-普拉特演算法(Knuth–Morris–Pratt algorithm / KMP algorithm)」是一種字串搜尋演算法(string-searching algorithm),可用來在一長串文字中,尋找特定字串。


匹配陣列(PS Array)

用來比較一字串中的內容重複出現的程度;在比較兩字串時,若兩字串不相符,匹配陣列(PS Array)可協助將比較的字串往後移。

在生成「PS Array」時,會將一索引值對應的內容與前面的內容相較,重複出現的內容越長,則「PS Array」累加的數字越高,例如生成「棗子(jujube)」這個單字的「PS Array」時,結果為 001200,過程如下:

第一輪:n=0、i=1,預設索引值 0 處的「PS Array」值為 0:

第二輪:n=0、i=2:

第三輪:n=1、i=3:

第四輪:n=2、i=4:

第五輪:n=0、i=5:

為了要將該字串與其他字串配對比較,須將「PS Array」全部往右移動一個索引值,原本索引值為 0 對應的陣列值則先改成「?」,稍後將回頭說明這個「?」應該填什麼數字。

當「jujube」這個字串要拿去跟其他字串比較,若兩字串出現不同的內容,將「jujube」往右移動的格數,即為另一字串比較處的索引值減去「jujube」在「PS Array」中的數字。

「PS Array」功能演示:範例一

若將「jujube」與「jujuju」比較,則當「jujube」的第二個「j」對應到「jujuju」的第三個「j」時,兩者內容不同,則將「jujube」往右移動的格數就是「jujuju」的第三個「j」的索引值 4 減去「jujube」第二個「j」的「PS Array」值 2,一共要移動兩格:

移動後進行下一輪比較時,兩字串相對位置如下:

「PS Array」功能演示:範例二

現在將「jujube」與同義詞「jujuba」比較,則當「jujube」的最後一個字母「e」對到「jujuba」的最後一個字母「a」時,兩者才不相同,「jujube」要往右移動的格數相當於「jujuba」中「a」的索引值 5 扣除「jujube」的「e」對應「PS Array」的值 0,等於要一次移動五格。

移動後,兩字串相對位置如下:

由上述比較可以發現,有了「PS Array」輔助,字串右移的幅度變大,已經比較過、確定不會相同的部分都不會重複比較,比一格一格往右移快速許多。

「PS Array」第一個值

最後,讓我們來將「PS Array」字串中的問號填上正確數字。如果第一個字就不一樣,代表整個字串要往右移動一格,此時另一字串的索引值要扣掉多少,結果才會為 1 呢?

答案是 (-1),實際運算過程如下:

最後可推得「jujube」的「PS Array」如下:

在任何的字串中,因為只要第一格內容相異就必會往右邊移動一格,因此「PS Array」的第一項必為 (-1)。


克努斯-莫里斯-普拉特演算法(KMP Algorithm)

在這個演算法中,共有下列幾個值:

  1. String1:欲搜尋的範圍,可擴大至一篇文章、一頁網站等。
  2. String2:欲尋找的字串。
  3. 指標:「i」指向「String1」內容、「j」指向「String2」內容。
  4. Counter:表示「String2」出現在「String1」的次數。

若兩字串指標的內容不同,就將「i」移動「i-PS[j]」格、「j」退回 0,相當於把整個「String2」往右移動「i-PS[j]」格後再開始比較。

現假設要在「take jujube jujas」中尋找「jujube」字串,KMP 演算法程圖示如下:

上述步驟中,「i」跟「j」對應到的內容都不一樣,因此只要將「String1」的「i」指標持續往右移動即可,也就是把「String2」一格一格往右移。

在下面的步驟中,「i」的內容開始與「String2」的「j」匹配,因此「j」指標也會往右移動,但「String2」本身留在原位,直到兩匹配資料內容不同、或比較完整個「String2」後發現該字串的內容完整出現在「String1」為止。

當「j」指標完整走過「String2」後,發現「String1」中有完全相同的內容,因此將「Counter」加上 1,代表在「String1」中找到一組「String2」。

一樣將「String2」的「j」指標所在處往右移動到對齊「String1」的「i」指標處。

接著重複一樣的比較流程:若無匹配內容則持續將「String2」隨著「i」往右移;若有匹配內容則讓「String2」留在原處與「String1」比較,直到兩字串內容不同、或又在「String1」中找到完整的「String2」為止。

「i」指標移到第 15 項時,發現與「j」指標內容不同,因此將「i」指標換到「i-PS[j]」處,索引值為 14。

「i」指標看似往前移動,實際上代表將「String2」第 0 項對到「String1」第 14 項進行比較,此時「i」與「j」兩指標內容不同,因此重複上述右移流程。

在上面的步驟中,「i」看似留在原地,其實代表「String2」又往右移動一格。

兩指標內容不同,因此持續將「i」指標往右移動。

當「i」指標超出「String1」長度時,跳出迴圈,比較停止。

最終的「Counter」為 1,代表在「String1」中,找到一個「String2」字串。

#演算法 #KMP演算法







你可能感興趣的文章

【THM Walkthrough】Breaching Active Directory

【THM Walkthrough】Breaching Active Directory

0 - 0.5 的實體伺服器架設

0 - 0.5 的實體伺服器架設

[ JS101] JavaScript 運算

[ JS101] JavaScript 運算






留言討論