So implementieren Sie die längste gemeinsame Teilsequenz in Javascript

Die längste gemeinsame Folge (longest common sequence) und die längste gemeinsame Teilzeichenfolge (longest common substring) sind nicht dasselbe. Der folgende Artikel führt Sie hauptsächlich in die relevanten Informationen zur Implementierung der längsten gemeinsamen Teilfolge in JavaScript ein. Freunde in Not können sich darauf beziehen.

Einführung

Longest Common Subsequence LCS (Longest Common Subsequence LCS) besteht darin, alle Elemente aus den beiden gegebenen Sequenzen X und Y zu extrahieren Die möglichen zusätzlichen Zeichen werden in der Reihenfolge angeordnet, in der sie in der ursprünglichen Reihenfolge angeordnet sind. Der Algorithmus für LCS-Probleme hat ein breites Anwendungsspektrum. Beispielsweise wird der LCS-Algorithmus bei der Verwaltung verschiedener Softwareversionen verwendet, um die Ähnlichkeiten und Unterschiede zwischen der alten und der neuen Version zu ermitteln wird zum Vergleich aufgezeichneter und wiedergegebener Sequenzen verwendet; im Bereich der Gentechnik wird der LCS-Algorithmus verwendet. Der Algorithmus überprüft die Ähnlichkeiten und Unterschiede zwischen dem DNA-Strang des Patienten und dem DNA-Strang der Bindung, dem LCS-Algorithmus Wird verwendet, um die Plagiatsrate der Arbeit zu überprüfen. Der LCS-Algorithmus kann auch zur Messung der Programmcode-Ähnlichkeit, zum Abrufen menschlicher Laufsequenzen, zum Abgleich von Videosegmenten usw. verwendet werden, sodass die Forschung am LCS-Algorithmus einen hohen Anwendungswert hat.

Grundkonzepte

Folge: Eine Teilfolge einer bestimmten Folge besteht aus null oder mehr Elementen in einer gegebenen Folge. Das nach dem Entfernen erhaltene Ergebnis ( ohne die relative Reihenfolge zwischen den Elementen zu ändern). Die Teilfolgen der Folge lauten beispielsweise: , ,

Gemeinsame Teilfolge: Gegeben seien die Folgen X und Y, Folge Z ist eine Teilfolge von X und eine Teilfolge von Y, dann ist Z die gemeinsame Teilfolge von X und Y. Zum Beispiel: X und Y sind die gemeinsame Teilfolge von , ihre Länge beträgt 3. Aber Z ist nicht die längste gemeinsame Teilfolge von X und Y, und die Folgen [B, C, B, A] und [B, D, A, B] sind mit einer Länge von auch die längsten gemeinsamen Teilfolgen von X und Y 4 und X und Y haben keine gemeinsame Teilfolge mit einer Länge größer oder gleich 5. Für die gemeinsamen Teilfolgen der Folge [A, B, C] und der Folge [E, F, G] gibt es nur die leere Folge [].

Längste gemeinsame Teilsequenz: Wählen Sie bei gegebenen Sequenzen X und Y die eine oder mehrere mit der längsten Länge aus allen ihren gemeinsamen Teilsequenzen aus.
Teilzeichenfolge: Eine neue Serie, die durch Löschen von null oder mehreren Zeichen am Anfang, am Ende oder an beiden einer Sequenz gebildet wird. Der Unterschied besteht darin, dass in Teilsequenzen Zeichen aus der Mitte herausgeschnitten werden können. Wie viele Teilsequenzen gibt es in der Zeichenfolge cnblogs? Offensichtlich gibt es 27, wie cb, cgs usw. sind alles Teilsequenzen

Geben Sie mir ein Bild zur Erklärung:

Wir können sehen Die Teilsequenz ist nicht unbedingt kontinuierlich, was kontinuierlich ist, ist der Teilstring.

Problemanalyse

Wir starten die Analyse immer noch von einer Matrix und leiten die Zustandsübergangsgleichung selbst ab.

Zuerst wandeln wir das Problem in ein Konzept um, das dem Frontend ausreichend vertraut ist. Anstatt es seriell aufzurufen, kann es sich als Array oder String vorstellen. Der Einfachheit halber nehmen wir einfach an, dass zwei Zeichenfolgen verglichen werden.

