Lengste vanlige sekvens: Python, C++ Eksempel

Hva er den lengste vanlige sekvensen?

Lengste felles undersekvens (LCS) betyr at du vil bli gitt to strenger/mønstre/sekvenser av objekter. Blant disse to sekvensene/strengene må du finne den lengste undersekvensen av elementer i samme rekkefølge som finnes i både strenger eller mønstre.

Eksempel

For eksempel er det to strenger.

La oss anta at

Pattern_1 = «RGBGARGA»
Pattern_2 = «BGRARG»

Fra mønster_1 kan sekvenser produseres som "RGB", "RGGA", "RGAR". For å lage en sekvens må du opprettholde den relative posisjonen til hvert tegn i strengen.
Fra pattern_2 kan vi produsere sekvenser som "BGR", "BRAG", "RARG". Sekvenser kan produseres så lenge de opprettholder den opprinnelige strengens relative posisjon.

Begrepet relativ stilling betyr orden.

For eksempel er "BRG" en gyldig sekvens fordi "B" dukket opp først, deretter "R" og deretter "G" i det opprinnelige strengmønsteret_2. Imidlertid, hvis en sekvens er "RBRG", er den ikke gyldig. For i den originale strengen (pattern_2) kommer "B" først.

Vi har to alternativer for å finne den lengste vanlige undersekvensen fra de gitte to sekvensene eller matrisene.

Naiv metode
Dynamisk programmeringsløsning: Lengste vanlige undersekvens er også kjent som LCS.

En naiv løsning har større tidskompleksitet og er ikke den optimale løsningen. Ved å bruke Dynamic Programming Solution (DP) overvinner vi kompleksitetsproblemet.

Naiv metode

Naiv metode er en enkel tilnærming til problemet uavhengig av tidskompleksitet og andre optimaliseringsfaktorer.

Den naive metoden består av "Brute Force", flere looper, rekursive metoder i de fleste tilfeller.

Begrepet brute force betyr å gå gjennom alle mulige mønstre for et gitt problem.

Eksempel

Fra eksemplet ovenfor på mønster1 og mønster2, la oss anta at mønster1 har en lengde på m og mønster2 har en lengde på n. For å sjekke alle mulige tilfeller, må vi evaluere alle mulige undersekvenser av mønster1 med mønster2.

Her er en enkel 4 bokstavs streng "ABCD". For eksempel må vi lage en sekvens fra "ABCD." Enten kan vi ta en karakter eller ikke. Det betyr at vi har to valg for hver karakter.

De er:

Tegnet vil bli lagt til i etterfølgen.
Tegnet vil ikke bli lagt til i etterfølgen.

Her viser bildene alle sekvensene vi kan lage fra strengen "ABCD".

Sekvens med 1 tegn:

Sekvenser med 2 tegn:

Sekvenser med 3 tegn:

Fra diagrammet ovenfor er det 14 sekvenser. Hvis vi ikke tar bokstaver, i utgangspunktet en tom streng, vil den totale sekvensen være 15. Dessuten er strengen "ABCD" i seg selv en sekvens. Så de totale sekvensene er 16.

Så det er mulig å generere 2⁴ eller 16 undersekvenser fra "ABCD". Deretter en streng med en lengde på m vil ha en total etterfølge på 2^m.

For hver undersekvens må vi sjekke den for hele mønsteret2. Det vil ta 0(n) tid. 0(n) betyr kompleksitetsfunksjonen som beregner tiden det tar å utføre.

Så total tidskompleksitet blir O(n*2^m). For eksempelet har vi ovenfor sett verdien av m=8 og n=5.

Her er trinnene for den naive metoden:

Trinn 1) Ta en sekvens fra mønsteret1.
Trinn 2) Match sekvensen fra trinn 1 med mønster2.
Trinn 3) Hvis det stemmer, lagre etterfølgen.
Trinn 4) Hvis det er mer sekvens igjen i mønsteret1, gå til trinn 1 igjen.
Trinn 5) Skriv ut den lengste etterfølgen.

Optimal understruktur

Begrepet optimal underbygning betyr at en optimal løsning (enkel) kan finnes ved å løse delproblemene. For eksempel, i eksemplet ovenfor, har vi mønster1 og mønster2.

Trinn 1) Ta de to første tegnene fra hvert mønster

Trinn 2) Ta den tredje til femte karakteren fra hvert mønster.

Trinn 3) Fortsett på samme måte med de resterende tegnene.

Optimal understruktur — Rekursiv struktur av LCS-problem

Vi finner LCS på understrengen (streng generert fra en original streng). Deretter fører vi oversikt over lengden på LCS til delstrengene.

Nå, her er en annen interessant egenskap overlappende delproblemer. Et problem sies å ha overlappende delproblemer hvis problemformuleringen kan brytes opp i små delproblemer og brukes flere ganger i programmet.

Diagrammet nedenfor viser at den rekursive algoritmen kalte funksjonen med samme parameter flere ganger.

La oss for eksempel se rekursjonstreet.

