Levenshtein-Distanz Rechner

Berechne die Levenshtein-Distanz (Edit Distance) zwischen Strings, Ähnlichkeit in %, Damerau mit Transposition und Suche des ähnlichsten Wortes in Liste.

Berechnungsparameter
Scegli il tipo di calcolo.
Prima stringa da confrontare.
Seconda stringa. Per 'closest_word' è la parola di riferimento.
Per modo closest_word: dizionario in cui cercare la parola più vicina a s1.
War dieser Rechner nützlich?

Die Levenshtein-Distanz

Die Levenshtein-Distanz, 1965 vom russischen Mathematiker Wladimir Lewenstein eingeführt, zählt die minimale Anzahl elementarer Operationen (Einfügen, Löschen, Ersetzen), um eine Zeichenkette in eine andere umzuwandeln.

Elementare Operationen

  1. Einfügen.
  2. Löschen.
  3. Ersetzen.

Distanz zwischen „kitten" und „sitting" = 3.

Die vier Modi

  1. Klassische Distanz mit DP-Matrix.
  2. Normalisierte Ähnlichkeit (0-100 %).
  3. Damerau-Levenshtein mit Transposition.
  4. Ähnlichstes Wort in Liste.

Wagner-Fischer-Algorithmus

d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1]+c), c = 0 bei Gleichheit, sonst 1. Komplexität O(m·n).

Damerau-Levenshtein

Ergänzt um Transposition: d[i][j] ≤ d[i-2][j-2]+1 falls a[i-1]=b[j-2] und a[i-2]=b[j-1]. „teh" → „the" = 1 bei Damerau.

Varianten

  • Hamming: nur Ersetzungen bei gleicher Länge.
  • Jaro / Jaro-Winkler: bevorzugt gemeinsame Präfixe.
  • N-Gramm / Jaccard: Mengen von k-Teilzeichenketten.
  • Needleman-Wunsch: gewichtete Verallgemeinerung (Bioinformatik).
  • Smith-Waterman: lokale Ausrichtung.

Anwendungen

  • Rechtschreibprüfer: Aspell, Hunspell.
  • Fuzzy-Suche: Elasticsearch, Solr.
  • Diff/Merge: Unix, Git (Myers 1986).
  • DNA: BLAST, FASTA.
  • Deduplizierung von Datensätzen.
  • OCR-Nachbearbeitung.

Optimierungen

  • Speicher O(min(m,n)): zwei 1D-Arrays genügen (aktuelle und vorherige Zeile).
  • Ukkonen-Cutoff: bei Distanz ≤ k beschränkt man sich auf ein Diagonalband der Breite 2k+1, Komplexität O(k·max(m,n)).
  • Bit-Parallel Myers 1999: mit SIMD und Bitweise-Operationen ~60× schneller bei kurzen Strings (bis 64 Zeichen).
  • Vorfilterung mit q-Grammen vor exakter Berechnung: verwirft entfernte Kandidaten per Hash.

Schritt-für-Schritt-Beispiel

Distanz zwischen „kitten" und „sitting" berechnen. Die 7×8-DP-Matrix ergibt d[6][7] = 3. Optimale Operationsfolge: k→s (Ersetzung), e→i (Ersetzung), „g" anhängen (Einfügung). Prüfung: 3 minimale Operationen. Ähnlichkeit = 1 − 3/7 = 0,571 = 57,1 %.

Wo die Editierdistanz die alltagliche Software antreibt

Die Levenshtein-Distanz ist eine jener diskreten Ideen, die unsichtbar in Werkzeugen wirken, die wir taglich nutzen. Die Rechtschreibprufung verwendet sie, um das korrekte Wort vorzuschlagen, das dem falsch geschriebenen am nachsten kommt, und die Autokorrektur des Telefons nutzt sie, um aus fehlerhaften Tastenanschlagen deine Absicht zu erraten. Die unscharfe Suche, die Ergebnisse auch bei Tippfehlern findet, stutzt sich auf einen aus dieser Distanz abgeleiteten Ahnlichkeitsschwellenwert, und Systeme zur optischen Zeichenerkennung nutzen sie, um zweifelhafte Lesungen durch Vergleich mit einem Worterbuch zu korrigieren.

Ihre Reichweite geht weit uber gewohnlichen Text hinaus. In der Bioinformatik richten Varianten derselben Idee DNA- und Proteinsequenzen aus, um ihre evolutionare Verwandtschaft zu messen, ein Problem im Herzen der modernen Genomik. Plagiatserkenner vergleichen Dokumente, Datensatzverknupfungssysteme fuhren Datenbanken zusammen, indem sie fast identische, unterschiedlich geschriebene Eintrage erkennen, und Versionsverwaltungswerkzeuge berechnen die Unterschiede zwischen Dateien. In all diesen Fallen bietet das Zahlen der minimalen Anzahl von Editierungen ein robustes und universelles Mass dafur, wie sehr sich zwei Zeichenketten ahneln.

Die Idee der dynamischen Programmierung hinter dem Algorithmus

