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

Qual è la sottosequenza comune più lunga?

Il problema della sottosequenza comune più lunga (LCS) consiste nel trovare la sottosequenza più lunga di elementi, nello stesso ordine, presenti in entrambe le stringhe o nei due modelli, data una serie di stringhe, modelli o sequenze di oggetti.

Esempio

Ad esempio, vengono fornite due stringhe. Supponiamo che:

Modello_1 = “RGBGARGA”
Modello_2 = “BGRARG”

• A partire dal pattern_1, è possibile generare sequenze come "RGB", "RGGA", "RGAR". Per creare una sequenza, è necessario mantenere la posizione relativa di ciascun carattere nella stringa.
• A partire da pattern_2, possiamo generare sequenze come “BGR”, “BRAG”, “RARG”. Le sequenze possono essere generate purché mantengano la posizione relativa della stringa originale.

Il termine posizione relativa significa ordine.

Ad esempio, "BRG" è una sequenza valida perché nella stringa originale pattern_2 la "B" compare per prima, seguita dalla "R" e infine dalla "G". Tuttavia, se la sequenza è "RBRG", non è valida, perché nella stringa originale (pattern_2) la "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 presenta una complessità temporale maggiore e non rappresenta la soluzione ottimale. Utilizzando la programmazione dinamica (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. Consiste, nella maggior parte dei casi, in un approccio "a forza bruta", con cicli multipli e chiamate ricorsive. Il termine "forza bruta" si riferisce all'analisi di tutti i possibili schemi 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 a partire da "ABCD". Possiamo scegliere un carattere o meno. Ciò significa che, per ogni carattere, abbiamo due possibilità:

• 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 riportato, si evince che ci sono 14 sequenze. Se non consideriamo alcuna lettera, ovvero una stringa vuota, il numero totale di sequenze sale a 15. Inoltre, la stringa "ABCD" stessa costituisce una sequenza. Pertanto, il numero totale di sequenze è 16.

Quindi, è possibile generare 2^4 o 16 sottosequenze da “ABCD”. Quindi, una stringa con una lunghezza di m avrà una sottosequenza totale di 2^m.

Per ogni sottosequenza, dobbiamo controllarla per l'intero pattern2. Ciò richiederà un tempo O(n). O(n) indica la funzione di complessità che calcola il tempo necessario per l'esecuzione.

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

Ecco i passaggi del Metodo Naive:

Passo 1) Prendi una sequenza dal modello1.
Passo 2) Abbina la sequenza del passaggio 1 al modello 2.
Passo 3) Se corrisponde, salva la sottosequenza.
Passo 4) Se nel pattern1 sono ancora presenti delle sequenze, ripetere il passaggio 1.
Passo 5) Stampa la sottosequenza più lunga.

Sottostruttura ottimale

Il termine sottostruttura ottimale significa che è possibile trovare una soluzione ottimale risolvendo i sottoproblemi. Ad esempio, nell'esempio precedente, abbiamo pattern1 e pattern2.

Passo 1) Prendi i primi due caratteri da ogni schema.

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

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

Struttura ricorsiva del problema LCS

Troviamo la LCS (Least Significant Side) sulla sottostringa (una stringa generata da una stringa originale). Quindi memorizziamo la lunghezza della LCS delle sottostringhe.

Ora, ecco un'altra proprietà interessante sovrapposizioneping sottoproblemiSi dice che un problema abbia una sovrapposizioneping sottoproblemi se l'enunciato del problema può essere scomposto in piccoli sottoproblemi e utilizzato più volte nel programma.

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

Ad esempio, osserva l'albero di ricorsione. Nel riquadro scuro, puoi notare una sovrapposizione.ping sottoproblemi. (“RG”, “RA”), (“RG”,”R”) e altri vengono chiamati più volte.

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

Metodo ricorsivo della sottosequenza comune più lunga

Il grafico mostrato sopra rappresenta il metodo ricorsivo. Ogni funzione ricorsiva ha un caso base per interrompere la ricorsione o iniziare a tornare dallo stack.

Per questa implementazione, useremo un caso base. Quindi, il algoritmo è come il seguente:

• Se tutti gli elementi precedenti all'ultimo elemento corrispondono, incrementa la lunghezza di uno e ritorna.
• Passa due pattern alla funzione e prendi il valore massimo tra quelli restituiti.
• Se un modello ha lunghezza zero, non abbiamo alcuna sottosequenza da confrontare. Restituisce 0 in questo caso. Questo è il caso base della ricorsione.

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

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

Produzione:

Length of LCS is:  5

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

La programmazione dinamica consiste nell'ottimizzare il metodo ricorsivo standard. Ad esempio, osservando il grafico dell'approccio ricorsivo o ingenuo, si possono notare diverse chiamate di funzione identiche. Il metodo di programmazione dinamica memorizza tutti i calcoli in un array e li riutilizza quando necessario.

Useremo un array 2D con dimensioni mxn, dove m e n sono le lunghezze di pattern1 e pattern2. Per un matrice 2D, possiamo utilizzare le strutture dati List in Python o strutture dati vettoriali/array in C++.

Soprannome Code per LCS utilizzando 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 bidimensionale per l'approccio di programmazione dinamica.

Analizziamo la logica che abbiamo utilizzato. I passaggi sono:

Passo 1) Se i o j è zero, prendiamo una stringa vuota dalle due stringhe date e cerchiamo di trovare le sottosequenze comuni. Tuttavia, poiché la sottostringa che prendiamo è 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) (della riga precedente).

Passo 3) Se non c'è corrispondenza, prenderemo il valore massimo di LCS tra i due indici adiacenti. In questo modo, dobbiamo riempire tutti i valori nell'array 2D.

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

In sostanza, tutti i valori nell'array bidimensionale contengono 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 < 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;
}

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, nel metodo DP calcoliamo semplicemente ogni compito una sola volta. Nel metodo ricorsivo, potremmo avere sovrapposizioniping sottoproblemi.

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], allora 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, DP[m-1][n-1], conterrà la lunghezza.

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

DOMANDE FREQUENTI