Kürzeste gemeinsame Superzeichenfolge: Finde die kürzeste Zeichenfolge, die alle angegebenen Zeichenfolgenfragmente enthält

12

Bei einigen Fragmenten würde ich gerne die kürzestmögliche einzelne Zeichenfolge ("Ausgabezeichenfolge") finden, die alle Fragmente enthält. Fragmente können sich in der Ausgabezeichenfolge überlappen.

Beispiel:

Für die Saitenfragmente:

BCDA
AGF
ABC

Die folgende Ausgabezeichenfolge enthält alle Fragmente und wurde durch naives Anhängen erstellt:

BCDAAGFABC

Diese Ausgabezeichenfolge ist jedoch besser (kürzer), da sie Überlappungen verwendet:

ABCDAGF
^
ABC
 ^
 BCDA
    ^ 
    AGF

Ich suche nach Algorithmen für dieses Problem. Es ist nicht unbedingt wichtig, den kürzesten Ausgabestring zu finden, aber je kürzer, desto besser. Ich suche einen Algorithmus, der besser ist als der offensichtlich naive, der versucht, alle Permutationen der Eingabefragmente anzufügen und Überlappungen zu entfernen (die NP-vollständig zu sein scheinen).

Ich habe angefangen, an einer Lösung zu arbeiten, die sich als sehr interessant herausstellt. Ich würde gerne sehen, was sich andere Leute einfallen lassen. Ich werde diese Frage in Kürze um meine in Bearbeitung befindlichen Arbeiten ergänzen.

Occulus
quelle
3
Das Problem scheint NP-vollständig zu sein. In diesem Fall können Sie keinen Polynomalgorithmus zur Bestimmung der kürzesten Zeichenfolge finden, es kann jedoch Polynomalgorithmen geben, die ungefähre (nicht die kürzest mögliche) Lösungen liefern.
SuperM
3
Dieser Blog-Beitrag zu NP-Complete ist nett: codinghorror.com/blog/2008/11/…
occulus
Das Blog ist wirklich schön, ich habe es die ganze Zeit gelesen)))
superM
@superM das ist ähnlich genug wie bei einem Handelsreisenden (jede Saite ist eine Stadt und kostet zwischen den Städten = einige Zahlenüberschneidungen)
Ratschenfreak
@ratchet Freak, es ist _ Sie könnten kleine Kosten zwischen Städten angeben, wenn sie häufigere Buchstaben haben, und die größten Kosten, wenn sie überhaupt keinen gemeinsamen Buchstaben haben
superM

Antworten:

14

Was Sie fragen, ist das Shortest Common Superstring-Problem, für das es keinen Algorithmus gibt, der für alle Fälle funktioniert. Es ist jedoch ein häufiges Problem (bei der Komprimierung und DNA-Sequenzierung) und es sind mehrere Approximationsalgorithmen bekannt.

"Gierige" Algorithmen gelten allgemein als die effektivsten (da sie den schlechtesten und schlechtesten Fall haben).

Lesen Sie den Artikel Approximationsalgorithmen für das kürzeste häufig auftretende Superstring-Problem von Jonathan Turner, um weitere Informationen zu erhalten.

pdr
quelle
Hmm, beachte, dass der erste Link in meinem Kommentar direkt oben die Supersequenzen und nicht die Superstrings anspricht! Eine Supersequenz scheint nicht zu erfordern, dass alle Zeichen in einer Sequenz zusammenhängend sind.
Occulus
Ihr Link ist tot.
Majid