Längste gemeinsame Teilfolge (LCS)
Wenn Sie zwei Versionen einer Datei vergleichen, bilden die unveränderten Zeilen eine gemeinsame Teilfolge beider Versionen. Wer die längste findet, weiß genau, was hinzugefügt und was entfernt wurde. Dieselbe Idee richtet DNA-Stränge aneinander aus und schlägt Rechtschreibkorrekturen vor, und gelöst wird sie mit einer der elegantesten Tabellen der Informatik.
Das Problem
Eine Teilfolge eines Worts behält einige seiner Buchstaben in ihrer ursprünglichen Reihenfolge: ACE ist eine Teilfolge von ABCDE, EA aber nicht. Eine gemeinsame Teilfolge zweier Wörter ist eine Teilfolge von beiden, und die Aufgabe besteht darin, die längste zu finden. Ein Wort der Länge n hat 2ⁿ Teilfolgen, alle durchzuprobieren ist also schon bei wenigen Buchstaben aussichtslos.
Die Tabelle
Sei len[i][j] die Länge der längsten gemeinsamen Teilfolge der ersten i Buchstaben des einen Worts und der ersten j Buchstaben des anderen. Ein leeres Wort hat mit nichts etwas gemeinsam, daher sind die erste Zeile und Spalte 0. Ist Buchstabe i gleich Buchstabe j, gilt len[i][j] = len[i − 1][j − 1] + 1: Die Übereinstimmung verlängert, was davor kam. Andernfalls ist len[i][j] der größere Wert von len[i − 1][j] und len[i][j − 1]: Man lässt einen der beiden Buchstaben weg und behält das bessere Ergebnis.
Ein Beispiel
Vergleichen Sie ABCBDAB mit BDCABA. Der erste Buchstabe des zweiten Worts, B, stimmt mit dem B in Zeile 2 überein; das C in der dritten Spalte stimmt mit Zeile 3 überein, und so weiter, wobei jede Übereinstimmung eins zur Zelle links oben addiert. Die Zelle unten rechts endet bei 4. Das Zurücklesen von dort ergibt BCBA, aber BCAB und BDAB sind genauso lang: Eine längste gemeinsame Teilfolge muss nicht eindeutig sein.
Die Antwort zurücklesen
Beginnen Sie in der Zelle unten rechts. Stimmen die Buchstaben ihrer Zeile und Spalte überein, gehört dieser Buchstabe zur Antwort: Notieren Sie ihn und gehen Sie diagonal nach links oben. Andernfalls gehen Sie zum Nachbarn darüber oder links daneben, der den größeren Wert hat, denn von dort hat die Zelle ihren Wert. Halten Sie in der ersten Zeile oder Spalte an. Die notierten Buchstaben, in umgekehrter Reihenfolge, sind die Teilfolge.
Geschichte und Anwendungen
Das Tabellenverfahren wurde um 1970 von mehreren Personen unabhängig voneinander gefunden, darunter Robert Wagner und Michael Fischer, deren Arbeit von 1974 die eng verwandte Editierdistanz löste. 1975 zeigte Dan Hirschberg, wie man die Teilfolge mit weit weniger Speicher findet, und 1976 bauten James Hunt und Douglas McIlroy das Programm Unix diff auf längsten gemeinsamen Teilfolgen von Zeilen auf. Biologen nutzen dieselbe Idee, mit Bewertungen, um DNA- und Proteinsequenzen auszurichten.
Selbst ausprobieren
Öffnen Sie die App und drücken Sie Schritt. Die beiden verglichenen Buchstaben leuchten in den Überschriften auf; bei einer Übereinstimmung wird die blaue Zelle links oben gelesen, bei einem Unterschied die zwei blauen Zellen darüber und links daneben. Wenn die Tabelle voll ist, steigt der orangefarbene Pfad von der Ecke zurück, und die Buchstaben der Antwort erscheinen unter der Tabelle.
Häufig gestellte Fragen
Wie viel Zeit und Speicher braucht der LCS-Algorithmus?
O(m·n) Zeit für Wörter der Längen m und n. Die vollständige Tabelle braucht ebenfalls O(m·n) Speicher, um die Antwort zurückzulesen; Dan Hirschberg zeigte 1975, wie man die Teilfolge selbst mit nur O(min(m, n)) Speicher findet.
Wie nutzt diff die längste gemeinsame Teilfolge?
Es behandelt jede Zeile einer Datei als ein Symbol und findet eine längste gemeinsame Teilfolge der Zeilen beider Dateien. Zeilen in dieser Teilfolge sind unverändert; die übrigen Zeilen der alten Datei wurden gelöscht, und die übrigen Zeilen der neuen Datei wurden hinzugefügt.
Und bei drei oder mehr Wörtern?
Die Tabelle bekommt eine Dimension pro Wort, drei Wörter der Länge n brauchen also n³ Zellen. Für eine beliebige Anzahl von Wörtern ist das Problem NP-schwer.
Wie hängt die LCS mit der Editierdistanz zusammen?
Sind nur Einfügen und Löschen erlaubt, ist die Editierdistanz zweier Wörter ihre Gesamtlänge minus die doppelte Länge ihrer längsten gemeinsamen Teilfolge. Erlaubt man zusätzlich das Ersetzen, erhält man die Levenshtein-Distanz, die mit einer sehr ähnlichen Tabelle berechnet wird.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Längste gemeinsame Teilfolge ausprobieren