Sous-séquence commune la plus longue

Dans ce didacticiel, vous apprendrez comment trouver la sous-séquence commune la plus longue. En outre, vous trouverez des exemples fonctionnels de la plus longue sous-séquence commune en C, C ++, Java et Python.

La sous-séquence commune la plus longue (LCS) est définie comme la sous-séquence la plus longue qui est commune à toutes les séquences données, à condition que les éléments de la sous-séquence ne soient pas obligés d'occuper des positions consécutives dans les séquences d'origine.

Si S1 et S2 sont les deux séquences données, alors Z est la sous-séquence commune de S1 et S2 si Z est une sous-séquence de S1 et S2. De plus, Z doit être une séquence strictement croissante des indices de S1 et S2.

Dans une séquence strictement croissante, les indices des éléments choisis parmi les séquences d'origine doivent être dans l'ordre croissant en Z.

Si

 S1 = (B, C, D, A, A, C, D)

Alors, (A, D, B)ne peut pas être une sous-séquence de S1 car l'ordre des éléments n'est pas le même (c'est-à-dire pas une séquence strictement croissante).

Comprenons LCS avec un exemple.

Si

 S1 = (B, C, D, A, A, C, D) S2 = (A, C, D, B, A, C)

Ensuite, les sous-séquences courantes sont (B, C), (C, D, A, C), (D, A, C), (A, A, C), (A, C), (C, D), …

Parmi ces sous-séquences, se (C, D, A, C)trouve la plus longue sous-séquence commune. Nous allons trouver cette plus longue sous-séquence commune en utilisant la programmation dynamique.

Avant de continuer, si vous ne connaissez pas déjà la programmation dynamique, veuillez passer par la programmation dynamique.

Utilisation de la programmation dynamique pour trouver le LCS

Prenons deux séquences:

La première séquence Deuxième séquence

Les étapes suivantes sont suivies pour trouver la sous-séquence commune la plus longue.

  1. Créez une table de dimension n+1*m+1où n et m sont respectivement les longueurs de X et Y. La première ligne et la première colonne sont remplies de zéros. Initialiser une table
  2. Remplissez chaque cellule du tableau en utilisant la logique suivante.
  3. Si le caractère correspondant à la ligne actuelle et à la colonne actuelle correspondent, remplissez la cellule actuelle en en ajoutant un à l'élément diagonal. Pointez une flèche vers la cellule diagonale.
  4. Sinon, prenez la valeur maximale de la colonne précédente et de l'élément de ligne précédent pour remplir la cellule actuelle. Pointez une flèche vers la cellule avec la valeur maximale. S'ils sont égaux, indiquez l'un d'entre eux. Remplissez les valeurs
  5. L'étape 2 est répétée jusqu'à ce que le tableau soit rempli. Remplissez toutes les valeurs
  6. La valeur de la dernière ligne et de la dernière colonne correspond à la longueur de la sous-séquence commune la plus longue. Le coin inférieur droit correspond à la longueur du LCS
  7. Afin de trouver la sous-séquence commune la plus longue, commencez par le dernier élément et suivez le sens de la flèche. Les éléments correspondant au symbole () forment la plus longue sous-séquence commune. Créez un chemin selon les flèches

Ainsi, la sous-séquence commune la plus longue est CD.

LCS

Comment un algorithme de programmation dynamique est-il plus efficace que l'algorithme récursif lors de la résolution d'un problème LCS?

La méthode de programmation dynamique réduit le nombre d'appels de fonction. Il stocke le résultat de chaque appel de fonction afin qu'il puisse être utilisé dans les appels futurs sans avoir besoin d'appels redondants.

Dans l'algorithme dynamique ci-dessus, les résultats obtenus à partir de chaque comparaison entre les éléments de X et les éléments de Y sont stockés dans une table afin qu'ils puissent être utilisés dans de futurs calculs.

Ainsi, le temps pris par une approche dynamique est le temps mis pour remplir le tableau (ie. O (mn)). Alors que l'algorithme de récursivité a la complexité de 2 max (m, n) .

Algorithme de sous-séquence le plus long

 X et Y sont deux séquences données Initialiser une table LCS de dimension X.length * Y.length X.label = X Y.label = Y LCS (0) () = 0 LCS () (0) = 0 Démarrer à partir de LCS ( 1) (1) Comparez X (i) et Y (j) Si X (i) = Y (j) LCS (i) (j) = 1 + LCS (i-1, j-1) Pointez une flèche vers LCS (i) (j) Sinon LCS (i) (j) = max (LCS (i-1) (j), LCS (i) (j-1)) Pointez une flèche vers max (LCS (i-1) ( j), LCS (i) (j-1))

Exemples Python, Java et C / C ++

Python Java C C ++ 
 # The longest common subsequence in Python # Function to find lcs_algo def lcs_algo(S1, S2, m, n): L = ((0 for x in range(n+1)) for x in range(m+1)) # Building the mtrix in bottom-up way for i in range(m+1): for j in range(n+1): if i == 0 or j == 0: L(i)(j) = 0 elif S1(i-1) == S2(j-1): L(i)(j) = L(i-1)(j-1) + 1 else: L(i)(j) = max(L(i-1)(j), L(i)(j-1)) index = L(m)(n) lcs_algo = ("") * (index+1) lcs_algo(index) = "" i = m j = n while i> 0 and j> 0: if S1(i-1) == S2(j-1): lcs_algo(index-1) = S1(i-1) i -= 1 j -= 1 index -= 1 elif L(i-1)(j)> L(i)(j-1): i -= 1 else: j -= 1 # Printing the sub sequences print("S1 : " + S1 + "S2 : " + S2) print("LCS: " + "".join(lcs_algo)) S1 = "ACADB" S2 = "CBDA" m = len(S1) n = len(S2) lcs_algo(S1, S2, m, n)
 // The longest common subsequence in Java class LCS_ALGO ( static void lcs(String S1, String S2, int m, int n) ( int()() LCS_table = new int(m + 1)(n + 1); // Building the mtrix in bottom-up way for (int i = 0; i <= m; i++) ( for (int j = 0; j <= n; j++) ( if (i == 0 || j == 0) LCS_table(i)(j) = 0; else if (S1.charAt(i - 1) == S2.charAt(j - 1)) LCS_table(i)(j) = LCS_table(i - 1)(j - 1) + 1; else LCS_table(i)(j) = Math.max(LCS_table(i - 1)(j), LCS_table(i)(j - 1)); ) ) int index = LCS_table(m)(n); int temp = index; char() lcs = new char(index + 1); lcs(index) = ''; int i = m, j = n; while (i> 0 && j> 0) ( if (S1.charAt(i - 1) == S2.charAt(j - 1)) ( lcs(index - 1) = S1.charAt(i - 1); i--; j--; index--; ) else if (LCS_table(i - 1)(j)> LCS_table(i)(j - 1)) i--; else j--; ) // Printing the sub sequences System.out.print("S1 : " + S1 + "S2 : " + S2 + "LCS: "); for (int k = 0; k <= temp; k++) System.out.print(lcs(k)); System.out.println(""); ) public static void main(String() args) ( String S1 = "ACADB"; String S2 = "CBDA"; int m = S1.length(); int n = S2.length(); lcs(S1, S2, m, n); ) )
 // The longest common subsequence in C #include #include int i, j, m, n, LCS_table(20)(20); char S1(20) = "ACADB", S2(20) = "CBDA", b(20)(20); void lcsAlgo() ( m = strlen(S1); n = strlen(S2); // Filling 0's in the matrix for (i = 0; i <= m; i++) LCS_table(i)(0) = 0; for (i = 0; i <= n; i++) LCS_table(0)(i) = 0; // Building the mtrix in bottom-up way for (i = 1; i <= m; i++) for (j = 1; j = LCS_table(i)(j - 1)) ( LCS_table(i)(j) = LCS_table(i - 1)(j); ) else ( LCS_table(i)(j) = LCS_table(i)(j - 1); ) ) int index = LCS_table(m)(n); char lcsAlgo(index + 1); lcsAlgo(index) = ''; int i = m, j = n; while (i> 0 && j> 0) ( if (S1(i - 1) == S2(j - 1)) ( lcsAlgo(index - 1) = S1(i - 1); i--; j--; index--; ) else if (LCS_table(i - 1)(j)> LCS_table(i)(j - 1)) i--; else j--; ) // Printing the sub sequences printf("S1 : %s S2 : %s ", S1, S2); printf("LCS: %s", lcsAlgo); ) int main() ( lcsAlgo(); printf(""); )
 // The longest common subsequence in C++ #include using namespace std; void lcsAlgo(char *S1, char *S2, int m, int n) ( int LCS_table(m + 1)(n + 1); // Building the mtrix in bottom-up way for (int i = 0; i <= m; i++) ( for (int j = 0; j <= n; j++) ( if (i == 0 || j == 0) LCS_table(i)(j) = 0; else if (S1(i - 1) == S2(j - 1)) LCS_table(i)(j) = LCS_table(i - 1)(j - 1) + 1; else LCS_table(i)(j) = max(LCS_table(i - 1)(j), LCS_table(i)(j - 1)); ) ) int index = LCS_table(m)(n); char lcsAlgo(index + 1); lcsAlgo(index) = ''; int i = m, j = n; while (i> 0 && j> 0) ( if (S1(i - 1) == S2(j - 1)) ( lcsAlgo(index - 1) = S1(i - 1); i--; j--; index--; ) else if (LCS_table(i - 1)(j)> LCS_table(i)(j - 1)) i--; else j--; ) // Printing the sub sequences cout << "S1 : " << S1 << "S2 : " << S2 << "LCS: " << lcsAlgo << ""; ) int main() ( char S1() = "ACADB"; char S2() = "CBDA"; int m = strlen(S1); int n = strlen(S2); lcsAlgo(S1, S2, m, n); )

Applications de sous-séquences courantes les plus longues

  1. dans la compression des données de reséquençage du génome
  2. pour authentifier les utilisateurs sur leur téléphone mobile grâce à des signatures en direct

Articles intéressants...