Levenshtein-Distanz Suchmaschinenanmeldung Suchmaschieneneintrag

Levenshtein-Distanz

Hier der Sourecode für Delphi und PHP:

PHP

(PHP 3 >= 3.0.17, PHP 4 >= 4.0.1, PHP 5)

levenshtein -- Berechnet den Levenshtein-Unterschied zweier Strings
Beschreibung:
int levenshtein ( string str1, string str2 )

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

int levenshtein ( string str1, string str2, function cost )

Diese Funktion errechnet die Differenz zwischen den als Argumente übergebenen zwei Strings. Ist einer der Strings länger als die zulässigen 255 Zeichen, wird -1 zurück gegeben.

Die Levenshtein-Differenz ist definiert als die minimale Anzahl an Zeichen, die ersetzt, eingefügt oder gelöscht werden müssen um den str1 nach str2 umzusetzen. Die Komplexität des Algorithmus ist O(m*n), wobei n und m der Länge der Strings str1 und str2 (viel besser als bei der Funktion similar_text(), wo sie O(max(n,m)**3) beträgt).

Siehe auch soundex(), similar_text() und metaphone().

Delphi 4, Delphi 5, Delphi 6, Delphi 7

function TKeywordForm.Levenshtein(const str1, str2: string): integer;
var
   delta: array of integer;
   len1, len2: integer;
   idx1, idx2: integer;
   clast, cnew: integer;
begin
   len1 := Length(str1);
   len2 := Length(str2);
   if (len1 = 0) and (len2 = 0) then
     Result := 0
   else if (len1 = 0) or (len2 = 0) then
     Result := 100
   else
   begin
     SetLength(delta, len2 + 1);

   for idx2 := 0 to len2 do
     delta[idx2] := idx2;

   for idx1 := 1 to len1 do
   begin
     clast := delta[0];
     delta[0] := idx1;

     for idx2 := 1 to len2 do
     begin
       cnew := clast + Ord(str1[idx1] <> str2[idx2]);
         if delta[idx2] + 1 < cnew then
         cnew := delta[idx2] + 1;
         if delta[idx2 - 1] + 1 < cnew then
         cnew := delta[idx2 - 1] + 1;
         clast := delta[idx2];
         delta[idx2] := cnew;
     end;
     end;

   Result := delta[len2] * 100 div len2;
   end;
  end;