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.