Langste gemeenschappelijke vervolgreeks: Python, C++ Voorbeeld

Wat is de langste gemeenschappelijke deelreeks?

Longest Common Subsequence (LCS) betekent dat u twee strings/patronen/reeksen van objecten krijgt. Van deze twee reeksen/strings moet je de langste subreeks van elementen in dezelfde volgorde vinden die in beide strings of patronen aanwezig is.

Voorbeeld

Er zijn bijvoorbeeld twee strings aanwezig.

Laten we aannemen dat,

Patroon_1 = “RGBGARGA”
Patroon_2 = "BGRARG"

• Vanaf patroon_1 kunnen sequenties worden geproduceerd zoals “RGB”, “RGGA”, “RGAR”. Om een ​​reeks te maken, moet u de relatieve positie van elk teken in de tekenreeks behouden.
• Uit patroon_2 kunnen we reeksen produceren zoals "BGR", "BRAG", "RARG". Reeksen kunnen worden geproduceerd zolang ze de relatieve positie van de oorspronkelijke string behouden.

De term relatieve positie betekent orde.

'BRG' is bijvoorbeeld een geldige reeks omdat 'B' eerst verscheen, vervolgens 'R' en vervolgens 'G' in het oorspronkelijke tekenreekspatroon_2. Als een reeks echter “RBRG” is, is deze niet geldig. Omdat in de originele string (patroon_2) “B” op de eerste plaats komt.

We hebben twee opties om de langste gemeenschappelijke deelreeks uit de gegeven twee reeksen of arrays te vinden.

• Naïeve methode
• Dynamische programmeeroplossing: de langste gemeenschappelijke vervolgreeks wordt ook wel LCS genoemd.

Een naïeve oplossing heeft een grotere tijdcomplexiteit en is niet de optimale oplossing. Met behulp van Dynamic Programming Solution (DP) overwinnen we het complexiteitsprobleem.

Naïeve methode

De naïeve methode is een eenvoudige benadering van het probleem, ongeacht de tijdcomplexiteit en andere optimalisatiefactoren.

De Naïeve methode bestaat uit “Brute Force”, meerdere lussen, in de meeste gevallen recursieve methoden.

De term brute kracht betekent het doorlopen van alle mogelijke patronen voor een bepaald probleem.

Voorbeeld

Laten we, uitgaande van het bovenstaande voorbeeld van patroon1 en patroon2, aannemen dat patroon1 een lengte heeft van m en dat patroon2 een lengte heeft van n. Om elk mogelijk geval te controleren, moeten we elke mogelijke deelreeks van patroon1 evalueren met patroon2.

Hier is een eenvoudige reeks van vier letters "ABCD". We moeten bijvoorbeeld een reeks maken van 'ABCD'. Ofwel kunnen we een personage aannemen of niet. Dat betekent dat we voor elk personage twee keuzes hebben.

Dat zijn:

• Het personage wordt aan de vervolgreeks toegevoegd.
• Het teken wordt niet aan de vervolgreeks toegevoegd.

Hier tonen de afbeeldingen alle reeksen die we kunnen maken uit de reeks "ABCD".

Reeks met 1 teken:

Reeksen met 2 karakters:

Reeksen met 3 karakters:

Uit het bovenstaande diagram zijn er 14 reeksen. Als we geen letters nemen, wat eigenlijk een lege string is, zal het totaal aantal reeksen 15 zijn. Bovendien is de string “ABCD” zelf een reeks. Het totaal aantal reeksen is dus 16.

Het is dus mogelijk om er 2 te genereren⁴ of 16 deelreeksen van “ABCD”. Dan een touwtje met een lengte van m zal een totale deelreeks van 2 moeten hebben^m.

Voor elke subsequentie moeten we het controleren voor het hele patroon2. Het zal 0(n) tijd kosten. 0(n) betekent de complexiteitsfunctie die de tijd berekent die nodig is voor de uitvoering.

De totale tijdscomplexiteit wordt dus O(n*2^m). Voor het voorbeeld hebben we hierboven de waarde van m=8 en n=5 gezien.

Hier zijn de stappen van de naïeve methode:

Stap 1) Neem een ​​reeks uit patroon 1.
Stap 2) Zorg ervoor dat de reeks uit stap 1 overeenkomt met patroon 2.
Stap 3) Als dit overeenkomt, slaat u de deelreeks op.
Stap 4) Als er meer reeksen over zijn in patroon 1, ga dan opnieuw naar stap 1.
Stap 5) Druk de langste deelreeks af.

Optimale onderbouw

De term optimale onderbouw betekent dat er een optimale oplossing (eenvoudig) kan worden gevonden door de deelproblemen op te lossen. In het bovenstaande voorbeeld hebben we bijvoorbeeld patroon1 en patroon2.

Stap 1) Neem de eerste twee karakters van elk patroon

Stap 2) Neem van elk patroon het derde tot en met het vijfde karakter.

Stap 3) Ga op dezelfde manier verder met de overige tekens.

We vinden de LCS op de substring (string gegenereerd op basis van een originele string). Vervolgens houden we de lengte van de LCS van de substrings bij.

Hier is nog een interessante eigenschap overlappende deelproblemen. Van een probleem wordt gezegd dat het overlappende deelproblemen heeft als de probleemstelling in kleine deelproblemen kan worden opgedeeld en meerdere keren in het programma kan worden gebruikt.

