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.
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.
Nelle parti seguenti ti mostriamo tre approcci efficienti per risolvere il problema della LCS:
Hai trovato questo articolo utile?
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
|
N.B.
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 utilitydiff
, 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
- L’ultima lettera è uguale.
- L’ultima lettera non è uguale.
- La lunghezza di una sequenza è zero.
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)
|
N.B.
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}")
pythonJava
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);
}
}
java Registra il tuo dominio
- Certificato SSL Wildcard incluso
- Registrazione di dominio sicura
- Indirizzo e-mail professionale da 2 GB
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;
}
c++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)}")
pythonJava
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);
}
}
javaC++
#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;
}
c++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}")
pythonJava
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);
}
}
javaC++
#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;
}
c++