levenshtein()

Die Funktion levenshtein() berechnet den Levenshtein-Abstand zwischen zwei Zeichenketten — die minimale Anzahl einzelner Zeichenoperationen (Einfügungen, Löschungen oder Ersetzungen), die nötig sind, um eine Zeichenkette in die andere umzuwandeln. Ein kleinerer Abstand bedeutet, dass sich die Zeichenketten ähnlicher sind. Daher ist levenshtein() das Standardwerkzeug für Fuzzy-Matching: Rechtschreibprüfungen, „Meinten Sie …?"-Vorschläge, Deduplizierung nahezu identischer Datensätze und die Rangordnung von Suchergebnissen nach Ähnlichkeit.

Dieses Kapitel behandelt die Syntax, die optionalen Kostengewichtungen, die Unterschiede zu verwandten Funktionen, häufige Fallstricke und ausführbare Beispiele.

Syntax

levenshtein(string $string1, string $string2): int

Oder mit benutzerdefinierten Bearbeitungskosten:

levenshtein(
    string $string1,
    string $string2,
    int $insertion_cost,
    int $replacement_cost,
    int $deletion_cost
): int

Parameter

• $string1 — die erste zu vergleichende Zeichenkette.
• $string2 — die zweite zu vergleichende Zeichenkette.
• $insertion_cost (optional) — Kosten für das Einfügen eines Zeichens. Standard 1.
• $replacement_cost (optional) — Kosten für das Ersetzen eines Zeichens. Standard 1.
• $deletion_cost (optional) — Kosten für das Löschen eines Zeichens. Standard 1.

Die Funktion gibt den Levenshtein-Abstand als int zurück. Mit den Standardgewichtungen ist dieser Abstand symmetrisch — levenshtein($a, $b) ergibt dasselbe wie levenshtein($b, $a).

Einfaches Beispiel

Die Ausgabe dieses Codes ist:

4

Die Funktion gibt 4 zurück: um „Hello" in „World" umzuwandeln, sind vier Ersetzungen nötig (H→W, e→o, l→r, o→d); nur das zweite l bleibt unverändert.

Wie der Abstand berechnet wird

Jede Bearbeitungsoperation zählt als ein Schritt (mit Standardgewichtungen). Das klassische Lehrbuchbeispiel „kitten" → „sitting" benötigt drei Bearbeitungen:

<?php
echo levenshtein("kitten", "sitting"); // 3
// k → s   (substitution)
// e → i   (substitution)
// (append) g   (insertion)
?>

Ausgabe:

3

levenshtein() unterscheidet Groß- und Kleinschreibung

Unterschiedliche Groß- und Kleinschreibung zählt als Bearbeitung, was viele überrascht:

<?php
echo levenshtein("Hello", "hello"), "\n"; // 1  (H vs h)
echo levenshtein(strtolower("Hello"), strtolower("hello")), "\n"; // 0
?>

Ausgabe:

1
0

Für einen Vergleich ohne Berücksichtigung der Groß- und Kleinschreibung normalisieren Sie beide Zeichenketten mit strtolower() (oder mb_strtolower() für Multibyte-Text), bevor Sie levenshtein() aufrufen.

Bearbeitungen unterschiedlich gewichten

Wenn Einfügungen, Löschungen und Ersetzungen nicht die gleichen Kosten haben sollen, übergeben Sie die drei Kostenargumente. Hier werden Löschungen teuer gemacht:

<?php
// $insertion_cost = 1, $replacement_cost = 1, $deletion_cost = 5
echo levenshtein("cats", "cat", 1, 1, 5); // 5
?>

Ausgabe:

5

Das Entfernen des abschließenden s ist eine einzelne Löschung, aber mit Kosten von 5 wird der gemeldete Abstand als 5 ausgegeben. Dies ist nützlich, wenn eine bestimmte Art von Tippfehler stärker bestraft werden soll als eine andere.

Praktische Anwendung: „Meinten Sie?"-Vorschläge

Eine häufige Aufgabe in der Praxis ist es, das nächste bekannte Wort zur Eingabe eines Benutzers zu finden:

<?php
$input = "comit";
$dictionary = ["commit", "command", "comment", "compile"];

$best = null;
$bestDistance = PHP_INT_MAX;

foreach ($dictionary as $word) {
    $d = levenshtein($input, $word);
    if ($d < $bestDistance) {
        $bestDistance = $d;
        $best = $word;
    }
}

echo "Did you mean: {$best}? (distance {$bestDistance})";
?>

Ausgabe:

Did you mean: commit? (distance 1)

Fallstricke

• Bytes, keine Zeichen. levenshtein() arbeitet auf einzelnen Bytes, sodass Multibyte-UTF-8-Zeichen (Akzente, Emoji, nicht-lateinische Schriften) falsch gezählt werden können. Für genaue Ergebnisse mit solchen Texten sollten Sie transliterieren oder normalisiertes ASCII vergleichen.
• Lange Zeichenketten kosten Speicher und Zeit. Die Komplexität ist grob proportional zum Produkt der beiden Zeichenkettenlängen — vermeiden Sie die Funktion daher bei sehr großen Eingaben.
• Groß-/Kleinschreibung und Leerzeichen zählen. Kürzen Sie zuerst und wandeln Sie in Kleinbuchstaben um, wenn diese Unterschiede ignoriert werden sollen.

Verwandte Funktionen

• similar_text() — gibt die Anzahl übereinstimmender Zeichen (und optional einen Prozentsatz) zurück, anstatt einen Bearbeitungsabstand.
• soundex() und metaphone() — vergleichen Zeichenketten anhand ihrer Aussprache statt ihrer Schreibweise.
• strcmp() — ein strenger, binärsicherer Vergleich, der nur angibt, ob Zeichenketten gleich sind oder welche zuerst sortiert wird.

Übung