Plus longue sous-séquence commune

Ne doit pas être confondu avec plus longue sous-chaîne 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 ${\displaystyle 2^{n}}$ sous-séquences pour une chaîne de longueur ${\displaystyle n}$. 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ù ${\displaystyle X_{l}}$ désigne les ${\displaystyle l}$ premiers caractères de la séquence ${\displaystyle X}$)^[2]:

Les trois cas ${\displaystyle \left\langle x_{m}=y_{n}\right\rangle }$, ${\displaystyle \left\langle x_{m}\neq y_{n}~{\mathsf {ET}}~z_{k}\neq x_{m}\right\rangle }$ et ${\displaystyle \left\langle x_{m}\neq y_{n}~{\mathsf {ET}}~z_{k}\neq y_{n}\right\rangle }$ 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 ${\displaystyle c[1\cdot \cdot m][1\cdot \cdot n]}$ dans lequel chaque case ${\displaystyle c[i][j]}$ est destiné à contenir la longueur des PLSCs entre ${\displaystyle X_{i}}$ et ${\displaystyle Y_{j}}$. On peut alors calculer de proche en proche ${\displaystyle c[i][j]}$ pour chaque couple d'indice ${\displaystyle i}$ et ${\displaystyle j}$. Du théorème précédent découle en effet la formule^[2]:

${\displaystyle c[i][j]={\begin{cases}0&{\text{ si }}i=0{\text{ ou }}j=0,\\c[i-1][j-1]+1&{\text{ si }}i,j>0{\text{ et }}x_{i}=y_{j},\\{\mathsf {max}}(c[i][j-1],c[i-1][j])&{\text{ si }}i,j>0{\text{ et }}x_{i}\neq y_{j}.\end{cases}}}$

Le calcul du contenu des cases de ${\displaystyle c}$ peut être effectué avec une complexité ${\displaystyle {\mathcal {O}}(mn)}$, car le contenu de chaque case est calculable à partir des cases précédente en ${\displaystyle {\mathcal {O}}(1)}$^[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 ${\displaystyle c}$. On peut reconstituer une plus longue sous-séquence commune grâce à lui.

Pour cela on effectue un parcours depuis ${\displaystyle c[m][n]}$ suivant la règle suivante

Depuis une case ${\displaystyle c[i][j]}$ de valeur ${\displaystyle \alpha }$:

• Si ${\displaystyle x_{i}=y_{j}}$, on passe à la case ${\displaystyle c[i-1][j-1]}$ de valeur ${\displaystyle \alpha -1}$ et on ajoute ce caractère (${\displaystyle x_{i}=y_{j}}$) au début de la PLSC en construction.

• Si ${\displaystyle x_{i}\neq y_{j}}$,
  • Si ${\displaystyle c[i][j-1]=c[i-1][j]=\alpha }$, on passe indifféremment à la case ${\displaystyle c[i-1][j]}$ ou ${\displaystyle c[i][j-1]}$.
  • Si ${\displaystyle c[i][j-1]=\alpha >c[i-1][j]}$, on passe à la case ${\displaystyle c[i][j-1]}$
  • Si ${\displaystyle c[i-1][j]=\alpha >c[i][j-1]}$, on passe à la case ${\displaystyle c[i-1][j]}$

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 :

Complexité de l'algorithme

Le calcul du contenu des cases de ${\displaystyle c}$ peut être effectué avec une complexité ${\displaystyle {\mathcal {O}}(mn)}$, car le contenu de chaque case est calculable à partir des cases précédente en ${\displaystyle {\mathcal {O}}(1)}$^[2].

Une fois ${\displaystyle c}$ connu, l'obtention d'une PLSC a une complexité ${\displaystyle {\mathcal {O}}(m+n)}$^[2].

Notes et références

Bibliographie complémentaire

• Masashi Kiyomi, Takashi Horiyama et Yota Otachi, « Longest common subsequence in sublinear space », Information Processing Letters, vol. 168,‎ juin 2021, article n^o 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,‎ août 2023, article n^o 106398 (DOI 10.1016/j.ipl.2023.106398)

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

• Portail de l'informatique théorique