So erstellen Sie eine öffentliche Teilsequenz in JS

Dieses Mal zeige ich Ihnen, wie Sie eine öffentliche Teilsequenz in JS erstellen. Was sind die Vorsichtsmaßnahmen für die Implementierung einer öffentlichen Teilsequenz in JS?

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 ist eine Teilfolge einer gegebenen Folge erhalten, indem null oder mehr Elemente entfernt werden (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=[A,B,C,B,D,A,B], Y=[B,D,C,A,B,A[, dann ist die Sequenz Z=[B,C,A]. 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 Neutronensequenzen hat diese Reihe von 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 weiterhin 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 gehen wir einfach davon aus, 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.

x	""	B	D	C	A	B	A
""
A
B
C
D
A
B

Angenommen 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 zweier leerer Zeichenfolgen beträgt 0.

Dann verschieben wir X nicht und lassen die leere Zeichenfolge weiterhin aus dem Array kommen, und Y lässt „B“ Offensichtlich ist ihr gemeinsamer Bereich Die Länge von Wenn nur die leere Wortzeichenfolge angegeben wird, ist es dasselbe wie in der obigen Analyse, alle sind 0 und die erste Spalte ist 0.

x	""	B	D	C	A	B	A
""	0
A
B
C
D
A
B

Das LCS-Problem unterscheidet sich ein wenig vom Rucksackproblem. Das Rucksackproblem kann auch auf -1 gesetzt werden. Bei der längsten gemeinsamen Teilsequenz sind die linke und obere Seite aufgrund des Auftretens leerer Teilsequenzen von Anfang an festgelegt.

x	""	B	D	C	A	B	A
""	0	0	0	0	0	0	0
A	0
B	0
C	0
D	0
A	0
B	0

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

x	""	B	D	C	A	B	A
""	0	0	0	0	0	0	0
A	0	0	0	0	1
B	0
C	0
D	0
A	0
B	0

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.

x	""	B	D	C	A	B	A
""	0	0	0	0	0	0	0
A	0	0	0	0	1	1	1
B	0	1
C	0
D	0
A	0
B	0

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 weiter aus, bis zum zweiten B von Y ist alles 1. Denn wenn es um BDCAB geht, haben sie eine weitere gemeinsame Teilsequenz, AB.

x	""	B	D	C	A	B	A
""	0	0	0	0	0	0	0
A	0	0	0	0	1	1	1
B	0	1	1	1	1	2
C	0
D	0
A	0
B	0

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, ist der entsprechende Rasterwert gleich dem Wert der linken, rechten und oberen linken Ecke und der linke, obere und obere linke Wert 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, 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 enthalten 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, neue Arrays 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];
}

Drucken Sie ein LCS

Wir geben Ihnen zunächst die Druckfunktion und sehen, wie Sie eines drucken. 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 störender 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. Als bereits berufstätiger Mensch kann ich nicht wie ein Schüler in der Schule Code schreiben, ohne Unit-Tests durchzuführen und ihn dann online zu stellen, 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)
}

Verwendung:

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 ähnelt der oben genannten. Beachten Sie, dass es in der LCS-Methode einen Math.max-Wert gibt. Dieser integriert tatsächlich drei Situationen, 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
 } 
 }

Verwendung:

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

Raumoptimierung

Verwendung Rolling Array:

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 Teilfolge von str1 entspricht der tiefgestellten Folge {1, 2, … , a Daher hat str1 insgesamt ${2^m}$ verschiedene Teilsequenzen (dasselbe gilt für str2, wie 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 glaube, dass Sie die Methode beherrschen, nachdem Sie den Fall in diesem Artikel gelesen haben. Weitere spannende Informationen finden Sie in anderen verwandten Artikeln auf der chinesischen PHP-Website!

Empfohlene Lektüre:

So verwenden Sie die Datumsauswahl

Detaillierte Erläuterung der Verwendung der NavigatorIOS-Komponente

Die Verwendung der ejsExcel-Vorlage in Vue.js

Das obige ist der detaillierte Inhalt vonSo erstellen Sie eine öffentliche Teilsequenz in JS. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!