Længste fælles efterfølger: Python, C++ Eksempel

Hvad er den længste fælles efterfølger?

Længste fælles delsekvens (LCS) betyder, at du får to strenge/mønstre/sekvenser af objekter. Blandt disse to sekvenser/strenge skal du finde den længste undersekvens af elementer i samme rækkefølge, der er til stede i både strenge eller mønstre.

Eksempel

For eksempel er der to strenge.

Lad os antage, at

Pattern_1 = "RGBGARGA"
Pattern_2 = "BGRARG"

Fra mønster_1 kan sekvenser produceres som "RGB", "RGGA", "RGAR". For at oprette en sekvens skal du bevare den relative placering af hvert tegn i strengen.
Fra pattern_2 kan vi producere sekvenser som "BGR", "BRAG", "RARG". Sekvenser kan produceres, så længe de bevarer den oprindelige strengs relative position.

Udtrykket relativ position betyder orden.

For eksempel er "BRG" en gyldig sekvens, fordi "B" dukkede op først, derefter "R" og derefter "G" i det originale strengmønster_2. Men hvis en sekvens er "RBRG", er den ikke gyldig. For i den originale streng (pattern_2) kommer "B" først.

Vi har to muligheder for at finde den længste fælles undersekvens fra de givne to sekvenser eller arrays.

Naiv metode
Dynamisk programmeringsløsning: Længste fælles undersekvens er også kendt som LCS.

En naiv løsning har større tidskompleksitet og er ikke den optimale løsning. Ved hjælp af Dynamic Programming Solution (DP) overvinder vi kompleksitetsproblemet.

Naiv metode

Naiv metode er en simpel tilgang til problemet uanset tidskompleksiteten og andre optimeringsfaktorer.

Den naive metode består af "Brute Force", multiple loops, rekursive metoder i de fleste tilfælde.

Udtrykket brute force betyder at gennemgå alle mulige mønstre for et givet problem.

Eksempel

Fra ovenstående eksempel på mønster1 og mønster2, lad os antage, at mønster1 har en længde på m og mønster2 har en længde på n. For at kontrollere alle mulige tilfælde er vi nødt til at evaluere alle mulige efterfølger af mønster1 med mønster2.

Her er en simpel 4-bogstavs streng "ABCD". For eksempel skal vi oprette en sekvens fra "ABCD." Enten kan vi tage en karakter eller ej. Det betyder, at vi har to valg for hver karakter.

De er:

Tegnet vil blive tilføjet til efterfølgen.
Tegnet vil ikke blive tilføjet til efterfølgen.

Her viser billederne alle de sekvenser, vi kan lave fra strengen "ABCD".

Sekvens med 1 tegn:

Sekvenser med 2 tegn:

Sekvenser med 3 tegn:

Fra ovenstående diagram er der 14 sekvenser. Hvis vi ikke tager bogstaver, dybest set en tom streng, vil de samlede sekvenser være 15. Desuden er strengen "ABCD" i sig selv en sekvens. Så de samlede sekvenser er 16.

Så det er muligt at generere 2⁴ eller 16 efterfølger fra "ABCD". Derefter en snor med en længde på m skal i alt efterfølge 2^m.

For hver undersekvens skal vi kontrollere det for hele mønsteret2. Det vil tage 0(n) tid. 0(n) betyder kompleksitetsfunktionen, der beregner den tid, det tager at udføre.

Så den samlede tidskompleksitet bliver O(n*2^m). For eksemplet har vi ovenfor set værdien af m=8 og n=5.

Her er trinene i den naive metode:

Trin 1) Tag en sekvens fra mønsteret1.
Trin 2) Match sekvensen fra trin 1 med mønster2.
Trin 3) Hvis det matcher, skal du gemme efterfølgen.
Trin 4) Hvis der er mere sekvens tilbage i mønsteret1, så gå til trin 1 igen.
Trin 5) Udskriv den længste sekvens.

Optimal underbygning

Begrebet optimal underbygning betyder, at en optimal løsning (simpel) kan findes ved at løse delproblemerne. For eksempel, i ovenstående eksempel har vi mønster1 og mønster2.

Trin 1) Tag de første to tegn fra hvert mønster

Trin 2) Tag det tredje til femte tegn fra hvert mønster.

Trin 3) Fortsæt på samme måde med de resterende tegn.

Optimal underbygning — Rekursiv struktur af LCS-problem

Vi finder LCS på understrengen (streng genereret ud fra en original streng). Derefter registrerer vi længden af LCS af understrengene.

Her er en anden interessant egenskab overlappende delproblemer. Et problem siges at have overlappende underproblemer, hvis problemformuleringen kan opdeles i små underproblemer og bruges flere gange i programmet.

Diagrammet nedenfor viser, at den rekursive algoritme kaldte funktionen med den samme parameter flere gange.

Lad os for eksempel se rekursionstræet.

I den mørke boks kan du bemærke overlappende underproblemer. ("RG", "RA"), ("RG",,"R") og andre kaldes flere gange.

