Dislaimer | Kontakt | Sitemap

Hintergrund

Du bist hier: Tips » Scripte » PHP
PHP
Referenzliste

levenshtein
String-Funktionen

    Befehl:
int levenshtein ( string $str1 , string $str2 )

int levenshtein ( string $str1 , string $str2 , int $cost_ins , int $cost_rep , int $cost_del )


    Parameter-Liste:
NameBeschreibung
str1Eine der Zeichenketten, für die die Levenshtein-Distanz zu berechnen ist.
str2Eine der Zeichenketten, für die die Levenshtein-Distanz zu berechnen ist.
cost_insDefiniert die Kosten des Einfügens.
cost_repDefiniert die Kosten des Ersetzens.
cost_delDefiniert die Kosten des Löschens.

    Rückgabewerte:
Die Funktion gibt die Levenshtein-Distanz zwischen den beiden Argument-Strings oder -1 zurück, sofern eines der Argumente länger als 255 Zeichen ist.

    Beschreibung:
Die Levenshtein-Distanz bezeichnet die minimale Anzahl von Zeichen, die Sie ersetzen, einfügen oder löschen müssen, um str1 in str2 umzuwandeln. Die Komplexität des Algorithmus ist 0(m*n), wobei n und m die Länge von str1 und str2 darstellen (deutlich besser, wenn man mit similar_text() vergleicht, was mit 0(max(n,m)**3) daher kommt, aber trotzdem immer noch teuer).

In ihrer einfachsten Form erhält die Funktion nur die zwei Strings als Parameter und berechnet nur die Anzahl der Einfügungen, Ersetzungen und Löschungen, die benötigt werden, um str1 in str2 zu überführen.

Eine zweite Variante verwendet drei zusätzliche Parameter, die die Kosten von Einfügungen, Ersetzungen und Löschungen festlegen. Dies ist eine allgemeingültigere und anpassungsfähigere Version als Variante eins, aber nicht so effizient.


    Aktiv in Version:
(PHP 4 >= 4.0.1, PHP 5, PHP 7)

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

levenshtein() - Beispiel:

Eingabe: 
<?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";
}

?>


Ausgabe:
Eingegebenes Word: carrrot
Meinten Sie: carrot?
levenshtein() - Beispiel 2:

Eingabe: 
<?PHP
$var_1 = 'Müller';
$var_2 = 'Füller';
$var_3 = 'ranke';
$var_4 = 'schlanke';
echo 'Um aus ' . $var_1 . ' ' . $var_2 . ' zu machen, wird ' .
     levenshtein ( $var_1, $var_2 ) . ' Vorgang benötigt.<br>';
echo 'Um aus ' . $var_3 . ' ' . $var_4 . ' zu machen, werden ' .
     levenshtein ( $var_3, $var_4 ) . ' Vorgänge benötigt.';
?>


Ausgabe:
Um aus M�ller F�ller zu machen, wird 1 Vorgang ben�tigt.
Um aus ranke schlanke zu machen, werden 4 Vorg�nge ben�tigt.

Beschreibung:
Mit levenshtein() kann man den Unterschied zweier Strings (str1 und str2) berechnen. Dabei wird berechnet, wie viele Vorg�nge (Einf�gen, Austauschen oder L�schen) ben�tigt werden, um aus dem ersten String (str1) den zweiten String (str2) zu erzeugen. Sollte einer der Strings l�nger als 255 Zeichen sein, so wird -1 zur�ckgegeben.
lcfirst
String-Funktionen