Plus longue 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[1] : le temps d'exécution de tout algorithme est exponentiel en le nombre de séquences.
Exemple
[modifier | modifier le code]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.
Algorithme par force brute
[modifier | modifier le code]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 en temps polynomial pour deux suites
[modifier | modifier le code]Une telle sous-séquence peut être obtenue par un algorithme de programmation dynamique dont le temps d'exécution est proportionnel au produit des longueurs des deux séquences[2].
Structure d'une solution
[modifier | modifier le code]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 )[2]:
Théorème — Soit et deux séquences, et soit une plus longue sous-séquence commune quelconque de et . On a alors :
- Si alors et de plus est une PLSC de et ;
- Si alors si on a qui est une PLSC de et ;
- Si alors si on a qui est une PLSC de et .
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
[modifier | modifier le code]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[2]:
Le calcul du contenu des cases de peut être effectué avec une complexité , car le contenu de chaque case est calculable à partir des cases précédente en [2].
Obtention d'une plus longue sous-séquence commune
[modifier | modifier le code]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
[modifier | modifier le code]Le calcul du contenu des cases de peut être effectué avec une complexité , car le contenu de chaque case est calculable à partir des cases précédente en [2].
Une fois connu, l'obtention d'une PLSC a une complexité [2].
Notes et références
[modifier | modifier le code]- David Maier, « The Complexity of Some Problems on Subsequences and Supersequences », Journal of the ACM, vol. 25, no 2, , p. 322-336 (DOI 10.1145/322063.322075
, S2CID 16120634)
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique, Dunod, [détail de l’édition], chapitre 15.4, Programmation dynamique : plus longue sous-séquence commune.
Bibliographie complémentaire
[modifier | modifier le code]- Masashi Kiyomi, Takashi Horiyama et Yota Otachi, « Longest common subsequence in sublinear space », Information Processing Letters, vol. 168, , article no 106084 (DOI 10.1016/j.ipl.2020.106084)
- Hideo Bannai, Tomohiro I et Dominik Köppl, « Longest bordered and periodic subsequences », Information Processing Letters, vol. 182, , article no 106398 (DOI 10.1016/j.ipl.2023.106398)
Voir aussi
[modifier | modifier le code]- 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