Cea mai lungă secvență comună: Python, C++ Exemplu

Care este cea mai lungă subsecvență comună?

Cea mai lungă subsecvență comună (LCS) înseamnă că vi se vor da două șiruri de caractere, modele sau secvențe de obiecte. Dintre aceste două secvențe sau șiruri de caractere, trebuie să găsiți cea mai lungă subsecvență de elemente în aceeași ordine prezente în ambele șiruri de caractere sau modele.

Exemplu

De exemplu, sunt furnizate două șiruri de caractere. Să presupunem că:

Model_1 = „RGBGARGA”
Model_2 = „BGRARG”

• Din pattern_1, se pot produce secvențe precum „RGB”, „RGGA”, „RGAR”. Pentru a crea o secvență, trebuie să mențineți poziția relativă a fiecărui caracter din șir.
• Din pattern_2, putem produce secvențe precum „BGR”, „BRAG”, „RARG”. Secvențele pot fi produse atâta timp cât mențin poziția relativă a șirului original.

Termenul poziție relativă înseamnă ordine.

De exemplu, „BRG” este o secvență validă deoarece „B” a apărut primul, apoi „R” și apoi „G” în șirul original pattern_2. Totuși, dacă o secvență este „RBRG”, nu este validă, deoarece în șirul original (pattern_2), „B” apare primul.

Avem două opțiuni pentru a găsi cea mai lungă subsecvență comună din cele două secvențe sau matrice date.

• Metoda naiva
• Soluție de programare dinamică: cea mai lungă subsecvență comună este cunoscută și sub numele de LCS.

O soluție naivă are o complexitate temporală mai mare și nu este soluția optimă. Folosind Soluția de Programare Dinamică (DP), depășim problema complexității.

Metoda naivă

Metoda Naive este o abordare simplă a problemei, indiferent de complexitatea timpului și de alți factori de optimizare. Aceasta constă în „forță brută”, bucle multiple și apeluri recursive în majoritatea cazurilor. Termenul „forță brută” înseamnă parcurgerea tuturor modelelor posibile pentru o anumită problemă.

Exemplu

Din exemplul de mai sus de model1 și model2, să presupunem că modelul1 are o lungime de m și modelul2 are o lungime de n. Pentru a verifica fiecare caz posibil, trebuie să evaluăm fiecare subsecvență posibilă a pattern1 cu pattern2.

Iată un șir simplu de 4 litere, „ABCD”. De exemplu, trebuie să creăm o secvență din „ABCD”. Putem fie să luăm un caracter, fie nu. Asta înseamnă că, pentru fiecare caracter, avem două opțiuni:

• Personajul va fi adăugat la următoarea.
• Personajul nu va fi adăugat la următoarea.

Aici, imaginile arată toate secvențele pe care le putem face din șirul „ABCD”.

Secvență cu 1 caracter:

Secvențe cu 2 caractere:

Secvențe cu 3 caractere:

Din diagrama de mai sus, există 14 secvențe. Dacă nu luăm nicio literă, practic un șir gol, totalul secvențelor va fi 15. Mai mult, șirul „ABCD” în sine este o secvență. Deci, totalul secvențelor este 16.

Deci, este posibil să se genereze 2^4 sau 16 subsecvențe din „ABCD”. Apoi, un șir cu o lungime de m va avea o subsecvență totală de 2^m.

Pentru fiecare subsecvență, trebuie să o verificăm pentru întregul model2. Va dura O(n) timp. O(n) reprezintă funcția de complexitate care calculează timpul necesar execuției.

Deci, complexitatea totală a timpului devine O(n*2^m). Pentru exemplul pe care l-am văzut mai sus, valoarea lui m=8 și n=5.

Iată pașii Metodei Naive:

Pas 1) Luați o secvență din modelul 1.
Pas 2) Asociați secvența de la pasul 1 cu modelul 2.
Pas 3) Dacă se potrivește, atunci salvați următoarea.
Pas 4) Dacă au mai rămas mai multe secvențe în modelul 1, atunci treceți din nou la pasul 1.
Pas 5) Tipăriți cea mai lungă secvență.

Substructură optimă

Termenul substructură optimă înseamnă că o soluție optimă poate fi găsită prin rezolvarea subproblemelor. De exemplu, în exemplul de mai sus, avem modelul1 și modelul2.

Pas 1) Luați primele două caractere din fiecare model.

Pas 2) Luați al treilea până la al cincilea caracter din fiecare model.

Pas 3) Continuați în mod similar cu caracterele rămase.

Structura recursiva a problemei LCS

Găsim LCS-ul pe subșir (un șir generat dintr-un șir original). Apoi înregistrăm lungimea LCS-ului subșirurilor.

Acum, iată o altă proprietate interesantă suprapuneping subproblemeSe spune că o problemă are suprapuneriping subprobleme dacă enunțul problemei poate fi împărțit în subprobleme mici și utilizat de mai multe ori în program.

