Gefüllte Zellen
Editierdistanz
Behaltene Buchstaben

  • Wird gefüllt
  • Wird gelesen
  • Ergebnis

Mehr über die Editierdistanz

Editierdistanz (Levenshtein-Distanz)

Wie viele Änderungen einzelner Buchstaben machen aus kitten das Wort sitting? Drei: k durch s ersetzen, e durch i ersetzen und ein g anhängen. Diese Zahl ist die Editierdistanz. Mit ihr ordnen Rechtschreibprüfungen ihre Vorschläge, und Biologen vergleichen damit Gene. Geben Sie zwei Wörter ein und sehen Sie zu, wie eine Tabelle sie bestimmt. 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 links an der Seite der Tabelle, das zweite oben. Jede Zelle enthält die kleinste Zahl von Änderungen, die die Buchstaben bis zu ihrer Zeile in die Buchstaben bis zu ihrer Spalte verwandeln. Am Ende werden die Änderungen 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 links an der Seite der Tabelle, das zweite 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 den günstigsten ihrer drei Nachbarn nimmt, und verfolgen Sie dann, wie die Änderungen in Orange zurückgelesen werden.

So funktioniert die Tabelle

Eine Zelle enthält die kleinste Zahl von Änderungen, die die Buchstaben des ersten Wortes bis zu ihrer Zeile in die Buchstaben des zweiten Wortes bis zu ihrer Spalte verwandeln. Die erste Zeile zählt Einfügungen, die das zweite Wort aus dem Nichts aufbauen, und die erste Spalte zählt Löschungen. Sind die beiden Buchstaben einer Zelle gleich, übernimmt sie den Wert der Zelle links oben: Es ist keine Änderung nötig. Andernfalls ist sie um eins größer als der kleinste von drei Nachbarn: links oben für Ersetzen, oben für Löschen und links für Einfügen.

Die Änderungen zurücklesen

Die Zelle unten rechts ist die Editierdistanz. Von dort aus ermittelt die App, von welchem Nachbarn der Wert der Zelle stammt, und geht zu ihm: diagonal für einen behaltenen oder ersetzten Buchstaben, nach oben für einen gelöschten, nach links für einen eingefügten. Von oben links gelesen ergeben die Schritte eine kürzeste Liste von Änderungen, die unter der Tabelle steht: Ein einfacher Buchstabe wird behalten, k→s ist ein Ersetzen, −e ein Löschen und +g ein Einfügen.

Häufig gestellte Fragen

Was ist die Levenshtein-Distanz?

Ein anderer Name für diese Editierdistanz: die kleinste Zahl von Einfügungen, Löschungen und Ersetzungen einzelner Buchstaben, die eine Zeichenkette in eine andere verwandeln. Sie ist nach Vladimir Levenshtein benannt, der sie 1965 beschrieb.

Wie groß ist die Editierdistanz zwischen kitten und sitting?

3: k durch s ersetzen, e durch i ersetzen und am Ende g einfügen. Die Tabelle zeigt, dass es keine kürzere Liste von Änderungen gibt.

Wie schnell ist der Algorithmus für die Editierdistanz?

Für Wörter der Längen m und n hat die Tabelle (m + 1)·(n + 1) Zellen, die jeweils in einem Schritt gefüllt werden, also braucht er O(m·n) Zeit. Wird nur die Distanz gebraucht, reichen zwei Zeilen der Tabelle.

Welche anderen Editierdistanzen gibt es?

Die Damerau–Levenshtein-Distanz zählt zusätzlich das Vertauschen zweier benachbarter Buchstaben als eine Änderung, was gut zu Tippfehlern passt. Die Hamming-Distanz erlaubt nur Ersetzungen und funktioniert für Zeichenketten gleicher Länge. Die LCS-Distanz erlaubt nur Einfügungen und Löschungen.

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