Levenshtein-Edit-Distanz in NLP: String-Ähnlichkeit in Python messen

In der Natural Language Processing (NLP) ist das Bewerten und Vergleichen der Ähnlichkeit zweier Strings eine zentrale Fähigkeit. Ob Tippfehler korrigiert, Plagiate erkannt, Namen abgeglichen oder maschinell erzeugte Texte beurteilt werden: Wenn sich messen lässt, wie „nah“ zwei Strings beieinanderliegen, kann das die Leistungsfähigkeit sprachbasierter Anwendungen spürbar steigern. Eine der bekanntesten und am häufigsten eingesetzten Methoden für diesen Zweck ist die Levenshtein Edit Distance. Dieser Ansatz berechnet die Ähnlichkeit zwischen zwei Zeichenketten, indem er die minimale Anzahl an Änderungen misst, die erforderlich sind, um eine Zeichenkette in die andere umzuwandeln. Oft wird sie einfach als edit distance bezeichnet und kommt häufig in NLP-Systemen, Rechtschreibprüfungen, Suchmaschinen und Fuzzy-Matching-Prozessen zum Einsatz. In diesem Artikel zeigen wir, wie sich die Levenshtein-Distanz in Python implementieren lässt, vergleichen verfügbare Bibliotheken, betrachten Performance-Aspekte und untersuchen ihre Rolle in modernen NLP- sowie LLM-gestützten Workflows.

Wichtigste Erkenntnisse

• Die Levenshtein Distance ist eine zentrale Metrik zur String-Ähnlichkeit und berechnet die minimale Anzahl einzelner Zeichen-Edits (Einfügen, Löschen, Ersetzen), um einen String in einen anderen zu überführen.
• Sie wird häufig für Rechtschreibkorrektur, unscharfe Suche, Autokorrektur, Plagiatserkennung und Bioinformatik eingesetzt.
• Das Verfahren basiert auf Dynamic Programming, meist umgesetzt mit einer Matrix, und liefert deterministische sowie exakte Ergebnisse.
• Python-Pakete wie Levenshtein, fuzzywuzzy und distance vereinfachen die praktische Umsetzung für reale Anwendungsfälle.
• Trotz der Stärken ist die Levenshtein-Distanz rechnerisch aufwendig und bildet keine semantische Bedeutung ab, weshalb sie für tiefere NLP-Aufgaben mit Volltext-Semantik weniger geeignet ist.
• Andere Metriken – etwa Jaro-Winkler, Damerau-Levenshtein, Jaccard und Cosine Similarity – haben je nach Szenario unterschiedliche Vorteile (zum Beispiel: Namenabgleich, Token-Overlap, semantische Ähnlichkeit).

So funktioniert die Levenshtein-Distanz

Die Levenshtein-Distanz zählt die kleinste Anzahl an Zeichen-Operationen (Einfügen, Löschen oder Ersetzen), die nötig ist, um einen String in einen anderen umzuwandeln. Unten folgt ein direkter, aber vollständiger Durchlauf anhand eines Matrix-Beispiels, das sich leicht nachvollziehen lässt:

„book“ → „back“

Gegeben:

• String 1, s1 = „book“ (length = 4)
• String 2, s2 = „back“ (length = 4)

Schritt 1: Matrix initialisieren

Um die Strings in einer Matrix abzubilden, erstellen wir ein 5 X 5 Raster, damit auch der leere String („ “) an Index 0 berücksichtigt wird. Empty Matrix Initialization:

Schritt 2: Die Matrix ausfüllen

Die Levenshtein-Distanz zwischen zwei Strings i, j (mit den Längen | i | bzw. | j |) wird als D ⁡( i, j ) ausgedrückt, wobei gilt:

Schauen wir uns ein paar wichtige Zellen an:

Cell (1,1): Compare ‘b’ and ‘b’ → Match

D(1,1)=D(0,0)=0

Cell (2,2): Compare ‘o’ and ‘a’ → No match

D(1,2) = 1 (deletion)

D(2,1) = 2 (insertion)