Diagrama de mai jos arată că algoritmul recursiv a numit funcția cu același parametru de mai multe ori.

De exemplu, uitați-vă la arborele de recurență. În caseta de culoare închisă, puteți observa suprapunereaping subprobleme. („RG”, „RA”), („RG”, „R”) și altele sunt apelate de mai multe ori.

Pentru a optimiza acest lucru, avem abordarea Programare dinamică (DP).

Metoda recursivă a celei mai lungi subsecvențe comune

Graficul prezentat mai sus este metoda recursivă. Fiecare funcție recursivă are un caz de bază pentru a întrerupe recursivitatea sau pentru a începe să se întoarcă din stiva sa.

Pentru această implementare, vom folosi un caz de bază. Deci, Algoritmul este ca urmatorul:

• Dacă toate elementele dinaintea ultimului element au o potrivire, atunci crește lungimea cu unu și returnează.
• Transmiteți două modele funcției și luați valoarea maximă a valorii returnate.
• Dacă un model are lungime zero, atunci nu avem nicio subsecvență de comparat. Returnați 0 în acest caz. Acesta este cazul de bază al recursiunii.

Pseudo Code:

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

Implementarea în 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;
}

ieșire:

Length of LCS is: 5

Implementarea în 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("Length of LCS is: ", lcs(pattern_1, pattern_2, len(pattern_1), len(pattern_2)))

ieșire:

Length of LCS is:  5

Metoda de programare dinamică a celei mai lungi subsecvențe comune (LCS)

Programarea dinamică înseamnă optimizarea metodei recursive simple. De exemplu, dacă ne uităm la graficul cu abordare recursivă sau naivă, putem observa că există mai multe apeluri de funcții identice. Metoda de programare dinamică înregistrează toate calculele într-un array și le reutilizează atunci când este nevoie.

Vom folosi o matrice 2D cu dimensiunile mxn, unde m și n sunt lungimile modelului1 și modelului2. Pentru a Matrice 2D, putem folosi structuri de date List în Python sau structuri de date vector/matrice în C++.

Pseudo Code pentru LCS folosind 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]

Iată tabelul LCS utilizat ca structură de date de tip matrice 2D pentru abordarea programării dinamice.

Să discutăm despre logica folosită aici. Pașii sunt:

Pas 1) Dacă i sau j este zero, luăm un șir gol din cele două șiruri date și încercăm să găsim subsecvențele comune. Totuși, deoarece subșirul pe care îl luăm este gol, lungimea subsecvenței este 0.

Pas 2) Dacă două caractere se potrivesc, vom atribui valoarea indicelui (i,j) prin incrementarea LCS-ului calculat anterior, care este prezent în indicele (i-1,j-1) (din rândul anterior).

Pas 3) Dacă nu se potrivește, atunci vom lua LCS-ul maxim al celor doi indici adiacenți. Și în acest fel, trebuie să completăm toate valorile din matricea 2D.

Pas 4) În cele din urmă, vom returna valoarea ultimei celule a matricei 2D.

Practic, toate valorile din matricea 2D conțin lungimea subsecvențelor comune. Printre acestea, ultima celulă conține lungimea celei mai lungi subsecvențe comune.

Implementarea în 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 < n + 1; i++) {
    for (int j = 0; j < 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;
}

ieșire:

Length of LCS: 5

Implementarea în 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))

ieșire:

Length of LCS: 5

Deci, ambele șiruri au cea mai lungă subsecvență comună de lungime 5.

Pe scurt, în metoda DP calculăm pur și simplu fiecare sarcină o singură dată. În metoda recursivă, este posibil să avem suprapuneri.ping subprobleme.

În acest algoritm de programare dinamică, folosim o matrice 2D. Vor fi date două șiruri (să presupunem că ambele au lungimea n). Atunci spațiul necesar în matrice este nx n. Dacă șirurile sunt suficient de mari, vom avea nevoie de o versiune optimizată pentru memorie a soluției DP.

Logica simplificată care a fost luată în cod este:

• Declarați o matrice 2D DP[m][n].
• Completați primul rând și prima coloană a matricei DP cu 0.
• Luați i și j pentru iterație.
• Dacă modelul1[i] este egal cu modelul2[j], atunci se actualizează DP[i][j] = DP[i-1][j-1] + 1.
• Dacă pattern1[i] nu este egal cu pattern2[j], atunci DP[i][j] va fi valoarea maximă dintre DP[i-1][j] și DP[i][j-1].
• Continuați până când i și j ajung la m și n.
• Ultimul element, DP[m-1][n-1], va conține lungimea.

Aici, este adresat ca DP[m-1][n-1] deoarece indicele matricei începe de la 0.

Întrebări frecvente