Datenstrukturen und Algorithmen in JavaScript (5): Klassische KMP-Algorithmus-Javascript-Kenntnisse

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

Ich habe die Bilder verglichen und herausgefunden:

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:

Code kopieren Der Code lautet wie folgt:

Verschiebende Ziffern = Anzahl der übereinstimmenden Zeichen – Entsprechender Teilübereinstimmungswert

Der Offset-Algorithmus bezieht sich nur auf Teilzeichenfolgen, nicht auf Textzeichenfolgen, daher muss hier besondere Aufmerksamkeit gewidmet werden
Wie verstehen wir also die Anzahl der übereinstimmenden Zeichen in der Teilzeichenfolge und den entsprechenden Teilübereinstimmungswert?

Übereinstimmende Zeichen:

Code kopieren Der Code lautet wie folgt:

T: abababaabab
p: ababacb

Die rote Markierung in p ist das übereinstimmende Zeichen, das leicht zu verstehen ist

Teilweiser Übereinstimmungswert:

Dies ist der Kernalgorithmus und auch schwer zu verstehen

Wenn:

Code kopieren Der Code lautet wie folgt:

T:aaronaabbcc
P:aaronaac

Wenn wir beim Matching von c einen Fehler machen, wo wird unser nächster Zug basierend auf der vorherigen Struktur erfolgen?

Code kopieren Der Code lautet wie folgt:

aaronaabbcc
aaronaac

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:

Code kopieren Der Code lautet wie folgt:

a a r o n a a c
[0, 1, 0, 0, 0, 1, 2, 0]

Ich bin definitiv verwirrt, also machen Sie sich keine Sorgen, lassen Sie es uns aufschlüsseln, Präfixe und Suffixe

Code kopieren Der Code lautet wie folgt:

Übereinstimmungszeichenfolge: „Aaron“
Präfix: A, Aa, Aar, Aaro
Suffix: aron,ron,on,n

Verschieben der Position: Tatsächlich werden die Präfixe und Suffixe jedes übereinstimmenden Zeichens verglichen, um festzustellen, ob sie gleich sind, und dann die Gesamtlänge berechnet

Zerlegung der teilweise passenden Tabelle

Der Matching-Table-Algorithmus in KMP, wobei p das Präfix, n das Suffix und r das Ergebnis darstellt

Code kopieren Der Code lautet wie folgt:

a,        p=>0, n=>0 r = 0

aa,      p=>[a], n=>[a], r = a.length =>

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

Ähnlich wie beim BF-Algorithmus wird zunächst die Position jedes möglichen übereinstimmenden Indexes zerlegt und zwischengespeichert. Verwenden Sie beim Abgleichen diese „Teilübereinstimmungstabelle“, um die Anzahl der Ziffern zu ermitteln, die verschoben werden müssen

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ählung

Basierend 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;
  }

Ganz in Übereinstimmung mit der Implementierung des Matching-Table-Algorithmus in KMP wird a->aa->aar->aaro->aaron->aarona-> zerlegt durch str.substring(0, i 1) aaronaa-aaronaac

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

Die rote Markierung ist der Kernpunkt von KMP. Der Wert von next = die Anzahl der übereinstimmenden Zeichen – der entsprechende Teilübereinstimmungswert

//子循环
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;
  }
}

Vollständiger KMP-Algorithmus

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>

git代码下载: https://github.com/JsAaron/data_structure