Längste gemeinsame Teilfolge: Python, C++ Beispiel

Was ist die längste gemeinsame Folge?

Die längste gemeinsame Teilfolge (LCS) bedeutet, dass Ihnen zwei Zeichenketten, Muster oder Sequenzen von Objekten gegeben sind. Sie müssen unter diesen beiden Sequenzen oder Zeichenketten die längste Teilfolge von Elementen finden, die in beiden Zeichenketten oder Mustern in der gleichen Reihenfolge vorkommen.

Beispiel

Beispielsweise sind zwei Zeichenketten gegeben. Nehmen wir an, dass:

Muster_1 = „RGBGARGA“
Pattern_2 = „BGRARG“

• Aus Muster_1 lassen sich Sequenzen wie „RGB“, „RGGA“, „RGAR“ erzeugen. Um eine Sequenz zu erstellen, muss die relative Position jedes Zeichens in der Zeichenkette beibehalten werden.
• Aus Muster_2 lassen sich Sequenzen wie „BGR“, „BRAG“ und „RARG“ erzeugen. Sequenzen können erzeugt werden, solange die relative Position der ursprünglichen Zeichenkette erhalten bleibt.

Der Begriff relative Position bedeutet Ordnung.

Beispielsweise ist die Sequenz „BRG“ gültig, da im ursprünglichen Stringmuster „pattern_2“ zuerst „B“, dann „R“ und schließlich „G“ vorkommt. Die Sequenz „RBRG“ hingegen ist ungültig, da im ursprünglichen Stringmuster (pattern_2) „B“ an erster Stelle steht.

Wir haben zwei Möglichkeiten, die längste gemeinsame Teilsequenz aus den beiden gegebenen Sequenzen oder Arrays zu finden.

• Naive Methode
• Dynamische Programmierlösung: Die längste gemeinsame Teilsequenz wird auch als LCS bezeichnet.

Eine naive Lösung hat eine höhere Zeitkomplexität und ist nicht optimal. Mithilfe der dynamischen Programmierung (DP) lässt sich dieses Komplexitätsproblem überwinden.

Naive Methode

Die naive Methode ist ein einfacher Lösungsansatz für das Problem, unabhängig von der Zeitkomplexität und anderen Optimierungsfaktoren. Sie besteht in den meisten Fällen aus einer Art „Brute-Force“-Methode, mehreren Schleifen und rekursiven Aufrufen. Brute-Force bedeutet, alle möglichen Lösungsmuster für ein gegebenes Problem durchzugehen.

Beispiel

Nehmen wir aus dem obigen Beispiel von Muster1 und Muster2 an, dass Muster1 eine Länge von m und Muster2 eine Länge von n hat. Um jeden möglichen Fall zu überprüfen, müssen wir jede mögliche Teilfolge von Muster1 mit Muster2 auswerten.

Hier ist die einfache 4-Buchstaben-Zeichenkette „ABCD“. Wir müssen beispielsweise aus „ABCD“ eine Sequenz erstellen. Dabei können wir entweder ein Zeichen verwenden oder nicht. Das bedeutet, dass wir für jedes Zeichen zwei Möglichkeiten haben:

• Das Zeichen wird zur Teilsequenz hinzugefügt.
• Das Zeichen wird nicht zur Teilsequenz hinzugefügt.

Hier zeigen die Bilder alle Sequenzen, die wir aus der Zeichenfolge „ABCD“ erstellen können.

Sequenz mit 1 Zeichen:

Sequenzen mit 2 Zeichen:

Sequenzen mit 3 Zeichen:

Aus dem obigen Diagramm ergeben sich 14 Sequenzen. Wenn wir keine Buchstaben berücksichtigen, also im Grunde eine leere Zeichenkette betrachten, beträgt die Gesamtzahl der Sequenzen 15. Darüber hinaus ist die Zeichenkette „ABCD“ selbst eine Sequenz. Somit ergibt sich eine Gesamtzahl von 16 Sequenzen.

Es ist also möglich, aus „ABCD“ 2⁴ oder 16 Teilfolgen zu erzeugen. Dann kann man eine Zeichenkette der Länge m wird eine Gesamtteilfolge von 2^m haben.

Für jede Teilsequenz muss das gesamte Muster² überprüft werden. Dies benötigt O(n) Zeit. O(n) bezeichnet die Komplexitätsfunktion, die die Ausführungszeit berechnet.

Die Gesamtzeitkomplexität wird also O(n*2^m). Im obigen Beispiel gilt: m=8 und n=5.

Hier sind die Schritte der Naiven Methode:

Schritt 1) Nimm eine Sequenz aus Muster1.
Schritt 2) Ordne die Sequenz aus Schritt 1 dem Muster 2 zu.
Schritt 3) Wenn es übereinstimmt, speichern Sie die Teilsequenz.
Schritt 4) Falls in Muster1 noch weitere Sequenzen übrig sind, gehe erneut zu Schritt 1.
Schritt 5) Drucken Sie die längste Teilsequenz.

