levenshtein

[PHP]

Berechnet die Levenshtein-Distanz zwischen zwei Strings

Die Levenshtein-Distanz bezeichnet die minimale Anzahl von Zeichen, die Sie ersetzen, einfügen oder löschen müssen, um str1in str2umzuwandeln. Die Komplexität des Algorithmus ist 0(m*n), wobei n undm die Länge von str1undstr2darstellen (deutlich besser, wenn man mit similar_text() vergleicht, was mit 0(max(n,m)**3) daherkommt, aber trotzdem immer noch teuer).




Beispiel:

// 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