I den mørke boksen kan du legge merke til overlappende underproblemer. ("RG", "RA"), ("RG",,"R") og andre kalles flere ganger.

For å optimalisere dette har vi tilnærmingen til Dynamisk programmering (DP).

Rekursiv metode med lengste komm-sekvens

Grafen som vises ovenfor er den rekursive metoden. Hver rekursiv funksjon har et grunnleggende tilfelle for å bryte rekursjonen eller begynne å returnere fra stabelen.

For denne implementeringen bruker vi en base case. Så, den algoritme er som følgende:

Hvis alle elementene før det siste elementet har en match, øk lengden med én og returner
Gi to mønstre til funksjonen, og ta maksverdien av avkastningen
Hvis ett mønster har null lengde, har vi ingen etterfølger å sammenligne. Returner 0 i dette tilfellet. Dette er basistilfellet av rekursjonen.

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)

Gjennomføring 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;
}

Utgang:

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

Utgang:

Lenght of LCS is:  5

Dynamisk programmeringsmetode for lengste felles etterfølger (LCS)

Dynamisk programmering betyr å optimalisere den vanlige rekursive metoden. For eksempel, hvis vi ser den rekursive eller naive tilnærmingsgrafen, kan vi se at det er flere samme funksjonskall. Den dynamiske programmeringsmetoden registrerer alle beregningene i en matrise og bruker den ved behov.

Vi bruker en 2D-matrise med dimensjonene mxn, der m og n er lengdene på mønster1 og mønster2.

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

Pseudokode for LCS som bruker 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 som brukes som en 2D-matrisedatastruktur for den dynamiske programmeringsmetoden.

La oss diskutere logikken vi brukte her. Trinnene er:

Trinn 1) Hvis i eller j er null, tar vi en tom streng fra de gitte to strengene og prøver å finne de vanlige undersekvensene. Men siden understrengen vi tar er tom, er undersekvenslengden 0.

Trinn 2) Hvis to tegn samsvarer, tildeler vi verdien til (i,j)-indeksen ved å øke den tidligere beregnede LCS, som er tilstede i (i-1,j-1)-indeksen (fra forrige rad).

Trinn 3) Hvis det ikke stemmer, tar vi maks LCS for de to tilstøtende indeksene. Og på denne måten må vi fylle alle verdiene i 2D-matrisen.

Trinn 4) Til slutt vil vi returnere verdien til den siste cellen i 2D-matrisen.

I utgangspunktet inneholder all verdien i 2D-matrisen lengden på vanlige undersekvenser. Blant disse inneholder den siste cellen lengden på den lengste felles undersekvensen.

Gjennomføring 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;
}

Utgang:

Length of LCS: 5

Gjennomføring 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))

Utgang:

Length of LCS: 5

Så begge strengene har den lengste felles etterfølgen av lengde 5.

I et nøtteskall, vi beregner ganske enkelt hver oppgave én gang i DP-metoden i DP-metoden. I den rekursive metoden kan vi ha overlappende underproblemer.

I denne dynamiske programmeringsalgoritmen bruker vi en 2D-matrise. Det vil være gitt to strenger (anta at begge har lengde n). Da er plassen som trengs i matrisen nx n. Hvis strengene er store nok, trenger vi en minneoptimalisert versjon av DP-løsningen.

Den forenklede logikken som ble tatt i koden er:

Erklær en 2D-array DP[m][n].
Fyll den første raden og den første kolonnen i DP-matrisen med 0.
Ta i og j for iterasjonen.
Hvis mønster1[i] er lik mønster2[j], så oppdater DP[i][j] = DP[i-1][j-1] + 1
Hvis mønster1[i] ikke er lik mønster2[j], vil DP[i][j] være maksimumsverdien mellom DP[i-1][j] og DP[i][j-1].
Fortsett til i og j når m og n.
Det siste elementet eller DP[m-1][n-1], vil inneholde lengden.

Her er det adressert som DP[m-1][n-1], fordi array-indeksen begynner fra 0.

Sammendrag

DP-metoden har lavere tidskompleksitet; det er O(mn), der m og n er lengden på inndatastrengen eller matrisen.
DP er en raskere tilnærming enn den rekursive, med tidskompleksiteten til O(n*2^m).
Dynamisk programmering (DP) er ikke minneoptimalisert. Vi brukte en 2D-array som har lengden m*n. Så romkompleksiteten er (m*n).
Rekursiv metode, i verste fall vil det høyeste minnet det vil oppta være m+n, i utgangspunktet den totale lengden på den innlagte strengen.
Dagens moderne datamaskin er tilstrekkelig til å håndtere denne mengden minne.

Hva er den lengste vanlige sekvensen?

Eksempel

Naiv metode

Eksempel

Optimal understruktur

RELATERTE ARTIKLER

Rekursiv metode med lengste komm-sekvens

Gjennomføring i C++

Implementering i python

Dynamisk programmeringsmetode for lengste felles etterfølger (LCS)

Gjennomføring i C++

Gjennomføring i Python

Sammendrag

Registrer deg for nyhetsbrevet