Sous-séquence commune la plus longue : Python, C++ Exemple

Quelle est la sous-séquence commune la plus longue ?

La plus longue sous-séquence commune (LCS) consiste à trouver, parmi deux chaînes de caractères, motifs ou séquences d'objets, la plus longue sous-séquence d'éléments présents dans le même ordre dans les deux.

Exemple

Par exemple, deux chaînes de caractères sont fournies. Supposons que :

Motif_1 = « RGBGARGA »
Motif_2 = « BGRARG »

• À partir du motif 1, on peut générer des séquences comme « RGB », « RGGA », « RGAR ». Pour créer une séquence, il faut conserver la position relative de chaque caractère dans la chaîne.
• À partir du motif 2, nous pouvons générer des séquences telles que « BGR », « BRAG », « RARG ». Ces séquences peuvent être générées tant qu'elles conservent la position relative de la chaîne d'origine.

Le terme position relative signifie ordre.

Par exemple, la séquence « BRG » est valide car « B » apparaît en premier, suivi de « R », puis de « G » dans la chaîne originale pattern_2. En revanche, la séquence « RBRG » n’est pas valide car, dans la chaîne originale (pattern_2), « B » apparaît en premier.

Nous avons deux options pour trouver la sous-séquence commune la plus longue à partir des deux séquences ou tableaux donnés.

• Méthode naïve
• Solution de programmation dynamique : la sous-séquence commune la plus longue est également connue sous le nom de LCS.

Une solution naïve présente une complexité temporelle plus élevée et n'est pas optimale. L'utilisation de la programmation dynamique (PD) permet de surmonter ce problème de complexité.

Méthode naïve

La méthode naïve est une approche simple du problème, indépendante de la complexité temporelle et des autres facteurs d'optimisation. Elle repose généralement sur une approche exhaustive, utilisant de multiples boucles et des appels récursifs. L'expression « approche exhaustive » désigne le fait d'explorer toutes les solutions possibles pour un problème donné.

Exemple

À partir de l’exemple ci-dessus de pattern1 et pattern2, supposons que pattern1 a une longueur de m et pattern2 a une longueur de n. Pour vérifier tous les cas possibles, nous devons évaluer chaque sous-séquence possible de pattern1 avec pattern2.

Voici une simple chaîne de 4 lettres, « ABCD ». Par exemple, nous devons créer une séquence à partir de « ABCD ». Soit nous prenons un caractère, soit nous ne le prenons pas. Cela signifie que, pour chaque caractère, nous avons deux choix :

• Le personnage sera ajouté à la sous-séquence.
• Le personnage ne sera pas ajouté à la sous-séquence.

Ici, les images montrent toutes les séquences que l'on peut réaliser à partir de la chaîne « ABCD ».

Séquence à 1 caractère :

Séquences à 2 personnages :

Séquences à 3 personnages :

D'après le diagramme ci-dessus, il existe 14 séquences. Si l'on ne considère aucune lettre, c'est-à-dire une chaîne vide, on obtient 15 séquences. De plus, la chaîne « ABCD » est elle-même une séquence. On arrive donc à un total de 16 séquences.

Il est donc possible de générer 2⁴ ou 16 sous-séquences à partir de « ABCD ». On obtient alors une chaîne de caractères d'une longueur de m aura une sous-séquence totale de 2^m.

Pour chaque sous-séquence, il faut vérifier si elle correspond au motif complet 2. Cela prendra un temps O(n). O(n) désigne la fonction de complexité qui calcule le temps d'exécution.

Ainsi, la complexité temporelle totale devient O(n*2^m). Pour l'exemple que nous avons vu ci-dessus, la valeur de m=8 et n=5.

Voici les étapes de la méthode naïve :

Étape 1) Prenez une séquence du modèle 1.
Étape 2) Faites correspondre la séquence de l'étape 1 avec le motif 2.
Étape 3) Si cela correspond, enregistrez la sous-séquence.
Étape 4) S'il reste d'autres séquences dans le motif 1, retournez à l'étape 1.
Étape 5) Imprimez la sous-séquence la plus longue.

Sous-structure optimale

Le terme « sous-structure optimale » signifie qu'une solution optimale peut être trouvée en résolvant les sous-problèmes. Par exemple, dans l'exemple ci-dessus, nous avons le motif 1 et le motif 2.

