Längsta vanliga följdsekvens: Python, C++ Exempelvis

Vad är den längsta vanliga följden?

Longest Common Subsequence (LCS) innebär att du kommer att få två strängar/mönster/sekvenser av objekt. Bland dessa två sekvenser/strängar måste du hitta den längsta undersekvensen av element i samma ordning som finns i både strängar eller mönster.

Exempelvis

Till exempel finns det två strängar.

Låt oss anta att

Pattern_1 = "RGBGARGA"
Pattern_2 = "BGRARG"

• Från mönster_1 kan sekvenser produceras som "RGB", "RGGA", "RGAR". För att skapa en sekvens måste du behålla den relativa positionen för varje tecken i strängen.
• Från pattern_2 kan vi producera sekvenser som "BGR", "BRAG", "RARG". Sekvenser kan produceras så länge de bibehåller den ursprungliga strängens relativa position.

Termen relativ position betyder ordning.

Till exempel är "BRG" en giltig sekvens eftersom "B" dök upp först, sedan "R" och sedan "G" i det ursprungliga strängmönster_2. Men om en sekvens är "RBRG", är den inte giltig. För i originalsträngen (pattern_2) kommer "B" först.

Vi har två alternativ för att hitta den längsta vanliga undersekvensen från de givna två sekvenserna eller arrayerna.

• Naiv metod
• Dynamisk programmeringslösning: Längsta vanliga delsekvensen kallas även LCS.

En naiv lösning har större tidskomplexitet och är inte den optimala lösningen. Med hjälp av Dynamic Programming Solution (DP) övervinner vi komplexitetsproblemet.

Naiv metod

Naiv metod är ett enkelt förhållningssätt till problemet oavsett tidskomplexitet och andra optimeringsfaktorer.

Den naiva metoden består av "Brute Force", multipla loopar, rekursiva metoder i de flesta fall.

Termen brute force betyder att gå igenom alla möjliga mönster för ett givet problem.

Exempelvis

Från ovanstående exempel på mönster1 och mönster2, låt oss anta att mönster1 har längden m och mönster2 har längden n. För att kontrollera alla möjliga fall måste vi utvärdera alla möjliga följder av mönster1 med mönster2.

Här är en enkel sträng med fyra bokstäver "ABCD". Till exempel måste vi skapa en sekvens från "ABCD." Antingen kan vi ta en karaktär eller inte. Det betyder att vi har två val för varje karaktär.

De är:

• Tecknet kommer att läggas till i efterföljden.
• Tecknet kommer inte att läggas till i efterföljden.

Här visar bilderna alla sekvenser som vi kan göra från strängen "ABCD".

Sekvens med 1 tecken:

Sekvenser med 2 tecken:

Sekvenser med 3 tecken:

Från diagrammet ovan finns det 14 sekvenser. Om vi ​​inte tar bokstäver, i princip en tom sträng, blir den totala sekvensen 15. Dessutom är själva strängen "ABCD" en sekvens. Så de totala sekvenserna är 16.

Så det är möjligt att generera 2⁴ eller 16 efterföljder från "ABCD". Sedan, ett snöre med en längd på m kommer att behöva en total efterföljd av 2^m.

För varje undersekvens måste vi kontrollera det för hela mönstret2. Det tar 0(n) tid. 0(n) betyder komplexitetsfunktionen som beräknar tiden det tar för exekvering.

Så total tidskomplexitet blir O(n*2^m). För exemplet har vi ovan sett värdet på m=8 och n=5.

Här är stegen i den naiva metoden:

Steg 1) Ta en sekvens från mönstret1.
Steg 2) Matcha sekvensen från steg 1 med mönster2.
Steg 3) Om det matchar, spara sedan undersekvensen.
Steg 4) Om mer sekvens finns kvar i mönstret1, gå sedan till steg 1 igen.
Steg 5) Skriv ut den längsta efterföljden.

Optimal underlag

Termen optimal understruktur betyder att en optimal lösning (enkel) kan hittas genom att lösa delproblemen. Till exempel, i exemplet ovan har vi mönster1 och mönster2.

Steg 1) Ta de två första tecknen från varje mönster

Steg 2) Ta det tredje till femte tecknet från varje mönster.

Steg 3) Fortsätt på samma sätt med de återstående tecknen.

Vi hittar LCS på delsträngen (sträng genererad från en originalsträng). Sedan sparar vi längden på LCS för delsträngarna.

Nu, här är en annan intressant egenskap överlappande delproblem. Ett problem sägs ha överlappande delproblem om problemformuleringen kan delas upp i små delproblem och användas flera gånger i programmet.

Diagrammet nedan visar att den rekursiva algoritmen anropade funktionen med samma parameter flera gånger.

