首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >如何在Delphi中实现Levenshtein距离?

如何在Delphi中实现Levenshtein距离?
EN

Stack Overflow用户
提问于 2008-09-10 17:38:05
回答 1查看 4.6K关注 0票数 20

我是本着回答你自己的问题的精神来发布这篇文章的。

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

只需注意一下性能:这东西非常快。在我的台式机(2.33ghz双核,2 2GB内存,WinXP)上,我可以在不到一秒的时间内处理100K字符串数组。

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2008-09-10 17:38:16

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;
票数 17
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/54797

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档