So berechnen Sie die Levenshtein-Distanz in Python

Der Levenshtein-Distanz zwischen zwei Zeichenfolgen ist die Mindestanzahl von Einzelzeichenänderungen, die erforderlich sind, um ein Wort in das andere umzuwandeln.

Das Wort "Einzelzeichenänderungen" umfasst dabei Ersetzungen, Einfügungen und Löschungen.

Angenommen, wir haben die folgenden zwei Wörter:

• PARTY
• PARK

Der Levenshtein-Distanz zwischen den beiden Wörtern (d.h. die Anzahl der Änderungen, die wir vornehmen müssen, um ein Wort in das andere umzuwandeln) beträgt 2:

In der Praxis wird der Levenshtein-Distanz in vielen verschiedenen Anwendungen verwendet, einschließlich der ungefähren Zeichenfolgenübereinstimmung, Rechtschreibprüfung und Verarbeitung natürlicher Sprache.

In diesem Tutorial wird erläutert, wie Sie den Levenshtein-Distanz zwischen Zeichenfolgen in Python mithilfe des Python-Levenshtein-Moduls berechnen.

Sie können die folgende Syntax verwenden, um dieses Modul zu installieren:

pip install python-Levenshtein

Sie können dann die Funktion laden, um die Levenshtein-Entfernung zu berechnen:

from Levenshtein import distance as lev

Die folgenden Beispiele zeigen, wie diese Funktion in der Praxis verwendet wird.

Beispiel 1: Levenshtein-Distanz zwischen zwei Saiten

Der folgende Code zeigt, wie der Levenshtein-Distanz zwischen den beiden Zeichenfolgen "Party" und "Park" berechnet wird:

# Levenshtein Abstand berechnen
lev('party', 'park')

2

Der Levenshtein-Distanz beträgt 2.

Beispiel 2: Levenshtein-Distanz zwischen zwei Arrays

Der folgende Code zeigt, wie der Levenshtein-Distanz zwischen jeder paarweisen Kombination von Zeichenfolgen in zwei verschiedenen Arrays berechnet wird:

# Arrays definieren
a = ['Mavs', 'Spurs', 'Lakers', 'Cavs']
b <- ['Rockets', 'Pacers', 'Warriors', 'Celtics']

# Berechnen Sie den Levenshtein-Distanz zwischen zwei Arrays
for i,k in zip(a, b):
  print(lev(i, k))

6
4
5
5

Die Interpretation der Ausgabe ist wie folgt:

• Der Levenshtein-Distanz zwischen 'Mavs' und 'Rockets' beträgt 6.
• Der Levenshtein-Distanz zwischen 'Spurs' und 'Pacers' beträgt 4.
• Der Levenshtein-Distanz zwischen 'Lakers' und 'Warriors' beträgt 5.
• Der Levenshtein-Distanz zwischen 'Cavs' und 'Celtics' beträgt 5.

Zusätzliche Ressourcen

So berechnen Sie die Hamming-Entfernung in Python
So berechnen Sie die euklidische Entfernung in Python
So berechnen Sie die Mahalanobis-Entfernung in Python