Étape 1) Prenez les deux premiers caractères de chaque motif.

Étape 2) Prenez le troisième au cinquième caractère de chaque motif.

Étape 3) Continuez de la même manière avec les personnages restants.

Structure récursive du problème LCS

Nous déterminons la plus longue sous-chaîne (LCS) de la sous-chaîne (une chaîne générée à partir d'une chaîne originale). Ensuite, nous enregistrons la longueur de la LCS des sous-chaînes.

Maintenant, voici une autre propriété intéressante qui est chevauchementping sous-problèmesOn dit qu'un problème présente un chevauchement.ping sous-problèmes si l'énoncé du problème peut être décomposé en petits sous-problèmes et utilisé plusieurs fois dans le programme.

Le diagramme ci-dessous montre que l'algorithme récursif a appelé plusieurs fois la fonction avec le même paramètre.

Par exemple, regardez l'arbre de récursion. Dans la case foncée, vous pouvez remarquer un chevauchement.ping sous-problèmes. (« RG », « RA »), (« RG », « R »), et d'autres sont appelés plusieurs fois.

Pour optimiser cela, nous avons l'approche de Programmation dynamique (DP).

Méthode récursive de la plus longue sous-séquence commune

Le graphique ci-dessus représente la méthode récursive. Chaque fonction récursive possède un cas de base permettant d'interrompre la récursion ou de commencer à retourner des éléments de sa pile.

Pour cette implémentation, nous utiliserons un cas de base. Donc, le algorithme est comme ceci :

• Si tous les éléments précédant le dernier élément ont une correspondance, alors augmentez la longueur de un et retournez.
• Transmettez deux motifs à la fonction et prenez la valeur maximale du résultat.
• Si un motif a une longueur nulle, alors nous n’avons aucune sous-séquence à comparer. Renvoie 0 dans ce cas. C'est le cas de base de la récursion.

Faux Code:

def lcs:
    input: pattern_1, pattern_2, len_1, len_2
    if len_1 or len_2 is zero:
        return 0
    if pattern_1[len_1 - 1] equals pattern_2[len_2 - 1]:
        return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1)
    else:
        return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2),
                   lcs(pattern_1, pattern_2, len_1, len_2 - 1))

Mise en œuvre dans C++

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int lcs(string pattern_1, string pattern_2, int len_1, int len_2) {
  if (len_1 == 0 || len_2 == 0)
    return 0;
  if (pattern_1[len_1 - 1] == pattern_2[len_2 - 1]) {
    return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1);
  } else {
    return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2), lcs(pattern_1, pattern_2, len_1, len_2 - 1));
  }
}
int main() {
  string pattern_1, pattern_2;
  pattern_1 = "RGBGARGA";
  pattern_2 = "BGRARG";
  cout<<"Length of LCS is: "<<lcs(pattern_1, pattern_2, pattern_1.size(), pattern_2.size())<<endl;
}

Sortie :

Length of LCS is: 5

Mise en œuvre dans Python

def lcs(pattern_1, pattern_2, len_1, len_2):
    if len_1 == 0 or len_2 == 0:
        return 0
    if pattern_1[len_1 - 1] == pattern_2[len_2 - 1]:
        return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1)
    else:
        return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2),
                   lcs(pattern_1, pattern_2, len_1, len_2 - 1))

pattern_1 = "RGBGARGA"
pattern_2 = "BGRARG"
print("Length of LCS is: ", lcs(pattern_1, pattern_2, len(pattern_1), len(pattern_2)))

Sortie :

Length of LCS is:  5

Méthode de programmation dynamique de la plus longue sous-séquence commune (LCS)

La programmation dynamique consiste à optimiser une méthode récursive classique. Par exemple, si l'on observe le graphe d'une approche récursive ou naïve, on constate la présence de nombreux appels de fonction identiques. La programmation dynamique, quant à elle, enregistre tous les calculs dans un tableau et les réutilise au besoin.

Nous utiliserons un tableau 2D de dimensions mxn, où m et n sont les longueurs des motifs pattern1 et pattern2. tableau 2D, nous pouvons utiliser des structures de données de type liste dans Python ou des structures de données vectorielles/tableaux dans C++.

