Lektion 5.4

Die längste gemeinsame Teilfolge

20 min Lesezeit
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?

Definition

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.

Definition

Zustände aus zwei Präfixen

Wir nennen die Zeichenketten AA und BB und ihre Längen mm und nn. Ein Präfix ist ein Anfang einer Zeichenkette. Das Präfix der Länge null ist die leere Zeichenkette.

Der Wert L(i,j)L(i,j) ist die Länge einer längsten gemeinsamen Teilfolge der ersten ii Zeichen von AA und der ersten jj Zeichen von BB. Es gilt 0≤i≤m0\le i\le m und 0≤j≤n0\le j\le n. Die Zeichen selbst nummerieren wir ab 1, also etwa AiA_i für das letzte Zeichen des ersten Präfixes.

Ist eines der Präfixe leer, kann die gemeinsame Teilfolge kein Zeichen enthalten. Daher gilt L(0,j)=0L(0,j)=0 und L(i,0)=0L(i,0)=0. Die gesuchte Gesamtlänge ist L(m,n)L(m,n).

Satz

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 AA oder das letzte Zeichen von BB weg und wählen das bessere Ergebnis.

L(i,j)={L(i−1,j−1)+1,Ai=Bj,max⁡{L(i−1,j),L(i,j−1)},Ai≠Bj.L(i,j)=\begin{cases}L(i-1,j-1)+1,&A_i=B_j,\\\max\{L(i-1,j),L(i,j-1)\},&A_i\ne B_j.\end{cases}
Beispiel

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 BLeerBBABAC
Leer0000
A0011
AB0111
ABC0112

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 L(3,3)=1+1=2L(3,3)=1+1=2.

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.

Beispiel

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.

Häufige Fehler

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.

Richtig ist

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.

  • L(i,j)L(i,j) 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

Aufgabe 1Multiple Choice

Welche Zeichenkette ist eine Teilfolge von „ABCD“?

Aufgabe 2Numerisch

Welche Länge hat eine längste gemeinsame Teilfolge von „ABCD“ und „ACBD“?

Aufgabe 3Numerisch

Eine Zeichenkette ist leer, die andere hat fünf Zeichen. Welche Länge hat ihre längste gemeinsame Teilfolge?

Aufgabe 4Freitext

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?