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

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[modifier | modifier le code]

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^[2]:

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)$ ^[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 $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}$ $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[modifier | modifier le code]

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)$ ^[2].

Une fois $c$ connu, l'obtention d'une PLSC a une complexité ${\mathcal {O}}(m+n)$ ^[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, n^o 2,‎ 1978, p. 322-336 (DOI 10.1145/322063.322075 , S2CID 16120634)
↑ ^{a b c d e et f} Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique, Dunod, 2002 [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,‎ 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[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

Portail de l'informatique théorique

[1] David Maier, « The Complexity of Some Problems on Subsequences and Supersequences », Journal of the ACM, vol. 25, n^o 2,‎ 1978, p. 322-336 (DOI 10.1145/322063.322075 , S2CID 16120634)

[Cormen-2] {a b c d e et f} Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique, Dunod, 2002 [détail de l’édition], chapitre 15.4, Programmation dynamique : plus longue sous-séquence commune.

[1]

[2]

v · m Algorithmique du texte
Recherche de sous-chaîne	Algorithme de Knuth-Morris-Pratt Algorithme de Boyer-Moore Algorithme de Boyer-Moore-Horspool Algorithme de Raita Algorithme de Baeza-Yates-Gonnet Algorithme Z Algorithme de Rabin-Karp Algorithme d'Aho-Corasick
Alignement de chaînes	Algorithme de Needleman-Wunsch Algorithme de Smith-Waterman Transformée de Burrows-Wheeler
Mesure de similarité	Distance de Jaro-Winkler Distance de Levenshtein Distance de Hamming
Arbre des suffixes	Algorithmes de Weiner et de McCreight Algorithme d'Ukkonen Tableau des suffixes Tableau de Lyndon
Comparaisons	Plus longue sous-séquence commune Plus longue sous-chaîne commune Plus courte super-séquence commune