Faux Code pour LCS utilisant DP :

LCS(pattern_1, pattern_2):
    m = length of pattern_1 + 1
    n = length of pattern_2 + 1
    dp[n][m]
    for i in range 0 to n + 1:
        for j in range 0 to m + 1:
            if i or j equals to 0:
                dp[i][j] = 0
            else if pattern_1[i] == pattern_2[j]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]

Voici le tableau LCS utilisé comme structure de données de tableau 2D pour l'approche de programmation dynamique.

Examinons la logique que nous avons utilisée ici. Les étapes sont les suivantes :

Étape 1) Si i ou j vaut zéro, on extrait une chaîne vide des deux chaînes données et on cherche les sous-séquences communes. Cependant, comme la sous-chaîne extraite est vide, sa longueur est nulle.

Étape 2) Si deux caractères correspondent, nous attribuerons la valeur à l'index (i,j) en incrémentant le LCS précédemment calculé, qui est présent dans l'index (i-1,j-1) (de la ligne précédente).

Étape 3) S'il n'y a pas de correspondance, on prendra la plus grande plus longue sous-séquence (LCS) des deux indices adjacents. On remplit ainsi toutes les valeurs du tableau 2D.

Étape 4) Enfin, nous renverrons la valeur de la dernière cellule du tableau 2D.

En résumé, toutes les valeurs du tableau 2D contiennent la longueur des sous-séquences communes. Parmi celles-ci, la dernière cellule contient la longueur de la plus longue sous-séquence commune.

Mise en œuvre dans C++

#include<iostream>
using namespace std;
int lcs(string pattern_1, string pattern_2) {
  int m = pattern_1.size();
  int n = pattern_2.size();
  // dp will store solutions as the iteration goes on
  int dp[n + 1][m + 1];
  for (int i = 0; i < n + 1; i++) {
    for (int j = 0; j < m + 1; j++) {
      if (i == 0 || j == 0) {
        dp[i][j] = 0;
      } else if (pattern_2[i - 1] == pattern_1[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[n][m];
}
int main() {
  string pattern_1 = "RGBGARGA";
  string pattern_2 = "BGRARG";
  cout<<"Length of LCS: "<<lcs(pattern_1, pattern_2)<<endl;
}

Sortie :

Length of LCS: 5

Mise en œuvre dans Python

def lcs(pattern_1, pattern_2):
    m = len(pattern_1)
    n = len(pattern_2)
    # dp will store solutions as the iteration goes on
    dp = [[None] * (n + 1) for item in range(m + 1)]
    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0 or j == 0:
                dp[i][j] = 0
            elif pattern_1[i - 1] == pattern_2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

pattern_1 = "RGBGARGA"
pattern_2 = "BGRARG"
print("Length of LCS: ", lcs(pattern_1, pattern_2))

Sortie :

Length of LCS: 5

Ainsi, les deux chaînes ont la plus longue sous-séquence commune de longueur 5.

En résumé, la méthode de programmation dynamique (DP) calcule chaque tâche une seule fois. Dans la méthode récursive, il peut y avoir des chevauchements.ping sous-problèmes.

Dans cet algorithme de programmation dynamique, nous utilisons une matrice 2D. Deux chaînes seront données (en supposant que les deux aient une longueur n). Ensuite, l'espace nécessaire dans le tableau est nx n. Si les chaînes sont suffisamment grandes, nous aurons besoin d’une version optimisée en mémoire de la solution DP.

La logique simplifiée prise en compte dans le code est la suivante :

• Déclarez un tableau 2D DP[m][n].
• Remplissez la première ligne et la première colonne du tableau DP avec 0.
• Prenez i et j pour l'itération.
• Si pattern1[i] est égal à pattern2[j], alors mettez à jour DP[i][j] = DP[i-1][j-1] + 1.
• Si pattern1[i] n'est pas égal à pattern2[j], alors DP[i][j] sera la valeur maximale entre DP[i-1][j] et DP[i][j-1].
• Continuez jusqu'à ce que i et j atteignent m et n.
• Le dernier élément, DP[m-1][n-1], contiendra la longueur.

Ici, il est désigné par DP[m-1][n-1] car l'indice du tableau commence à 0.

FAQ