Wie implementieren Sie Levenshtein Distanz in Delphi?

Question

Ich poste dies im Geiste der Beantwortung Ihrer eigenen Fragen.

Die Frage, die ich hatte, war: Wie kann ich den Levenshtein-Algorithmus zur Berechnung der Bearbeitungs-Abstand zwischen zwei Strings, wie described here, in Delphi?

Nur eine Anmerkung zur Leistung: Dieses Ding ist sehr schnell. Auf meinem Desktop (2.33 Ghz Dual-Core, 2GB RAM, WinXP) kann ich in weniger als einer Sekunde ein Array von 100K-Strings durchlaufen.

Answer 1

function EditDistance(s, t: string): integer; 
var 
    d : array of array of integer; 
    i,j,cost : integer; 
begin 
    { 
    Compute the edit-distance between two strings. 
    Algorithm and description may be found at either of these two links: 
    http://en.wikipedia.org/wiki/Levenshtein_distance 
    http://www.google.com/search?q=Levenshtein+distance 
    } 

    //initialize our cost array 
    SetLength(d,Length(s)+1); 
    for i := Low(d) to High(d) do begin 
    SetLength(d[i],Length(t)+1); 
    end; 

    for i := Low(d) to High(d) do begin 
    d[i,0] := i; 
    for j := Low(d[i]) to High(d[i]) do begin 
     d[0,j] := j; 
    end; 
    end; 

    //store our costs in a 2-d grid 
    for i := Low(d)+1 to High(d) do begin 
    for j := Low(d[i])+1 to High(d[i]) do begin 
     if s[i] = t[j] then begin 
     cost := 0; 
     end 
     else begin 
     cost := 1; 
     end; 

     //to use "Min", add "Math" to your uses clause! 
     d[i,j] := Min(Min(
       d[i-1,j]+1,  //deletion 
       d[i,j-1]+1),  //insertion 
       d[i-1,j-1]+cost //substitution 
       ); 
    end; //for j 
    end; //for i 

    //now that we've stored the costs, return the final one 
    Result := d[Length(s),Length(t)]; 

    //dynamic arrays are reference counted. 
    //no need to deallocate them 
end;