KMP-Algorithmus und BM-Algorithmus
KMP ist ein klassischer Algorithmus für den Präfixabgleich und den BM-Suffixabgleich. Es ist ersichtlich, dass der Unterschied zwischen Präfixabgleich und Suffixabgleich nur in der Vergleichsreihenfolge liegt
Präfixübereinstimmung bedeutet: Der Vergleich der Musterzeichenfolge und der übergeordneten Zeichenfolge erfolgt von links nach rechts, und die Bewegung der Musterzeichenfolge erfolgt ebenfalls von links nach rechts
Suffix-Matching bedeutet: Der Vergleich der Musterzeichenfolge und der übergeordneten Zeichenfolge erfolgt von rechts nach links und die Bewegung der Musterzeichenfolge erfolgt von links nach rechts.
Durch das vorherige Kapitel ist es offensichtlich, dass der BF-Algorithmus auch ein Präfixalgorithmus ist, aber die Effizienz des Eins-zu-eins-Abgleichs ist natürlich sehr arrogant, es ist nicht notwendig, O( zu erwähnen. mn). KMP, was online nervig ist, erklärt im Grunde genommen den Weg auf hoher Ebene und Sie sind vielleicht verwirrt. Ich habe versucht, es auf die bodenständigste Art und Weise zu beschreiben >
KMP
KMP ist auch eine optimierte Version des Präfixalgorithmus. Der Grund, warum er KMP genannt wird, ist die Abkürzung der drei Namen Knuth, Morris und Pratt. Im Vergleich zu BF ist der Optimierungspunkt des KMP-Algorithmus „der“. Distanz jeder Rückwärtsbewegung“ Die Bewegungsdistanz jeder Musterzeichenfolge wird dynamisch angepasst. BF ist jedes Mal 1,Nicht unbedingt für KMP
Wie in der Abbildung gezeigt, wird der Unterschied zwischen dem BF- und dem KMP-Voralgorithmus verglichen
Suchen Sie nach der Musterzeichenfolge P in der Textzeichenfolge T. Wenn sie auf natürliche Weise mit dem sechsten Buchstaben c übereinstimmt, wird festgestellt, dass die zweite Ebene inkonsistent ist. Dann besteht die BF-Methode darin, die gesamte Musterzeichenfolge P um eine Stelle zu verschieben. und KMP soll es um zwei Stellen verschieben.
Wir kennen die Matching-Methode von BF, aber warum verschiebt KMP zwei Ziffern statt einer, drei oder vier Ziffern?
Lassen Sie uns das vorherige Bild erklären. Die Musterzeichenfolge P ist korrekt, wenn sie mit c übereinstimmt. Dann ist die Idee des KMP-Algorithmus: Ababa ist korrekt Wir verwenden diese Informationen, um die „Suchposition“ nicht zurück zur verglichenen Position zu verschieben, sondern sie weiter nach hinten zu verschieben, was die Effizienz verbessert.
Dann stellt sich die Frage: Woher weiß ich, wie viele Positionen ich verschieben muss?
Die Autoren dieses Offset-Algorithmus KMP haben es für uns zusammengefasst:
Übereinstimmende Zeichen:
Teilweiser Übereinstimmungswert:
Dies ist der Kernalgorithmus und auch schwer zu verstehenWenn:
Das heißt: Wenn innerhalb des Mustertextes der Anfang und das Ende eines bestimmten Absatzes mit Zeichen identisch sind, kann dieser Inhaltsabsatz bei der natürlichen Filterung übersprungen werden.
Wenn man diese Regel kennt, lautet der angegebene Teil-Matching-Table-Algorithmus wie folgt:
Zunächst müssen Sie zwei Konzepte verstehen: „Präfix“ und „Suffix“. „Präfix“ bezieht sich auf alle Kopfkombinationen einer Zeichenfolge mit Ausnahme des letzten Zeichens; „Suffix“ bezieht sich auf alle Endkombinationen einer Zeichenfolge mit Ausnahme des ersten Zeichens.
„Teilübereinstimmungswert“ ist die Länge des längsten gemeinsamen Elements zwischen „Präfix“ und „Suffix““
Werfen wir einen Blick auf die Division von Aaronaac, wenn es sich um ein BF-Match handelt
Verschiebung von BF: a,aa,aar,aaro,aaron,aarona,aaronaa,aaronaac
Was ist also mit den Abteilungen von KMP? Hier müssen wir Präfixe und Suffixe einführen
Sehen wir uns zunächst die Ergebnisse der KMP-Partial-Matching-Tabelle an:
Ich bin definitiv verwirrt, also machen Sie sich keine Sorgen, lassen Sie es uns aufschlüsseln, Präfixe und Suffixe
Zerlegung der teilweise passenden Tabelle
Der Matching-Table-Algorithmus in KMP, wobei p das Präfix, n das Suffix und r das Ergebnis darstellt
aa, p=>[a], n=>[a], r = a.length =>
aar, p=>[a,aa], n=>[r,ar] ,r = 0aaro, 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
Das Endergebnis der Matching-Tabelle von Aaronaac ist also 0,1,0,0,0,1,2,0
Die JS-Version von KMP wird unten implementiert, es gibt 2 Typen
KMP-Implementierung (1): KMP-Caching-Matching-Tabelle
KMP-Implementierung (2): Nächsten KMP dynamisch berechnen
KMP-Implementierung (1)
Passender Tisch
Das Wichtigste im KMP-Algorithmus ist die Matching-Tabelle. Wenn die Matching-Tabelle nicht erforderlich ist, ist es die Implementierung von BF. Das Hinzufügen der Matching-Tabelle ist KMP
Die Matching-Tabelle bestimmt die nächste VerschiebungszählungBasierend auf den Regeln der obigen Matching-Tabelle entwerfen wir eine kmpGetStrPartMatchValue-Methode
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;
}
Berechnen Sie dann die Länge der gemeinsamen Elemente durch Präfix und Suffix in jeder Zerlegung
Backoff-Algorithmus
KMP ist auch ein Front-End-Algorithmus. Die einzige Änderung besteht darin, dass BF beim Backtracking direkt 1 hinzufügt, wir können den nächsten Wert über die Matching-Tabelle berechnen
//子循环
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（二）
第一种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>
