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

Was ist die längste gemeinsame Folge?

Longest Common Subsequence (LCS) bedeutet, dass Sie zwei Zeichenfolgen/Muster/Sequenzen von Objekten erhalten. Unter diesen beiden Sequenzen/Strings müssen Sie die längste Teilsequenz von Elementen in derselben Reihenfolge finden, die in beiden Strings oder Mustern vorhanden sind.

Beispiel

Beispielsweise werden zwei Zeichenfolgen bereitgestellt.

Nehmen wir an, dass

Muster_1 = „RGBGARGA“
Pattern_2 = „BGRARG“

• Aus Muster_1 können Sequenzen wie „RGB“, „RGGA“, „RGAR“ erzeugt werden. Um eine Sequenz zu erstellen, müssen Sie die relative Position jedes Zeichens in der Zeichenfolge beibehalten.
• Aus Muster_2 können wir Sequenzen wie „BGR“, „BRAG“, „RARG“ erzeugen. Sequenzen können erstellt werden, solange sie die relative Position der ursprünglichen Zeichenfolge beibehalten.

Der Begriff relative Position bedeutet Ordnung.

Beispielsweise ist „BRG“ eine gültige Sequenz, da „B“ zuerst vorkam, dann „R“ und dann „G“ im ursprünglichen Zeichenfolgenmuster_2. Wenn eine Sequenz jedoch „RBRG“ ist, ist sie ungültig. Denn im Originalstring (pattern_2) steht „B“ an erster Stelle.

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 die optimale Lösung. Mit Dynamic Programming Solution (DP) überwinden wir das Komplexitätsproblem.

Naive Methode

Die naive Methode ist eine einfache Herangehensweise an das Problem, unabhängig von der Zeitkomplexität und anderen Optimierungsfaktoren.

Die Naive-Methode besteht in den meisten Fällen aus „Brute Force“, mehreren Schleifen und rekursiven Methoden.

Der Begriff Brute Force bedeutet, alle möglichen Muster für ein bestimmtes 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 eine einfache 4-Buchstaben-Zeichenfolge „ABCD“. Beispielsweise müssen wir eine Sequenz aus „ABCD“ erstellen. Entweder wir können einen Charakter annehmen oder nicht. Das bedeutet, dass wir für jeden Charakter zwei Möglichkeiten haben.

Sie sind:

• 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, im Grunde eine leere Zeichenfolge, nehmen, beträgt die Gesamtzahl der Sequenzen 15. Darüber hinaus ist die Zeichenfolge „ABCD“ selbst eine Sequenz. Die Gesamtzahl der Sequenzen beträgt also 16.

Es ist also möglich, 2 zu generieren⁴ oder 16 Teilsequenzen von „ABCD“. Dann eine Zeichenfolge mit einer Länge von m muss eine Teilfolge von 2 ergeben^m.

Für jede Teilsequenz müssen wir das gesamte Muster2 überprüfen. Dies dauert 0(n). 0(n) steht für die Komplexitätsfunktion, die die für die Ausführung benötigte Zeit berechnet.

Die Gesamtzeitkomplexität wird also O(n*2^m). Für das Beispiel haben wir oben den Wert von m=8 und n=5 gesehen.

Hier sind die Schritte der Naiven Methode:

Schritt 1) Nehmen Sie eine Sequenz aus dem Muster1.
Schritt 2) Ordnen Sie die Sequenz aus Schritt 1 dem Muster 2 zu.
Schritt 3) Wenn es übereinstimmt, speichern Sie die Teilsequenz.
Schritt 4) Wenn im Muster1 noch mehr Sequenz übrig ist, fahren Sie erneut mit Schritt 1 fort.
Schritt 5) Drucken Sie die längste Teilsequenz.

Optimale Unterstruktur

Der Begriff „optimale Unterstruktur“ bedeutet, dass durch die Lösung der Teilprobleme eine optimale (einfache) Lösung gefunden werden kann. Im obigen Beispiel haben wir beispielsweise Muster1 und Muster2.

Schritt 1) Nehmen Sie 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.

Wir finden das LCS im Sub-String (String, der aus einem Original-String generiert wurde). Dann führen wir Aufzeichnungen über die Länge des LCS der Teilzeichenfolgen.

Nun, hier ist eine weitere interessante Eigenschaft überlappende Teilprobleme. Ein Problem weist überlappende Teilprobleme auf, 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.

