摘要:寫在最前本次分享一下通過實現算法的動畫效果來試圖展示的基本思路。算法的關鍵是利用匹配失敗后的信息,盡量減少模式串與主串的匹配次數以達到快速匹配的目的。本次主要通過動畫演示的方式展現樸素算法與算法對比過程的異同從而試圖理解的基本思路。
寫在最前
本次分享一下通過實現kmp算法的動畫效果來試圖展示kmp的基本思路。
歡迎關注我的博客,不定期更新中——
前置概念 字符串匹配字符串匹配是計算機科學中最古老、研究最廣泛的問題之一。一個字符串是一個定義在有限字母表∑上的字符序列。例如,ATCTAGAGA是字母表∑ = {A,C,G,T}上的一個字符串。字符串匹配問題就是在一個大的字符串T中搜索某個字符串P的所有出現位置。kmp算法
KMP算法是一種改進的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同時發現,因此人們稱它為克努特——莫里斯——普拉特操作(簡稱KMP算法)。KMP算法的關鍵是利用匹配失敗后的信息,盡量減少模式串與主串的匹配次數以達到快速匹配的目的。具體實現就是實現一個next()函數,函數本身包含了模式串的局部匹配信息。時間復雜度O(m+n)。
在js中字符串匹配我們通常使用的是原生api,indexOf;其本身是c++實現的不在這次的討論范圍中。本次主要通過動畫演示的方式展現樸素算法與kmp算法對比過程的異同從而試圖理解kmp的基本思路。
PS:在之后的敘述中BBC ABCDAB ABCDABCDABDE為主串;ABCDABD為模式串
效果預覽上方為樸素算法即按位比較,下方為kmp算法實現的字符串比較方式。kmp可以通過較少的比較次數完成匹配。
基本思路從上圖的效果預覽中可以看出使用樸素算法依次比較模式串需要移位13次,而使用kmp需要8次,故可以說kmp的思路是通過避免無效的移位,來快速移動到指定的地點。接下來我們關注一下kmp是如何“跳著”移動的:
與樸素算法一致,在之前對于主串“BBC ”的匹配中模式串ABCBABD的第一個字符均與之不同故向后移位到現在上圖所示的位置。主串通過依次與模式串中的字符比較我們可以看出,模式串的前6個字符與主串相同即ABCDAB;而這也就是kmp算法的關鍵。
根據已知信息計算下一次移位位置我們先從下圖來看樸素算法與kmp中下一次移位的過程:
樸素算法雨打不動得向后移了一位。而kmp跳過了主串的BCD三個字符。從而進行了一次避免無意義的移位比較。那么它是怎么知道我這次要跳過三個而不是兩個或者不跳呢?關鍵在于上一次已經匹配的部分ABCDAB
從已匹配部分發掘信息我們已知此時主串與模式串均有此相同的部分ABCDAB。那么如何從這共同部分中獲得有用的信息?或者換個角度想一下:我們能跳過部分位置的依據是什么?
第一次匹配失敗時的情形如下:
BBC ABCDAB ABCDABCDABDE ABCDABD D != 空格 故失敗
為了從已匹配部分提取信息。現在將主串做一下變形:
ABCDABXXXXXX... X可能是任何字符
我們現在只知道已匹配的部分,因為匹配已經失敗了不會再去讀取后面的字符,故用X代替。
那么我們能跳過多少位置的問題就可以由下面的解得知答案:
//ABCDAB向后移動幾位可能能匹配上? ABCDABXXXXXX... ABCDABD
答案自然是如下移動:
ABCDABXXXXXX... ABCDABD
因為我們不知道X代表什么,只能從已匹配的串來分析。
故我們能跳過部分位置的依據是什么?
答:已匹配的模式串的前n位能否等于匹配部分的主串的后n位。并且n盡可能大。
舉個例子:
//第一次匹配失敗時匹配到ABCDDDABC為共同部分 XXXABCDDDABCFXXX ABCDDDABCE //尋找模式串的最大前幾位與主串匹配到的部分后幾位相同, //可以發現最多是ABC部分相同,故可以略過DDD的匹配因為肯定對不上 XXXABCDDDABCFXXX ABCDDDABCE
現在kmp的基本思路已經很明顯了,其就是通過經失敗后得知的已匹配字段,來尋找主串尾部與模式串頭部的相同最大匹配,如果有則可以跨過中間的部分,因為所謂“中間”的部分,也是有可能進入主串尾與模式串頭的,沒進去的原因即是相對位置字符不同,故最終在模式串移位時可以跳過。
部分匹配值上面是用通俗的話來述說我們如何根據已匹配的部分來決定下一次模式串移位的位置,大家應該已經大體知道kmp的思路了。現在來引出官方的說法。
之前敘述的在已匹配部分中查找主串頭部與模式串尾部相同的部分的結果我們可以用部分匹配值的說法來形容:
其中定義"前綴"和"后綴"。"前綴"指除了最后一個字符以外,一個字符串的全部頭部組合;"后綴"指除了第一個字符以外,一個字符串的全部尾部組合。
"部分匹配值"就是"前綴"和"后綴"的最長的共有元素的長度。
例如ABCDAB
前綴分別為A、AB、ABC、ABCD、ABCDA
后綴分別為B、AB、DAB、CDAB、BCDAB
很容易發現部分匹配值為2即AB的長度。從而結合之前的思路可以知道將模式串直接移位到主串AB對應的地方即可,中間的部分一定是不匹配的。移動幾位呢?
答:匹配串長度 - 部分匹配值;本次例子中為6-2=4,模式串向右移動四位
代碼實現 計算部分匹配表function pmtArr(target) { var pmtArr = [] target = target.split("") for(var j = 0; j < target.length; j++) { //獲取模式串不同長度下的部分匹配值 var pmt = target var pmtNum = 0 for (var k = 0; k < j; k++) { var head = pmt.slice(0, k + 1) //前綴 var foot = pmt.slice(j - k, j + 1) //后綴 if (head.join("") === foot.join("")) { var num = head.length if (num > pmtNum) pmtNum = num } } pmtArr.push(j + 1 - pmtNum) } return pmtArr }kmp算法
function mapKMPStr(base, target) { var isMatch = [] var pmt = pmtArr(target) console.time("kmp") var times = 0 for(var i = 0; i < base.length; i++) { times++ var tempIndex = 0 for(var j = 0; j < target.length; j++) { if(i + target.length <= base.length) { if (target.charAt(j) === base.charAt(i + j)) { isMatch.push(target.charAt(j)) } else { if(!j) break //第一個就不匹配直接跳到下一個 var skip = pmt[j - 1] tempIndex = i + skip - 1 break } } } var data = { index: i, matchArr: isMatch } callerKmp.push(data) if(tempIndex) i = tempIndex if(isMatch.length === target.length) { console.timeEnd("kmp") console.log("移位次數:", times) return i } isMatch = [] } console.timeEnd("kmp") return -1
有了思路后整體實現并不復雜,只需要先通過模式串計算各長度的部分匹配值,在之后的與主串的匹配過程中,每失敗一次后如果有部分匹配值存在,我們就可以通過部分匹配值查找到下一次應該移位的位置,省去不必要的步驟。
所以在某些極端情況下,比如需要搜索的詞如果內部完全沒有重復,算法就會退化成遍歷,性能可能還不如傳統算法,里面還涉及了比較的開銷。
參考文章字符串匹配的KMP算法
最后慣例po作者的博客,不定時更新中——
有問題歡迎在issues下交流。
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/92937.html
摘要:字符串的普通模式匹配普通模式匹配的原理不進行說明了,簡單來說就是兩個字符串的每個字符依次進行匹配。 這篇文章主要是介紹KMP模式匹配算法,在正式介紹KMP之前我們先看一下普通模式匹配,由普通模式匹配在進一步的推導KMP模式會更容易理解。 字符串的普通模式匹配 普通模式匹配的原理不進行說明了,簡單來說就是兩個字符串的每個字符依次進行匹配。 public int match(String ...
摘要:第一種方法常規方法。如果不存在公共前綴,返回空字符串。注意假設字符串的長度不會超過。說明本題中,我們將空字符串定義為有效的回文串。示例輸入輸出一個可能的最長回文子序列為。數值為或者字符串不是一個合法的數值則返回。 說明 本文作者:wwwxmu 原文地址:https://www.weiweiblog.cn/13s... 作者的博客站點:https://www.weiweiblog.c...
摘要:樸素的模式匹配算法這種算法又被稱為暴力匹配算法。如果匹配失敗,則回溯到主串的下一個位置重新逐位匹配。當然,在匹配算法中不同的輸入會有不同的復雜度,最好的情況就是一開始就匹配成功。切入結束,下篇詳解匹配算法 最近在看關于算法方面的,正好看到關于KMP算法相關的部分,這里就做一個總結。假設我們有這樣的一個主串 S = googlgomglegoogle 和一個子串 C = google 我...
閱讀 2269·2021-11-23 09:51
閱讀 5657·2021-09-22 15:39
閱讀 3343·2021-09-02 15:15
閱讀 3493·2019-08-30 15:54
閱讀 2355·2019-08-30 15:53
閱讀 1397·2019-08-30 14:04
閱讀 2445·2019-08-29 18:33
閱讀 2364·2019-08-29 13:08