|
Plus courte super-séquence communeEn 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É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. AlgorithmePour 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 voisinsLe 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
Bibliographie
Articles liés
Liens externes |
