Längste gemeinsame Folge

In diesem Tutorial erfahren Sie, wie die längste gemeinsame Teilsequenz gefunden wird. Außerdem finden Sie Arbeitsbeispiele für die längste gemeinsame Teilsequenz in C, C ++, Java und Python.

Die längste gemeinsame Teilsequenz (LCS) ist definiert als die längste Teilsequenz, die allen gegebenen Sequenzen gemeinsam ist, vorausgesetzt, die Elemente der Teilsequenz müssen keine aufeinanderfolgenden Positionen innerhalb der ursprünglichen Sequenzen einnehmen.

Wenn S1 und S2 die zwei gegebenen Sequenzen sind, dann ist Z die gemeinsame Teilfolge von S1 und S2, wenn Z eine Teilfolge von S1 und S2 ist. Darüber hinaus muss Z eine streng ansteigende Folge der Indizes von S1 und S2 sein.

In einer streng ansteigenden Reihenfolge müssen die Indizes der aus den ursprünglichen Sequenzen ausgewählten Elemente in aufsteigender Reihenfolge in Z sein.

Wenn

 S1 = (B, C, D, A, A, C, D)

Dann (A, D, B)kann keine Teilfolge von S1 sein, da die Reihenfolge der Elemente nicht dieselbe ist (dh nicht streng ansteigende Reihenfolge).

Lassen Sie uns LCS anhand eines Beispiels verstehen.

Wenn

 S1 = (B, C, D, A, A, C, D) S2 = (A, C, D, B, A, C)

Dann sind gemeinsame Teilsequenzen (B, C), (C, D, A, C), (D, A, C), (A, A, C), (A, C), (C, D), …

Unter diesen Teilsequenzen (C, D, A, C)ist die längste gemeinsame Teilsequenz. Wir werden diese längste gemeinsame Teilsequenz mit dynamischer Programmierung finden.

Bevor Sie fortfahren, sollten Sie die dynamische Programmierung durchlaufen, wenn Sie noch nichts über dynamische Programmierung wissen.

Verwenden der dynamischen Programmierung zum Auffinden des LCS

Nehmen wir zwei Sequenzen:

Die erste Sequenz

Zweite Sequenz

Die folgenden Schritte werden ausgeführt, um die längste gemeinsame Teilsequenz zu finden.

Erstellen Sie eine Dimensionstabelle, n+1*m+1in der n und m die Längen von X bzw. Y sind. Die erste Zeile und die erste Spalte sind mit Nullen gefüllt. Initialisieren Sie eine Tabelle
Füllen Sie jede Zelle der Tabelle mit der folgenden Logik.
Wenn das Zeichen, das der aktuellen Zeile und der aktuellen Spalte entspricht, übereinstimmt, füllen Sie die aktuelle Zelle, indem Sie dem diagonalen Element eins hinzufügen. Zeigen Sie mit einem Pfeil auf die diagonale Zelle.
Andernfalls nehmen Sie den Maximalwert aus der vorherigen Spalte und dem vorherigen Zeilenelement, um die aktuelle Zelle zu füllen. Zeigen Sie mit einem Pfeil auf die Zelle mit dem Maximalwert. Wenn sie gleich sind, zeigen Sie auf einen von ihnen. Füllen Sie die Werte
Schritt 2 wird wiederholt, bis die Tabelle gefüllt ist. Füllen Sie alle Werte aus
Der Wert in der letzten Zeile und der letzten Spalte ist die Länge der längsten gemeinsamen Teilsequenz. Die untere rechte Ecke ist die Länge des LCS
Um die längste gemeinsame Teilsequenz zu finden, beginnen Sie mit dem letzten Element und folgen Sie der Pfeilrichtung. Die Elemente, die dem Symbol () entsprechen, bilden die längste gemeinsame Teilsequenz. Erstellen Sie einen Pfad gemäß den Pfeilen

Somit ist die längste gemeinsame Teilsequenz CD.

LCS

Wie ist ein dynamischer Programmieralgorithmus effizienter als der rekursive Algorithmus bei der Lösung eines LCS-Problems?

Die Methode der dynamischen Programmierung reduziert die Anzahl der Funktionsaufrufe. Es speichert das Ergebnis jedes Funktionsaufrufs, sodass es in zukünftigen Aufrufen verwendet werden kann, ohne dass redundante Aufrufe erforderlich sind.

In dem obigen dynamischen Algorithmus werden die Ergebnisse, die aus jedem Vergleich zwischen Elementen von X und den Elementen von Y erhalten werden, in einer Tabelle gespeichert, so dass sie in zukünftigen Berechnungen verwendet werden können.

Die Zeit, die ein dynamischer Ansatz benötigt, ist also die Zeit, die zum Füllen der Tabelle benötigt wird (dh O (mn)). Während der Rekursionsalgorithmus die Komplexität von 2 ^{max (m, n) hat} .

Längster gemeinsamer Subsequenzalgorithmus

 X und Y sind zwei gegebene Sequenzen. Initialisieren Sie eine Tabelle LCS der Dimension X.Länge * Y.Länge X.Label = X Y.Label = Y LCS (0) () = 0 LCS () (0) = 0 Beginnen Sie mit LCS ( 1) (1) Vergleiche X (i) und Y (j) Wenn X (i) = Y (j) LCS (i) (j) = 1 + LCS (i-1, j-1) Zeigen Sie mit einem Pfeil auf LCS (i) (j) Sonst LCS (i) (j) = max (LCS (i-1) (j), LCS (i) (j-1)) Zeigen Sie mit einem Pfeil auf max (LCS (i-1) ( j), LCS (i) (j-1))