D(1,1) = 0 (substitution)

D(2,2)=1+min(1,2,0)=1

Cell (3,3): Compare ‘o’ and ‘c’ → No match

D(2,3) = 2

D(3,2) = 2

D(2,2) = 1

D(3,3)=1+min⁡(2,2,1)=2 Continue this process…

Schritt 3: Finale Matrix

Levenshtein-Distance D(4,4) = 2 – Es sind also 2 Schritte erforderlich, um „book“ in „back“ umzuwandeln:

• Ersetze ‘o’ → ‘a’
• Ersetze ‘o’ → ‘c’

Im obigen Beispiel wurde die Edit-Distanz berechnet, während die Matrix Schritt für Schritt aufgebaut wurde. Die Levenshtein-Distanz ergibt sich, indem bei jedem Schritt Einfügungen, Löschungen und Ersetzungen bewertet werden; das finale Ergebnis steht in der rechten unteren Matrixzelle.

Levenshtein-Distance in Python implementieren – ohne Libraries

Unten steht Python-Code, der die Levenshtein-Distanz berechnet und zusätzlich die Matrix ausgibt.

def levenshtein_distance(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0 for _ in range(n+1)] for _ in range(m+1)]

    # Initialize base cases
    for i in range(m+1):
        dp[i][0] = i
    for j in range(n+1):
        dp[0][j] = j

    # Fill the matrix
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                cost = 0
            else:
                cost = 1
            dp[i][j] = min(
                dp[i-1][j] + 1,      # deletion
                dp[i][j-1] + 1,      # insertion
                dp[i-1][j-1] + cost  # substitution
            )

    # Print the matrix
    print("Levenshtein Distance Matrix:")
    print("   ", "  ".join([" "] + list(s2)))
    for i in range(m+1):
        row = [s1[i-1] if i > 0 else " "]
        for j in range(n+1):
            row.append(str(dp[i][j]))
        print("  ".join(row))

    return dp[m][n]

# Example: "book" to "back"
s1 = "book"
s2 = "back"
distance = levenshtein_distance(s1, s2)
print(f"\nLevenshtein distance between '{s1}' and '{s2}' is {distance}")

**Levenshtein Distance Matrix:**
       **b  a  c  k**

   **0  1  2  3  4**

**b  1  0  1  2  3**

**o  2  1  1  2  3**

**o  3  2  2  2  3**

**k  4  3  3  3  2**

Levenshtein distance between ‘book’ and ‘back’ is 2

Nutze Python-Bibliotheken für den Levenshtein distance

1. Anwendung von python-Levenshtein

!pip install python-Levenshtein

import Levenshtein
s1 = „book“

s2 = „back“
distance = Levenshtein.distance(s1, s2)

print(f“Levenshtein distance: {distance}“)

2. Verwendung von fuzzywuzzy (für fuzzy matching)

!pip install fuzzywuzzy python-Levenshtein

from fuzzywuzzy import fuzz
s1 = „book“

s2 = „back“
# Fuzzy match ratio based on Levenshtein distance

ratio = fuzz.ratio(s1, s2)

print(f“Fuzzy match ratio: {ratio}%“)

3. Mit rapidfuzz (ressourcenschonend und schnell)

!pip install rapidfuzz

from rapidfuzz.distance import Levenshtein
s1 = „book“

s2 = „back“
distance = Levenshtein.distance(s1, s2)

print(f“Levenshtein distance: {distance}“)

4.Verwendung von „distance“ (einfaches und reines Python)

!pip install distance

import distance
s1 = „book“

s2 = „back“
distance_val = distance.levenshtein(s1, s2)

print(f“Levenshtein distance: {distance_val}“)

5. Verwendung von textdistance (flexibel und mit Unterstützung für viele Algorithmen)

!pip install textdistance

import textdistance
s1 = „book“

s2 = „back“
distance = textdistance.levenshtein(s1, s2)

print(f“Levenshtein distance: {distance}“)

Komplettes Python-Performance-Benchmark

