JavaScript中數(shù)據(jù)結(jié)構(gòu)與算法(五):經(jīng)典KMP算法
KMP算法和BM算法
KMP是前綴匹配和BM后綴匹配的經(jīng)典算法,看得出來前綴匹配和后綴匹配的區(qū)別就僅僅在于比較的順序不同
前綴匹配是指:模式串和母串的比較從左到右,模式串的移動也是從 左到右
后綴匹配是指:模式串和母串的的比較從右到左,模式串的移動從左到右。
通過上一章顯而易見BF算法也是屬于前綴的算法,不過就非常霸蠻的逐個匹配的效率自然不用提了O(mn),網(wǎng)上蛋疼的KMP是講解很多,基本都是走的高大上路線看的你也是一頭霧水,我試圖用自己的理解用最接地氣的方式描述
KMP
KMP也是一種優(yōu)化版的前綴算法,之所以叫KMP就是Knuth、Morris、Pratt三個人名的縮寫,對比下BF那么KMP的算法的優(yōu)化點(diǎn)就在“每次往后移動的距離”它會動態(tài)的調(diào)整每次模式串的移動距離,BF是每次都+1,
KMP則不一定
如圖BF與KMP前置算法的區(qū)別對比
我通過圖對比我們發(fā)現(xiàn):
在文本串T中搜索模式串P,在自然匹配第6個字母c的時候發(fā)現(xiàn)二等不一致了,那么BF的方法,就是把整個模式串P移動一位,KMP則是移動二位.
BF的匹配方法我們是知道的,但是KMP為什么會移動二位,而不是一位或者三位四位呢?
這就上一張圖我們講解下,模式串P在匹配了ababa的時候都是正確的,當(dāng)?shù)絚的時候才是錯誤,那么KMP算法的想法是:ababa是正確的匹配完成的信息,我們能不能利用這個信息,不要把"搜索位置"移回已經(jīng)比較過的位置,繼續(xù)把它向后移,這樣就提高了效率。
那么問題來了, 我怎么知道要移動多少個位置?
這個偏移的算法KMP的作者們就給我們總結(jié)好了:
移動位數(shù) = 已匹配的字符數(shù) - 對應(yīng)的部分匹配值
偏移算法只跟子串有關(guān)系,沒文本串沒毛線關(guān)系,所以這里需要特別注意了
那么我們怎么理解子串中已匹配的字符數(shù)與對應(yīng)的部分匹配值?
已匹配的字符:
T : abababaabab
p : ababacb
p中紅色的標(biāo)記就是已經(jīng)匹配的字符,這個很好理解
部分匹配值:
這個就是核心的算法了,也是比較難于理解的
假如:
T:aaronaabbcc
P:aaronaac
我們可以觀察這個文本如果我們在匹配c的時候出錯,我們下一個移動的位置就上個的結(jié)構(gòu)來講,移動到那里最合理?
aaronaabbcc
aaronaac
那么就是說:在模式文本內(nèi)部,某一段字符頭尾都一樣,那么自然過濾的時候可以跳過這一段內(nèi)容了,這個思路也是合理的
知道了這個規(guī)律,那么給出來的部分匹配表算法如下:
首先,要了解兩個概念:"前綴"和"后綴"。 "前綴"指除了最后一個字符以外,一個字符串的全部頭部組合;"后綴"指除了第一個字符以外,一個字符串的全部尾部組合。
"部分匹配值"就是"前綴"和"后綴"的最長的共有元素的長度”
我們看看aaronaac的如果是BF匹配的時候劃分是這樣的
BF的位移: a,aa,aar,aaro,aaron,aarona,aaronaa,aaronaac
那么KMP的劃分呢?這里就要引入前綴與后綴了
我們先看看KMP部分匹配表的結(jié)果是這樣的:
a a r o n a a c
[0, 1, 0, 0, 0, 1, 2, 0]
肯定是一頭霧水,不急我們分解下,前綴與后綴
匹配字符串 :“Aaron”
前綴:A,Aa, Aar ,Aaro
后綴:aron,ron,on,n
移動的位置:其實(shí)就是針對每一個已匹配的字符做前綴與后綴的對比是否相等,然后算出共有的長度
部分匹配表的分解
KMP中的匹配表的算法,其中p表示前綴,n表示后綴,r表示結(jié)果
a, p=>0, n=>0 r = 0
aa, p=>[a],n=>[a] , r = a.length => 1
aar, p=>[a,aa], n=>[r,ar] ,r = 0
aaro, p=>[a,aa,aar], n=>[o,ra,aro] ,r = 0
aaron p=>[a,aa,aar,aaro], n=>[n,on,ron,aron] ,r = 0
aarona, p=>[a,aa,aar,aaro,aaron], n=>[a,na,ona,rona,arona] ,r = a.lenght = 1
aaronaa, p=>[a,aa,aar,aaro,aaron,aarona], n=>[a,aa,naa,onaa,ronaa,aronaa] , r = Math.max(a.length,aa.length) = 2
aaronaac p=>[a,aa,aar,aaro,aaron,aarona], n=>[c,ac,aac,naac,onaac,ronaac] r = 0
類似BF算法一下,先分解每一次可能匹配的下標(biāo)的位置先緩存起來,在匹配的時候通過這個《部分匹配表》來定位需要后移動的位數(shù)
所以最后aaronaac的匹配表的結(jié)果 0,1,0,0,0,1,2,0 就是這么來的
下面將會實(shí)現(xiàn)JS版的KMP,有2種
KMP實(shí)現(xiàn)(一):緩存匹配表的KMP
KMP實(shí)現(xiàn)(二):動態(tài)計(jì)算next的KMP
KMP實(shí)現(xiàn)(一)
匹配表
KMP算法中最重要的就是匹配表,如果不要匹配表那就是BF的實(shí)現(xiàn),加上匹配表就是KMP了
匹配表決定了next下一個位移的計(jì)數(shù)
針對上面匹配表的規(guī)律,我們設(shè)計(jì)一個kmpGetStrPartMatchValue的方法
function kmpGetStrPartMatchValue(str) { var prefix = []; var suffix = []; var partMatch = []; for (var i = 0, j = str.length; i < j; i++) { var newStr = str.substring(0, i + 1); if (newStr.length == 1) { partMatch[i] = 0; } else { for (var k = 0; k < i; k++) { //前綴 prefix[k] = newStr.slice(0, k + 1); //后綴 suffix[k] = newStr.slice(-k - 1); //如果相等就計(jì)算大小,并放入結(jié)果集中 if (prefix[k] == suffix[k]) { partMatch[i] = prefix[k].length; } } if (!partMatch[i]) { partMatch[i] = 0; } } } return partMatch; }
完全按照KMP中的匹配表的算法的實(shí)現(xiàn),通過str.substring(0, i + 1) 分解a->aa->aar->aaro->aaron->aarona->aaronaa-aaronaac
然后在每一個分解中通過前綴后綴算出共有元素的長度
回退算法
KMP也是前置算法,完全可以把BF那一套搬過來,唯一修改的地方就是BF回溯的時候直接是加1,KMP在回溯的時候我們就通過匹配表算出這個next值即可
//子循環(huán) for (var j = 0; j < searchLength; j++) { //如果與主串匹配 if (searchStr.charAt(j) == sourceStr.charAt(i)) { //如果是匹配完成 if (j == searchLength - 1) { result = i - j; break; } else { //如果匹配到了,就繼續(xù)循環(huán),i++是用來增加主串的下標(biāo)位 i++; } } else { //在子串的匹配中i是被疊加了 if (j > 1 && part[j - 1] > 0) { i += (i - j - part[j - 1]); } else { //移動一位 i = (i - j) } break; } }
紅色標(biāo)記的就是KMP的核心點(diǎn) next的值 = 已匹配的字符數(shù) - 對應(yīng)的部分匹配值
完整的KMP算法
<!doctype html><div id="test2"><div><script type="text/javascript"> function kmpGetStrPartMatchValue(str) { var prefix = []; var suffix = []; var partMatch = []; for (var i = 0, j = str.length; i < j; i++) { var newStr = str.substring(0, i + 1); if (newStr.length == 1) { partMatch[i] = 0; } else { for (var k = 0; k < i; k++) { //取前綴 prefix[k] = newStr.slice(0, k + 1); suffix[k] = newStr.slice(-k - 1); if (prefix[k] == suffix[k]) { partMatch[i] = prefix[k].length; } } if (!partMatch[i]) { partMatch[i] = 0; } } } return partMatch; } function KMP(sourceStr, searchStr) { //生成匹配表 var part = kmpGetStrPartMatchValue(searchStr); var sourceLength = sourceStr.length; var searchLength = searchStr.length; var result; var i = 0; var j = 0; for (; i < sourceStr.length; i++) { //最外層循環(huán),主串 //子循環(huán) for (var j = 0; j < searchLength; j++) { //如果與主串匹配 if (searchStr.charAt(j) == sourceStr.charAt(i)) { //如果是匹配完成 if (j == searchLength - 1) { result = i - j; break; } else { //如果匹配到了,就繼續(xù)循環(huán),i++是用來增加主串的下標(biāo)位 i++; } } else { //在子串的匹配中i是被疊加了 if (j > 1 && part[j - 1] > 0) { i += (i - j - part[j - 1]); } else { //移動一位 i = (i - j) } break; } } if (result || result == 0) { break; } } if (result || result == 0) { return result } else { return -1; } } var s = "BBC ABCDAB ABCDABCDABDE"; var t = "ABCDABD"; show('indexOf',function() { return s.indexOf(t) }) show('KMP',function() { return KMP(s,t) }) function show(bf_name,fn) { var myDate = +new Date() var r = fn(); var div = document.createElement('div') div.innerHTML = bf_name +'算法,搜索位置:' + r + ",耗時" + (+new Date() - myDate) + "ms"; document.getElementById("test2").appendChild(div); } </script></div></div>
KMP(二)
第一種kmp的算法很明顯,是通過緩存查找匹配表也就是常見的空間換時間了。那么另一種就是時時查找的算法,通過傳遞一個具體的完成字符串,算出這個匹配值出來,原理都一樣
生成緩存表的時候是整體全部算出來的,我們現(xiàn)在等于只要挑其中的一條就可以了,那么只要算法定位到當(dāng)然的匹配即可
next算法
function next(str) { var prefix = []; var suffix = []; var partMatch; var i = str.length var newStr = str.substring(0, i + 1); for (var k = 0; k < i; k++) { //取前綴 prefix[k] = newStr.slice(0, k + 1); suffix[k] = newStr.slice(-k - 1); if (prefix[k] == suffix[k]) { partMatch = prefix[k].length; } } if (!partMatch) { partMatch = 0; } return partMatch; }
其實(shí)跟匹配表是一樣的,去掉了循環(huán)直接定位到當(dāng)前已成功匹配的串了
完整的KMP.next算法
<!doctype html><div id="testnext"><div><script type="text/javascript"> function next(str) { var prefix = []; var suffix = []; var partMatch; var i = str.length var newStr = str.substring(0, i + 1); for (var k = 0; k < i; k++) { //取前綴 prefix[k] = newStr.slice(0, k + 1); suffix[k] = newStr.slice(-k - 1); if (prefix[k] == suffix[k]) { partMatch = prefix[k].length; } } if (!partMatch) { partMatch = 0; } return partMatch; } function KMP(sourceStr, searchStr) { var sourceLength = sourceStr.length; var searchLength = searchStr.length; var result; var i = 0; var j = 0; for (; i < sourceStr.length; i++) { //最外層循環(huán),主串 //子循環(huán) for (var j = 0; j < searchLength; j++) { //如果與主串匹配 if (searchStr.charAt(j) == sourceStr.charAt(i)) { //如果是匹配完成 if (j == searchLength - 1) { result = i - j; break; } else { //如果匹配到了,就繼續(xù)循環(huán),i++是用來增加主串的下標(biāo)位 i++; } } else { if (j > 1) { i += i - next(searchStr.slice(0,j)); } else { //移動一位 i = (i - j) } break; } } if (result || result == 0) { break; } } if (result || result == 0) { return result } else { return -1; } } var s = "BBC ABCDAB ABCDABCDABDE"; var t = "ABCDAB"; show('indexOf',function() { return s.indexOf(t) }) show('KMP.next',function() { return KMP(s,t) }) function show(bf_name,fn) { var myDate = +new Date() var r = fn(); var div = document.createElement('div') div.innerHTML = bf_name +'算法,搜索位置:' + r + ",耗時" + (+new Date() - myDate) + "ms"; document.getElementById("testnext").appendChild(div); } </script></div></div>
相關(guān)文章
5個javascript的數(shù)字格式化函數(shù)分享
Javascript沒有任何內(nèi)建的格式化函數(shù),這里我們通過Google收集了5個javascript的數(shù)字格式化函數(shù),希望對于大家的web開發(fā)能夠帶來方便2011-12-12JavaScript重復(fù)元素處理方法分析【統(tǒng)計(jì)個數(shù)、計(jì)算、去重復(fù)等】
這篇文章主要介紹了JavaScript重復(fù)元素處理方法,結(jié)合實(shí)例形式分析了javascript針對字符串、數(shù)組中重復(fù)元素的個數(shù)統(tǒng)計(jì),計(jì)算及去重復(fù)等相關(guān)操作技巧,需要的朋友可以參考下2017-12-12webpack dll打包重復(fù)問題優(yōu)化的解決
在使用dll plugin過程中出現(xiàn)的一個包依賴問題,這個問題導(dǎo)致打出來的包會包含重復(fù)的代碼。這篇文章主要介紹了webpack dll打包重復(fù)問題優(yōu)化的解決,感興趣的小伙伴們可以參考一下2018-10-10基于HTML+JavaScript實(shí)現(xiàn)中國象棋
這篇文章主要為大家詳細(xì)介紹了如何利用HTML+CSS+JS實(shí)現(xiàn)中國象棋游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下2022-08-08