algorithm
Längste häufige Folge
Suche…
Längste häufige Teilsequenz Erklärung
Eine der wichtigsten Implementierungen der dynamischen Programmierung besteht darin, die längste häufige Teilsequenz herauszufinden. Lassen Sie uns zuerst einige der grundlegenden Terminologien definieren.
Folge:
Eine Untersequenz ist eine Sequenz, die aus einer anderen Sequenz abgeleitet werden kann, indem einige Elemente gelöscht werden, ohne die Reihenfolge der übrigen Elemente zu ändern. Nehmen wir an, wir haben einen String ABC . Wenn wir null oder ein oder mehr als ein Zeichen aus dieser Zeichenfolge löschen, erhalten wir die Untersequenz dieser Zeichenfolge. Die Untersequenzen der Zeichenfolge ABC sind also { "A" , "B" , "C" , "AB" , "AC" , "BC" , "ABC" , "" }. Auch wenn wir alle Zeichen entfernen, ist die leere Zeichenfolge auch eine Folge. Um die Untersequenz herauszufinden, haben wir für jedes Zeichen in einer Zeichenfolge zwei Optionen - entweder nehmen wir das Zeichen oder nicht. Wenn also die Länge der Zeichenfolge n ist , gibt es 2 n Untersequenzen dieser Zeichenfolge.
Längste häufige Folge:
Wie der Name vermuten lässt, ist die längste gemeinsame Untersequenz (LCS) von allen gemeinsamen Untersequenzen zwischen zwei Strings diejenige mit der maximalen Länge. Zum Beispiel: Die gemeinsamen Untersequenzen zwischen "HELLOM" und "HMLD" sind "H" , "HL" , "HM" usw. Hier ist "HLL" die längste gemeinsame Untersequenz, die die Länge 3 hat.
Brute-Force-Methode:
Wir können alle Untersequenzen von zwei Strings durch Rückverfolgung erzeugen. Dann können wir sie vergleichen, um die üblichen Untersequenzen herauszufinden. Danach müssen wir die maximale Länge herausfinden. Wir haben bereits gesehen, dass es 2 n Untersequenzen einer Folge der Länge n gibt . Es würde Jahre dauern, das Problem zu lösen, wenn unser n 20-25 kreuzt.
Dynamische Programmiermethode:
Gehen wir mit einem Beispiel an unsere Methode heran. Angenommen, wir haben zwei Zeichenketten abcdaf und acbcf . Bezeichnen wir diese mit s1 und s2 . Die längste gemeinsame Untersequenz dieser beiden Zeichenfolgen ist also "abcf" mit der Länge 4. Ich erinnere Sie daran, dass Teilfolgen in der Zeichenfolge nicht fortlaufend sein müssen. Um "abcf" zu konstruieren, haben wir "da" in s1 und "c" in s2 ignoriert. Wie finden wir das mit der dynamischen Programmierung heraus?
Wir beginnen mit einer Tabelle (einem 2D-Array), die alle Zeichen von s1 in einer Reihe und alle Zeichen von s2 in der Spalte enthält. Hier ist die Tabelle 0-indexiert und wir setzen die Zeichen von 1 bis weiter. Wir werden die Tabelle für jede Zeile von links nach rechts durchqueren. Unser Tisch wird wie folgt aussehen:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Jede Zeile und Spalte repräsentiert dabei die Länge der längsten gemeinsamen Untersequenz zwischen zwei Zeichenfolgen, wenn wir die Zeichen dieser Zeile und Spalte nehmen und zum Präfix hinzufügen. Zum Beispiel: Tabelle [2] [3] repräsentiert die Länge der längsten gemeinsamen Untersequenz zwischen "ac" und "abc" .
Die 0-te Spalte repräsentiert die leere Teilsequenz von s1 . In ähnlicher Weise repräsentiert die 0-te Zeile die leere Teilsequenz von s2 . Wenn wir eine leere Untersequenz einer Zeichenfolge nehmen und versuchen, sie mit einer anderen Zeichenfolge abzugleichen, egal wie lang die zweite Teilzeichenfolge ist, wird die gemeinsame Untersequenz die Länge 0 haben. So können wir die 0-ten Zeilen und die 0-ten Spalten mit 0 füllen. Wir bekommen:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Lass uns anfangen. Wenn wir Tabelle [1] [1] füllen, fragen wir uns, ob wir eine Zeichenfolge a und eine andere Zeichenfolge a und nichts anderes hatten. Was ist die längste gemeinsame Folge hier? Die Länge des LCS wird hier 1 betragen. Nun wollen wir uns Tabelle [1] [2] ansehen. Wir haben string ab und string a . Die Länge des LCS ist 1. Wie Sie sehen, sind die restlichen Werte auch 1 für die erste Zeile, da sie nur die Zeichenfolge a mit abcd , abcda , abcdaf berücksichtigt . So wird unser Tisch aussehen:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Für Reihe 2, die jetzt c enthält . Für Tabelle [2] [1] haben wir ac auf der einen und a auf der anderen Seite. Die Länge des LCS ist also 1. Woher haben wir diese 1? Von oben bezeichnet der LCS einen zwischen zwei Teilstrings. Wir sagen also, wenn s1 [2] und s2 [1] nicht gleich sind, dann ist die Länge der LCS das Maximum der Länge der LCS oben oder links . Die Länge des LCS an der Spitze bedeutet, dass wir das aktuelle Zeichen nicht aus s2 nehmen . Wenn Sie die Länge des LCS auf der linken Seite angeben, bedeutet dies ebenfalls, dass wir nicht das aktuelle Zeichen von s1 nehmen , um das LCS zu erstellen. Wir bekommen:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Unsere erste Formel lautet also:
if s2[i] is not equal to s1[j]
Table[i][j] = max(Table[i-1][j], Table[i][j-1]
endif
Weiter für Tabelle [2] [2] haben wir string ab und ac . Da c und b nicht gleich sind, setzen wir hier das Maximum von oben oder links. In diesem Fall ist es wieder 1. Danach haben wir für Tabelle [2] [3] die Zeichenfolgen abc und ac . Diese aktuellen Werte für Zeile und Spalte sind gleich. Nun ist die Länge des LCS gleich der maximalen Länge von LCS + 1. Wie erhalten wir die maximale Länge von LCS? Wir prüfen den Diagonalwert, der die beste Übereinstimmung zwischen ab und a darstellt . Aus diesem Zustand haben wir für die aktuellen Werte ein weiteres Zeichen zu s1 und s2 hinzugefügt, das zufällig dasselbe war. Die Länge von LCS wird sich natürlich verlängern. Wir setzen 1 + 1 = 2 in Tabelle [2] [3] . Wir bekommen,
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | 1 | 2 | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Unsere zweite Formel lautet also:
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
endif
Wir haben beide Fälle definiert. Mit diesen beiden Formeln können wir die gesamte Tabelle füllen. Nach dem Auffüllen der Tabelle sieht das so aus:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | 1 | 2 | 2 | 2 | 2 | 2 |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | 1 | 2 | 3 | 3 | 3 | 3 |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | 1 | 2 | 3 | 3 | 3 | 4 |
+-----+-----+-----+-----+-----+-----+-----+-----+
Die Länge des LCS zwischen s1 und s2 beträgt Tabelle [5] [6] = 4 . Hier sind 5 und 6 die Länge von s2 bzw. s1 . Unser Pseudo-Code lautet:
Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
Table[0][i] = 0
endfor
for i from 1 to s2.length
Table[i][0] = 0
endfor
for i from 1 to s2.length
for j from 1 to s1.length
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
else
Table[i][j] = max(Table[i-1][j], Table[i][j-1])
endif
endfor
endfor
Return Table[s2.length][s1.length]
Die zeitliche Komplexität für diesen Algorithmus ist: O (mn) wobei m und n die Länge der einzelnen Strings bedeuten.
Wie finden wir die längste gemeinsame Folge heraus? Wir beginnen von rechts unten. Wir werden prüfen, woher der Wert kommt. Wenn der Wert von der Diagonale kommt, das heißt, wenn Tabelle [i-1] [j-1] gleich Tabelle [i] [j] -1 ist , drücken wir entweder s2 [i] oder s1 [j] (beide sind gleich) und bewegen sich diagonal. Wenn der Wert von oben kommt, heißt das, wenn Tabelle [i-1] [j] gleich Tabelle [i] [j] ist , bewegen wir uns nach oben. Wenn der Wert von links kommt, heißt das, wenn Tabelle [i] [j-1] gleich Tabelle [i] [j] ist , bewegen wir uns nach links. Wenn wir die linke oder oberste Spalte erreichen, ist unsere Suche beendet. Dann ziehen wir die Werte aus dem Stapel und drucken sie. Der Pseudo-Code:
Procedure PrintLCS(LCSlength, s1, s2)
temp := LCSlength
S = stack()
i := s2.length
j := s1.length
while i is not equal to 0 and j is not equal to 0
if Table[i-1][j-1] == Table[i][j] - 1 and s1[j]==s2[i]
S.push(s1[j]) //or S.push(s2[i])
i := i - 1
j := j - 1
else if Table[i-1][j] == Table[i][j]
i := i-1
else
j := j-1
endif
endwhile
while S is not empty
print(S.pop)
endwhile
Zu beachten ist: wenn sowohl Tabelle [i-1] [j] als auch Tabelle [i] [j-1] gleich Tabelle [i] [j] und Tabelle [i-1] [j-1] ist gleich zu Tabelle [i] [j] -1 kann es für diesen Moment zwei LCS geben. Dieser Pseudo-Code berücksichtigt diese Situation nicht. Sie müssen dies rekursiv lösen, um mehrere LCSs zu finden.
Die zeitliche Komplexität für diesen Algorithmus ist: O (max (m, n)) .