Das folgende Benchmark-Skript bewertet die Geschwindigkeit der Levenshtein-Distanz in diesen Libraries: rapidfuzz, python-Levenshtein, textdistance und distance.

Zuerst die benötigten Abhängigkeiten installieren, falls noch nicht vorhanden:

pip install matplotlib rapidfuzz python-Levenshtein textdistance distance

import time
import matplotlib.pyplot as plt
import Levenshtein
import textdistance
import distance as dist
from rapidfuzz.distance import Levenshtein as r_lev

# Strings to compare
s1 = "book"
s2 = "back"
N = 100_000

# Store results
results = {}

# Benchmark function
def benchmark(name, func):
    start = time.time()
    for _ in range(N):
        func(s1, s2)
    end = time.time()
    duration = end - start
    avg_time_us = duration / N * 1e6
    results[name] = (duration, avg_time_us)
    print(f"{name:<25}: {duration:.4f} sec (Avg: {avg_time_us:.2f} µs)")

print("Benchmarking Levenshtein Distance (100,000 repetitions):\n")

# Run benchmarks
benchmark("rapidfuzz", lambda a, b: r_lev.distance(a, b))
benchmark("python-Levenshtein", lambda a, b: Levenshtein.distance(a, b))
benchmark("textdistance", lambda a, b: textdistance.levenshtein(a, b))
benchmark("distance (pure Python)", lambda a, b: dist.levenshtein(a, b))

# Plotting the results
libraries = list(results.keys())
total_times = [results[lib][0] for lib in libraries]
avg_times = [results[lib][1] for lib in libraries]

plt.figure(figsize=(10, 5))
bars = plt.bar(libraries, avg_times, color=['#66c2a5', '#fc8d62', '#8da0cb', '#e78ac3'])

plt.title("Levenshtein Distance Avg Time per Call (µs)")
plt.ylabel("Average Time (µs)")
plt.xlabel("Python Library")
plt.grid(axis='y', linestyle='--', alpha=0.7)
plt.tight_layout()

# Annotate bars with actual times
for bar, avg in zip(bars, avg_times):
    yval = bar.get_height()
    plt.text(bar.get_x() + bar.get_width() / 2, yval + 0.5, f"{avg:.2f}", ha='center', va='bottom', fontsize=9)

plt.show()

Benchmarking Levenshtein Distance (100,000 repetitions):

• rapidfuzz : 0.0866 sec (Avg: 0.87 µs)
• python-Levenshtein : 0.0881 sec (Avg: 0.88 µs)
• textdistance : 0.3400 sec (Avg: 3.40 µs)
• distance (pure Python) : 1.4420 sec (Avg: 14.42 µs)

Vergleich mit anderen String-Ähnlichkeitsmetriken

String-Similarity-Matrizen sind eine Methode, bei der Strings in einem strukturierten Raster dargestellt werden, um zu messen, wie ähnlich oder unterschiedlich Begriffe sind. Dabei werden Unterschiede auf Zeichen- oder Token-Ebene in einer Tabelle abgebildet. Solche Matrizen sind essenziell für Algorithmen wie Levenshtein, Damerau-Levenshtein und verwandte Verfahren, bei denen jede Zelle die „Kosten“ bzw. die „Distanz“ beschreibt, die nötig ist, um einen Teilstring in einen anderen zu überführen – über Operationen wie Einfügen, Löschen, Ersetzen oder Transposition.

Üblicherweise startet die Matrix mit ansteigenden Werten in der ersten Zeile und der ersten Spalte, um die Kosten der Umwandlung eines leeren Strings in die Zeichen des anderen Strings zu beschreiben.

Während das Raster Zeile für Zeile und Spalte für Spalte gefüllt wird, wird jede Zelle anhand einer Rekurrenzregel berechnet, die die aktuellen Zeichen vergleicht und den minimalen Kostenwert aus vorherigen Zellen auswählt. So entsteht ein Dynamic-Programming-Grid, dessen rechte untere Zelle die finale Distanz bzw. den Ähnlichkeitswert für die vollständigen Strings enthält. Solche Similarity-Matrizen bilden die Grundlage für fortgeschrittene NLP-Anwendungen wie Rechtschreibprüfung, Fuzzy Matching und Data-Deduplication.