Wir konzentrieren uns auf das Konzept der „Teilsequenz“, das mehrere oder null Einsen oder alle löschen kann. Zu diesem Zeitpunkt ist unsere erste Teilsequenz eine leere Zeichenfolge (wenn unsere Sequenz keine Zeichenfolge ist, können wir dies trotzdem tun)! Darauf müssen Sie unbedingt achten! Viele Leute können die Tabelle in „Einführung in Algorithmen“ einfach nicht verstehen, und es gibt auch viele Blogger, die nicht vorgeben, sie zu verstehen. Wir vergleichen immer von links nach rechts, und natürlich wird die erste Zeichenfolge, da sie die Höhe der Matrix darstellt, vertikal platziert.

Angenommen, X ＝ „ABCDAB“ und Y = „BDCABA“ nehmen jeweils die kürzeste Sequenz heraus, dh vergleichen die leere Zeichenfolge mit der leeren Zeichenfolge. Die Lösung der LCS-Gleichung ist eine Zahl, daher kann diese Tabelle nur mit Zahlen gefüllt werden. Die Länge des gemeinsamen Bereichs zwischen zwei leeren Zeichenfolgen beträgt 0.

Dann verschieben wir X nicht und lassen weiterhin die leere Zeichenfolge erscheinen, und Y lässt „B“ erscheinen. Offensichtlich ist die Länge ihrer gemeinsamen Bereiche 0. Y wird durch andere Zeichen ersetzt, D, C, oder , sie sind kontinuierliche Kombinationen von DC und DDC, die Situation hat sich nicht geändert, sie ist immer noch 0. Daher ist die erste Zeile 0. Dann verschieben wir Y nicht und Y erzeugt nur leere Zeichenfolgen, dann ist es dasselbe wie oben Analyse, alle sind 0, die ersten Die Spalten sind alle 0.

Das LCS-Problem unterscheidet sich ein wenig vom Rucksackproblem. Das Rucksackproblem kann auch auf -1 Zeile und die längste eingestellt werden Aufgrund des Vorkommens leerer Teilsequenzen ist die gemeinsame Teilsequenz links oben fixiert.

Dann erweitern wir das Problem noch ein wenig. Diesmal erzeugen beide Seiten ein Zeichen. Offensichtlich kann es nur dann eine gemeinsame Teilfolge geben, die keine leere Zeichenfolge ist, und die Länge auch verstanden werden als 1.

Jede Teilfolge, in der A „X“ und Y „BDCA“ ist

Füllen Sie weiterhin die Lücken auf der rechten Seite aus. Offensichtlich kann LCS nicht größer als die Länge von

Wenn . Schauen wir uns dann zuerst B an, ${X_1} == ${Y_0}, wir erhalten einen neuen öffentlichen Teilstring und sollten 1 hinzufügen. Warum? Denn unsere Matrix ist eine Zustandstabelle, die den Zustandsmigrationsprozess von links nach rechts und von oben nach unten beschreibt und diese Zustände auf der Grundlage vorhandener Zustände akkumuliert. Was wir jetzt bestätigen müssen, ist die Beziehung zwischen dem Wert des Gitters, das wir ausfüllen möchten, und den Werten der Gitter um es herum, die bereits ausgefüllt wurden. Derzeit gibt es zu wenige Informationen und es handelt sich nur um einen Einzelpunkt. Füllen Sie einfach 1 aus.

Dann geben wir Y ein zusätzliches D als Helfer, {"",A,B,AB} vs. {"",B,D,BD}. Füllen Sie natürlich weiterhin 1 aus. Füllen Sie es bis zum zweiten aus einer von Y Vor B ist alles 1. Denn wenn es um BDCAB geht, haben sie eine weitere gemeinsame Teilsequenz, AB.

An dieser Stelle können wir einige Regeln zusammenfassen. Anschließend werden wir unsere Ideen durch Berechnungen überprüfen und neue Regeln oder Einschränkungen hinzufügen, um sie zu verbessern.

