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 : 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 $2^{n}$ sous-séquences pour une chaîne de longueur $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.

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ù $X_{l}$ désigne les $l$ premiers caractères de la séquence $X$):

Théorème — Soit $X=[x_{1},\dots ,x_{m}]$ et $Y=[y_{1},\dots ,y_{n}]$ deux séquences, et soit $Z=[z_{1},\dots ,z_{k}]$ une plus longue sous-séquence commune quelconque de $X$ et $Y$. On a alors :

• Si $x_{m}=y_{n}$ alors $z_{k}=x_{m}=y_{n}$ et de plus $Z_{k-1}$ est une PLSC de $X_{m-1}$ et $Y_{n-1}$ ;
• Si $x_{m}\neq y_{n}$ alors si $z_{k}\neq x_{m}$ on a $Z$ qui est une PLSC de $X_{m-1}$ et $Y$ ;
• Si $x_{m}\neq y_{n}$ alors si $z_{k}\neq y_{n}$ on a $Z$ qui est une PLSC de $X$ et $Y_{n-1}$.

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

$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 $c$ peut être effectué avec une complexité ${\mathcal {O}}(mn)$, car le contenu de chaque case est calculable à partir des cases précédente en ${\mathcal {O}}(1)$.

Obtention d'une plus longue sous-séquence commune

La formule précédente permet de calculer de proche en proche les cases de $c$. On peut reconstituer une plus longue sous-séquence commune grâce à lui.

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

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

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

• Si $x_{i}\neq y_{j}$,
  • Si $c[i][j-1]=c[i-1][j]=\alpha$, on passe indifféremment à la case $c[i-1][j]$ ou $c[i][j-1]$.
  • Si $c[i][j-1]=\alpha >c[i-1][j]$, on passe à la case $c[i][j-1]$
  • Si $c[i-1][j]=\alpha >c[i][j-1]$, on passe à la case $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 :

		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 $c$ peut être effectué avec une complexité ${\mathcal {O}}(mn)$, car le contenu de chaque case est calculable à partir des cases précédente en ${\mathcal {O}}(1)$.

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

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