JavaScript中資料結構與演算法(五)：經典KMP演算法_javascript技巧
KMP演算法與BM演算法
KMP是前綴匹配和BM後綴匹配的經典演算法，看得出來前綴匹配和後綴匹配的區別就僅僅在於比較的順序不同
前綴匹配是指：模式串和母串的比較從左到右，模式串的移動也是從 左到右
後綴匹配是指：模式串和母串的比較從右到左，模式串的移動從左到右。
透過上一章顯而易見BF演算法也是屬於前綴的演算法，不過就非常霸蠻的逐個配對的效率自然不用提了O(mn)，網路上蛋疼的KMP是講解很多，基本上都是走的高大上路線看的你也是一頭霧水，我試著用自己的理解用最接地氣的方式描述
KMP
KMP也是一種最佳化版的前綴演算法，之所以叫KMP就是Knuth、Morris、Pratt三個人名的縮寫，對比下BF那麼KMP的演算法的最佳化點就在“每次往後移動的距離”它會動態的調整每次模式串的移動距離，BF是每次都1，
KMP則不一定
如圖BF與KMP前置演算法的差異比較
我透過圖對比我們發現：
在文字串T中搜尋模式串P，在自然匹配第6個字母c的時候發現二等不一致了，那麼BF的方法，就是把整個模式串P移動一位，KMP則是移動二位.
BF的配對方法我們是知道的，但是KMP為什麼會移動二位，而不是一位或三位四位呢？
這就上一張圖我們講解下，模式串P在匹配了ababa的時候都是正確的，當到c的時候才是錯誤，那麼KMP算法的想法是：ababa是正確的匹配完成的訊息，我們能不能利用這個訊息，不要把"搜尋位置"移回已經比較過的位置，繼續把它向後移，這樣就提高了效率。
那麼問題來了, 我怎麼知道要移動多少個位置？
這個偏移的演算法KMP的作者們就給我們總結好了：
移動位數 = 已匹配的字元數 - 對應的部分匹配值
偏移演算法只跟子字串有關係，沒文字串沒毛線關係，所以這裡要特別注意了
那我們怎麼理解子字串中已匹配的字元數與對應的部分匹配值？
已匹配的字元：
T : abababaabab
p : ababacb
p中紅色的標記就是已經匹配的字符，這個很好理解
部分匹配值：
這個就是核心的演算法了，也是比較難於理解的
假如：
T：aaronaabbcc
P：aaronaac
我們可以觀察這個文本如果我們在匹配c的時候出錯，我們下一個移動的位置就上個的結構來講，移動到那裡最合理？
aaronaabbcc
aaronaac
那麼就是說：在模式文本內部，某一段字符頭尾都一樣，那麼自然過濾的時候可以跳過這一段內容了，這個思路也是合理的
知道了這個規律，那麼給出來的部分匹配表演算法如下：
首先，要了解兩個概念："前綴"和"後綴"。 "字首"指除了最後一個字元以外，一個字串的全部頭部組合；"後綴"指除了第一個字元以外，一個字串的全部尾部組合。
"部分匹配值"就是"前綴"和"後綴"的最長的共有元素的長度」
我們來看看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演算法一下，先分解每一次可能匹配的下標的位置先緩存起來，在匹配的時候通過這個《部分匹配表》來定位需要後移動的位數
所以最後aaronaac的配對表的結果 0,1,0,0,0,1,2,0 就是這麼來的
以下將會實現JS版的KMP，有2種
KMP實作（一）：快取匹配表的KMP
KMP實作（二）：動態計算next的KMP
KMP實作（一）
匹配表
KMP演算法中最重要的就是匹配表，如果不要匹配表那就是BF的實現，加上匹配表就是KMP了
匹配表決定了next下一個位移的計數
針對上面匹配表的規律，我們設計一個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中的匹配表的演算法的實現，透過str.substring(0, i 1) 分解a->aa->aar->aaro->aaron->aarona->aaronaa-aaronaac
然後在每一個分解中透過前綴後綴算出共有元素的長度
回退演算法
KMP也是前置演算法，完全可以把BF那一套搬過來，唯一修改的地方就是BF回溯的時候直接是加1，KMP在回溯的時候我們就透過配對表算出這個next值即可
//子循环
for (var j = 0; j < searchLength; j++) {
//如果与主串匹配
if (searchStr.charAt(j) == sourceStr.charAt(i)) {
//如果是匹配完成
if (j == searchLength - 1) {
result = i - j;
break;
} else {
//如果匹配到了，就继续循环，i++是用来增加主串的下标位
i++;
}
} else {
//在子串的匹配中i是被叠加了
if (j > 1 && part[j - 1] > 0) {
i += (i - j - part[j - 1]);
} else {
//移动一位
i = (i - j)
}
break;
}
}
紅色標記的就是KMP的核心點 next的值 = 已匹配的字元數 - 對應的部分匹配值
完整的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++) { //最外层循环，主串
//子循环
for (var j = 0; j < searchLength; j++) {
//如果与主串匹配
if (searchStr.charAt(j) == sourceStr.charAt(i)) {
//如果是匹配完成
if (j == searchLength - 1) {
result = i - j;
break;
} else {
//如果匹配到了，就继续循环，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的算法很明显，是通过缓存查找匹配表也就是常见的空间换时间了。那么另一种就是时时查找的算法，通过传递一个具体的完成字符串，算出这个匹配值出来，原理都一样
生成缓存表的时候是整体全部算出来的，我们现在等于只要挑其中的一条就可以了，那么只要算法定位到当然的匹配即可
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;
}
其实跟匹配表是一样的，去掉了循环直接定位到当前已成功匹配的串了
完整的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++) { //最外层循环，主串
//子循环
for (var j = 0; j < searchLength; j++) {
//如果与主串匹配
if (searchStr.charAt(j) == sourceStr.charAt(i)) {
//如果是匹配完成
if (j == searchLength - 1) {
result = i - j;
break;
} else {
//如果匹配到了，就继续循环，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>
熱AI工具
Undresser.AI Undress
人工智慧驅動的應用程序，用於創建逼真的裸體照片
AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。
Undress AI Tool
免費脫衣圖片
Clothoff.io
AI脫衣器
Video Face Swap
使用我們完全免費的人工智慧換臉工具，輕鬆在任何影片中換臉！
熱門文章
熱工具
記事本++7.3.1
好用且免費的程式碼編輯器
SublimeText3漢化版
中文版，非常好用
禪工作室 13.0.1
強大的PHP整合開發環境
Dreamweaver CS6
視覺化網頁開發工具
SublimeText3 Mac版
神級程式碼編輯軟體(SublimeText3)
熱門話題
使用C++實現機器學習演算法：常見挑戰及解決方案
Jun 03, 2024 pm 01:25 PM
C++中機器學習演算法面臨的常見挑戰包括記憶體管理、多執行緒、效能最佳化和可維護性。解決方案包括使用智慧指標、現代線程庫、SIMD指令和第三方庫，並遵循程式碼風格指南和使用自動化工具。實作案例展示如何利用Eigen函式庫實現線性迴歸演算法，有效地管理記憶體和使用高效能矩陣操作。
探究C++sort函數的底層原理與演算法選擇
Apr 02, 2024 pm 05:36 PM
C++sort函數底層採用歸併排序，其複雜度為O(nlogn)，並提供不同的排序演算法選擇，包括快速排序、堆排序和穩定排序。
使用Java函數比較進行複雜資料結構比較
Apr 19, 2024 pm 10:24 PM
Java中比較複雜資料結構時，使用Comparator提供靈活的比較機制。具體步驟包括：定義比較器類，重寫compare方法定義比較邏輯。建立比較器實例。使用Collections.sort方法，傳入集合和比較器實例。
改進的檢測演算法：用於高解析度光學遙感影像目標檢測
Jun 06, 2024 pm 12:33 PM
01前景概要目前，難以在檢測效率和檢測結果之間取得適當的平衡。我們研究了一種用於高解析度光學遙感影像中目標偵測的增強YOLOv5演算法，利用多層特徵金字塔、多重偵測頭策略和混合注意力模組來提高光學遙感影像的目標偵測網路的效果。根據SIMD資料集，新演算法的mAP比YOLOv5好2.2%，比YOLOX好8.48%，在偵測結果和速度之間達到了更好的平衡。 02背景&動機隨著遠感技術的快速發展，高解析度光學遠感影像已被用於描述地球表面的許多物體，包括飛機、汽車、建築物等。目標檢測在遠感影像的解釋中
Java資料結構與演算法：深入詳解
May 08, 2024 pm 10:12 PM
資料結構與演算法是Java開發的基礎，本文深入探討Java中的關鍵資料結構（如陣列、鍊錶、樹等）和演算法（如排序、搜尋、圖演算法等）。這些結構透過實戰案例進行說明，包括使用陣列儲存分數、使用鍊錶管理購物清單、使用堆疊實現遞歸、使用佇列同步執行緒以及使用樹和雜湊表進行快速搜尋和身份驗證等。理解這些概念可以編寫高效且可維護的Java程式碼。
演算法在 58 畫像平台建置中的應用
May 09, 2024 am 09:01 AM
一、58畫像平台建置背景首先和大家分享下58畫像平台的建造背景。 1.傳統的畫像平台傳統的想法已經不夠，建立用戶畫像平台依賴數據倉儲建模能力，整合多業務線數據，建構準確的用戶畫像；還需要數據挖掘，理解用戶行為、興趣和需求，提供演算法側的能力；最後，還需要具備數據平台能力，有效率地儲存、查詢和共享用戶畫像數據，提供畫像服務。業務自建畫像平台和中台類型畫像平台主要區別在於，業務自建畫像平台服務單條業務線，按需定制；中台平台服務多條業務線，建模複雜，提供更為通用的能力。 2.58中台畫像建構的背景58的使用者畫像
PHP資料結構：AVL樹的平衡之道，維持高效有序的資料結構
Jun 03, 2024 am 09:58 AM
AVL樹是一種平衡二元搜尋樹，確保快速且有效率的資料操作。為了實現平衡，它執行左旋和右旋操作，調整違反平衡的子樹。 AVL樹利用高度平衡，確保樹的高度相對於節點數始終較小，從而實現對數時間複雜度(O(logn))的查找操作，即使在大型資料集上也能保持資料結構的效率。
基於全域的圖增強的新聞推薦演算法
Apr 08, 2024 pm 09:16 PM
作者|汪昊審校|重樓新聞App是人們日常生活中獲取資訊來源的重要方式。在2010年左右，國外比較火的新聞App包括Zite和Flipboard等，而國內比較火的新聞App主要是四大門戶。而隨著今日頭條為代表的新時代新聞推薦產品的火爆，新聞App進入了全新的時代。而科技公司，不管哪一家，只要掌握了高精尖的新聞推薦演算法技術，就基本在技術層面掌握了主動權和話語權。今天，我們來看看RecSys2023的最佳長篇論文提名獎論文－GoingBeyondLocal:GlobalGraph-EnhancedP