For at optimere dette har vi tilgangen til Dynamisk programmering (DP).

Rekursiv metode med længste kommunikationssekvens

Grafen vist ovenfor er den rekursive metode. Hver rekursiv funktion har et basistilfælde til at bryde rekursionen eller begynde at vende tilbage fra sin stak.

Til denne implementering vil vi bruge en basiscase. Så algoritme er som følgende:

Hvis alle elementer før det sidste element har en match, så øg længden med en og vend tilbage
Send to mønstre til funktionen, og tag den maksimale værdi af returneringen
Hvis et mønster har nul længde, så har vi ingen efterfølger at sammenligne. Returner 0 i dette tilfælde. Dette er grundtilfældet af rekursionen.

Pseudokode:

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)

Gennemførelse i 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;
}

Output:

Length of LCS is: 5

Implementering i 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)))

Output:

Lenght of LCS is:  5

Dynamisk programmeringsmetode for længste fælles sekvens (LCS)

Dynamisk programmering betyder optimering af den almindelige rekursive metode. For eksempel, hvis vi ser den rekursive eller naive tilgangsgraf, kan vi se, at der er flere samme funktionskald. Den dynamiske programmeringsmetode registrerer alle beregninger i et array og bruger det, når det er nødvendigt.

Vi bruger et 2D-array med dimensionerne mxn, hvor m og n er længderne af mønster1 og mønster2.

Til 2D-array, kan vi bruge Liste datastrukturer i python eller vektor/array datastrukturer i C++.

Pseudokode for LCS ved hjælp af 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]

Her er tabellen LCS, der bruges som en 2D-array-datastruktur til den dynamiske programmeringstilgang.

Lad os diskutere den logik, vi brugte her. Trin er:

Trin 1) Hvis i eller j er nul, tager vi en tom streng fra de givne to strenge og forsøger at finde de fælles undersekvenser. Men da den understreng, vi tager, er tom, er undersekvenslængden 0.

Trin 2) Hvis to tegn matcher, tildeler vi værdien til (i,j)-indekset ved at øge den tidligere beregnede LCS, som er til stede i (i-1,j-1)-indekset (fra den forrige række).

Trin 3) Hvis det ikke stemmer overens, tager vi den maksimale LCS for de to tilstødende indekser. Og på denne måde skal vi udfylde alle værdierne i 2D-arrayet.

Trin 4) Til sidst returnerer vi værdien af den sidste celle i 2D-arrayet.

Grundlæggende indeholder al værdien i 2D-arrayet længden af fælles undersekvenser. Blandt disse indeholder den sidste celle længden af den længste fælles undersekvens.

Gennemførelse i 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;
}

Output:

Length of LCS: 5

Gennemførelse i 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))

Output:

Length of LCS: 5

Så begge strenge har den længste fælles efterfølger af længde 5.

I en nøddeskal beregner vi simpelthen hver opgave én gang i DP-metoden i DP-metoden. I den rekursive metode kan vi have overlappende underproblemer.

I denne dynamiske programmeringsalgoritme bruger vi en 2D-matrix. Der vil være givet to strenge (antag at begge har længden n). Så er den nødvendige plads i arrayet nx n. Hvis strengene er store nok, skal vi bruge en hukommelsesoptimeret version af DP-løsningen.

Den forenklede logik, der blev taget i koden, er:

Erklær en 2D Array DP[m][n].
Udfyld den første række og første kolonne i DP-arrayet med 0.
Tag i og j for iterationen.
Hvis mønster1[i] er lig med mønster2[j], så opdater DP[i][j] = DP[i-1][j-1] + 1
Hvis mønster1[i] ikke er lig med mønster2[j], så vil DP[i][j] være den maksimale værdi mellem DP[i-1][j] og DP[i][j-1].
Fortsæt indtil i og j når m og n.
Det sidste element eller DP[m-1][n-1], vil indeholde længden.

Her adresseres det som DP[m-1][n-1], fordi array-indekset begynder fra 0.

Resumé

DP-metoden har lavere tidskompleksitet; det er O(mn), hvor m og n er længden af inputstrengen eller arrayet.
DP er en hurtigere tilgang end den rekursive, med tidskompleksiteten på O(n*2^m).
Dynamisk programmering (DP) er ikke hukommelsesoptimeret. Vi brugte et 2D-array, der har længden m*n. Så rumkompleksiteten er (m*n).
Rekursiv metode, i det værste tilfælde vil den højeste hukommelse, den vil optage, være m+n, dybest set den samlede længde af den indtastede streng.
Dagens moderne computer er tilstrækkelig til at håndtere denne mængde hukommelse.

Hvad er den længste fælles efterfølger?

Eksempel

Naiv metode

Eksempel

Optimal underbygning

RELATEREDE ARTIKLER

Rekursiv metode med længste kommunikationssekvens

Gennemførelse i C++

Implementering i python

Dynamisk programmeringsmetode for længste fælles sekvens (LCS)

Gennemførelse i C++

Gennemførelse i Python

Resumé

Tilmeld dig nyhedsbrevet