DelphiでLevenshtein距離をどのように実装しますか？

Question

私はあなた自身の質問に答える精神でこれを掲示しています。

質問：2つの文字列間の編集距離を計算するためのLevenshteinアルゴリズムを実装するには、どうすればよいですか？described here、Delphi？

パフォーマンスに関するメモ： このことは非常に高速です。私のデスクトップ（2.33GHzデュアルコア、2GB RAM、WinXP）では、1秒未満で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;