Het onderstaande diagram laat zien dat het recursieve algoritme de functie met dezelfde parameter meerdere keren heeft aangeroepen.

Laten we bijvoorbeeld de recursieboom bekijken.

In het donkergekleurde vak kunt u overlappende subproblemen opmerken. (“RG”, “RA”), (“RG”, “R”) en andere worden meerdere keren genoemd.

Om dit te optimaliseren hebben wij de aanpak van Dynamisch programmeren (DP).

Recursieve methode van de langste communicatiereeks

De grafiek hierboven is de recursieve methode. Elke recursieve functie heeft een basisscenario om de recursie te doorbreken of terug te keren van de stapel.

Voor deze implementatie gebruiken we een basisscenario. Dus de algoritme is als volgt:

• Als alle elementen vóór het laatste element overeenkomen, verhoog dan de lengte met één en keer terug
• Geef twee patronen door aan de functie en neem de maximale waarde van de return
• Als één patroon een lengte nul heeft, hebben we geen deelreeks om te vergelijken. Retourneert in dit geval 0. Dit is het basisscenario van de recursie.

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)

implementatie 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;
}

Output:

Length of LCS is: 5

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

Output:

Lenght of LCS is:  5

Dynamische programmeermethode van Longest Common Subsequence (LCS)

Dynamisch programmeren betekent het optimaliseren van de eenvoudig recursieve methode. Als we bijvoorbeeld de recursieve of naïeve benaderingsgrafiek zien, kunnen we zien dat er meerdere dezelfde functieaanroepen zijn. De Dynamic Programming-methode registreert alle berekeningen in een array en gebruikt deze wanneer dat nodig is.

We gebruiken een 2D-array met de afmetingen mxn, waarbij m en n de lengtes zijn van patroon1 en patroon2.

Voor 2D-reeks, we kunnen lijstgegevensstructuren gebruiken in python of vector-/arraygegevensstructuren in C++.

Pseudocode voor LCS met 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 is de tabel LCS die wordt gebruikt als een 2D-arraygegevensstructuur voor de dynamische programmeerbenadering.

Laten we de logica bespreken die we hier hebben gebruikt. Stappen zijn:

Stap 1) Als i of j nul is, nemen we een lege string uit de gegeven twee strings en proberen we de gemeenschappelijke deelreeksen te vinden. Omdat de subtekenreeks die we nemen echter leeg is, is de lengte van de subreeks 0.

Stap 2) Als twee tekens overeenkomen, wijzen we de waarde toe aan de (i,j) index door de eerder berekende LCS te verhogen, die aanwezig is in de (i-1,j-1) index (uit de vorige rij).

Stap 3) Als het niet overeenkomt, nemen we de maximale LCS van de aangrenzende twee indexen. En op deze manier moeten we alle waarden in de 2D-array invullen.

Stap 4) Ten slotte zullen we de waarde van de laatste cel van de 2D-array retourneren.

Kortom, alle waarden in de 2D-array bevatten de lengte van gemeenschappelijke subreeksen. Hiervan bevat de laatste cel de lengte van de langste gemeenschappelijke deelreeks.

implementatie 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;
}

Output:

Length of LCS: 5

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

Output:

Length of LCS: 5

Beide snaren hebben dus de langste gemeenschappelijke deelreeks van lengte 5.

Kort gezegd berekenen we elke taak eenvoudigweg één keer in de DP-methode in de DP-methode. Bij de recursieve methode kunnen we overlappende deelproblemen hebben.

In dit dynamische programmeeralgoritme gebruiken we een 2D-matrix. Er worden twee strings gegeven (neem aan dat beide lengte n hebben). De benodigde ruimte in de array is dan nx n. Als de tekenreeksen groot genoeg zijn, hebben we een voor geheugen geoptimaliseerde versie van de DP-oplossing nodig.

De vereenvoudigde logica die in de code is gebruikt, is:

• Declareer een 2D-array DP[m][n].
• Vul de eerste rij en eerste kolom van de DP-array met 0.
• Neem i en j voor de iteratie.
• Als patroon1[i] gelijk is aan patroon2[j], update dan DP[i][j] = DP[i-1][j-1] + 1
• Als patroon1[i] niet gelijk is aan patroon2[j], dan zal DP[i][j] de maximale waarde zijn tussen DP[i-1][j] en DP[i][j-1].
• Ga door totdat i en j m en n bereiken.
• Het laatste element of DP[m-1][n-1] zal de lengte bevatten.

Hier wordt het geadresseerd als DP[m-1][n-1], omdat de array-index begint vanaf 0.

Samenvatting

• De DP-methode heeft een lagere tijdcomplexiteit: O(mn), waarbij m en n de lengte van de invoerstring of -array zijn.
• DP is een snellere aanpak dan de recursieve, met de tijdcomplexiteit van O(n*2^m).
• Dynamische programmering (DP) is niet geheugengeoptimaliseerd. We gebruikten een 2D-array met de lengte m*n. De ruimtecomplexiteit is dus (m*n).
• Bij de recursieve methode zal in het slechtste geval het grootste geheugen dat het in beslag zal nemen m+n zijn, in feite de totale lengte van de ingevoerde string.
• De moderne computer van vandaag is voldoende om deze hoeveelheid geheugen te verwerken.