Optimale Unterstruktur

Der Begriff „optimale Teilstruktur“ bedeutet, dass eine optimale Lösung durch Lösen der Teilprobleme gefunden werden kann. Im obigen Beispiel haben wir beispielsweise Muster 1 und Muster 2.

Schritt 1) Nimm die ersten beiden Zeichen aus jedem Muster.

Schritt 2) Nehmen Sie aus jedem Muster das dritte bis fünfte Zeichen.

Schritt 3) Fahren Sie analog mit den restlichen Zeichen fort.

Rekursive Struktur des LCS-Problems

Wir ermitteln die längste gemeinsame Teilzeichenkette (LCS) der Teilzeichenkette (einer aus einer ursprünglichen Zeichenkette erzeugten Zeichenkette). Anschließend speichern wir die Länge der LCS der Teilzeichenketten.

Nun, hier ist eine weitere interessante Eigenschaft überlappenping TeilproblemeMan sagt, ein Problem weise Überschneidungen auf.ping Teilprobleme, wenn die Problemstellung in kleine Teilprobleme zerlegt und mehrmals im Programm verwendet werden kann.

Das folgende Diagramm zeigt, dass der rekursive Algorithmus die Funktion mehrmals mit demselben Parameter aufgerufen hat.

Betrachten Sie beispielsweise den Rekursionsbaum. Im dunkel gefärbten Kasten können Sie Überlappungen erkennen.ping Teilprobleme. („RG“, „RA“), („RG“, „R“) und andere werden mehrmals aufgerufen.

Um dies zu optimieren, verfolgen wir folgenden Ansatz: Dynamische Programmierung (DP).

Rekursives Verfahren zur Bestimmung der längsten gemeinsamen Teilfolge

Das obige Diagramm zeigt die rekursive Methode. Jede rekursive Funktion hat einen Basisfall, der die Rekursion abbricht oder dazu führt, dass ein Wert vom Stack zurückgegeben wird.

Für diese Implementierung verwenden wir einen Basisfall. Also, Algorithmus ist wie folgt:

• Wenn alle Elemente vor dem letzten Element eine Übereinstimmung haben, dann erhöhe die Länge um eins und gib die Funktion zurück.
• Übergeben Sie der Funktion zwei Muster und nehmen Sie den Maximalwert des Rückgabewerts.
• Wenn ein Muster die Länge Null hat, haben wir keine Teilfolge zum Vergleichen. Geben Sie in diesem Fall 0 zurück. Dies ist der Basisfall der Rekursion.

Spitzname Code:

def lcs:
    input: pattern_1, pattern_2, len_1, len_2
    if len_1 or len_2 is zero:
        return 0
    if pattern_1[len_1 - 1] equals pattern_2[len_2 - 1]:
        return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1)
    else:
        return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2),
                   lcs(pattern_1, pattern_2, len_1, len_2 - 1))

Umsetzung in C++

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int lcs(string pattern_1, string pattern_2, int len_1, int len_2) {
  if (len_1 == 0 || len_2 == 0)
    return 0;
  if (pattern_1[len_1 - 1] == pattern_2[len_2 - 1]) {
    return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1);
  } else {
    return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2), lcs(pattern_1, pattern_2, len_1, len_2 - 1));
  }
}
int main() {
  string pattern_1, pattern_2;
  pattern_1 = "RGBGARGA";
  pattern_2 = "BGRARG";
  cout<<"Length of LCS is: "<<lcs(pattern_1, pattern_2, pattern_1.size(), pattern_2.size())<<endl;
}

Ausgang:

Length of LCS is: 5

Umsetzung in Python

def lcs(pattern_1, pattern_2, len_1, len_2):
    if len_1 == 0 or len_2 == 0:
        return 0
    if pattern_1[len_1 - 1] == pattern_2[len_2 - 1]:
        return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1)
    else:
        return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2),
                   lcs(pattern_1, pattern_2, len_1, len_2 - 1))

pattern_1 = "RGBGARGA"
pattern_2 = "BGRARG"
print("Length of LCS is: ", lcs(pattern_1, pattern_2, len(pattern_1), len(pattern_2)))

Ausgang:

Length of LCS is:  5

Dynamische Programmierungsmethode zur Bestimmung der längsten gemeinsamen Teilfolge (LCS)

Dynamische Programmierung bedeutet die Optimierung der einfachen rekursiven Methode. Betrachtet man beispielsweise den Graphen des rekursiven oder naiven Ansatzes, so sieht man, dass es mehrere identische Funktionsaufrufe gibt. Die Methode der dynamischen Programmierung speichert alle Berechnungen in einem Array und verwendet sie bei Bedarf wieder.

