array ( 0 => 'index.php', 1 => 'PHP Manual', ), 'head' => array ( 0 => 'UTF-8', 1 => 'de', ), 'this' => array ( 0 => 'function.levenshtein.php', 1 => 'levenshtein', 2 => 'Berechnet die Levenshtein-Distanz zwischen zwei Strings', ), 'up' => array ( 0 => 'ref.strings.php', 1 => 'String-Funktionen', ), 'prev' => array ( 0 => 'function.lcfirst.php', 1 => 'lcfirst', ), 'next' => array ( 0 => 'function.localeconv.php', 1 => 'localeconv', ), 'alternatives' => array ( ), 'source' => array ( 'lang' => 'de', 'path' => 'reference/strings/functions/levenshtein.xml', ), 'history' => array ( ), ); $setup["toc"] = $TOC; $setup["toc_deprecated"] = $TOC_DEPRECATED; $setup["parents"] = $PARENTS; manual_setup($setup); contributors($setup); ?>

levenshtein

(PHP 4 >= 4.0.1, PHP 5, PHP 7, PHP 8)

levenshtein — Berechnet die Levenshtein-Distanz zwischen zwei Strings

Beschreibung

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

Die Levenshtein-Distanz bezeichnet die minimale Anzahl von Zeichen, die Sie ersetzen, einfügen oder löschen müssen, um string1 in string2 umzuwandeln. Die Komplexität des Algorithmus ist O(m*n), wobei n und m die Länge von string1 und string2 darstellen (recht gut, im Vergleich zu similar_text(), das O(max(n,m)**3) ist, aber trotzdem immer noch aufwendig).

Wenn insertion_cost, replacement_cost und/oder deletion_cost ungleich 1 sind, passt sich der Algorithmus an, um die günstigsten Transformationen zu wählen. Wenn z. B. $insertion_cost + $deletion_cost < $replacement_cost, werden keine Ersetzungen durchgeführt, sondern stattdessen Einfügungen und Löschungen.

Parameter-Liste

string1

Eine der Zeichenketten, für die die Levenshtein-Distanz zu berechnen ist.

string2

Eine der Zeichenketten, für die die Levenshtein-Distanz zu berechnen ist.

insertion_cost

Definiert die Kosten des Einfügens.

replacement_cost

Definiert die Kosten des Ersetzens.

deletion_cost

Definiert die Kosten des Löschens.

Rückgabewerte

Die Funktion gibt die Levenshtein-Distanz zwischen den beiden Argument-Strings zurück.

Changelog

Version Beschreibung
8.0.0 Vor dieser Version musste levenshtein() entweder mit zwei oder fünf Argumenten aufgerufen werden.
8.0.0 Vor dieser Version gab levenshtein() -1 zurück, wenn eines der Argumente länger als 255 Zeichen war.

Beispiele

Beispiel #1 levenshtein()-Beispiel

<?php
// eingegebenes falsch geschriebenes Wort
$input = 'carrrot';

// Wörterarray als Vergleichsquelle
$words = array('apple','pineapple','banana','orange',
'radish','carrot','pea','bean','potato');

// noch keine kürzeste Distanz gefunden
$shortest = -1;

// durch die Wortliste gehen, um das ähnlichste Wort zu finden
foreach ($words as $word) {

// berechne die Distanz zwischen Inputwort und aktuellem Wort
$lev = levenshtein($input, $word);

// auf einen exakten Treffer prüfen
if ($lev == 0) {

// das nächste Wort ist das Wort selbst (exakter Treffer)
$closest = $word;
$shortest = 0;

// Schleife beenden, da wir einen exakten Treffer gefunden haben
break;
}

// Wenn die Distanz kleiner ist als die nächste gefundene kleinste Distanz
// ODER wenn ein nächstkleineres Wort noch nicht gefunden wurde
if ($lev <= $shortest || $shortest < 0) {
// setze den nächstliegenden Treffer und die kürzestes Distanz
$closest = $word;
$shortest = $lev;
}
}

echo "Eingegebenes Wort: $input\n";
if ($shortest == 0) {
echo "Exakter Treffer gefunden: $closest\n";
} else {
echo "Meinten Sie: $closest?\n";
}

?>

Das oben gezeigte Beispiel erzeugt folgende Ausgabe:

Eingegebenes Word: carrrot
Meinten Sie: carrot?

Siehe auch