Y sendet alle Zeichen, X Wenn die Menge der Teilfolgen von C und ABC größer ist als die Menge der Teilfolgen von AB, dann sind sie und die Menge der B-Teilfolgen von Y größer. Auch wenn sie nicht größer sind, können sie nicht kleiner sein als die ursprünglichen. Offensichtlich kann das neu hinzugefügte C keine Kampfkraft werden und ist kein gemeinsames Zeichen zwischen den beiden, daher sollte der Wert gleich der Teilsequenzmenge von AB sein.

Und wir können sicher sein, dass sich das auszufüllende Raster auf die linke oder obere Seite bezieht und die größere Seite verwendet wird, wenn die zu vergleichenden Zeichen zwischen den beiden Zeichenfolgen unterschiedlich sind.

Wenn die verglichenen Zeichen gleich sind, machen Sie sich keine Sorgen, es kommt vor, dass das C von B,C,AB,BC, ABC} wird mit der Teilsequenzmenge {"",B,D,C,BD,DC,BDC} von BDC verglichen, und die erhaltenen gemeinsamen Teilzeichenfolgen sind "",B,D. Zu diesem Zeitpunkt ist die Schlussfolgerung immer noch dieselbe wie zuvor. Wenn die Zeichen gleich sind, entspricht der entsprechende Rasterwert dem Wert der linken, rechten und oberen linken Ecke und der linken, oberen und oberen linken Seite immer gleich. Zur Demonstration dieser Geheimnisse sind strengere mathematische Kenntnisse erforderlich.

Angenommen, es gibt zwei Arrays, A und B. A[i] ist das i-te Element von A und A(i) ist das Präfix, das aus dem ersten Element bis zum i-ten Element von A besteht. m(i, j) ist die längste gemeinsame Teilsequenzlänge von A(i) und B(j).

Aufgrund der rekursiven Natur des Algorithmus selbst muss tatsächlich nur bewiesen werden, dass für ein bestimmtes i und j gilt:

m(i, j) = m(i- 1, j-1) + 1 (Wenn A[i] = B[j])

m(i, j) = max( m(i-1, j), m(i, j- 1) ) (Wenn A[ i] != B[j])