Wir verwenden ein zweidimensionales Array der Dimensionen m x n, wobei m und n die Längen von Muster1 bzw. Muster2 sind. 2D-ArrayWir können Listendatenstrukturen verwenden in Python oder Vektor-/Array-Datenstrukturen in C++.

Spitzname Code für LCS mit DP:

LCS(pattern_1, pattern_2):
    m = length of pattern_1 + 1
    n = length of pattern_2 + 1
    dp[n][m]
    for i in range 0 to n + 1:
        for j in range 0 to m + 1:
            if i or j equals to 0:
                dp[i][j] = 0
            else if pattern_1[i] == pattern_2[j]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]

Hier ist die Tabelle LCS, die als 2D-Array-Datenstruktur für den dynamischen Programmierungsansatz verwendet wird.

Lassen Sie uns die hier angewandte Logik besprechen. Die Schritte sind:

Schritt 1) Wenn i oder j gleich null ist, wird aus den beiden gegebenen Zeichenketten eine leere Zeichenkette extrahiert und versucht, die gemeinsamen Teilfolgen zu finden. Da die extrahierte Teilzeichenkette jedoch leer ist, beträgt die Länge der Teilfolge 0.

Schritt 2) Wenn zwei Zeichen übereinstimmen, weisen wir dem Index (i,j) den Wert zu, indem wir die zuvor berechnete LCS, die im Index (i-1,j-1) (aus der vorherigen Zeile) vorhanden ist, inkrementieren.

Schritt 3) Falls keine Übereinstimmung besteht, nehmen wir das größte gemeinsame Teiler (kgV) der beiden benachbarten Indizes. Auf diese Weise müssen wir alle Werte im zweidimensionalen Array auffüllen.

Schritt 4) Schließlich geben wir den Wert der letzten Zelle des 2D-Arrays zurück.

Im Prinzip enthalten alle Werte im zweidimensionalen Array die Länge gemeinsamer Teilfolgen. Die letzte Zelle enthält dabei die Länge der längsten gemeinsamen Teilfolge.

Umsetzung in C++

#include<iostream>
using namespace std;
int lcs(string pattern_1, string pattern_2) {
  int m = pattern_1.size();
  int n = pattern_2.size();
  // dp will store solutions as the iteration goes on
  int dp[n + 1][m + 1];
  for (int i = 0; i < n + 1; i++) {
    for (int j = 0; j < m + 1; j++) {
      if (i == 0 || j == 0) {
        dp[i][j] = 0;
      } else if (pattern_2[i - 1] == pattern_1[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[n][m];
}
int main() {
  string pattern_1 = "RGBGARGA";
  string pattern_2 = "BGRARG";
  cout<<"Length of LCS: "<<lcs(pattern_1, pattern_2)<<endl;
}

Ausgang:

Length of LCS: 5

Umsetzung in Python

def lcs(pattern_1, pattern_2):
    m = len(pattern_1)
    n = len(pattern_2)
    # dp will store solutions as the iteration goes on
    dp = [[None] * (n + 1) for item in range(m + 1)]
    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0 or j == 0:
                dp[i][j] = 0
            elif pattern_1[i - 1] == pattern_2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

pattern_1 = "RGBGARGA"
pattern_2 = "BGRARG"
print("Length of LCS: ", lcs(pattern_1, pattern_2))

Ausgang:

Length of LCS: 5

Beide Strings haben also die längste gemeinsame Teilsequenz der Länge 5.

Kurz gesagt, berechnen wir im DP-Verfahren jede Aufgabe nur einmal. Im rekursiven Verfahren kann es zu Überschneidungen kommen.ping Teilprobleme.

In diesem dynamischen Programmieralgorithmus verwenden wir eine 2D-Matrix. Es werden zwei Zeichenfolgen angegeben (angenommen, beide haben die Länge n). Dann ist der im Array benötigte Platz nx n. Wenn die Strings groß genug sind, benötigen wir eine speicheroptimierte Version der DP-Lösung.

Die vereinfachte Logik, die im Code übernommen wurde, lautet:

• Deklarieren Sie ein 2D-Array DP[m][n].
• Füllen Sie die erste Zeile und erste Spalte des DP-Arrays mit 0.
• Nehmen Sie i und j für die Iteration.
• Wenn pattern1[i] gleich pattern2[j] ist, dann aktualisiere DP[i][j] = DP[i-1][j-1] + 1.
• Wenn pattern1[i] nicht gleich pattern2[j] ist, dann ist DP[i][j] der Maximalwert zwischen DP[i-1][j] und DP[i][j-1].
• Fahren Sie fort, bis i und j m und n erreichen.
• Das letzte Element, DP[m-1][n-1], enthält die Länge.

Hier wird es als DP[m-1][n-1] adressiert, da der Array-Index bei 0 beginnt.

Häufig gestellte Fragen