Beispiele für Python, Java und C / C ++

Python Java C C ++

 # The longest common subsequence in Python # Function to find lcs_algo def lcs_algo(S1, S2, m, n): L = ((0 for x in range(n+1)) for x in range(m+1)) # Building the mtrix in bottom-up way for i in range(m+1): for j in range(n+1): if i == 0 or j == 0: L(i)(j) = 0 elif S1(i-1) == S2(j-1): L(i)(j) = L(i-1)(j-1) + 1 else: L(i)(j) = max(L(i-1)(j), L(i)(j-1)) index = L(m)(n) lcs_algo = ("") * (index+1) lcs_algo(index) = "" i = m j = n while i> 0 and j> 0: if S1(i-1) == S2(j-1): lcs_algo(index-1) = S1(i-1) i -= 1 j -= 1 index -= 1 elif L(i-1)(j)> L(i)(j-1): i -= 1 else: j -= 1 # Printing the sub sequences print("S1 : " + S1 + "S2 : " + S2) print("LCS: " + "".join(lcs_algo)) S1 = "ACADB" S2 = "CBDA" m = len(S1) n = len(S2) lcs_algo(S1, S2, m, n)

 // The longest common subsequence in Java class LCS_ALGO ( static void lcs(String S1, String S2, int m, int n) ( int()() LCS_table = new int(m + 1)(n + 1); // Building the mtrix in bottom-up way for (int i = 0; i <= m; i++) ( for (int j = 0; j <= n; j++) ( if (i == 0 || j == 0) LCS_table(i)(j) = 0; else if (S1.charAt(i - 1) == S2.charAt(j - 1)) LCS_table(i)(j) = LCS_table(i - 1)(j - 1) + 1; else LCS_table(i)(j) = Math.max(LCS_table(i - 1)(j), LCS_table(i)(j - 1)); ) ) int index = LCS_table(m)(n); int temp = index; char() lcs = new char(index + 1); lcs(index) = ''; int i = m, j = n; while (i> 0 && j> 0) ( if (S1.charAt(i - 1) == S2.charAt(j - 1)) ( lcs(index - 1) = S1.charAt(i - 1); i--; j--; index--; ) else if (LCS_table(i - 1)(j)> LCS_table(i)(j - 1)) i--; else j--; ) // Printing the sub sequences System.out.print("S1 : " + S1 + "S2 : " + S2 + "LCS: "); for (int k = 0; k <= temp; k++) System.out.print(lcs(k)); System.out.println(""); ) public static void main(String() args) ( String S1 = "ACADB"; String S2 = "CBDA"; int m = S1.length(); int n = S2.length(); lcs(S1, S2, m, n); ) )

 // The longest common subsequence in C #include #include int i, j, m, n, LCS_table(20)(20); char S1(20) = "ACADB", S2(20) = "CBDA", b(20)(20); void lcsAlgo() ( m = strlen(S1); n = strlen(S2); // Filling 0's in the matrix for (i = 0; i <= m; i++) LCS_table(i)(0) = 0; for (i = 0; i <= n; i++) LCS_table(0)(i) = 0; // Building the mtrix in bottom-up way for (i = 1; i <= m; i++) for (j = 1; j = LCS_table(i)(j - 1)) ( LCS_table(i)(j) = LCS_table(i - 1)(j); ) else ( LCS_table(i)(j) = LCS_table(i)(j - 1); ) ) int index = LCS_table(m)(n); char lcsAlgo(index + 1); lcsAlgo(index) = ''; int i = m, j = n; while (i> 0 && j> 0) ( if (S1(i - 1) == S2(j - 1)) ( lcsAlgo(index - 1) = S1(i - 1); i--; j--; index--; ) else if (LCS_table(i - 1)(j)> LCS_table(i)(j - 1)) i--; else j--; ) // Printing the sub sequences printf("S1 : %s S2 : %s ", S1, S2); printf("LCS: %s", lcsAlgo); ) int main() ( lcsAlgo(); printf(""); )

 // The longest common subsequence in C++ #include using namespace std; void lcsAlgo(char *S1, char *S2, int m, int n) ( int LCS_table(m + 1)(n + 1); // Building the mtrix in bottom-up way for (int i = 0; i <= m; i++) ( for (int j = 0; j <= n; j++) ( if (i == 0 || j == 0) LCS_table(i)(j) = 0; else if (S1(i - 1) == S2(j - 1)) LCS_table(i)(j) = LCS_table(i - 1)(j - 1) + 1; else LCS_table(i)(j) = max(LCS_table(i - 1)(j), LCS_table(i)(j - 1)); ) ) int index = LCS_table(m)(n); char lcsAlgo(index + 1); lcsAlgo(index) = ''; int i = m, j = n; while (i> 0 && j> 0) ( if (S1(i - 1) == S2(j - 1)) ( lcsAlgo(index - 1) = S1(i - 1); i--; j--; index--; ) else if (LCS_table(i - 1)(j)> LCS_table(i)(j - 1)) i--; else j--; ) // Printing the sub sequences cout << "S1 : " << S1 << "S2 : " << S2 << "LCS: " << lcsAlgo << ""; ) int main() ( char S1() = "ACADB"; char S2() = "CBDA"; int m = strlen(S1); int n = strlen(S2); lcsAlgo(S1, S2, m, n); )