algorithm
La plus longue sous-séquence commune
Recherche…
Plus longue explication de sous-séquence commune
L'une des implémentations les plus importantes de la programmation dynamique consiste à trouver la sous- séquence commune la plus longue . Définissons d'abord certaines des terminologies de base.
Sous-séquence:
Une sous-séquence est une séquence qui peut être dérivée d'une autre séquence en supprimant certains éléments sans modifier l'ordre des éléments restants. Disons que nous avons une chaîne ABC . Si nous effaçons zéro ou un ou plusieurs caractères de cette chaîne, nous obtenons la sous-séquence de cette chaîne. Les sous-séquences de la chaîne ABC seront donc { "A" , "B" , "C" , "AB" , "AC" , "BC" , "ABC" , "" }. Même si nous supprimons tous les caractères, la chaîne vide sera également une sous-séquence. Pour trouver la sous-séquence, pour chaque caractère d'une chaîne, nous avons deux options: soit nous prenons le caractère, soit nous ne le faisons pas. Donc, si la longueur de la chaîne est n , il y a 2 n sous- séquences de cette chaîne.
Plus longue sous-séquence commune:
Comme son nom l'indique, de toutes les sous-séquences communes entre deux chaînes, la plus longue sous-séquence commune (LCS) est celle qui a la longueur maximale. Par exemple: Les sous-séquences communes entre "HELLOM" et "HMLD" sont "H" , "HL" , "HM", etc. Ici, "HLL" est la plus longue sous-séquence commune de longueur 3.
Méthode Brute-Force:
Nous pouvons générer toutes les sous-séquences de deux chaînes en utilisant le backtracking . Ensuite, nous pouvons les comparer pour trouver les sous-séquences communes. Après nous aurons besoin de trouver celui avec la longueur maximale. Nous avons déjà vu que, il y a 2 n sous- séquences d'une chaîne de longueur n . Il faudrait des années pour résoudre le problème si notre n traverse 20-25.
Méthode de programmation dynamique:
Abordons notre méthode avec un exemple. Supposons que nous ayons deux chaînes abcdaf et acbcf . Notons ceux-ci avec s1 et s2 . Donc, la plus longue sous-séquence commune de ces deux chaînes sera "abcf" , qui a la longueur 4. Encore une fois, je vous le rappelle, les sous-séquences ne doivent pas nécessairement être continues dans la chaîne. Pour construire "abcf" , nous avons ignoré "da" dans s1 et "c" dans s2 . Comment trouvons-nous cela en utilisant la programmation dynamique?
Nous allons commencer avec une table (un tableau 2D) ayant tous les caractères de s1 dans une ligne et tous les caractères de s2 dans la colonne. Ici, la table est indexée sur 0 et nous mettons les caractères de 1 à plus. Nous allons parcourir la table de gauche à droite pour chaque ligne. Notre table ressemblera à:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Ici, chaque ligne et chaque colonne représente la longueur de la plus longue sous-séquence commune entre deux chaînes si nous prenons les caractères de cette ligne et de cette colonne et les ajoutons au préfixe précédent. Par exemple: La table [2] [3] représente la longueur de la plus longue sous-séquence commune entre "ac" et "abc" .
La colonne 0-th représente la sous-séquence vide de s1 . De même, la 0ème ligne représente la sous-séquence vide de s2 . Si nous prenons une sous-séquence vide d'une chaîne et essayons de la faire correspondre à une autre chaîne, quelle que soit la longueur de la seconde sous-chaîne, la sous-séquence commune aura une longueur de 0. Nous pouvons donc remplir les lignes 0 et 0 et les colonnes 0 avec des 0. On a:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Commençons. Lorsque nous remplissons la table [1] [1] , nous nous demandons si nous avons une chaîne a et une autre chaîne a et rien d'autre, quelle sera la plus longue sous-séquence commune ici? La longueur du LCS sera de 1. Regardons maintenant le tableau [1] [2] . Nous avons une chaîne ab et une chaîne a . La longueur du LCS sera 1. Comme vous pouvez le voir, le reste des valeurs sera également 1 pour la première ligne car il ne considère que la chaîne a avec abcd , abcda , abcdaf . Donc, notre table ressemblera à:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Pour la ligne 2, qui inclura désormais c . Pour le tableau [2] [1], nous avons ac d'un côté et a de l'autre côté. La longueur du LCS est donc de 1. Où avons-nous obtenu ce 1? Du haut, qui désigne le LCS a entre deux sous-chaînes. Donc, ce que nous disons, c'est que si s1 [2] et s2 [1] ne sont pas identiques, alors la longueur du LCS sera le maximum de la longueur de LCS en haut ou à gauche . En prenant la longueur du LCS en haut, cela signifie que nous ne prenons pas le caractère actuel de s2 . De même, la prise en compte de la longueur du LCS à gauche indique que nous ne prenons pas le caractère actuel de s1 pour créer le LCS. On a:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Donc, notre première formule sera:
if s2[i] is not equal to s1[j]
Table[i][j] = max(Table[i-1][j], Table[i][j-1]
endif
Passons maintenant à la table [2] [2], nous avons la chaîne ab et ac . Puisque c et b ne sont pas les mêmes, nous mettons le maximum du haut ou de gauche ici. Dans ce cas, c'est encore 1. Après cela, pour la Table [2] [3], nous avons la chaîne abc et ac . Cette fois, les valeurs actuelles des lignes et des colonnes sont identiques. Maintenant, la longueur de LCS sera égale à la longueur maximale de LCS jusqu'à présent. 1. Comment pouvons-nous obtenir la longueur maximale de LCS jusqu'à présent? Nous vérifions la valeur diagonale, qui représente la meilleure correspondance entre ab et a . A partir de cet état, pour les valeurs actuelles, nous avons ajouté un caractère supplémentaire à s1 et s2, qui se sont avérés identiques. Ainsi, la longueur de LCS va bien sûr augmenter. Nous allons mettre 1 + 1 = 2 dans le tableau [2] [3] . On a,
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | 1 | 2 | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Donc, notre deuxième formule sera:
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
endif
Nous avons défini les deux cas. En utilisant ces deux formules, nous pouvons remplir toute la table. Après avoir rempli la table, cela ressemblera à ceci:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | 1 | 2 | 2 | 2 | 2 | 2 |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | 1 | 2 | 3 | 3 | 3 | 3 |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | 1 | 2 | 3 | 3 | 3 | 4 |
+-----+-----+-----+-----+-----+-----+-----+-----+
La longueur du LCS entre s1 et s2 sera la table [5] [6] = 4 . Ici, 5 et 6 sont respectivement la longueur de s2 et s1 . Notre pseudo-code sera:
Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
Table[0][i] = 0
endfor
for i from 1 to s2.length
Table[i][0] = 0
endfor
for i from 1 to s2.length
for j from 1 to s1.length
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
else
Table[i][j] = max(Table[i-1][j], Table[i][j-1])
endif
endfor
endfor
Return Table[s2.length][s1.length]
La complexité temporelle de cet algorithme est la suivante: O (mn) où m et n désignent la longueur de chaque chaîne.
Comment pouvons-nous trouver la plus longue sous-séquence commune? Nous allons commencer par le coin inférieur droit. Nous allons vérifier d'où vient la valeur. Si la valeur provient de la diagonale, c'est-à-dire si la table [i-1] [j-1] est égale à la table [i] [j] - 1 , on appuie sur s2 [i] ou s1 [j] sont les mêmes) et se déplacer en diagonale. Si la valeur vient du haut, cela signifie que si la table [i-1] [j] est égale à la table [i] [j] , nous passons au sommet. Si la valeur vient de gauche, cela signifie que si la table [i] [j-1] est égale à la table [i] [j] , nous nous déplaçons vers la gauche. Lorsque nous atteignons la colonne la plus à gauche ou la plus haute, notre recherche se termine. Ensuite, nous affichons les valeurs de la pile et les imprimons. Le pseudo-code:
Procedure PrintLCS(LCSlength, s1, s2)
temp := LCSlength
S = stack()
i := s2.length
j := s1.length
while i is not equal to 0 and j is not equal to 0
if Table[i-1][j-1] == Table[i][j] - 1 and s1[j]==s2[i]
S.push(s1[j]) //or S.push(s2[i])
i := i - 1
j := j - 1
else if Table[i-1][j] == Table[i][j]
i := i-1
else
j := j-1
endif
endwhile
while S is not empty
print(S.pop)
endwhile
Point à noter: si le tableau [i-1] [j] et le tableau [i] [j-1] sont égaux au tableau [i] [j] et le tableau [i-1] [j-1] n’est pas égale à la table [i] [j] - 1 , il peut y avoir deux LCS pour ce moment. Ce pseudo-code ne considère pas cette situation. Vous devrez résoudre ce problème de manière récursive pour trouver plusieurs LCS.
La complexité temporelle de cet algorithme est la suivante: O (max (m, n)) .
