La recherche de la longest common sub­se­quence compte parmi les problèmes clas­siques en in­for­ma­tique. Les solutions aux problèmes LCS sont souvent abordées dans des en­tre­tiens relatifs à la pro­gram­ma­tion et dans des cours sur les al­go­rithmes.

Problème de la longest common sub­se­quence : de quoi s’agit-il ?

Ce problème consiste à trouver la plus longue sous-séquence commune (« longest common sub­se­quence ») à deux séquences. Une sous-séquence (« sub­se­quence ») 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 il­lustrent 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 dif­fé­ren­cier la plus longue sous-séquence commune de la plus longue sous-chaîne commune (« longest common substring »). Con­trai­re­ment à 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 sub­se­quence revêt de l’im­por­tance 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 res­sem­blances et les dif­fé­rences entre deux textes, ce qui permet de détecter le plagiat. L’uti­li­taire populaire diff, qui met en évidence les mo­di­fi­ca­tions apportées aux fichiers texte sources, se base lui aussi sur le problème LCS.

Dans le domaine bio-in­for­ma­tique, le problème de la longest common sub­se­quence se rencontre aussi dans l’analyse des séquences ADN. Avec le temps, dif­fé­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 com­prendre les mo­di­fi­ca­tions gé­né­tiques entre les espèces dans le cadre de l’évolution.

Les lin­guistes utilisent quant à eux le problème de la longest common sub­se­quence pour étudier l’évolution des langues au fil des siècles. Si, dans deux langues dif­fé­rentes, des mots partagent la même sig­ni­fi­ca­tion 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 his­to­rique de la mise en cor­res­pon­dance de dif­fé­rentes lettres.

Comment fonc­tion­nent les solutions au problème de la longest common sub­se­quence ?

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 op­ti­mi­sa­tion ni méthode par­ti­cu­lière. Elle consiste à dé­ter­mi­ner 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 mal­heu­reu­se­ment 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. Op­ti­mi­sa­tion par mé­moï­sa­tion
  3. Pro­gram­ma­tion dynamique

Ces approches ont un point commun : elles dis­tin­guent trois cas dif­fé­rents par rapport aux deux séquences qu’elles examinent :

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

Elles pré­sen­tent toutefois des dif­fé­rences en matière de com­plexité tem­po­relle (exécution asymp­to­tique) 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)
Op­ti­mi­sa­tion par mé­moï­sa­tion O(n *m) O(n* m)
Pro­gram­ma­tion dynamique O(n *m) O(n* m)
Note

Les al­go­rithmes présentés ci-dessous dé­ter­mi­nent, 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é­ter­mi­nées par d’autres étapes.

Dé­ter­mi­ner la longest common sub­se­quence 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’im­plé­men­ta­tion d’un tel al­go­rithme dans trois langages de pro­gram­ma­tion po­pu­laires.

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))
# Let’s test
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
  • 1 cer­ti­fi­cat SSL Wildcard par contrat
  • Fonction incluse Domain Connect pour une con­fi­gu­ra­tion DNS sim­pli­fiée

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ï­sa­tion

Dans le cadre de l’approche récursive, des sous-séquences qui se che­vauchent sont calculées. Cette propriété, com­mu­né­ment appelée « over­lap­ping sub­pro­blems » (lit­té­ra­le­ment « sous-problèmes qui se che­vauchent »), 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’ef­fi­ca­cité du processus, il peut s’avérer pertinent de recourir à la mé­moï­sa­tion. Il s’agit, en d’autres termes, de mettre en cache les sous-problèmes déjà calculés dans une matrice bi­di­men­sion­nelle.

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

Pro­gram­mer la longest common sub­se­quence de façon dynamique

La pro­gram­ma­tion dynamique est une technique non récursive qui permet de résoudre un problème d’op­ti­mi­sa­tion en le divisant en plusieurs sous-problèmes, ensuite résolus à l’aide d’une approche as­cen­dante. La pro­gram­ma­tion dynamique sert notamment de solution aux problèmes liés aux al­go­rithmes de pa­th­fin­ding (recherche de chemin). Le problème de la longest common sub­se­quence peut aussi être résolu à l’aide de la pro­gram­ma­tion dynamique, par l’in­ter­mé­diaire d’une matrice bi­di­men­sion­nelle.

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++
Aller au menu principal