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

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

La sous-séquence commune la plus longue (LCS) signifie que vous recevrez deux chaînes/modèles/séquences d'objets. Parmi ces deux séquences/chaînes, vous devez trouver la sous-séquence la plus longue d'éléments présents dans le même ordre dans les deux chaînes ou motifs.

Exemple

Par exemple, deux chaînes sont fournies.

Supposons que,

Motif_1 = « RGBGARGA »
Motif_2 = « BGRARG »

• A partir du pattern_1, des séquences peuvent être produites comme « RGB », « RGGA », « RGAR ». Pour créer une séquence, vous devez conserver la position relative de chaque caractère dans la chaîne.
• A partir du pattern_2, nous pouvons produire des séquences comme « BGR », « BRAG », « RARG ». Les séquences peuvent être produites à condition qu'elles conservent la position relative de la chaîne d'origine.

Le terme position relative signifie ordre.

Par exemple, « BRG » est une séquence valide car « B » est apparu en premier, puis « R » et enfin « G » dans la chaîne d'origine pattern_2. Cependant, si une séquence est « RBRG », elle n'est pas valide. Parce que dans la chaîne d'origine (pattern_2), « B » vient 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 a une complexité temporelle plus grande et n’est pas la solution optimale. En utilisant la solution de programmation dynamique (DP), nous surmontons le problème de complexité.

Méthode naïve

La méthode naïve est une approche simple du problème indépendamment de la complexité temporelle et des autres facteurs d’optimisation.

La méthode Naive est constituée de « Brute Force », de boucles multiples, de méthodes récursives dans la plupart des cas.

Le terme force brute signifie passer en revue tous les modèles 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 on peut prendre un personnage, soit pas. Cela signifie que, pour chaque personnage, nous avons deux choix.

Ils sont les suivants:

• 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 y a 14 séquences. Si nous ne prenons pas de lettres, essentiellement une chaîne vide, le total des séquences sera de 15. De plus, la chaîne « ABCD » elle-même est une séquence. Le nombre total de séquences est donc de 16.

Il est donc possible de générer 2⁴ ou 16 sous-séquences de « ABCD ». Ensuite, une chaîne d'une longueur de m devra totaliser une sous-séquence de 2^m.

Pour chaque sous-séquence, nous devons la vérifier pour l’ensemble du motif2. Cela prendra 0(n) temps. 0(n) signifie la fonction de complexité qui calcule le temps nécessaire à l'exécution.

Ainsi, la complexité temporelle totale devient O(n*2^m). Pour l'exemple, 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 motif1.
É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 plus de séquence dans le motif 1, passez à nouveau à 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 (simple) peut être trouvée en résolvant les sous-problèmes. Par exemple, dans l’exemple ci-dessus, nous avons pattern1 et pattern2.

É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.

On retrouve le LCS sur la sous-chaîne (chaîne générée à partir d'une chaîne originale). Ensuite, nous gardons l'enregistrement de la longueur du LCS des sous-chaînes.

Maintenant, voici une autre propriété intéressante qui est sous-problèmes qui se chevauchent. On dit qu’un problème comporte des sous-problèmes qui se chevauchent si l’énoncé du problème peut être divisé 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, regardons l'arbre de récursivité.

Dans la case de couleur sombre, vous pouvez remarquer des sous-problèmes qui se chevauchent. (« 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 séquence de communication la plus longue

Le graphique présenté ci-dessus est la méthode récursive. Chaque fonction récursive a un cas de base pour rompre la récursion ou commencer à revenir de sa pile.

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

• Si tous les éléments avant le dernier élément correspondent, augmentez la longueur de un et revenez
• Passez deux modèles à la fonction et prenez la valeur maximale du retour
• 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.

Pseudo code:

def lcs:
    input: pattern_1, pattern_2, len_1, len_2
if len_1 or len_2 is zero:
    then
return 0
if pattern_1[len_1 - 1] equals pattern_2[len_2 - 1]
then
return 1 + lcs(pattern_1, pattern_2,
    len_1 - 1, len_2 - 1)
else
    max of 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

Implémentation en 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("Lenght of LCS is: ", lcs(pattern_1, pattern_2, len(pattern_1), len(pattern_2)))

Sortie :

Lenght of LCS is:  5

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

La programmation dynamique signifie optimiser la méthode récursive simple. Par exemple, si nous voyons le graphe d’approche récursive ou naïve, nous pouvons voir qu’il existe plusieurs mêmes appels de fonction. La méthode de programmation dynamique enregistre tous les calculs dans un tableau et l'utilise en cas de besoin.

Nous utiliserons un tableau 2D avec des dimensions de mxn, où m et n sont les longueurs de pattern1 et pattern2.

Pour tableau 2D, nous pouvons utiliser des structures de données de liste en python ou des structures de données vectorielles/tableaux dans C++.

Pseudo-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 la table LCS utilisée comme structure de données de tableau 2D pour l'approche de programmation dynamique.

Discutons de la logique que nous avons utilisée ici. Les étapes sont :

Étape 1) Si i ou j vaut zéro, nous prenons une chaîne vide parmi les deux chaînes données et essayons de trouver les sous-séquences communes. Cependant, comme la sous-chaîne que nous prenons est vide, la longueur de la sous-séquence est 0.

É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) Si cela ne correspond pas, nous prendrons le LCS maximum des deux index adjacents. Et de cette façon, nous devons remplir toutes les valeurs du tableau 2D.

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

Fondamentalement, 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 sous-séquence commune la plus longue.

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 & lt; n + 1; i++) {
    for (int j = 0; j & lt; 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 un mot, nous calculons simplement chaque tâche une fois dans la méthode DP dans la méthode DP. Dans la méthode récursive, nous pourrions avoir des sous-problèmes qui se chevauchent.

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 ou DP[m-1][n-1], contiendra la longueur.

Ici, il est adressé comme DP[m-1][n-1], car l'index du tableau commence à 0.

Résumé

• La méthode DP a une complexité temporelle moindre ; c'est O(mn), où m et n sont la longueur de la chaîne ou du tableau d'entrée.
• DP est une approche plus rapide que l'approche récursive, avec la complexité temporelle de O(n*2^m).
• La programmation dynamique (DP) n'est pas optimisée en mémoire. Nous avons utilisé un tableau 2D d’une longueur de m*n. Ainsi, la complexité spatiale est (m*n).
• Méthode récursive, dans le pire des cas, la mémoire la plus élevée qu'elle occupera sera m+n, essentiellement la longueur totale de la chaîne saisie.
• L'ordinateur moderne d'aujourd'hui est suffisant pour gérer cette quantité de mémoire.