DAA - Sous-séquence commune la plus longue

Le problème de sous-séquence le plus long est de trouver la séquence la plus longue qui existe dans les deux chaînes données.

Sous-séquence

Considérons une suite S = <s 1 , s 2 , s 3 , s 4 ,…, s n >.

Une suite Z = <z 1 , z 2 , z 3 , z 4 ,…, z m > sur S est appelée une sous-séquence de S, si et seulement si elle peut être dérivée de la suppression S de certains éléments.

Sous-séquence commune

Supposer, X et Ysont deux séquences sur un ensemble fini d'éléments. On peut dire çaZ est une sous-séquence commune de X et Y, si Z est une sous-séquence des deux X et Y.

Sous-séquence commune la plus longue

Si un ensemble de séquences est donné, le problème de sous-séquence le plus long est de trouver une sous-séquence commune de toutes les séquences qui est de longueur maximale.

Le problème de sous-séquence le plus long est un problème informatique classique, à la base de programmes de comparaison de données tels que l'utilitaire de diff, et a des applications en bioinformatique. Il est également largement utilisé par les systèmes de contrôle de révision, tels que SVN et Git, pour réconcilier plusieurs modifications apportées à une collection de fichiers contrôlée par révision.

Méthode naïve

Laisser X être une séquence de longueur m et Y une séquence de longueur n. Vérifiez chaque sous-séquence deX s'il s'agit d'une sous-séquence de Yet renvoie la plus longue sous-séquence commune trouvée.

Il y a 2m sous-séquences de X. Tester les séquences, qu'il s'agisse ou non d'une sous-séquence deY prend O(n)temps. Ainsi, l'algorithme naïf prendraitO(n2m) temps.

Programmation dynamique

Soit X = <x 1 , x 2 , x 3 ,…, x m > et Y = <y 1 , y 2 , y 3 ,…, y n > les suites. Pour calculer la longueur d'un élément, l'algorithme suivant est utilisé.

Dans cette procédure, table C[m, n] est calculé dans l'ordre principal de la ligne et dans une autre table B[m,n] est calculé pour construire une solution optimale.

Algorithm: LCS-Length-Table-Formulation (X, Y)
m := length(X) 
n := length(Y) 
for i = 1 to m do 
   C[i, 0] := 0 
for j = 1 to n do 
   C[0, j] := 0 
for i = 1 to m do 
   for j = 1 to n do 
      if xi = yj 
         C[i, j] := C[i - 1, j - 1] + 1 
         B[i, j] := ‘D’ 
      else 
         if C[i -1, j] ≥ C[i, j -1] 
            C[i, j] := C[i - 1, j] + 1 
            B[i, j] := ‘U’ 
         else 
         C[i, j] := C[i, j - 1]
         B[i, j] := ‘L’ 
return C and B
Algorithm: Print-LCS (B, X, i, j)
if i = 0 and j = 0 
   return  
if B[i, j] = ‘D’ 
   Print-LCS(B, X, i-1, j-1) 
   Print(xi) 
else if B[i, j] = ‘U’ 
   Print-LCS(B, X, i-1, j) 
else 
   Print-LCS(B, X, i, j-1)

Cet algorithme imprimera la plus longue sous-séquence commune de X et Y.

Une analyse

Pour peupler la table, le for boucle itère m les temps et l'intérieur for boucle itère nfois. Par conséquent, la complexité de l'algorithme est O (m, n) , oùm et n sont la longueur de deux chaînes.

Exemple

Dans cet exemple, nous avons deux chaînes X = BACDB et Y = BDCB pour trouver la sous-séquence commune la plus longue.

En suivant l'algorithme LCS-Length-Table-Formulation (comme indiqué ci-dessus), nous avons calculé le tableau C (montré sur le côté gauche) et le tableau B (montré sur le côté droit).

Dans le tableau B, au lieu de «D», «L» et «U», nous utilisons respectivement la flèche diagonale, la flèche gauche et la flèche haut. Après avoir généré la table B, le LCS est déterminé par la fonction LCS-Print. Le résultat est BCB.