Die längste gemeinsame Teilfolge und Diff
Kurz gesagt: Die längste gemeinsame Teilfolge (LCS) zweier Folgen wird mit einer Tabelle in O(n · m) gefunden und steckt unter Diff: Die Zeilen außerhalb von ihr sind die gelöschten und die hinzugefügten.
Problem
Was hat sich in den Einstellungen geändert?
Der Shop hält seine Einstellungen in einer Textdatei. Ein Kunde schreibt, dass die Lieferung plötzlich günstiger ist. Das System hat zwei Versionen der Datei, die von gestern und die von heute, und du musst genau sehen, was sich geändert hat, Zeile für Zeile, so wie es git diff zeigt.
Die erste Idee ist, Zeile 1 mit Zeile 1 zu vergleichen, Zeile 2 mit Zeile 2 und so weiter:
was = [ "shop=Bookstore", "currency=EUR", "shipping=4.99", "free_from=50", "pay=card", "pay=cash",]now = [ "shop=Bookstore", "currency=EUR", "vat=20", "shipping=3.99", "free_from=50", "pay=card",]for old, new in zip(was, now): if old == new: print(" " + old) else: print("- " + old) print("+ " + new) shop=Bookstore currency=EUR- shipping=4.99+ vat=20- free_from=50+ shipping=3.99- pay=card+ free_from=50- pay=cash+ pay=cardDas Programm sagt, vier von sechs Zeilen haben sich geändert. In Wirklichkeit hat jemand eine Zeile hinzugefügt (vat=20), eine geändert (den Lieferpreis) und eine entfernt (Barzahlung). Die hinzugefügte Zeile hat jede Zeile danach um einen Platz nach unten geschoben, und der Vergleich nach Nummer erkennt sie nicht mehr.
Die Idee
Die Zeilen, die geblieben sind
Dreh die Frage um. Statt zu suchen, was sich geändert hat, finde, was geblieben ist: möglichst viele Zeilen, die in beiden Versionen stehen, in derselben Reihenfolge. Alles andere wurde entfernt („-“) oder hinzugefügt („+“).
Diese Zeilen stehen nicht unbedingt nebeneinander: Die neuen und entfernten stehen dazwischen. Deshalb heißt es Teilfolge: Sie behält die Reihenfolge, darf aber überspringen. Die größte Zahl solcher Zeilen ist die längste gemeinsame Teilfolge (LCS).
Sie zu finden, indem man jede Teilfolge ausprobiert, ist hoffnungslos: Eine Datei mit n Zeilen hat 2ⁿ Teilfolgen. Aber die Aufgabe hat, was du beim Wechselgeld und beim Rucksack gesehen hast: Die Antwort für zwei Dateien wird aus den Antworten für kürzere Teile von ihnen gebaut. Sei dp[i][j] die Länge der LCS der ersten i Zeilen der alten Version und der ersten j der neuen. Dann gilt:
- sind Zeile i und Zeile j gleich, ist sie gemeinsam: dp[i][j] = dp[i − 1][j − 1] + 1;
- sind sie verschieden, ist mindestens eine der beiden nicht in der gemeinsamen Teilfolge. Lass die eine oder die andere weg und nimm das Bessere: dp[i][j] = max(dp[i − 1][j], dp[i][j − 1]);
- Zeile 0 und Spalte 0 sind Nullen: Eine leere Datei hat mit nichts etwas gemeinsam.
Sieh es dir an
Die Tabelle
def lcs_table(was, now): n, m = len(was), len(now) dp = [[0] * (m + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(1, m + 1): if was[i - 1] == now[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: up = dp[i - 1][j] left = dp[i][j - 1] dp[i][j] = max(up, left) return dpfor _ in range(n + 1) erzeugt. Die Versuchung [[0] * (m + 1)] * (n + 1) ist eine Falle: Das sind n + 1 Verweise auf ein und dieselbe Zeile, und ein Schreibzugriff auf dp[1] ändert alle Zeilen auf einmal.Die zwei Versionen der Datei und die Tabelle, die das Programm für sie berechnet:
was = [ "shop=Bookstore", "currency=EUR", "shipping=4.99", "free_from=50", "pay=card", "pay=cash",]now = [ "shop=Bookstore", "currency=EUR", "vat=20", "shipping=3.99", "free_from=50", "pay=card",]for row in lcs_table(was, now): print(*row)0 0 0 0 0 0 00 1 1 1 1 1 10 1 2 2 2 2 20 1 2 2 2 2 20 1 2 2 2 3 30 1 2 2 2 3 40 1 2 2 2 3 4def diff(was, now): dp = lcs_table(was, now) result = [] i, j = len(was), len(now) while i > 0 and j > 0: if was[i - 1] == now[j - 1]: result.append(" " + was[i - 1]) i -= 1 j -= 1 elif dp[i][j - 1] >= dp[i - 1][j]: result.append("+ " + now[j - 1]) j -= 1 else: result.append("- " + was[i - 1]) i -= 1 while j > 0: result.append("+ " + now[j - 1]) j -= 1 while i > 0: result.append("- " + was[i - 1]) i -= 1 result.reverse() return resultdef lcs_table(was, now): n, m = len(was), len(now) dp = [[0] * (m + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(1, m + 1): if was[i - 1] == now[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: up = dp[i - 1][j] left = dp[i][j - 1] dp[i][j] = max(up, left) return dpSchritt für Schritt, in Worten
- Alte Version links (was), neue oben (now). Zeile 0 und Spalte 0 sind Nullen: Eine leere Datei hat mit nichts Zeilen gemeinsam.
- Zeile 1: shop=Bookstore ist dasselbe wie die erste Zeile von now. Gleiche Zeilen: die Diagonale + 1. Die Zelle wird grün.
- Verschiedene Zeilen: das Größere aus der Zelle darüber und der Zelle links. Keine neue gemeinsame Zeile, nur das Beste bisher.
- currency=EUR stimmt auch überein: 1 + 1 = 2. shipping=4.99 in Zeile 3 stimmt mit nichts überein, also übernimmt die Zeile nur die Zweien.
- Weiter unten stimmen free_from=50 und pay=card überein, und die Zahlen wachsen auf 3 und 4.
- Die Ecke dp[6][6] = 4: Die zwei Versionen haben 4 Zeilen gemeinsam. Welche, sagt der Weg zurück.
- Der Weg zurück beginnt in der Ecke. pay=cash ≠ pay=card, oben ist 4 und links 3: nach oben. pay=cash wurde entfernt: „- pay=cash“.
- pay=card = pay=card: eine gemeinsame Zeile, entlang der Diagonale. Genauso für free_from=50.
- shipping=4.99 ≠ shipping=3.99, und die Zahlen oben und links sind gleich: nach links, „+ shipping=3.99“. Dann „+ vat=20“.
- Oben ist 2, links 1: nach oben, „- shipping=4.99“. Dann die zwei gemeinsamen Zeilen entlang der Diagonale, zurück zur 0 in der Ecke.
- Der Weg lief vom Ende zum Anfang, deshalb dreht result.reverse() die Zeilen um. Das Diff: vat=20 ist neu, shipping hat sich geändert, pay=cash ist weg.
Die Zahl in der Ecke unten rechts ist 4: Vier Zeilen sind geblieben. Welche, sagt der Weg zurück.
Probier es aus
Sag die Ausgabe voraus
Die Route des Kuriers am Dienstag und am Mittwoch. Wie viele Stopps stehen an beiden Tagen in derselben Reihenfolge?
def lcs_table(was, now): n, m = len(was), len(now) dp = [[0] * (m + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(1, m + 1): if was[i - 1] == now[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: up = dp[i - 1][j] left = dp[i][j - 1] dp[i][j] = max(up, left) return dp
tuesday = [ "Lager", "Uferstraße", "Zentrum", "Hügelviertel", "Altstadt",]wednesday = [ "Lager", "Zentrum", "Uferstraße", "Altstadt",]dp = lcs_table(tuesday, wednesday)print(dp[-1][-1])Die Idee
Der Weg zurück: Diff
Die Tabelle merkt sich, wie jede Zahl entstanden ist. Beginne in der Ecke dp[n][m] und geh zurück:
- die Zeilen sind gleich: eine gemeinsame Zeile, schreibe sie mit einem Leerzeichen und geh die Diagonale entlang;
- die Zelle links ist nicht kleiner als die darüber: Zeile j der neuen Version ist nicht in der gemeinsamen Teilfolge, schreibe sie mit „+“ und geh nach links;
- sonst ist Zeile i der alten Version nicht in der neuen: schreibe sie mit „-“ und geh nach oben.
Wenn du das Ende einer Version erreichst, steht von der anderen alles Übrige nur mit „+“ oder nur mit „-“. Der Weg geht von den letzten Zeilen zu den ersten, deshalb wird die Liste am Ende umgedreht.
def diff(was, now): dp = lcs_table(was, now) result = [] i, j = len(was), len(now) while i > 0 and j > 0: if was[i - 1] == now[j - 1]: result.append(" " + was[i - 1]) i -= 1 j -= 1 elif dp[i][j - 1] >= dp[i - 1][j]: result.append("+ " + now[j - 1]) j -= 1 else: result.append("- " + was[i - 1]) i -= 1 while j > 0: result.append("+ " + now[j - 1]) j -= 1 while i > 0: result.append("- " + was[i - 1]) i -= 1 result.reverse() return resultfor line in diff(was, now): print(line) shop=Bookstore currency=EUR- shipping=4.99+ vat=20+ shipping=3.99 free_from=50 pay=card- pay=cashJetzt zeigt sich die Wahrheit: vat=20 ist neu, shipping hat sich geändert (eine alte Zeile entfernt und eine neue hinzugefügt), pay=cash ist weg. Die Wahl „nach links bei gleichen Zahlen“ setzt „-“ an derselben Stelle vor „+“, wie git es tut.
Probier es aus
Finde den Fehler
Ein Kollege hat die Tabelle geschrieben. Das Programm führt dasselbe diff aus, aber mit seiner Tabelle:
def lcs_table(was, now): n, m = len(was), len(now) dp = [[0] * (m + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(1, m + 1): if was[i - 1] == now[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: up = dp[i - 1][j] left = dp[i][j - 1] dp[i][j] = max(up, left) + 1 return dpfor line in diff(was, now): print(line) shop=Bookstore- currency=EUR- shipping=4.99- free_from=50- pay=card- pay=cash+ currency=EUR+ vat=20+ shipping=3.99+ free_from=50+ pay=cardcurrency=EUR wird sowohl entfernt als auch hinzugefügt, obwohl niemand es angerührt hat. In welcher Zeile steckt der Fehler?
Wähle die Zeile mit dem Fehler.
Wenn die Zeilen verschieden sind, gibt es keine neue gemeinsame Zeile: Das Beste ist die größere der beiden Nachbarzellen, ohne +1. Mit +1 wächst jede Zelle in jedem Schritt, die Zahlen sagen nicht mehr, welche Zeilen gemeinsam sind, und der Weg zurück läuft in die falsche Richtung. Richtig ist dp[i][j] = max(up, left).
Die Idee
Was es kostet
Die Tabelle hat (n + 1) · (m + 1) Zellen, und jede braucht einen Vergleich zweier Zeilen. Die Zeit ist O(n · m), und der Speicher auch (siehe Speicherkomplexität). Lass beide Wege laufen: jede Teilfolge der alten Version, eine nach der anderen, und die Tabelle. Wir zählen die geprüften Teilfolgen und die Zellen der Tabelle. Beide Versionen haben n Zeilen:
- Jede Teilfolge
O(2ⁿ) - Die Tabelle dp[i][j]
O(n²)
| Algorithmus | n = 10 | n = 20 | n = 1.000 | n = 3.000 | n = 100.000 |
|---|---|---|---|---|---|
| Jede Teilfolge | 1.024 | 1.048.576 | ≈ 10³⁰¹ | ≈ 10⁹⁰³ | ≈ 10³⁰¹⁰² |
| Die Tabelle dp[i][j] | 100 | 400 | 1.000.000 | 9.000.000 | ≈ 10.000.000.000 |
def lcs_table(was, now): n, m = len(was), len(now) dp = [[0] * (m + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(1, m + 1): if was[i - 1] == now[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: up = dp[i - 1][j] left = dp[i][j - 1] dp[i][j] = max(up, left) return dpBei 20 Zeilen gibt es schon 1.048.576 Teilfolgen, und die Tabelle hat 400 Zellen. Bei 1000 Zeilen hat die Tabelle 1.000.000 Zellen, bei 3000 Zeilen 9.000.000. Eine Datei mit 100.000 Zeilen braucht aber 10.000.000.000 Zellen, und bei 4 Byte pro Zelle sind das 40 GB Speicher. Deshalb füllen echte Diff-Werkzeuge nicht die ganze Tabelle.
Genauer, für Neugierige
Der Algorithmus von Myers (Eugene Myers, 1986) findet dasselbe kürzeste Diff, geht aber von der Frage aus: „Wie wenige Zeilen muss ich entfernen und hinzufügen?“ Ist diese Zahl D, ist die Zeit O((n + m) · D). Zwei Versionen einer Datei unterscheiden sich meist in wenigen Zeilen, also ist D klein, und der Algorithmus ist fast linear. Er ist der Standard in git diff und im GNU-diff. Git hat auch andere: --patience und --histogram liefern lesbarere Diffs, wenn Codeblöcke verschoben werden, und --minimal bemüht sich stärker um das kürzeste.
Wenn du nur die Länge der LCS brauchst, reichen zwei Zeilen der Tabelle: Zeile i benutzt nur Zeile i − 1. Der Speicher wird O(m). Der Algorithmus von Hirschberg (1975) behält auch den Weg, mit O(n + m) Speicher, indem er die Aufgabe halbiert.
So ist es in den Sprachen:
- Python hat
difflibin der Standardbibliothek:difflib.unified_diff(was, now)gibt ein Diff wie git aus. Es sucht den längsten gemeinsamen Block aufeinanderfolgender Zeilen und wiederholt das links und rechts, deshalb ist sein Diff nicht immer das kürzeste; - Java und C# haben kein Diff in der Standardbibliothek. Man benutzt Bibliotheken: java-diff-utils in Java, DiffPlex in C#, beide mit dem Algorithmus von Myers;
- JavaScript hat auch keins. Das Paket
diffauf npm (jsdiff) benutzt Myers.
Die Idee
Dieselbe Tabelle, eine andere Frage: „Meintest du …“
Ein Kunde sucht nach „Lapop“ und findet nichts. Die Suche des Shops soll „Laptop“ vorschlagen: das Katalogwort, das dem Getippten am nächsten ist.
Die Nähe wird mit der Levenshtein-Distanz gemessen: wie wenige Buchstaben du einfügen, löschen oder ändern musst, um ein Wort in das andere zu verwandeln. „Lapop“ → „Laptop“ ist 1: Du fügst „t“ ein.
Die Tabelle ist dieselbe wie bei der LCS, nur die Frage ist eine andere. d[i][j] ist die Distanz zwischen den ersten i Buchstaben der Suchanfrage und den ersten j des Worts:
- Zeile 0 und Spalte 0 sind nicht mehr Nullen: d[i][0] = i (du löschst alle i Buchstaben), d[0][j] = j;
- sonst ist d[i][j] der kleinste von drei Schritten: löschen (d[i − 1][j] + 1), einfügen (d[i][j − 1] + 1) und ändern (d[i − 1][j − 1], plus 1, wenn die Buchstaben verschieden sind).
Das schreibst du in der Aufgabe.
Genauer, für Neugierige
Echte Suchmaschinen hören hier nicht auf. Sie zählen, wie oft jedes Wort gesucht wird („Laptop“ ist wahrscheinlicher als „Lampe“, auch bei gleicher Distanz), wie nah die Buchstaben auf der Tastatur beieinander liegen und ob zwei Buchstaben nur vertauscht sind. Vertauschte benachbarte Buchstaben sind der häufigste Tippfehler, und Levenshtein zählt sie als 2. Die Variante von Damerau zählt eine Vertauschung als 1.
LCS und Levenshtein sind verwandt: Erlaubst du nur Einfügen und Löschen, ohne Ändern, ist die Distanz n + m − 2 · LCS. Jeder Buchstabe außerhalb der gemeinsamen Teilfolge wird aus einem Wort gelöscht oder in das andere eingefügt.
Übung
„Meintest du …“
Löse die Aufgabe in deinem Editor.
Vorschläge. Der Katalog ist „Laptop“, „Lampe“, „Tablet“, „Telefon“, „Kopfhörer“ und „Monitor“, und Kunden haben nach „Lapop“, „Telefno“, „Tabelt“ und „Monitro“ gesucht. Schreibe distance(query, word) mit der Levenshtein-Tabelle und gib für jede Suchanfrage das nächste Katalogwort und die Distanz aus (bei Gleichstand das erste im Katalog):
Lapop → Laptop (1)Telefno → Telefon (2)Tabelt → Tablet (2)Monitro → Monitor (2)Weitere Aufgaben
- Eine Vertauschung für 1. Füge den Schritt „zwei benachbarte Buchstaben vertauschen“ hinzu (Damerau-Levenshtein). Was wird aus „Tabelt“ → „Tablet“?
- Nur wenn nah. Schlage nichts vor, wenn das nächste Wort weiter als ein Drittel der Länge der Suchanfrage entfernt ist.
- Ein Diff von Wörtern. Lass das
diffder Lektion nicht auf Zeilen laufen, sondern auf den Wörtern zweier Produktbeschreibungen, an Leerzeichen getrennt.
Test