如何在Delphi中实现Levenshtein距离？

Question

我在回答你自己的问题的精神发布这个。

我的问题是：如何在Delphi中实现用于计算两个字符串之间编辑距离的Levenshtein算法，如described here？

只是关于性能的说明： 这件事情非常快。在我的桌面上（2.33 Ghz双核，2GB内存，WinXP），我可以在不到一秒的时间内运行100K字符串。

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;