Sottosequenza comune più lunga: Python, C++ Esempio

Qual è la sottosequenza comune più lunga?

La più lunga sottosequenza comune (LCS) significa che ti verranno fornite due stringhe/modelli/sequenze di oggetti. Tra queste due sequenze/stringhe, è necessario trovare la sottosequenza più lunga di elementi nello stesso ordine presenti in entrambe le stringhe o pattern.

Esempio

Ad esempio, vengono fornite due stringhe.

Supponiamo che,

Modello_1 = “RGBGARGA”
Modello_2 = “BGRARG”

• Da pattern_1 è possibile produrre sequenze come “RGB”, “RGGA”, ”RGAR”. Per creare una sequenza, è necessario mantenere la posizione relativa di ciascun carattere nella stringa.
• Da pattern_2, possiamo produrre sequenze come “BGR”, ”BRAG”, ”RARG”. È possibile produrre sequenze purché mantengano la posizione relativa della stringa originale.

Il termine posizione relativa significa ordine.

Ad esempio, "BRG" è una sequenza valida perché "B" è apparsa per prima, poi "R" e infine "G" nella stringa pattern_2 originale. Tuttavia, se una sequenza è “RBRG”, non è valida. Perché nella stringa originale (pattern_2), "B" viene prima.

Abbiamo due opzioni per trovare la sottosequenza comune più lunga dalle due sequenze o matrici fornite.

• Metodo ingenuo
• Soluzione di programmazione dinamica: la sottosequenza comune più lunga è nota anche come LCS.

Una soluzione ingenua ha una complessità temporale maggiore e non è la soluzione ottimale. Utilizzando Dynamic Programming Solution (DP), superiamo il problema della complessità.

Metodo ingenuo

Il metodo ingenuo è un approccio semplice al problema, indipendentemente dalla complessità temporale e da altri fattori di ottimizzazione.

Il metodo Naive consiste in “Brute Force”, loop multipli, metodi ricorsivi nella maggior parte dei casi.

Il termine forza bruta significa passare attraverso tutti gli schemi possibili per un dato problema.

Esempio

Dall'esempio precedente di pattern1 e pattern2, supponiamo che pattern1 abbia una lunghezza pari a m e pattern2 abbia una lunghezza pari a n. Per verificare ogni caso possibile, dobbiamo valutare ogni possibile sottosequenza di pattern1 con pattern2.

Ecco una semplice stringa di 4 lettere "ABCD". Ad esempio, dobbiamo creare una sequenza da "ABCD". O possiamo prendere un personaggio oppure no. Ciò significa che, per ogni personaggio, abbiamo due scelte.

Essi sono:

• Il carattere verrà aggiunto alla sequenza successiva.
• Il carattere non verrà aggiunto alla sequenza successiva.

Qui le immagini mostrano tutte le sequenze che possiamo realizzare dalla stringa “ABCD”.

Sequenza con 1 carattere:

Sequenze con 2 caratteri:

Sequenze con 3 caratteri:

Dal diagramma sopra, ci sono 14 sequenze. Se non prendiamo le lettere, praticamente una stringa vuota, le sequenze totali saranno 15. Inoltre, la stringa “ABCD” stessa è una sequenza. Quindi le sequenze totali sono 16.

Quindi è possibile generarne 2⁴ o 16 sottosequenze da “ABCD”. Quindi, una stringa con una lunghezza di m dovrà totalizzare una sequenza successiva di 2^m.

Per ogni sottosequenza, dobbiamo controllarla per l'intero pattern2. Ci vorrà tempo 0(n). 0(n) indica la funzione di complessità che calcola il tempo impiegato per l'esecuzione.

Quindi, la complessità temporale totale diventa O(n*2^m). Nell'esempio abbiamo visto sopra il valore di m=8 en=5.

Ecco i passaggi del Metodo Naive:

Passo 1) Prendi una sequenza dal pattern1.
Passo 2) Abbina la sequenza del passaggio 1 con il modello 2.
Passo 3) Se corrisponde, salva la sottosequenza.
Passo 4) Se nel pattern1 è rimasta più sequenza, andare di nuovo al passaggio 1.
Passo 5) Stampa la sottosequenza più lunga.

Sottostruttura ottimale

Il termine sottostruttura ottimale significa che una soluzione ottimale (semplice) può essere trovata risolvendo i sottoproblemi. Ad esempio, nell'esempio precedente, abbiamo pattern1 e pattern2.

Passo 1) Prendi i primi due caratteri di ogni modello

Passo 2) Prendi dal terzo al quinto carattere di ogni modello.

Passo 3) Continua allo stesso modo con i restanti personaggi.

Troviamo l'LCS sulla sottostringa (stringa generata da una stringa originale). Quindi teniamo traccia della lunghezza dell'LCS delle sottostringhe.

Ora, ecco un'altra proprietà interessante sottoproblemi sovrapposti. Si dice che un problema ha sottoproblemi sovrapposti se la formulazione del problema può essere suddivisa in piccoli sottoproblemi e utilizzata più volte nel programma.

Il diagramma seguente mostra che l'algoritmo ricorsivo ha chiamato più volte la funzione con lo stesso parametro.