Låt oss till exempel se rekursionsträdet.

I den mörkfärgade rutan kan du märka överlappande delproblem. ("RG", "RA"), ("RG",,"R") och andra anropas flera gånger.

För att optimera detta har vi tillvägagångssättet Dynamisk programmering (DP).

Rekursiv metod med längsta komm.sekvens

Grafen som visas ovan är den rekursiva metoden. Varje rekursiv funktion har ett basfall för att bryta rekursionen eller börja återvända från sin stack.

För den här implementeringen använder vi ett basfall. Alltså algoritm är som följande:

• Om alla element före det sista elementet har en matchning, öka längden med en och gå tillbaka
• Skicka två mönster till funktionen och ta maxvärdet för avkastningen
• Om ett mönster har noll längd, så har vi ingen följd att jämföra. Returnera 0 i detta fall. Detta är basfallet för rekursionen.

Pseudokod:

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)

Genomförande 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;
}

Produktion:

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

Produktion:

Lenght of LCS is:  5

Dynamisk programmeringsmetod för längsta vanliga följdsekvenser (LCS)

Dynamisk programmering innebär att optimera den enkla rekursiva metoden. Till exempel, om vi ser den rekursiva eller naiva strategin, kan vi se att det finns flera samma funktionsanrop. Den dynamiska programmeringsmetoden registrerar alla beräkningar i en array och använder den vid behov.

Vi kommer att använda en 2D-array med dimensionerna mxn, där m och n är längderna av mönster1 och mönster2.

För 2D-array, kan vi använda Listdatastrukturer i python eller vektor/array-datastrukturer i C++.

Pseudokod för LCS som använder 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]

Här är tabellen LCS som används som en 2D-matrisdatastruktur för den dynamiska programmeringsmetoden.

Låt oss diskutera logiken vi använde här. Stegen är:

Steg 1) Om i eller j är noll, tar vi en tom sträng från de givna två strängarna och försöker hitta de gemensamma undersekvenserna. Men eftersom delsträngen vi tar är tom, är delsekvenslängden 0.

Steg 2) Om två tecken matchar, tilldelar vi värdet till (i,j)-indexet genom att öka den tidigare beräknade LCS, som finns i (i-1,j-1)-indexet (från föregående rad).

Steg 3) Om det inte stämmer överens kommer vi att ta max LCS för de intilliggande två indexen. Och på detta sätt måste vi fylla alla värden i 2D-matrisen.

Steg 4) Slutligen kommer vi att returnera värdet för den sista cellen i 2D-matrisen.

I princip innehåller alla värden i 2D-matrisen längden på vanliga delsekvenser. Bland dessa innehåller den sista cellen längden på den längsta gemensamma undersekvensen.

Genomförande 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;
}

Produktion:

Length of LCS: 5

Genomförande 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))

Produktion:

Length of LCS: 5

Så båda strängarna har den längsta gemensamma följden av längd 5.

I ett nötskal, vi beräknar helt enkelt varje uppgift en gång i DP-metoden i DP-metoden. I den rekursiva metoden kan vi ha överlappande delproblem.

I denna dynamiska programmeringsalgoritm använder vi en 2D-matris. Det kommer att finnas två strängar (antag att båda har längden n). Då är utrymmet som behövs i arrayen nx n. Om strängarna är tillräckligt stora behöver vi en minnesoptimerad version av DP-lösningen.

Den förenklade logiken som togs i koden är:

• Deklarera en 2D Array DP[m][n].
• Fyll den första raden och den första kolumnen i DP-matrisen med 0.
• Ta i och j för iterationen.
• Om mönster1[i] är lika med mönster2[j], uppdatera DP[i][j] = DP[i-1][j-1] + 1
• Om mönster1[i] inte är lika med mönster2[j], så kommer DP[i][j] att vara det maximala värdet mellan DP[i-1][j] och DP[i][j-1].
• Fortsätt tills i och j når m och n.
• Det sista elementet eller DP[m-1][n-1], kommer att innehålla längden.

Här adresseras det som DP[m-1][n-1], eftersom arrayindex börjar från 0.

Sammanfattning

• DP-metoden har lägre tidskomplexitet; det är O(mn), där m och n är längden på inmatningssträngen eller matrisen.
• DP är ett snabbare tillvägagångssätt än det rekursiva, med tidskomplexiteten av O(n*2^m).
• Dynamisk programmering (DP) är inte minnesoptimerad. Vi använde en 2D-array som har längden m*n. Så rymdkomplexiteten är (m*n).
• Rekursiv metod, i ett värsta scenario kommer det högsta minnet att uppta vara m+n, i princip den totala längden på den inmatade strängen.
• Dagens moderna dator räcker för att hantera denna mängd minne.