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
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 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:

  1. Approccio ricorsivo
  2. Ottimizzazione tramite memoizzazione
  3. 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)
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}")
python

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);
        }
}
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)}")
python

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);
    }
}
java

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;
}
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}")
python

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);
    }
}
java

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;
}
c++
Hai trovato questo articolo utile?
Per offrirti una migliore esperienza di navigazione online questo sito web usa dei cookie, propri e di terze parti. Continuando a navigare sul sito acconsenti all’utilizzo dei cookie. Scopri di più sull’uso dei cookie e sulla possibilità di modificarne le impostazioni o negare il consenso.