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 23195a5eab8013c21303d3d24e81fe27 lauten beispielsweise: 4e2154b1242725e74a11c55ea3967ed3, 2cf3a2d5a55d4ffa7aceebabd439c436, f2bfead78e3f8cf3a5ede2eba562e2c9 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!