vignette|Sous-séquence commune. En informatique théorique, la plus longue sous-séquence commune à deux suites, ou deux chaînes de caractères, est une sous-suite extraite des deux suites, et de taille maximum. La résolution de ce problème peut être obtenue par programmation dynamique.
La généralisation à un nombre arbitraire de suites est un problème NP-difficile : le temps d'exécution de tout algorithme est exponentiel en le nombre de séquences.
Exemple Pour les deux séquences de caractères suivantes : « abcde », « ceij », la plus longue sous-séquence commune est « ce ».
Dans ce problème, il est nécessaire que les éléments communs soient dans le même ordre dans les différentes séquences, mais pas qu’ils soient obligatoirement consécutifs : « e » n’est pas consécutif à « c » dans la première séquence.
Résolution par force brute
On constate par dénombrement qu'il existe sous-séquences pour une chaîne de longueur . Les essayer toutes par force brute pour trouver la plus longue qui soit une sous-séquence d'une autre chaîne a donc une complexité exponentielle, ce qui n'est pas souhaitable en pratique.
Résolution par programmation dynamique
Pour deux suites en entrée, une telle sous-séquence peut être obtenue en temps polynomial par un algorithme de programmation dynamique dont le temps d'exécution est proportionnel au produit des longueurs des deux séquences, chapitre 15.4, Programmation dynamique : plus longue sous-séquence commune..
Structure d'une solution Il est possible de ramener le problème de recherche de plus longue sous séquence commune (PLSC) entre deux chaînes données à une recherche entre deux chaînes de taille inférieure grâce au théorème suivant (où désigne les premiers caractères de la séquence ):
Les trois cas , et sont exhaustifs, ce qui permet bien de se ramener à un problème de taille inférieure.
Longueur des plus longues sous-séquences communes On crée un tableau à deux dimensions dans lequel chaque case est destiné à contenir la longueur des PLSCs entre et . On peut alors calculer de proche en proche pour chaque couple d'indice et . Du théorème précédent découle en effet la formule:
Le calcul du contenu des cases de peut être effectué avec une complexité spatiale et temporelle en , car le contenu de chaque case est calculable à partir des cases précédentes en .
Obtention d'une plus longue sous-séquence commune La formule précédente permet de calculer de proche en proche les cases de . On peut reconstituer une plus longue sous-séquence commune grâce à lui.
Pour cela, on effectue un parcours depuis suivant la règle suivante
Depuis une case de valeur :
Si , on passe à la case de valeur et on ajoute ce caractère () au début de la PLSC en construction.
Si , Si , on passe indifféremment à la case ou . Si , on passe à la case Si , on passe à la case
Un exemple de parcours est donné par le tableau suivant, grâce auquel on déduit que MJAU est une plus longue sous-séquence commune à MZJAWXU et XMJYAUZ : 0 1 2 3 4 5 6 7 Ø M Z J A W X U 0 Ø 0 0 0 0 0 0 0 0 1 X 0 0 0 0 0 0 1 1 2 M 0 1 1 1 1 1 1 1 3 J 0 1 1 2 2 2 2 2 4 Y 0 1 1 2 2 2 2 2 5 A 0 1 1 2 3 3 3 3 6 U 0 1 1 2 3 3 3 4 7 Z 0 1 2 2 3 3 3 4
Complexité de l'algorithme Le calcul du contenu des cases de peut être effectué avec une complexité spatiale et temporelle en , car le contenu de chaque case est calculable à partir des cases précédentes en .
Une fois connu, l'obtention d'une PLSC a une complexité .
Variante linéaire en espace Pour de très grandes entrées, on peut calculer la sous-séquence commune en complexité en espace tout en conservant une complexité temporelle en . Pour cela, on utilise un algorithme mêlant programmation dynamique et diviser pour régner. Cet algorithme se nomme l'algorithme d'Hirschberg.
Notes et références
Bibliographie complémentaire
Voir aussi Plus longue sous-suite strictement croissante Plus longue sous-chaîne commune (restriction au cas où les éléments choisis dans chaque suite sont consécutifs) Chaîne la plus proche
Catégorie:Algorithme sur les chaînes de caractères Catégorie:Problème algorithmique