Was ist die Levenshtein-Distanz? Edit Distance mit Dynamic Programming

Die Levenshtein-Distanz, auch Edit Distance genannt, misst den Unterschied zwischen zwei Strings anhand der minimal notwendigen Bearbeitungsoperationen.

Erlaubt sind normalerweise:

• Insert
• Delete
• Replace

Jede Operation kostet standardmäßig 1.

Beispiel:

cat → cut

Nur ein Zeichen muss ersetzt werden:

Distance = 1

Klassisches Beispiel

kitten → sitting

Eine optimale Folge ist:

kitten → sitten
sitten → sittin
sittin → sitting

Damit beträgt die Distanz 3.

Dynamic Programming

Wir definieren:

dp[i][j]

als minimale Anzahl von Operationen, um die ersten i Zeichen des ersten Strings in die ersten j Zeichen des zweiten Strings umzuwandeln.

Die Basisfälle lauten:

dp[0][j] = j
dp[i][0] = i

Sind die aktuellen Zeichen gleich:

dp[i][j] = dp[i - 1][j - 1]

Ansonsten:

dp[i][j] = 1 + min(
  dp[i - 1][j],
  dp[i][j - 1],
  dp[i - 1][j - 1]
)

Die drei Werte repräsentieren Delete, Insert und Replace.

TypeScript-Implementierung

function levenshteinDistance(a: string, b: string): number {
  const dp = Array.from(
    { length: a.length + 1 },
    () => new Array(b.length + 1).fill(0)
  );

  for (let i = 0; i <= a.length; i++) {
    dp[i][0] = i;
  }

  for (let j = 0; j <= b.length; j++) {
    dp[0][j] = j;
  }

  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j],
          dp[i][j - 1],
          dp[i - 1][j - 1]
        );
      }
    }
  }

  return dp[a.length][b.length];
}

Komplexität

Für Stringlängen n und m:

Time Complexity: O(n × m)
Space Complexity: O(n × m)

Der Speicher kann auf O(min(n, m)) reduziert werden, wenn nur die aktuelle und vorherige Zeile gespeichert werden.

Spell Checking

Ein Benutzer schreibt beispielsweise:

programing

Die Distanz zu programming beträgt nur 1. Damit kann das Wort als guter Korrekturvorschlag verwendet werden.

Fuzzy Search

Bei:

Alexander
Alexnder

scheitert Exact Matching, obwohl die Strings offensichtlich sehr ähnlich sind.

Edit Distance kann diese Ähnlichkeit quantifizieren.

CRM und Datenbereinigung

Levenshtein kann bei der Erkennung möglicher Duplicate Records helfen.

Beispielsweise:

Arian Soleimanzadeh
Arian Soleimanzade

Eine geringe Distanz ist ein Signal, sollte aber in realen CRM-Systemen mit E-Mail, Telefonnummer oder anderen Identifikatoren kombiniert werden.

Weitere Anwendungen

• Fuzzy Search
• Rechtschreibkorrektur
• OCR
• NLP
• Data Cleaning
• Record Matching
• Bioinformatik

Unterschied zur Hamming-Distanz

Die Hamming-Distanz vergleicht nur korrespondierende Positionen und setzt normalerweise gleiche Längen voraus.

Levenshtein berücksichtigt auch Insert und Delete.

cat → cats

hat deshalb eine Levenshtein-Distanz von 1.

Weighted Edit Distance

Die Operationskosten können angepasst werden:

Insert = 1
Delete = 1
Replace = 2

Dadurch lässt sich der Algorithmus an bestimmte Anwendungen anpassen.

Typische Interviewfrage

Ein klassisches Dynamic-Programming-Problem lautet:

Bestimme die minimale Anzahl von Insert-, Delete- und Replace-Operationen zwischen zwei Strings.

Für:

horse → ros

ist das Ergebnis 3.

Fazit

Die Levenshtein-Distanz berechnet die minimale Anzahl von Insert-, Delete- und Replace-Operationen zwischen zwei Strings.

Die Standardlösung nutzt Dynamic Programming mit:

Time: O(n × m)
Space: O(n × m)

Das Verfahren ist nicht nur für Algorithmusaufgaben wichtig, sondern auch für Fuzzy Search, Rechtschreibprüfung, CRM-Deduplizierung, OCR und NLP.