Il problema della massima sottosequenza comune
L’individuazione della massima sottosequenza comune (LCS, dall’inglese “Longest Common Subsequence”) è un classico problema dell’informatica. Nelle interviste ai programmatori, alle programmatrici e nei corsi sugli algoritmi ricorrono spesso approcci alla risoluzione del problema della LCS.
Che cos’è il problema della massima sottosequenza comune?
L’obiettivo è individuare la massima sottosequenza comune (“Longest Common Subsequence”) di due sequenze. Una sottosequenza (“subsequence”) è ricavata da una sequenza originale. La sottosequenza contiene la stessa sequenza di elementi, alcuni dei quali sono però stati rimossi. È possibile descrivere il principio con alcuni esempi:
Sequenza X |
Sequenza Y |
LCS(X, Y) |
|---|---|---|
FATHER
|
PADRE
|
AER
|
MOTHER
|
MADRE
|
MRE
|
DAVIDE
|
DANIELE
|
DAIE
|
Vi è un’importante differenza tra la massima sottosequenza comune e la massima sottostringa comune (“Longest Common Substring”). A differenza della sottosequenza, una sottostringa non può contenere spazi vuoti. Nell’esempio con “DAVIDE” / “DANIELE” la massima sottostringa comune sarebbe “DA”, poiché le sequenze sono interrotte prima delle “I” da “V” o “N”.
Qual è un esempio pratico del problema della LCS?
Il problema della massima sottosequenza comune è importante in tutti i campi in cui si lavora con sequenze che derivano le une dalle altre. Gli approcci all’individuazione della LCS si utilizzano, ad esempio, per esaminare i testi alla ricerca di aspetti simili e differenze: in questo modo è possibile individuare un plagio. Anche la nota utility diff, che mostra le modifiche ai file di codice sorgente, si basa sul problema della LCS.
In bioinformatica, il problema della massima sottosequenza comune si incontra nell’analisi delle sequenze di DNA. Con il passare del tempo, le mutazioni provocano cambiamenti delle basi in singoli punti del DNA. La presenza di una lunga sottosequenza comune tra due sequenze è segno di un’elevata parentela genetica. In questo modo è possibile seguire gli sviluppi genetici tra le specie nel corso dell’evoluzione.
I linguisti sfruttano il problema della massima sottosequenza comune per studiare lo sviluppo delle lingue nel corso dei secoli. Se si individuano due parole in lingue diverse che hanno lo stesso significato e condividono una lunga sottosequenza comune, significa che condividono la loro origine. In questo modo è possibile dedurre lo sviluppo storico dalla corrispondenza delle lettere nelle parole.
Come funzionano gli approcci per la soluzione al problema della massima sottosequenza comune?
Per prima cosa, è possibile risolvere il problema della LCS con un approccio “naive”. Si tratta dell’approccio più ovvio in assenza di ottimizzazioni o metodologie particolari. A tal fine si determinano tutte le sottosequenze contenute nelle due sequenze e si individua la massima sottosequenza che le due sequenze hanno in comune. Purtroppo, questo approccio non è efficiente ed è quindi adatto solo a sequenze brevi.
Nelle parti seguenti ti mostriamo tre approcci efficienti per risolvere il problema della LCS:
- Approccio ricorsivo
- Ottimizzazione tramite memoizzazione
- Programmazione dinamica
Un aspetto condiviso da tutti gli approcci è che distinguono tre casi per quanto riguarda le due sequenze:
- L’ultima lettera è uguale.
- L’ultima lettera non è uguale.
- La lunghezza di una sequenza è zero.
Gli approcci differiscono per complessità temporale (tempo di esecuzione asintotico) e complessità spaziale (requisiti di memoria):
| Approccio | Tempo esec. | Req. memoria |
|---|---|---|
| Approccio naive | O(n * n²)
|
O(n)
|
| Approccio ricorsivo | O(n²)
|
O(1)
|
| Ottimizzazione tramite memoizzazione | O(n *m)
|
O(n* m)
|
| Programmazione dinamica | O(n *m)
|
O(n* m)
|
Ciascuno degli algoritmi seguenti determina la lunghezza della massima sottosequenza comune. Potrebbero essere presenti più sottosequenze effettive di questa lunghezza, che è possibile determinare mediante ulteriori passaggi.
Rilevamento ricorsivo della massima sottosequenza comune
Osservando il problema della LCS si nota che presenta una “sottostruttura ottimale”. In pratica, il problema è riducibile in sottoproblemi. È quindi possibile utilizzare un approccio ricorsivo per risolvere questo problema. Nelle parti seguenti ti mostriamo l’implementazione dell’algoritmo in tre linguaggi di programmazione particolarmente diffusi.
Python
def lcs(X, Y, m, n):
# Base case
if m == 0 or n == 0:
return 0
# Last elements are equal
elif X[m-1] == Y[n-1]:
return 1 + lcs(X, Y, m-1, n-1)
# Last elements differ
else:
return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n))
X, Y = "DANIELE", "DAVIDE"
lcs_len = lcs(X, Y, len(X), len(Y))
print(f"Length of LCS is: {lcs_len}")
Java
import java.io.*;
class LCS {
public static int lcs(String A, String B, int m, int n)
{
// Base case
if (m == 0 || n == 0)
return 0;
// Last elements are equal
if (A.charAt(m - 1) == B.charAt(n - 1))
return 1 + lcs(A, B, m - 1, n - 1);
// Last elements differ
else
return Math.max(lcs(A, B, m, n - 1),
lcs(A, B, m - 1, n));
}
// Let's test
public static void main(String[] args)
{
String X = "DAVID";
String Y = "DANIEL";
int lcsLength = LCS.lcs(X, Y, X.length(), Y.length());
System.out.println("Length of LCS is: " + lcsLength);
}
}
Registrazione dominio
Più di un semplice nome.
Registra il tuo dominio con IONOS e approfitta di tutte le nostre funzionalità.
C++
#include <iostream>
using namespace std;
int lcs(string X, string Y, int m, int n)
{
// Base case
if (m == 0 || n == 0) {
return 0;
}
// Last elements are equal
if (X[m - 1] == Y[n - 1]) {
return 1 + lcs(X, Y, m - 1, n - 1);
}
// Last elements differ
else {
return max(lcs(X, Y, m, n - 1), lcs(X, Y, m - 1, n));
}
}
// Let's test
int main()
{
// Initialize variables
string X = "DAVID";
string Y = "DANIEL";
// Compute and output length of LCS
cout << "Length of LCS is " << lcs(X, Y, X.size(), Y.size());
return 0;
}
Ottimizzazione dell’approccio ricorsivo tramite memoizzazione
Esaminando ulteriormente l’approccio ricorsivo si vede come porti al calcolo di sottosequenze sovrapposte. Questa caratteristica, che prende il nome di “sottoproblemi sovrapposti”, è nota sin dalla sequenza di Fibonacci. Anche in questo caso le parti ricorsive vengono calcolate ripetutamente avvicinandosi alla soluzione. Per rendere il processo più efficiente, è quindi opportuno utilizzare la memoizzazione. In altre parole, i sottoproblemi già calcolati vengono conservati in una cache a matrice bidimensionale.
Python
def lcs(X, Y, m, n, table):
# Base case
if (m == 0 or n == 0):
return 0
# Already computed value at given position
if (table[m][n] != -1):
return table[m][n]
# Last elements are equal
if X[m - 1] == Y[n - 1]:
table[m][n] = 1 + lcs(X, Y, m - 1, n - 1, table)
# Last elements differ
else:
table[m][n] = max(lcs(X, Y, m, n - 1, table), lcs(X, Y, m - 1, n, table))
return table[m][n]
# Let's test
X = "DAVIDE"
Y = "DANIELE"
m, n = len(X), len(Y)
# Initialize table fields to `-1`
table = [[-1 for i in range(n + 1)] for j in range(m + 1)]
// Compute and output length of LCS
print(f"Length of LCS is: {lcs(X, Y, m, n, table)}")
Java
import java.io.*;
class LCS {
public static int lcs(String X, String Y, int m, int n, int[][] table) {
// Base case
if (m == 0 || n == 0) {
return 0;
}
// Already computed value at given position
if (table[m][n] != -1) {
return table[m][n];
}
// Last elements are equal
if(X.charAt(m - 1) == Y.charAt(n - 1)) {
table[m][n] = 1 + lcs(X, Y, m - 1, n - 1, table);
return table[m][n];
}
// Last elements differ
else {
table[m][n] = Math.max(lcs(X, Y, m, n - 1, table),lcs(X, Y, m - 1, n, table));
return table[m][n];
}
}
// Let's test
public static void main(String args[]){
// Initialize variables
String X = "DAVID";
String Y = "DANIEL";
int m = X.length();
int n = Y.length();
int[][] table = new int[m + 1][n + 1];
// Initialize table fields to `-1`
for(int i=0; i < m + 1; i++) {
for(int j=0; j < n + 1; j++) {
table[i][j] = -1;
}
}
// Compute and output length of LCS
int lcsLength = lcs(X, Y, m, n, table);
System.out.println("Length of LCS is: " + lcsLength);
}
}
C++
#include <bits/stdc++.h>
using namespace std;
int lcs(char *X, char* Y, int m, int n, vector<vector<int>>& table)
{
// Base case
if (m == 0 || n == 0)
return 0;
// Already computed value at given position
if (table[m][n] != -1) {
return table[m][n];
}
// Last elements are equal
if (X[m - 1] == Y[n - 1]) {
table[m][n] = 1 + lcs(X, Y, m - 1, n - 1, table);
return table[m][n];
}
// Last elements differ
else {
table[m][n] = max(lcs(X, Y, m, n - 1, table), lcs(X, Y, m - 1, n, table));
return table;
}
}
// Let's test
int main()
{
// Initialize variables
char X[] = "DAVIDE";
char Y[] = "DANIELE";
int m = strlen(X);
int n = strlen(Y);
// Initialize table with `-1`
vector<vector<int>> table(m + 1, vector<int>(n + 1, -1));
// Compute and output length of LCS
cout << "Length of LCS is: " << lcs(X, Y, m, n, table);
return 0;
}
La programmazione dinamica per la massima sottosequenza comune
La programmazione dinamica è una tecnica non ricorsiva che permette di risolvere i problemi di ottimizzazione suddividendoli in sottoproblemi più piccoli e risolvendoli quindi con un approccio “bottom-up” (dal basso verso l’alto). La programmazione dinamica trova applicazione, ad esempio, come approccio agli algoritmi di pathfinding per la ricerca dei percorsi. È possibile risolvere il problema della massima sottosequenza comune anche per mezzo della programmazione dinamica utilizzando una matrice bidimensionale.
Python
def lcs(X , Y, m, n):
# Initialize dynamic programming table fields to `None`
table = [[None] * (n + 1) for _ in range(m + 1)]
# Compute table values
for i in range(m + 1):
for j in range(n + 1):
# Base case
if i == 0 or j == 0 :
table[i][j] = 0
# Last elements are equal
elif X[i - 1] == Y[j - 1]:
table[i][j] = table[i - 1][j - 1]+ 1
# Last elements differ
else:
table[i][j] = max(table[i - 1][j] , table[i][j - 1])
return table[m][n]
# Let's test
X = "DAVIDE"
Y = "DANIELE"
# Compute and output length of LCS
lcs_len = lcs(X, Y, len(X), len(Y))
print(f"Length of LCS is: {lcs_len}")
Java
import java.io.*;
class LCS {
public static int lcs(String X, String Y, int m, int n)
{
// Initialize dynamic programming table fields
int table[][] = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
// Base case
if (i == 0 || j == 0)
table[i][j] = 0;
// Last elements are equal
else if (X.charAt(i - 1) == Y.charAt(j - 1))
table[i][j] = table[i - 1][j - 1] + 1;
// Last elements differ
else
table[i][j] = Math.max(table[i - 1][j], table[i][j - 1]);
}
}
return table[m][n];
}
// Let's test
public static void main(String args[]){
// Initialize variables
String X = "DAVIDE";
String Y = "DANIELE";
int m = X.length();
int n = Y.length();
// Compute and output length of LCS
int lcsLength = lcs(X, Y, m, n);
System.out.println("Length of LCS is: " + lcsLength);
}
}
C++
#include <bits/stdc++.h>
using namespace std;
int lcs(string X, string Y, int m, int n) {
// Initialize dynamic programming table
int table[m + 1][n + 1];
// Compute table values
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
// Base case
if (i == 0 || j == 0)
table[i][j] = 0;
// Last elements are equal
else if (X[i - 1] == Y[j - 1])
table[i][j] = table[i - 1][j - 1] + 1;
// Last elements differ
else
table[i][j] = max(table[i - 1][j], table[i][j - 1]);
}
}
return table[m][n];
}
// Let's test
int main() {
// Initialize variables
string X = "DAVIDE";
string Y = "DANIELE";
int m = X.size();
int n = Y.size();
// Compute and output length of LCS
cout << "Length of LCS is " << lcs(X, Y, m, n);
return 0;
}
Articoli simili
Manipolare e collegare i valori con gli operatori Python
Sin dai tempi della scuola, avete familiarità con gli operatori aritmetici: più, meno, per, diviso sono tutti simboli di operazioni matematiche. Tuttavia, un linguaggio di programmazione come Python conosce molti più operatori. È possibile elaborare non solo numeri, ma anche stringhe, elenchi e oggetti in generale. Vi indichiamo ciò che dovete considerare e approfondiamo il contesto.
ra2 studioShutterstock Quale linguaggio di programmazione imparare? Una guida pratica
La competenza nei diversi linguaggi di programmazione determina opportunità di carriera, lavori redditizi e incarichi regolari. Il numero di linguaggi di programmazione è in costante aumento, ma i classici come Java o Python non sono sempre la scelta migliore. Quale linguaggio di programmazione dovreste quindi imparare? Vi illustriamo quali sono i migliori linguaggi di programmazione.
