Comment implémentez-vous la distance Levenshtein dans Delphi?

Question

Je poste ceci dans l'esprit de répondre à vos propres questions.

La question que j'avais était: Comment puis-je implémenter l'algorithme de Levenshtein pour calculer la distance d'édition entre deux chaînes, comme described here, en Delphi?

Juste une note sur la performance: Cette chose est très rapide. Sur mon bureau (2.33 Ghz dual-core, 2Go ram, WinXP), je peux parcourir un tableau de 100K chaînes en moins d'une seconde.

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;