Die effiziente Berechnung der Levenshtein-Distanz ist ein klassisches Beispiel dynamischer Programmierung. Statt alle moglichen Editierfolgen auszuprobieren, die astronomisch zahlreich waren, baut man eine Tabelle auf, in der jede Zelle die Distanz zwischen zwei Prafixen der Zeichenketten speichert. Der Wert jeder Zelle ergibt sich aus ihren drei bereits berechneten Nachbarn, indem man das Minimum aus Einfugen, Loschen oder Ersetzen eines Zeichens wahlt. Diese Eigenschaft der optimalen Teilstruktur erlaubt, das Problem in einer Zeit proportional zum Produkt der Langen zu losen.

Ist die Tabelle gefullt, enthalt die untere rechte Ecke die gesuchte Distanz, und durch Ruckwartsdurchlaufen der Matrix gewinnt man die konkrete Folge von Operationen, die sie realisiert. Dieselbe Struktur verbindet sich mit dem Problem der langsten gemeinsamen Teilfolge und mit der Sequenzausrichtung nach Needleman-Wunsch, von der die Editierdistanz eine Variante ist. Der Rechner zeigt die vollstandige Matrix fur kurze Zeichenketten, sodass man visuell verfolgen kann, wie sich jeder Wert von der oberen linken Ecke bis zur endgultigen Losung ausbreitet.

Aktualisiert im Juli 2026

Häufig gestellte Fragen

Was ist die Levenshtein-Distanz?

Es ist die minimale Anzahl elementarer Operationen (Einfugen, Loschen oder Ersetzen eines Zeichens), die notig sind, um eine Zeichenkette in eine andere zu verwandeln. 1965 vom russischen Mathematiker Vladimir Levenshtein eingefuhrt, ist sie das meistgenutzte Mass, um zu quantifizieren, wie sehr sich zwei Worter oder Texte unterscheiden. Fur "kitten" und "sitting" betragt sie 3.

Welche Modi bietet der Rechner?

Vier: die klassische Distanz mit der Matrix der dynamischen Programmierung, die normierte Ahnlichkeit von 0 bis 100%, die Damerau-Levenshtein-Variante, die die Vertauschung benachbarter Zeichen hinzufugt, und die Suche nach dem nachstgelegenen Wort in einer Liste. Jeder Modus zeigt die optimale Operationsfolge.

Wie berechnet man die Distanz?

Mit dynamischer Programmierung: man baut eine Matrix, in der d[i][j] die Distanz zwischen den ersten i Zeichen der ersten Zeichenkette und den ersten j der zweiten ist. Jede Zelle ist das Minimum aus d[i-1][j]+1, d[i][j-1]+1 und d[i-1][j-1]+Kosten, wobei die Kosten 0 sind, wenn die Zeichen ubereinstimmen, sonst 1.

Was ist die normierte Ahnlichkeit?

Es ist die Distanz als Prozentsatz der maximalen Lange der beiden Zeichenketten: Ahnlichkeit = (1 - Distanz/max(|s1|, |s2|)) x 100%. Sie betragt 100% fur identische Zeichenketten und fallt gegen 0 fur sehr verschiedene. Beim Fuzzy-Matching wird oft ein Schwellenwert von 80% verwendet, um zwei Zeichenketten als ahnlich zu betrachten.

Was ist die Damerau-Levenshtein-Distanz?

Es ist eine Variante, die eine vierte Operation hinzufugt: die Vertauschung zweier benachbarter Zeichen mit Kosten 1. Sie erfasst Tippfehler wie das Vertauschen benachbarter Buchstaben ("teh" statt "the") besser. Der Rechner zeigt zum Vergleich sowohl die Levenshtein- als auch die Damerau-Distanz.

Wie hoch ist die Komplexitat des Algorithmus?

Die Berechnung mit der Matrix benotigt Zeit und Speicher proportional zum Produkt der Langen der beiden Zeichenketten, also O(m x n). Es gibt Optimierungen: die Diagonalband-Version fur kleine Distanzen, der bit-parallele Algorithmus von Myers und die q-Gramm-Filterung, die Vergleiche uber grosse Worterbucher stark beschleunigen.

Wo wird die Levenshtein-Distanz verwendet?

In Rechtschreibprufungen und der Autokorrektur, in der unscharfen Suche, in der optischen Zeichenerkennung, in der Bioinformatik zum Ausrichten von DNA- und Proteinsequenzen, in der Plagiatserkennung, in der Datenbank-Deduplizierung und in Dateivergleichswerkzeugen. Sie wird uberall genutzt, wo die Ahnlichkeit zwischen Texten gemessen werden muss.

Wie findet man das ahnlichste Wort?

Man berechnet die Levenshtein-Distanz zwischen der gegebenen Zeichenkette und jedem Wort einer Kandidatenliste und wahlt das mit der kleinsten Distanz. Es ist der Mechanismus der Vorschlage von Rechtschreibprufungen und der Autovervollstandigung: unter allen Worterbuchwortern wird das vorgeschlagen, das die wenigsten Anderungen erfordert, um dem getippten Text zu entsprechen.

Kommentare (0)

Noch keine Kommentare. Sei der Erste!