Die längste gemeinsame Teilfolge
Lesen anpassen
Nach dieser Lektion kannst du
Eine Teilfolge von einem zusammenhängenden Teilwort unterscheiden.
Eine zweidimensionale Tabelle aus Präfixen zweier Zeichenketten aufbauen.
Die Länge und eine konkrete längste gemeinsame Teilfolge bestimmen.
Vorausgesetzt: Memoisierung und Tabellen: zwei Wege zur gleichen Lösung
Zwei Versionen eines Textes können dieselben Zeichen enthalten, obwohl dazwischen etwas eingefügt oder entfernt wurde. Um gemeinsame Struktur zu finden, reicht es deshalb nicht, nur zusammenhängende Textstücke zu vergleichen.
Nimm die Zeichenketten „ABC“ und „BAC“. Die Zeichen A und C stehen in beiden in dieser Reihenfolge, obwohl sie in der zweiten Zeichenkette nicht direkt nebeneinanderstehen. Auch B und C bilden eine solche gemeinsame Folge.
Wir suchen eine gemeinsame Folge mit möglichst vielen Zeichen. Dazu betrachten wir wieder kleinere Fragen: Was ist die beste gemeinsame Folge, wenn wir von jeder Zeichenkette nur einen Anfang betrachten?
Teilfolge und gemeinsames Optimum
Eine Zeichenkette ist eine endliche Folge von Zeichen. Eine Teilfolge entsteht, indem wir beliebige Zeichen weglassen, ohne die Reihenfolge der übrigen Zeichen zu ändern. Auch gar kein Zeichen oder kein einziges Zeichen wegzulassen ist erlaubt.
„AC“ ist eine Teilfolge von „ABC“. „CA“ ist dort keine Teilfolge, weil das C hinter dem A steht. Ein Teilwort wäre dagegen ein zusammenhängender Ausschnitt. „AC“ ist kein Teilwort von „ABC“.
Die längste gemeinsame Teilfolge, auf Englisch Longest Common Subsequence oder kurz LCS, hat unter allen Teilfolgen beider Zeichenketten die größte Länge. Mehrere verschiedene Teilfolgen können diese Länge erreichen.
Zustände aus zwei Präfixen
Wir nennen die Zeichenketten und und ihre Längen und . Ein Präfix ist ein Anfang einer Zeichenkette. Das Präfix der Länge null ist die leere Zeichenkette.
Der Wert ist die Länge einer längsten gemeinsamen Teilfolge der ersten Zeichen von und der ersten Zeichen von . Es gilt und . Die Zeichen selbst nummerieren wir ab 1, also etwa für das letzte Zeichen des ersten Präfixes.
Ist eines der Präfixe leer, kann die gemeinsame Teilfolge kein Zeichen enthalten. Daher gilt und . Die gesuchte Gesamtlänge ist .
Der Vergleich der letzten Zeichen
Wenn die beiden letzten Zeichen gleich sind, können wir ein gemeinsames Zeichen an eine beste Teilfolge der beiden um eins verkürzten Präfixe anhängen.
Sind sie verschieden, können sie nicht beide das letzte gemeinsame Zeichen liefern. Dann lassen wir das letzte Zeichen von oder das letzte Zeichen von weg und wählen das bessere Ergebnis.
Sind die letzten Zeichen verschieden, kann eine gemeinsame Teilfolge nicht beide letzten Positionen verwenden: Diese müssten sonst als letzte Zeichen der Teilfolge gleich sein. Mindestens eine letzte Position bleibt also ungenutzt. Die beiden verkürzten Teilprobleme erfassen damit alle Möglichkeiten.
Sind die letzten Zeichen gleich, betrachten wir eine optimale gemeinsame Teilfolge. Verwendet sie eine der letzten Positionen, lässt sich ihre letzte passende Position in der anderen Zeichenkette nötigenfalls nach hinten auf das gleiche letzte Zeichen verschieben. Verwendet sie keine, könnte man das gemeinsame letzte Zeichen anhängen; dann wäre sie nicht optimal. Es gibt daher eine optimale Folge, die beide letzten Positionen gemeinsam verwendet. Nach Entfernen dieses Zeichens bleibt eine optimale Folge der verkürzten Präfixe; eine bessere würde auch die ursprüngliche Folge verbessern.
Die Tabelle für „ABC“ und „BAC“
Die Tabelle für „ABC“ und „BAC“
Die Zeilen stehen für Präfixe von „ABC“, die Spalten für Präfixe von „BAC“. „Leer“ bezeichnet jeweils Länge null. Wir füllen die Tabelle zeilenweise von links nach rechts.
| Präfix von A / Präfix von B | Leer | B | BA | BAC |
|---|---|---|---|---|
| Leer | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 1 | 1 |
| AB | 0 | 1 | 1 | 1 |
| ABC | 0 | 1 | 1 | 2 |
In der Zeile „A“, Spalte „BA“ sind die letzten Zeichen beide A. Wir lesen diagonal links oben den Wert 0 und addieren 1.
In der Zeile „AB“, Spalte „BA“ vergleichen wir B mit A. Die Zeichen unterscheiden sich. Oberhalb und links steht jeweils 1; das Maximum bleibt 1. Beim letzten Feld passen C und C zusammen. Diagonal steht 1, also erhalten wir .
Für jede Zelle werden nur die linke Nachbarzelle, die obere Nachbarzelle oder die diagonal links oben liegende Zelle benötigt. Bei der gewählten Rechenreihenfolge sind alle diese Werte bereits bekannt.
Eine gemeinsame Teilfolge zurückverfolgen
Eine gemeinsame Teilfolge zurückverfolgen
Wir beginnen rechts unten. Weil die letzten Zeichen C und C gleich sind, notieren wir C und gehen diagonal zur Zelle für „AB“ und „BA“.
Dort sind B und A verschieden. Beide Nachbarzellen, oben und links, haben den Wert 1. Wir wählen die obere Zelle, also die Frage für „A“ und „BA“. Jetzt passen A und A zusammen: Wir notieren A und gehen diagonal.
Die Rückverfolgung endet, sobald ein Präfix leer ist. Wir haben die Zeichen von hinten nach vorne gesammelt: erst C, dann A. Umgedreht ergibt das „AC“. Wenn wir bei der Gleichheit der Nachbarwerte anders abbiegen, können wir stattdessen „BC“ erhalten. Beide Lösungen haben Länge 2.
Die Länge ist eindeutig, eine konkrete optimale Teilfolge muss es nicht sein. Die Rückverfolgung trifft bei gleichen Werten eine Wahl, ohne dadurch den optimalen Wert zu verlieren.
Bei ungleichen Zeichen nicht alles verwerfen
Bei ungleichen Zeichen nicht alles verwerfen
Beim Problem der längsten gemeinsamen Teilfolge darf ein ungleiches Zeichen übersprungen werden. Eine Zelle bei ungleichen Zeichen auf null zu setzen würde vorher gefundene Gemeinsamkeiten verlieren.
Wir übernehmen das Maximum aus oben und links. Das Zurücksetzen auf null gehört zu einer anderen Aufgabe: der Suche nach einem längsten gemeinsamen zusammenhängenden Teilwort. Dort darf eine Lücke den zusammenhängenden Abschnitt tatsächlich nicht fortsetzen.
Zusammenfassung
Eine Teilfolge darf Lücken haben, erhält aber immer die Reihenfolge der Zeichen.
beschreibt die beste gemeinsame Länge zweier Präfixe.
Gleiche letzte Zeichen liefern den Diagonalwert plus 1.
Bei verschiedenen letzten Zeichen wählen wir das Maximum aus oben und links.
Die Rückverfolgung liefert eine konkrete Lösung; bei Gleichstand können mehrere optimale Lösungen existieren.
Übungen
Welche Zeichenkette ist eine Teilfolge von „ABCD“?
Welche Länge hat eine längste gemeinsame Teilfolge von „ABCD“ und „ACBD“?
Eine Zeichenkette ist leer, die andere hat fünf Zeichen. Welche Länge hat ihre längste gemeinsame Teilfolge?
Die letzten Zeichen zweier Präfixe sind verschieden. Über der aktuellen Zelle steht 4, links steht 3. Welchen Wert trägst du ein und warum?