Verschiedene Metriken verfolgen unterschiedliche Ziele und können Edit-Distanz, Token-Overlap oder phonetische Ähnlichkeit stärker gewichten.

Betrachten wir das Beispiel „book“ und „back“ erneut:

Levenshtein distance is a strong general-purpose method for character-level string comparison, but more specialized measures can perform better in specific situations. Jaro-Winkler and Damerau-Levenshtein are especially helpful for name matching and typographical issues, since they may assign higher similarity to shared prefixes or swapped characters.

By contrast, set-based approaches like Jaccard and the Dice coefficient are more appropriate when comparing at the word or token level, which is useful for document or phrase similarity work.

To capture meaning beyond visible character changes, vector-based measures such as cosine similarity—applied to TF-IDF vectors or embeddings—enable semantic comparison in full-text or NLP scenarios. Each metric provides a distinct viewpoint on similarity, and the best choice depends on the desired granularity and the comparison context.

Anwendungen in NLP und LLMs

Die Levenshtein-Edit-Distanz gilt als grundlegendes Werkzeug in der Verarbeitung natürlicher Sprache (Natural Language Processing, NLP). Da sie misst, wie stark sich zwei Zeichenketten unterscheiden – basierend auf der minimalen Anzahl an Einfügungen, Löschungen oder Ersetzungen – eignet sie sich besonders gut für verrauschte, nutzergenerierte Eingaben. In modernen NLP-Pipelines und Large Language Models (LLMs) dient die Levenshtein-Distanz häufig als unterstützende Komponente, entweder in der Vorverarbeitung (z. B. Bereinigung, Rechtschreibkorrektur) oder in der Auswertung (z. B. Vergleich generierter Ausgaben mit Referenzdaten). Im Folgenden einige zentrale Anwendungsbereiche:

• Rechtschreibprüfung und Autokorrektur: Erkennen und Korrigieren von Tippfehlern durch Auswahl des ähnlichsten Wörterbucheintrags basierend auf der minimalen Edit-Distanz.
• Fuzzy-String-Matching: Abgleich falsch geschriebener oder ungefähr ähnlicher Zeichenketten, etwa in Suchfunktionen, Autocomplete-Systemen oder OCR-Anwendungen.
• Textnormalisierung: Bereinigung und Vereinheitlichung von verrauschtem oder nutzergeneriertem Text vor der Weiterverarbeitung in NLP-Pipelines.
• Named-Entity-Matching: Verbesserung der Entitätserkennung zur Deduplizierung und Verknüpfung von Namen mit geringfügigen Abweichungen.
• Bewertung von Textgenerierung: Vergleich von Modell-Ausgaben mit Referenzdaten, z. B. bei Aufgaben wie Zusammenfassung oder Übersetzung.
• Intent-Erkennung in Chatbots: Zuordnung von Nutzeranfragen zu vordefinierten Intents trotz Tippfehlern oder Variationen.
• Daten-Deduplizierung: Erkennung nahezu identischer Einträge in Datensätzen, insbesondere bei inkonsistenten Datenbankeinträgen.
  

Vorteile der Levenshtein-Distanz

Die Levenshtein-Edit-Distanz ist leicht verständlich und vergleichsweise einfach zu berechnen, wie in diesem Artikel gezeigt wurde. Sie funktioniert, indem sie die minimale Anzahl an Zeichenoperationen (Einfügen, Löschen oder Ersetzen) zählt, die erforderlich sind, um eine Zeichenkette in eine andere umzuwandeln. Diese Klarheit macht sie zu einer bevorzugten Methode für viele grundlegende Aufgaben des Zeichenkettenvergleichs.
Darüber hinaus ist die Methode sprachunabhängig, da sie ausschließlich auf Zeichenebene arbeitet. Sie basiert nicht auf sprachspezifischen Regeln und kann daher in unterschiedlichsten Sprachen und Zeichensätzen eingesetzt werden. Das Ergebnis ist eine exakte und deterministische Distanz, die eine klar definierte und reproduzierbare Messgröße für die Unterschiede zwischen zwei Zeichenketten liefert.

