算法 – 如何在Delphi中实现Levenshtein距离？

概述我本着回答自己的问题的精神发贴。 我的问题是：如何在Delphi中实现Levenshtein算法来计算两个字符串之间的编辑距离，如described here？ 只是一个关于表演的笔记： 这件事非常快。在我的桌面(2.33 Ghz双核，2GB RAM，WinXP)上，我可以在不到一秒钟内运行一个100K字符串的数组。 function EditDistance(s, t: string): int 我本着回答自己的问题的精神发贴。

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

只是一个关于表演的笔记：
这件事非常快。在我的桌面(2.33 Ghz双核，2GB RAM，WinXP)上，我可以在不到一秒钟内运行一个100K字符串的数组。

解决方法

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 themend;

总结

以上是内存溢出为你收集整理的算法 – 如何在Delphi中实现Levenshtein距离？全部内容，希望文章能够帮你解决算法 – 如何在Delphi中实现Levenshtein距离？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。