Definition Was ist die Levenshtein-Distanz?

Anbieter zum Thema

Vogel IT-Medien GmbH

Fujitsu Technology Solutions GmbH

Fivetran Germany GmbH

Die Levenshtein-Distanz ist die minimale Anzahl der notwendigen Änderungen, um zwei Zeichenketten aneinander anzugleichen. Sie wird auch als Editierdistanz bezeichnet und ermöglicht computerbasiert zu berechnen, wie ähnlich zwei Zeichenketten sind. Der Algorithmus arbeitet mit einer Matrixberechnung. Typischerweise kommt die Editierdistanz für Anwendungen wie die Rechtschreibprüfung oder für Suchfunktionen zum Einsatz.

Die „Levenshtein-Distanz“, auch als Editierdistanz bezeichnet, ist nach dem russischen Wissenschaftler Wladimir Lewenstein (1935-2017) benannt. Er entwickelte sie 1965. Mithilfe der Levenshtein-Distanz lässt sich die minimale Anzahl notwendiger Änderungen bestimmen, um zwei vorgegebene Zeichenketten aneinander anzugleichen. Änderungen sind zum Beispiel das Ersetzen, Löschen oder Einfügen von Zeichen. Computer können über die mit einem mathematischen Algorithmus berechnete Editierdistanz feststellen, wie ähnlich zwei vorgegebene Zeichenketten sind.

Identische Zeichenketten haben eine Editierdistanz von 0. Da die Levenshtein-Distanz nicht nur die Ähnlichkeit gleich langer, sondern auch unterschiedlich langer Zeichenketten bestimmen kann, lässt sie sich als Erweiterung des Hamming-Abstands betrachten. Typischerweise kommt die Editierdistanz für Anwendungen wie die Rechtschreibprüfung, für Suchfunktionen oder für das Erkennen von Duplikaten zum Einsatz.

Beispiele für die Levenshtein-Distanz

Für ein besseres Verständnis der Levenshtein-Distanz, hier drei einfache Beispiele:

• 1. Die Levenshtein-Distanz zwischen den beiden Zeichenketten „Auto“ und „Auto“ beträgt 0, da sie identisch sind.

• 2. Die Levenshtein-Distanz zwischen den beiden Zeichenketten „Wind“ und „Wirt“ beträgt 2. Die Buchstaben „n“ und „d“ müssen durch die Buchstaben „r“ und „t“ ersetzt werden.

• 3. Die Levenshtein-Distanz zwischen den beiden Zeichenketten „Buche“ und „Bach“ beträgt 2. Der Buchstabe „u“ muss durch „a“ ersetzt und der Buchstabe „e“ gelöscht werden.

Grundsätze der Levenshtein-Distanz

Die Levenshtein-Distanz folgt folgenden Grundsätzen: Zwei identische Zeichenketten haben die Distanz 0. Die Distanz kann bei unterschiedlichen Zeichenketten höchstens der Länge der längeren Zeichenkette entsprechen, muss aber mindestens so groß wie der Längenunterschied beider Ketten sein.

Algorithmus zu Bestimmung der Levenshtein-Distanz

In der ursprünglichen Definition der Levenshtein-Distanz aus dem Jahr 1965 ist kein Algorithmus zur Berechnung angegeben. Üblicherweise wird sie über einen dynamischen Programmieransatz und eine Matrix berechnet. Eine zweidimensionale Matrix ist durch die beiden zu untersuchenden Zeichenketten definiert. Gefüllt sind die Zellen der Matrix mit den berechneten Distanzen zwischen den jeweiligen Stellen der Zeichenketten. In der rechten unteren Ecke der Matrix steht am Ende der Berechnung die Levenshtein-Distanz. Die Berechnung der Editierdistanz wird umso aufwendiger, je länger die Zeichenketten sind.

Praktische Anwendungen der Levenshtein-Distanz

Die Levenshtein-Distanz kommt unter anderem für Rechtschreibprüfungen, Suchfunktionen oder für das Erkennen von Duplikaten und Plagiaten zum Einsatz. Über die Einstellung einer bestimmten Levenshtein-Distanz zwischen dem Suchbegriff und den zu durchsuchenden Zeichenketten lässt sich beispielsweise nach ähnlichen Begriffen (unscharfe Suche) suchen. Rechtschreibfehler bei der Eingabe eines Suchbegriffs liefern durch die Vorgabe einer Levenshtein-Distanz größer 0 unter Umständen dennoch das gewünschte Ergebnis.

(ID:48565119)