Nachteile der Levenshtein-Distanz

• Die Berechnung der Levenshtein Distance kann ressourcenintensiv sein, da ihre Zeitkomplexität bei O(m × n) liegt (wobei m und n die Längen der beiden Eingabezeichenketten sind). Bei langen Strings oder sehr großen Vergleichsmengen kann dies zu Performance-Problemen führen.
• Die Levenshtein Distance berücksichtigt weder Kontext noch Bedeutung, da sie ausschließlich Änderungen auf Zeichenebene misst. So ergibt beispielsweise „cat“ und „feline“ eine hohe Distanz, obwohl beide semantisch ähnlich sind.
• Die Standard Levenshtein distance geht nicht effizient mit Zeichenvertauschungen um. Beispielsweise wirken „form“ und „from“ sehr ähnlich, liefern aber dennoch eine Distanz von 2. Damerau-Levenshtein löst dieses Problem deutlich besser.
• Die Levenshtein-Distanz gewichtet Einfügungen, Löschungen und Ersetzungen gleichermaßen. In der Praxis sind jedoch bestimmte Änderungen – etwa das Vertauschen visuell ähnlicher Zeichen – wahrscheinlicher oder sollten mit geringeren Kosten bewertet werden als andere.
• Da sie sich ausschließlich auf einzelne Zeichen konzentriert, ist sie weniger geeignet für Aufgaben, die eine Ähnlichkeit auf Token- oder Phrasenebene erfordern, wie beispielsweise semantisches Matching oder Textklassifikation.

FAQs

• Wie kann man die Levenshtein-Distanz in Python berechnen?
  Du kannst sie mit Bibliotheken wie python-Levenshtein oder rapidfuzz berechnen oder einen eigenen Ansatz mittels dynamischer Programmierung implementieren.
• Wie berechnet man die Levenshtein-Distanz in Python ohne Bibliothek?
  Du kannst verschachtelte Schleifen in Kombination mit einer Matrix für dynamische Programmierung verwenden, wie im obigen Codebeispiel gezeigt.
• Wie hoch ist die Zeitkomplexität der Levenshtein-Distanz?
  Die Zeitkomplexität beträgt O(m*n), wobei m und n die Längen der beiden Strings sind.
• Was ist der Unterschied zwischen Levenshtein-Distanz und Hamming-Distanz?
  Die Hamming-Distanz funktioniert nur bei Strings gleicher Länge und zählt die abweichenden Positionen. Die Levenshtein-Distanz ist flexibler, da sie auch Einfügungen und Löschungen berücksichtigt.
• Welche Python-Bibliothek ist am schnellsten für die Levenshtein-Distanz?
  rapidfuzz gehört in der Regel zu den schnellsten und effizientesten Optionen für den produktiven Einsatz.
• Wird die Levenshtein-Distanz in Machine Learning oder LLMs verwendet?
  Ja. Sie wird in der Vorverarbeitung, zur Deduplizierung und Nachverarbeitung eingesetzt und kann auch semantische Matching-Workflows in LLM-Pipelines unterstützen.

Fazit

Die Levenshtein Distance zählt weiterhin zu den grundlegenden Verfahren zur Bestimmung von Zeichenkettenähnlichkeit in Python. Auch wenn moderne semantische Modelle die Möglichkeiten im NLP deutlich erweitert haben, bleibt sie besonders für Aufgaben relevant, bei denen ein exakter Vergleich auf Zeichenebene erforderlich ist. Mit leistungsstarken Bibliotheken wie rapidfuzz sowie hybriden Ansätzen, die Edit-Distanz mit Embeddings kombinieren, verfügen Python-Entwickler heute über ein breites Spektrum an effektiven Lösungen für Fuzzy-String-Matching-Probleme.