Plus courte super-séquence commune
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
modifierPour 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
modifierLe 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- 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).
- 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).
- 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- (en) Michael R. Garey et David S. Johnson, Computers and intractability : a guide to the theory of NP-completeness, New York, W.H. Freeman, , 338 p. (ISBN 0-7167-1045-5, zbMATH 0411.68039), p. 228, section A4.2, problème SR8
- (en) Wojciech Szpankowski, Average case analysis of algorithms on sequences, Chichester, Wiley, coll. « Wiley-Interscience Series in Discrete Mathematics and Optimization », , 551 p. (ISBN 0-471-24063-X, zbMATH 0968.68205)
- (en) Dan Gusfield, Algorithms on Strings, Trees and Sequences : Computer Science and Computational Biology, Cambridge/New York/Melbourne, Cambridge University Press, , 534 p. (ISBN 0-521-58519-8, lire en ligne)
