JavaScript中數(shù)據(jù)結構與算法(五)：經典KMP算法
KMP算法和BM算法
KMP是前綴匹配和BM后綴匹配的經典算法，看得出來前綴匹配和后綴匹配的區(qū)別就僅僅在于比較的順序不同
前綴匹配是指：模式串和母串的比較從左到右，模式串的移動也是從 左到右
后綴匹配是指：模式串和母串的的比較從右到左，模式串的移動從左到右。
通過上一章顯而易見BF算法也是屬于前綴的算法，不過就非常霸蠻的逐個匹配的效率自然不用提了O(mn)，網上蛋疼的KMP是講解很多，基本都是走的高大上路線看的你也是一頭霧水，我試圖用自己的理解用最接地氣的方式描述
KMP
KMP也是一種優(yōu)化版的前綴算法，之所以叫KMP就是Knuth、Morris、Pratt三個人名的縮寫，對比下BF那么KMP的算法的優(yōu)化點就在“每次往后移動的距離”它會動態(tài)的調整每次模式串的移動距離，BF是每次都+1，
KMP則不一定
如圖BF與KMP前置算法的區(qū)別對比
我通過圖對比我們發(fā)現(xiàn)：
在文本串T中搜索模式串P，在自然匹配第6個字母c的時候發(fā)現(xiàn)二等不一致了，那么BF的方法，就是把整個模式串P移動一位，KMP則是移動二位.
BF的匹配方法我們是知道的，但是KMP為什么會移動二位，而不是一位或者三位四位呢？
這就上一張圖我們講解下，模式串P在匹配了ababa的時候都是正確的，當?shù)絚的時候才是錯誤，那么KMP算法的想法是：ababa是正確的匹配完成的信息，我們能不能利用這個信息，不要把"搜索位置"移回已經比較過的位置，繼續(xù)把它向后移，這樣就提高了效率。
那么問題來了, 我怎么知道要移動多少個位置？
這個偏移的算法KMP的作者們就給我們總結好了：
移動位數(shù) = 已匹配的字符數(shù) - 對應的部分匹配值
偏移算法只跟子串有關系，沒文本串沒毛線關系，所以這里需要特別注意了
那么我們怎么理解子串中已匹配的字符數(shù)與對應的部分匹配值？
已匹配的字符：
T : abababaabab
p : ababacb
p中紅色的標記就是已經匹配的字符，這個很好理解
部分匹配值：
這個就是核心的算法了，也是比較難于理解的
假如：
T：aaronaabbcc
P：aaronaac
我們可以觀察這個文本如果我們在匹配c的時候出錯，我們下一個移動的位置就上個的結構來講，移動到那里最合理？
aaronaabbcc
aaronaac
那么就是說：在模式文本內部，某一段字符頭尾都一樣，那么自然過濾的時候可以跳過這一段內容了，這個思路也是合理的
知道了這個規(guī)律，那么給出來的部分匹配表算法如下：
首先，要了解兩個概念："前綴"和"后綴"。 "前綴"指除了最后一個字符以外，一個字符串的全部頭部組合；"后綴"指除了第一個字符以外，一個字符串的全部尾部組合。
"部分匹配值"就是"前綴"和"后綴"的最長的共有元素的長度”
我們看看aaronaac的如果是BF匹配的時候劃分是這樣的
BF的位移: a,aa,aar,aaro,aaron,aarona,aaronaa,aaronaac
那么KMP的劃分呢？這里就要引入前綴與后綴了
我們先看看KMP部分匹配表的結果是這樣的：
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
移動的位置：其實就是針對每一個已匹配的字符做前綴與后綴的對比是否相等，然后算出共有的長度
部分匹配表的分解
KMP中的匹配表的算法，其中p表示前綴，n表示后綴，r表示結果
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算法一下，先分解每一次可能匹配的下標的位置先緩存起來，在匹配的時候通過這個《部分匹配表》來定位需要后移動的位數(shù)
所以最后aaronaac的匹配表的結果 0,1,0,0,0,1,2,0 就是這么來的
下面將會實現(xiàn)JS版的KMP，有2種
KMP實現(xiàn)（一）：緩存匹配表的KMP
KMP實現(xiàn)（二）：動態(tài)計算next的KMP
KMP實現(xiàn)（一）
匹配表
KMP算法中最重要的就是匹配表，如果不要匹配表那就是BF的實現(xiàn)，加上匹配表就是KMP了
匹配表決定了next下一個位移的計數(shù)
針對上面匹配表的規(guī)律，我們設計一個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);
//如果相等就計算大小,并放入結果集中
if (prefix[k] == suffix[k]) {
partMatch[i] = prefix[k].length;
}
}
if (!partMatch[i]) {
partMatch[i] = 0;
}
}
}
return partMatch;
}
完全按照KMP中的匹配表的算法的實現(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++是用來增加主串的下標位
i++;
}
} else {
//在子串的匹配中i是被疊加了
if (j > 1 && part[j - 1] > 0) {
i += (i - j - part[j - 1]);
} else {
//移動一位
i = (i - j)
}
break;
}
}
紅色標記的就是KMP的核心點 next的值 = 已匹配的字符數(shù) - 對應的部分匹配值
完整的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++是用來增加主串的下標位
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)在等于只要挑其中的一條就可以了，那么只要算法定位到當然的匹配即可
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;
}
其實跟匹配表是一樣的，去掉了循環(huán)直接定位到當前已成功匹配的串了
完整的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++是用來增加主串的下標位
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>
相關文章
這篇文章主要介紹了url中的特殊符號有什么含義(推薦)的相關資料,需要的朋友可以參考下2016-06-06
這篇文章主要為大家詳細介紹了js實現(xiàn)網頁音樂播放器，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-06-06
本篇文章主要介紹了JS異步加載的三種實現(xiàn)方式，有些時候我們需要JS異步加載，這里整理了詳細的代碼,有需要的小伙伴可以參考下。2017-03-03
這篇文章主要介紹了JS保留兩位小數(shù) 四舍五入函數(shù)的小例子，有需要的朋友可以參考一下2013-11-11
詰屈聱牙之javascript中國象棋...2007-04-04
lazyload.js用于長頁面圖片的延遲加載，視口外的圖片會在窗口滾動到它的位置時再進行加載，這是與預加載相反的，這篇文章主要介紹了lazyload.js詳解,需要的朋友可以參考下2022-09-09
大部分小程序都會有這樣的需求，頁面有長列表，需要下拉到底時請求后臺數(shù)據(jù)，一直渲染數(shù)據(jù)，當數(shù)據(jù)列表長時，會發(fā)現(xiàn)明顯的卡頓，頁面白屏閃頓現(xiàn)象，那么如何實現(xiàn)小程序虛擬列表，感興趣的可以了解一下2021-07-07
本篇文章給詳細講解了9個JavaScript圖表庫以及用法，需要的朋友參考學習下。2017-12-12
詳解微信圖片防盜鏈“此圖片來自微信公眾平臺 未經允許不得引用”的解決方案
這篇文章主要介紹了詳解微信圖片防盜鏈“此圖片來自微信公眾平臺 未經允許不得引用”的解決方案，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2019-04-04
這篇文章主要為大家介紹了Babylon使用麥克風并處理常見問題解決，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-04-04