Die längste gemeinsame Teilsequenz erhält man, indem man aus den beiden gegebenen Sequenzen X und Y so viele Zeichen wie möglich nimmt und sie in der Reihenfolge anordnet, in der sie in der Originalsequenz 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 prü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.
Grundlegende Konzepte
-
Folge: Eine Teilfolge einer bestimmten Folge ist das Ergebnis der Entfernung von null oder mehr Elementen aus einer gegebenen Folge (die relative Reihenfolge der Elemente wird nicht geändert ). 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 der X- und Y-Folge. 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 oder 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 Untersequenzen
Geben Sie mir ein Bild zur Erklärung:
Wir können sehen, dass Teilsequenzen nicht unbedingt kontinuierlich sind, kontinuierliche Teilfolgen sind Teilzeichenfolgen.
Problemanalyse
Wir beginnen die Analyse weiterhin mit einer Matrix und leiten die Zustandsübergangsgleichung selbst ab.
Zuerst wandeln wir das Problem in ein Konzept um, das dem Frontend ausreichend bekannt 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 leerer String (wenn unsere Sequenz kein String ist, können wir es 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 leere Zeichenfolgen mit leeren Zeichenfolgen. 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.
| 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 |
Das LCS-Problem unterscheidet sich ein wenig vom Rucksackproblem. Das Rucksackproblem kann auch auf -1 Zeile und die längste eingestellt werden Aufgrund des Auftretens leerer Teilsequenzen in der gemeinsamen Teilsequenz ist die linke Seite 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
| 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 |
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 | 1 | 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? Da unsere Matrix eine Zustandstabelle ist, die den Zustandsmigrationsprozess von links nach rechts und von oben nach unten beschreibt, werden diese Zustände basierend auf den vorhandenen Zuständen 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 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.
| 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, wenn die zu vergleichenden Zeichen zwischen den beiden Zeichenfolgen unterschiedlich sind, sich das auszufüllende Raster auf die linke oder obere Seite bezieht, je nachdem, welche Seite es ist größer.
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.
假设有两个数组，A和B。A[i]为A的第i个元素，A(i)为由A的第一个元素到第i个元素所组成的前缀。m(i, j)为A(i)和B(j)的最长公共子序列长度。
由于算法本身的递推性质，其实只要证明，对于某个i和j：
m(i, j) = m(i-1, j-1) + 1 （当A[i] = B[j]时）
m(i, j) = max( m(i-1, j), m(i, j-1) ) （当A[i] != B[j]时）
第一个式子很好证明，即当A[i] = B[j]时。可以用反证，假设m(i, j) > m(i-1, j-1) + 1 （m(i, j)不可能小于m(i-1, j-1) + 1，原因很明显），那么可以推出m(i-1, j-1)不是最长的这一矛盾结果。
第二个有些trick。当A[i] != B[j]时，还是反证，假设m(i, j) > max( m(i-1, j), m(i, j-1) )。
由反证假设，可得m(i, j) > m(i-1, j)。这个可以推出A[i]一定在m(i, j)对应的LCS序列中（反证可得）。而由于A[i] != B[j]，故B[j]一定不在m(i, j)对应的LCS序列中。所以可推出m(i, j) = m(i, j-1)。这就推出了与反正假设矛盾的结果。
得证。</p>
<p> </p>
<p>Wir verwenden nun die untenstehende Gleichung, um mit dem Ausfüllen der Tabelle fortzufahren. </p>
<p><img src="https://img.php.cn/upload/article/000/054/025/4261b59f87cbe8cff3afd0492985a179-3.png" alt="Eine ausführliche Diskussion der längsten gemeinsamen Teilsequenz in JavaScript" ></p>
<h2>Programmimplementierung</h2>
<pre class="brush:php;toolbar:false">//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]
}Nach dem Login kopieren
LCS kann durch einfaches Verschieben der Position weiter vereinfacht werden, wodurch die Notwendigkeit entfällt, ein zu generieren neues Array
//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];
}Nach dem Login kopieren
Ein LCS drucken
Lassen Sie uns zuerst die Druckfunktion geben und sehen, wie man eines druckt. 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. 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)
}Nach dem Login kopieren
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 GTCGTCGGAAGCCGGCCGAANach dem Login kopieren
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
}
}Nach dem Login kopieren
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 GTCGTCGGAAGCCGGCCGAANach dem Login kopieren
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
}Nach dem Login kopieren
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
}
}Nach dem Login kopieren
Verwandte Empfehlungen:
Verwenden Sie die Python-Sprache, um die maximal kontinuierliche Teilsequenz zu beschreiben und
Maximal kontinuierliche Teilsequenz und Problem
PHP-Algorithmus-Implementierung zum Ermitteln der maximalen Summe von Teilsequenzen_PHP-Tutorial
Das obige ist der detaillierte Inhalt vonEine ausführliche Diskussion der längsten gemeinsamen Teilsequenz in JavaScript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
