Gefüllte Zellen
Übereinstimmende Paare
Bisher längste

  • Wird gefüllt
  • Wird gelesen
  • Ergebnis

Mehr über die längste gemeinsame Teilfolge

Längste gemeinsame Teilfolge (LCS)

Welche Buchstaben haben zwei Wörter in derselben Reihenfolge gemeinsam? Die längste gemeinsame Teilfolge beantwortet das, und Diff-Werkzeuge, Rechtschreibprüfungen und DNA-Vergleiche bauen darauf auf. Geben Sie zwei Wörter ein, sehen Sie zu, wie sich eine Tabelle ihrer Buchstaben füllt, und verfolgen Sie die Antwort dann von der Ecke aus zurück. Drücken Sie Abspielen, um zuzusehen, wie sich die Tabelle füllt, oder Schritt und Zurück, um Schritt für Schritt vorzugehen. Ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen. Geben Sie zwei Wörter ein: Das erste steht senkrecht am Rand der Tabelle, das zweite waagerecht oben. Jede Zelle enthält die Länge der längsten gemeinsamen Teilfolge der Buchstaben bis zu ihrer Zeile und Spalte. Am Ende werden die Buchstaben von der Zelle unten rechts aus zurückgelesen. Neues Beispiel wählt ein anderes Wortpaar. Wenn das Feld ausgewählt ist, gehen die Pfeiltasten schrittweise vor, die Leertaste startet und pausiert, und Pos1 und Ende springen zum Anfang und zum Ende.

Wie es funktioniert

  1. Geben Sie zwei Wörter ein: Das erste steht senkrecht am Rand der Tabelle, das zweite waagerecht oben.
  2. Drücken Sie Abspielen, oder gehen Sie mit Schritt und Zurück Schritt für Schritt vor. Ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen.
  3. Sehen Sie zu, wie jede Zelle ihre zwei Buchstaben vergleicht, und folgen Sie dann dem orangefarbenen Pfad von der Ecke zurück, um die Antwort abzulesen.

So funktioniert die Tabelle

Eine Zelle enthält die Länge der längsten gemeinsamen Teilfolge aus den Buchstaben des ersten Worts bis zu ihrer Zeile und den Buchstaben des zweiten Worts bis zu ihrer Spalte. Die mit – markierte Zeile und Spalte stehen für ein leeres Wort, daher sind sie 0. Sind die beiden Buchstaben einer Zelle gleich, ist die Zelle um eins größer als die Zelle links oben. Sind sie verschieden, gehört einer der beiden Buchstaben nicht zur Antwort, also übernimmt die Zelle den größeren Wert der Zelle darüber und der Zelle links daneben.

Die Buchstaben zurücklesen

Die Zelle unten rechts ist die Länge der Antwort. Um die Buchstaben zu finden, beginnen Sie dort: Wo die beiden Buchstaben übereinstimmen, gehört dieser Buchstabe zur Teilfolge, und Sie gehen nach links oben; sonst gehen Sie zur größeren der Zellen darüber und links daneben. Die unterwegs gesammelten Buchstaben, rückwärts gelesen, ergeben eine längste gemeinsame Teilfolge. Es kann weitere derselben Länge geben; das Zurücklesen findet eine davon.

Häufig gestellte Fragen

Was ist der Unterschied zwischen einer Teilfolge und einer Teilzeichenkette?

Eine Teilzeichenkette ist eine Reihe direkt aufeinanderfolgender Buchstaben, wie ACE in RACER. Eine Teilfolge behält die Reihenfolge bei, darf aber Buchstaben auslassen; ACE ist also auch eine Teilfolge von ABCDE. Die längste gemeinsame Teilzeichenkette ist ein anderes Problem mit einer ähnlichen Tabelle.

Wie schnell ist der LCS-Algorithmus?

Für Wörter der Längen m und n hat die Tabelle m·n Zellen, die jeweils in einem Schritt gefüllt werden; der Aufwand ist also O(m·n). Für zwei Texte mit 10.000 Zeilen sind das 100 Millionen Zellen, deshalb verwenden Diff-Werkzeuge raffiniertere Verfahren, die auf derselben Idee beruhen.

Ist die längste gemeinsame Teilfolge eindeutig?

Nein. ABCBDAB und BDCABA haben drei verschiedene gemeinsame Teilfolgen der Länge 4: BCBA, BCAB und BDAB. Die Tabelle liefert die Länge; das Zurücklesen wählt eine davon.

Zeigt die LCS, wie ähnlich sich zwei Wörter sind?

Teilweise. Zwei Wörter der Längen m und n mit einer längsten gemeinsamen Teilfolge der Länge k lassen sich ineinander umwandeln, indem man m − k Buchstaben löscht und n − k einfügt. Die Editierdistanz, die auch das Ersetzen eines Buchstabens erlaubt, ist oft ein besseres Maß.

Wird irgendetwas übertragen?

Nein. Alles wird in Ihrem Browser berechnet, und Ihre letzten Einstellungen bleiben im lokalen Speicher dieses Browsers.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Zum Editor