Plus longue sous-séquence commune

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
Ne doit pas être confondu avec plus longue sous-chaîne commune.

La plus longue sous-séquence commune à deux suites, ou deux chaînes de caractère, est une séquence étant sous-suite des deux suites, et étant 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 l'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[1].

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 )[1]:

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[1]:

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 [1].

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. On crée pour cela un tableau à deux dimensions dont chaque case est destinée à contenir l'un des trois symboles ↖, ← ou ↑. La case pour tout couple d'indice est définie par[1]:

On reconstruit alors une plus longue sous-séquence commune à partir de  ; pour cela on effectue un parcours depuis en suivant les flèches. Lorsque l'on passe par une case contenant ↖, c'est que et on ajoute ce caractère au début de la PLSC en construction. 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 [1].

Une fois connu, l'obtention d'une PLSC a une complexité [1].

Notes et références[modifier | modifier le code]

  1. a, b, c, d, e, f et g 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.

Voir aussi[modifier | modifier le code]