Die erste Formel ist leicht zu beweisen, das heißt, wenn A[i] = B[j]. Sie können einen Gegenbeweis verwenden, vorausgesetzt, dass m(i, j) > m(i-1, j-1) + 1 ist (m(i, j) darf nicht kleiner als m(i-1, j-1) + sein 1 aus einem sehr guten Grund (offensichtlich), dann können wir das widersprüchliche Ergebnis ableiten, dass m(i-1, j-1) nicht der längste ist.

Der zweite ist etwas knifflig. Wenn A[i] != B[j], ist es immer noch ein Widerlegungsbeweis, vorausgesetzt m(i, j) > max( m(i-1, j), m(i, j-1) ).

Durch die Widerlegung der Hypothese können wir m(i, j) > Daraus lässt sich ableiten, dass A[i] in der LCS-Sequenz sein muss, die m(i, j) entspricht (widersprüchliche Beweise liegen vor). Und da A[i] != B[j], darf B[j] nicht in der LCS-Sequenz enthalten, die m(i, j) entspricht. Daraus lässt sich ableiten, dass m(i, j) = m(i, j-1). Dies führt zu Ergebnissen, die der Hypothese ohnehin widersprechen.

Lassen Sie sich zertifizieren.

Wir verwenden nun die folgende Gleichung, um mit dem Ausfüllen der Tabelle fortzufahren.

Programmimplementierung

//by 司徒正美
function LCS(str1, str2){
  var rows = str1.split("")
  rows.unshift("")
  var cols = str2.split("")
  cols.unshift("")
  var m = rows.length 
  var n = cols.length 
  var dp = []
  for(var i = 0; i < m; i++){ 
   dp[i] = []
   for(var j = 0; j < n; j++){ 
    if(i === 0 || j === 0){
     dp[i][j] = 0
     continue
    }
    
    if(rows[i] === cols[j]){ 
     dp[i][j] = dp[i-1][j-1] + 1 //对角＋1
    }else{
     dp[i][j] = Math.max( dp[i-1][j], dp[i][j-1]) //对左边，上边取最大
    }
   }
   console.log(dp[i].join(""))//调试
  } 
  return dp[i-1][j-1]
 }

LCS kann weiter vereinfacht werden, indem die Position verschoben wird und die Notwendigkeit entfällt, ein neues Array zu generieren

//by司徒正美
function LCS(str1, str2){
 var m = str1.length 
 var n = str2.length
 var dp = [new Array(n+1).fill(0)] //第一行全是0
 for(var i = 1; i <= m; i++){ //一共有m+1行
  dp[i] = [0] //第一列全是0
  for(var j = 1; j <= n; j++){//一共有n+1列
   if(str1[i-1] === str2[j-1]){ 
    //注意这里，str1的第一个字符是在第二列中，因此要减1，str2同理
    dp[i][j] = dp[i-1][j-1] + 1 //对角＋1
   } else {
     dp[i][j] = Math.max( dp[i-1][j], dp[i][j-1]) 
   }
  }
 } 
 return dp[m][n];
}

Ein LCS drucken

Wir geben Ihnen die Druckfunktion und schauen uns zunächst an, wie man ein LCS ausdruckt. Wir beginnen in der unteren rechten Ecke zu schauen und enden in der oberen Zeile. Daher wird der Zielstring in umgekehrter Reihenfolge aufgebaut. Um die Verwendung problematischer Zwischengrößen wie stringBuffer zu vermeiden, können wir es rekursiv implementieren. Bei jeder Ausführung des Programms wird nur eine Zeichenfolge zurückgegeben, andernfalls wird eine leere Zeichenfolge zurückgegeben, indem wir printLCS(x,y,...) + verwenden str[ i] werden hinzugefügt, um die von uns benötigte Zeichenfolge zu erhalten.

Schreiben wir eine weitere Methode, um zu überprüfen, ob die Zeichenfolge, die wir erhalten, eine echte LCS-Zeichenfolge ist. Da ich bereits berufstätig bin, kann ich nicht wie ein Schüler Code schreiben und ihn online stellen, ohne Unit-Tests durchzuführen, damit andere darauf zugreifen können.

//by 司徒正美，打印一个LCS
function printLCS(dp, str1, str2, i, j){
 if (i == 0 || j == 0){
  return "";
 }
 if( str1[i-1] == str2[j-1] ){
  return printLCS(dp, str1, str2, i-1, j-1) + str1[i-1];
 }else{
  if (dp[i][j-1] > dp[i-1][j]){
   return printLCS(dp, str1, str2, i, j-1);
  }else{
   return printLCS(dp, str1, str2, i-1, j);
  }
 }
}
//by司徒正美， 将目标字符串转换成正则，验证是否为之前两个字符串的LCS
function validateLCS(el, str1, str2){
 var re = new RegExp( el.split("").join(".*") )
 console.log(el, re.test(str1),re.test(str2))
 return re.test(str1) && re.test(str2)
}

Verwenden Sie:

function LCS(str1, str2){
 var m = str1.length 
 var n = str2.length
 //....略，自行补充
 var s = printLCS(dp, str1, str2, m, n)
 validateLCS(s, str1, str2)
 return dp[m][n]
}
var c1 = LCS( "ABCBDAB","BDCABA");
console.log(c1) //4 BCBA、BCAB、BDAB
var c2 = LCS("13456778" , "357486782" );
console.log(c2) //5 34678 
var c3 = LCS("ACCGGTCGAGTGCGCGGAAGCCGGCCGAA" ,"GTCGTTCGGAATGCCGTTGCTCTGTAAA" );
console.log(c3) //20 GTCGTCGGAAGCCGGCCGAA

Alle LCS drucken

Die Idee ist ähnlich Beachten wir zum oben Gesagten, dass es in der LCS-Methode einen Math.max-Wert gibt, der tatsächlich drei Situationen integriert, sodass drei Zeichenfolgen gegabelt werden können. Unsere Methode gibt ein es6-Sammlungsobjekt zur automatischen Entfernung zurück. Dann wird jedes Mal der neue Satz verwendet, um die Zeichenfolgen des alten Satzes zusammenzuführen.

//by 司徒正美 打印所有LCS
function printAllLCS(dp, str1, str2, i, j){
 if (i == 0 || j == 0){
  return new Set([""])
 }else if(str1[i-1] == str2[j-1]){
  var newSet = new Set()
  printAllLCS(dp, str1, str2, i-1, j-1).forEach(function(el){
   newSet.add(el + str1[i-1])
  })
  return newSet
 }else{
  var set = new Set()
  if (dp[i][j-1] >= dp[i-1][j]){
   printAllLCS(dp, str1, str2, i, j-1).forEach(function(el){
    set.add(el)
   })
  }
  if (dp[i-1][j] >= dp[i][j-1]){//必须用>=，不能简单一个else搞定
   printAllLCS(dp, str1, str2, i-1, j).forEach(function(el){
    set.add(el)
   })
  } 
  return set
 } 
 }

Verwenden Sie:

function LCS(str1, str2){
 var m = str1.length 
 var n = str2.length
 //....略，自行补充
 var s = printAllLCS(dp, str1, str2, m, n)
 console.log(s)
 s.forEach(function(el){
  validateLCS(el,str1, str2)
  console.log("输出LCS",el)
 })
 return dp[m][n]
}
var c1 = LCS( "ABCBDAB","BDCABA");
console.log(c1) //4 BCBA、BCAB、BDAB
var c2 = LCS("13456778" , "357486782" );
console.log(c2) //5 34678 
var c3 = LCS("ACCGGTCGAGTGCGCGGAAGCCGGCCGAA" ,"GTCGTTCGGAATGCCGTTGCTCTGTAAA" );
console.log(c3) //20 GTCGTCGGAAGCCGGCCGAA

Platzoptimierung

Scrollendes Array verwenden:

function LCS(str1, str2){
 var m = str1.length 
 var n = str2.length
 var dp = [new Array(n+1).fill(0)],now = 1，row //第一行全是0
 for(var i = 1; i <= m; i++){ //一共有2行
  row = dp[now] = [0] //第一列全是0
  for(var j = 1; j <= n; j++){//一共有n+1列
   if(str1[i-1] === str2[j-1]){ 
    //注意这里，str1的第一个字符是在第二列中，因此要减1，str2同理
    dp[now][j] = dp[i-now][j-1] + 1 //对角＋1
   } else {
    dp[now][j] = Math.max( dp[i-now][j], dp[now][j-1]) 
   }
  }
  now = 1- now; //1-1=>0;1-0=>1; 1-1=>0 ...
 } 
 return row ? row[n]: 0
}

Gefährliche rekursive Lösung

Eine Teilsequenz von str1 entspricht einer Teilsequenz der tiefgestellten Sequenz {1, 2, …, m}-Sequenz, Daher hat str1 insgesamt ${2^m}$ verschiedene Teilsequenzen (dasselbe gilt für str2, z. B. ${2^n}$), sodass die Komplexität eine erstaunliche exponentielle Zeit erreicht (${2^m * 2^ n}$).

//警告，字符串的长度一大就会爆栈
function LCS(str1, str2, a, b) {
  if(a === void 0){
   a = str1.length - 1
  }
  if(b === void 0){
   b = str2.length - 1
  }
  if(a == -1 || b == -1){
   return 0
  } 
  if(str1[a] == str2[b]) {
   return LCS(str1, str2, a-1, b-1)+1;
  }
  if(str1[a] != str2[b]) {
   var x = LCS(str1, str2, a, b-1)
   var y = LCS(str1, str2, a-1, b)
   return x >= y ? x : y
  }
 }

Ich habe das Obige für Sie zusammengestellt und hoffe, dass es Ihnen in Zukunft hilfreich sein wird.

Verwandte Artikel:

Verwendung von Vue zur Implementierung der sekundären Routeneinstellungsmethode

Reagieren Sie auf die Projektentwicklung

Eine Vielzahl von Routing-Implementierungen in Vue-Router2.X

Das obige ist der detaillierte Inhalt vonSo implementieren Sie die längste gemeinsame Teilsequenz in Javascript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!