Berechnet die Levenshtein-Distanz zwischen zwei Strings

# levenshtein

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

levenshtein — Berechnet die Levenshtein-Distanz zwischen zwei Strings

### Beschreibung

function 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

- soundex() - Berechnet die Laut-Ähnlichkeit eines Strings
- similar_text() - Berechnet die Ähnlichkeit zweier Zeichenketten
- metaphone() - Berechnet den Metaphone-Schlüssel eines Strings

`↑` and `↓` to navigate • `Enter` to select • `Esc` to close • `/` to open