Ad esempio, vediamo l'albero di ricorsione.

Nella casella di colore scuro puoi notare sottoproblemi sovrapposti. ("RG", "RA"), ("RG", "R") e altri vengono chiamati più volte.

Per ottimizzare questo, abbiamo l'approccio di Programmazione dinamica (DP).

Metodo ricorsivo della sequenza di comunicazione più lunga

Il grafico mostrato sopra è il metodo ricorsivo. Ogni funzione ricorsiva ha un caso base per interrompere la ricorsione o iniziare a ritornare dal suo stack.

Per questa implementazione, utilizzeremo un caso base. Così il algoritmo è come il seguente:

• Se tutti gli elementi prima dell'ultimo elemento hanno una corrispondenza, aumenta la lunghezza di uno e ritorna
• Passa due pattern alla funzione e prendi il valore massimo del rendimento
• Se un modello ha lunghezza zero, non abbiamo alcuna sottosequenza da confrontare. Restituisce 0 in questo caso. Questo è il caso base della ricorsione.

Pseudo codice:

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)

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

Produzione:

Length of LCS is: 5

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

Produzione:

Lenght of LCS is:  5

Metodo di programmazione dinamica della sottosequenza comune più lunga (LCS)

Programmare dinamicamente significa ottimizzare il metodo ricorsivo semplice. Ad esempio, se vediamo il grafico dell'approccio ricorsivo o ingenuo, possiamo vedere che ci sono diverse chiamate di funzione identiche. Il metodo di programmazione dinamica registra tutti i calcoli in un array e lo utilizza quando necessario.

Utilizzeremo un array 2D con dimensioni mxn, dove m e n sono lunghezze di pattern1 e pattern2.

Da matrice 2D, possiamo usare strutture dati List in Python o strutture dati vector/array in C++.

Pseudo codice per LCS che utilizza 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]

Ecco la tabella LCS utilizzata come struttura dati array 2D per l'approccio di programmazione dinamica.

Parliamo della logica che abbiamo usato qui. I passaggi sono:

Passo 1) Se i o j sono zero, stiamo prendendo una stringa vuota dalle due stringhe fornite e provando a trovare le sottosequenze comuni. Tuttavia, poiché la sottostringa che stiamo prendendo è vuota, la lunghezza della sottosequenza è 0.

Passo 2) Se due caratteri corrispondono, assegneremo il valore all'indice (i,j) incrementando l'LCS precedentemente calcolato, che è presente nell'indice (i-1,j-1) (dalla riga precedente).

Passo 3) Se non corrisponde, prenderemo il LCS massimo dei due indici adiacenti. E in questo modo, dobbiamo riempire tutti i valori nell'array 2D.

Passo 4) Infine, restituiremo il valore dell'ultima cella dell'array 2D.

Fondamentalmente, tutto il valore nell'array 2D contiene la lunghezza delle sottosequenze comuni. Tra queste, l'ultima cella contiene la lunghezza della sottosequenza comune più lunga.

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

Produzione:

Length of LCS: 5

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

Produzione:

Length of LCS: 5

Quindi entrambe le stringhe hanno la sottosequenza comune più lunga di lunghezza 5.

In poche parole, stiamo semplicemente calcolando ciascuna attività una volta nel metodo DP nel metodo DP. Nel metodo ricorsivo, potremmo avere sottoproblemi sovrapposti.

In questo algoritmo di programmazione dinamica, stiamo utilizzando una matrice 2D. Verranno fornite due stringhe (supponiamo che entrambe abbiano lunghezza n). Quindi lo spazio necessario nell'array è nx n. Se le stringhe sono sufficientemente grandi, avremo bisogno di una versione ottimizzata per la memoria della soluzione DP.

La logica semplificata adottata nel codice è:

• Dichiarare un array 2D DP[m][n].
• Riempi la prima riga e la prima colonna dell'array DP con 0.
• Prendi i e j per l'iterazione.
• Se pattern1[i] è uguale a pattern2[j], aggiorna DP[i][j] = DP[i-1][j-1] + 1
• Se pattern1[i] non è uguale a pattern2[j], allora DP[i][j] sarà il valore massimo tra DP[i-1][j] e DP[i][j-1].
• Continua finché i e j raggiungono me n.
• L'ultimo elemento o DP[m-1][n-1], conterrà la lunghezza.

Qui viene indirizzato come DP[m-1][n-1], perché l'indice dell'array inizia da 0.

Sintesi

• Il metodo DP ha una complessità temporale inferiore: è O(mn), dove m e n sono la lunghezza della stringa o dell'array di input.
• DP è un approccio più veloce di quello ricorsivo, con una complessità temporale di O(n*2^m).
• La programmazione dinamica (DP) non è ottimizzata per la memoria. Abbiamo utilizzato un array 2D che ha la lunghezza di m*n. Quindi, la complessità spaziale è (m*n).
• Metodo ricorsivo, nel peggiore dei casi, la memoria più alta che occuperà sarà m+n, sostanzialmente la lunghezza totale della stringa immessa.
• I computer moderni di oggi sono sufficienti per gestire questa quantità di memoria.