Le problème de la longest common subsequence

La recherche de la longest common subsequence compte parmi les problèmes classiques en informatique. Les solutions aux problèmes LCS sont souvent abordées dans des entretiens relatifs à la programmation et dans des cours sur les algorithmes.

Problème de la longest common subsequence : de quoi s’agit-il ?

Ce problème consiste à trouver la plus longue sous-séquence commune (« longest common subsequence ») à deux séquences. Une sous-séquence (« subsequence ») provient d’une séquence originale. Les éléments d’une sous-séquence sont toujours dans le même ordre, mais certains d’entre eux peuvent avoir été supprimés. Découvrez avec nous quelques exemples qui illustrent ce principe :

Séquence X Séquence Y LCS(X, Y)
PÈRE MÈRE ÈRE
PAPA PAPI PAP
DAVID DANIEL DAI
Note

Il convient de bien différencier la plus longue sous-séquence commune de la plus longue sous-chaîne commune (« longest common substring »). Contrairement à la sous-séquence, la sous-chaîne ne peut contenir aucun espace. Dans l’exemple « |DAVID|DANIEL|DAI| », la plus longue sous-chaîne commune serait donc « DA », car le « I » se trouve après un « V » ou un « N ».

Exemple pratique du problème LCS

Le problème de la longest common subsequence revêt de l’importance dans tous les domaines où le travail avec des séquences dérivées est pertinent. Les solutions au problème LCS sont notamment utilisées pour examiner les ressemblances et les différences entre deux textes, ce qui permet de détecter le plagiat. L’utilitaire populaire diff, qui met en évidence les modifications apportées aux fichiers texte sources, se base lui aussi sur le problème LCS.

Dans le domaine bio-informatique, le problème de la longest common subsequence se rencontre aussi dans l’analyse des séquences ADN. Avec le temps, différentes mutations peuvent modifier les bases d’ADN à certains endroits isolés. La présence d’une longue sous-séquence commune à deux séquences indique alors un fort lien génétique. Il est donc possible de comprendre les modifications génétiques entre les espèces dans le cadre de l’évolution.

Les linguistes utilisent quant à eux le problème de la longest common subsequence pour étudier l’évolution des langues au fil des siècles. Si, dans deux langues différentes, des mots partagent la même signification et une longue sous-séquence commune, cela signifie que ces langues sont de même origine. Il est donc possible de déduire une évolution historique de la mise en correspondance de différentes lettres.

Comment fonctionnent les solutions au problème de la longest common subsequence ?

Le problème LCS peut tout d’abord être résolu par une approche dite « naïve ». Cette stratégie est la plus évidente ; elle ne demande ni optimisation ni méthode particulière. Elle consiste à déterminer toutes les sous-séquences des deux séquences, et de trouver la plus longue sous-séquence commune à celles-ci. Cette approche n’étant malheureusement pas très efficace, elle ne convient qu’aux séquences les plus courtes.

Découvrez trois solutions efficaces au problème LCS :

  1. Approche récursive
  2. Optimisation par mémoïsation
  3. Programmation dynamique

Ces approches ont un point commun : elles distinguent trois cas différents par rapport aux deux séquences qu’elles examinent :

  • La dernière lettre est identique.
  • La dernière lettre est différente.
  • La longueur de l’une des séquences est nulle.

Elles présentent toutefois des différences en matière de complexité temporelle (exécution asymptotique) et spatiale (besoin en mémoire) :

Approche Exécution Besoin en mémoire
Approche naïve O(n * n²) O(n)
Approche récursive O(n²) O(1)
Optimisation par mémoïsation O(n *m) O(n* m)
Programmation dynamique O(n *m) O(n* m)
Note

Les algorithmes présentés ci-dessous déterminent, pour chaque cas, la longueur de la plus longue sous-séquence commune. Il arrive parfois que plusieurs sous-séquences concrètes de cette même longueur existent, celles-ci pouvant être déterminées par d’autres étapes.

Déterminer la longest common subsequence de façon récursive

Le problème LCS présente une « sous-structure optimale » ; cela signifie que le problème peut être divisé en plusieurs sous-problèmes. Pour les résoudre, il convient alors d’adopter une approche récursive. Découvrez avec nous l’implémentation d’un tel algorithme dans trois langages de programmation populaires.

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 = "DANIEL", "DAVID"
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
Nom de domaine
Votre domaine en un clic
  • Domaine .eu ou .fr + éditeur de site gratuit pendant 6 mois
  • 1 certificat SSL Wildcard par contrat
  • Boîte email de 2 Go

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

Optimiser l’approche récursive par mémoïsation

Dans le cadre de l’approche récursive, des sous-séquences qui se chevauchent sont calculées. Cette propriété, communément appelée « overlapping subproblems » (littéralement « sous-problèmes qui se chevauchent »), est présente dans la suite de Fibonacci. Dans les deux cas, des séquences sont calculées de manière récursive et répétée jusqu’à l’obtention de la solution. Pour optimiser l’efficacité du processus, il peut s’avérer pertinent de recourir à la mémoïsation. Il s’agit, en d’autres termes, de mettre en cache les sous-problèmes déjà calculés dans une matrice bidimensionnelle.

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 = "DAVID"
Y = "DANIEL"
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[] = "DAVID";
    char Y[] = "DANIEL";
    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++

Programmer la longest common subsequence de façon dynamique

La programmation dynamique est une technique non récursive qui permet de résoudre un problème d’optimisation en le divisant en plusieurs sous-problèmes, ensuite résolus à l’aide d’une approche ascendante. La programmation dynamique sert notamment de solution aux problèmes liés aux algorithmes de pathfinding (recherche de chemin). Le problème de la longest common subsequence peut aussi être résolu à l’aide de la programmation dynamique, par l’intermédiaire d’une matrice bidimensionnelle.

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 = "DAVID"
Y = "DANIEL"
# 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 = "DAVID";
        String Y = "DANIEL";
        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 = "DAVID";
  string Y = "DANIEL";
  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++
Cet article vous a-t-il été utile ?