Sehen wir uns zum Beispiel den Rekursionsbaum an.

In der dunkel gefärbten Box sind sich überschneidende Teilprobleme zu erkennen. („RG“, „RA“), („RG“, „R“) und weitere werden mehrfach genannt.

Um dies zu optimieren, haben wir den Ansatz von Dynamische Programmierung (DP).

Rekursive Methode der längsten Kommunikationssequenz

Die oben gezeigte Grafik ist die rekursive Methode. Jede rekursive Funktion verfügt über einen Basisfall, um die Rekursion zu unterbrechen oder von ihrem Stapel zurückzukehren.

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

• Wenn alle Elemente vor dem letzten Element übereinstimmen, erhöhen Sie die Länge um eins und kehren Sie zurück
• Übergeben Sie zwei Muster an die Funktion und übernehmen Sie den Maximalwert der Rückgabe
• 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.

Pseudocode:

def lcs:
    input: pattern_1, pattern_2, len_1, len_2
if len_1 or len_2 is zero:
    then
return 0
if pattern_1[len_1 - 1] equals pattern_2[len_2 - 1]
then
return 1 + lcs(pattern_1, pattern_2,
    len_1 - 1, len_2 - 1)
else
    max of 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

Implementierung 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("Lenght of LCS is: ", lcs(pattern_1, pattern_2, len(pattern_1), len(pattern_2)))

Ausgang:

Lenght of LCS is:  5

Dynamische Programmiermethode der Longest Common Subsequence (LCS)

Dynamische Programmierung bedeutet die Optimierung der einfachen rekursiven Methode. Wenn wir beispielsweise den rekursiven oder naiven Ansatzgraphen sehen, können wir erkennen, dass es mehrere gleiche Funktionsaufrufe gibt. Die Methode der dynamischen Programmierung zeichnet alle Berechnungen in einem Array auf und verwendet sie bei Bedarf.

Wir verwenden ein 2D-Array mit den Abmessungen mxn, wobei m und n die Längen von Muster1 und Muster2 sind.

Für 2D-Arraykönnen wir Listen-Datenstrukturen in Python oder Vektor-/Array-Datenstrukturen in C++.

Pseudocode 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 Programmieransatz verwendet wird.

Lassen Sie uns die Logik besprechen, die wir hier verwendet haben. Schritte sind:

Schritt 1) Wenn i oder j Null ist, nehmen wir eine leere Zeichenfolge aus den beiden angegebenen Zeichenfolgen und versuchen, die gemeinsamen Teilsequenzen zu finden. Da der Teilstring, den wir verwenden, jedoch leer ist, beträgt die Länge der Teilsequenz 0.

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

Schritt 3) Wenn es nicht übereinstimmt, verwenden wir den maximalen LCS der beiden benachbarten Indizes. Und auf diese Weise müssen wir alle Werte im 2D-Array füllen.

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

Grundsätzlich enthalten alle Werte im 2D-Array die Länge gemeinsamer Teilsequenzen. Unter diesen enthält die letzte Zelle die Länge der längsten gemeinsamen Teilsequenz.

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 & lt; n + 1; i++) {
    for (int j = 0; j & lt; 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, wir berechnen einfach jede Aufgabe einmal in der DP-Methode in der DP-Methode. Bei der rekursiven Methode kann es zu überlappenden Teilproblemen kommen.

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 Muster1[i] gleich Muster2[j] ist, aktualisieren Sie DP[i][j] = DP[i-1][j-1] + 1
• Wenn Muster1[i] nicht gleich Muster2[j] ist, 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 oder DP[m-1][n-1] enthält die Länge.

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

Zusammenfassung

• Die DP-Methode weist eine geringere Zeitkomplexität auf; sie beträgt O(mn), wobei m und n die Länge der Eingabezeichenfolge oder des Eingabearrays sind.
• DP ist ein schnellerer Ansatz als der rekursive, mit der Zeitkomplexität von O(n*2^m).
• Dynamische Programmierung (DP) ist nicht speicheroptimiert. Wir haben ein 2D-Array mit der Länge m*n verwendet. Die Speicherkomplexität beträgt also (m*n).
• Rekursive Methode: Im schlimmsten Fall beträgt der höchste Speicherbedarf m+n, im Grunde die Gesamtlänge der eingegebenen Zeichenfolge.
• Der heutige moderne Computer reicht aus, um diese Speichermenge zu bewältigen.