Accueil🇫🇷Chercher

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

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

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

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

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

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

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 :

01234567
ØMZJAWXU
0Ø 00000000
1X 00000011
2M 01111111
3J 01122222
4Y 01122222
5A 01123333
6U 01123334
7Z 01223334

Complexité de l'algorithme

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

  1. 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 Accès libre, S2CID 16120634)
  2. 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

  • 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

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.