Plus courte super-séquence commune

problème d'informatique théorique

En informatique théorique, et notamment en algorithmique des textes, le problème de la plus courte sur-séquence commune est un problème dual du problème de la plus longue sous-séquence commune. On trouve aussi l'anglicisme superséquence, mais la dénomination sur-séquence est plus logique en français par opposition à sous-séquence.

Définition

modifier

Étant donné deux suites de symboles X et Y, une suite U est une sur-séquence commune de X et Y si X et Y sont des sous-séquences (ou suites extraites) de U.

Une plus courte sur-séquence commune est une sur-séquence de longueur minimale. Cette longueur est majorée par la somme des longueurs des deux séquences. Par exemple, si X=ab et Y=ba, les deux séquences U=aba et V=bab sont des sur-séquences communes de X et Y de longueur minimale. En général, et comme le montre l'exemple, une plus courte sur-séquence commune n'est pas unique.

Algorithme

modifier

Pour deux séquences d'entrée données, une plus courte sur-séquence commune peut être calculée facilement à partir d'une plus longue sous-séquence commune. Par exemple, pour X=abcbdab et Y=bdcaba, la plus longue sous-séquence commune est Z=bcba. En insérant les symboles de X=abcbdab et Y=bdcaba qui ne figurent pas dans Z tout en préservant l’ordre, on obtient U=abdcabdab. L'algorithme montre aussi que la longueur d'une plus courte sur-séquence commune est égale à la somme des deux longueurs diminuée de la longueur de la plus courte sous-séquence commune : |U|=|X|+|Y|-|Z|.

Problèmes voisins

modifier

Le problème plus général de trouver une chaîne de symboles S de longueur minimale qui est une sur-chaîne d'un ensemble de chaînes de symboles S1,S2,...,Sl, c'est-à-dire telle que chaque Si est une sous-suite de S, est NP-complet[1]. Il existe des algorithmes d'approximation bon en moyenne[2],[3].

Notes et références

modifier
  1. Kari-Jouko Räihä et Esko Ukkonen, « The shortest common supersequence problem over binary alphabet is NP-complete », Theoretical Computer Science, vol. 16, no 2,‎ , p. 187-198 (DOI 10.1016/0304-3975(81)90075-x).
  2. Tao Jiang et Ming Li, « On the approximation of shortest common supersequences and longest common subsequences », SIAM Journal on Computing, vol. 24, no 5,‎ , p. 1122–1139 (DOI 10.1137/s009753979223842x).
  3. Marek Karpinski et Richard Schmied, « On improved inapproximability results for the shortest superstring and related problems », Proceedings of 19th CATS CRPIT, vol. 141,‎ , p. 27–36 (lire en ligne)

Bibliographie

modifier

Articles liés

modifier

Liens externes

modifier