相关疑难解决方法(0)

我是在回答你自己的问题的精神发表这篇文章的.

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

只是关于性能的说明:这件事非常快.在我的桌面上(2.33 Ghz双核,2GB内存,WinXP),我可以在不到一秒的时间内完成100K字符串的数组运行.

我有一个字符串列表,其中一些字符串自我之前的版本以来已被修改过.一些变化是微不足道的(间隔,一个字等).我想检测只有"轻微"差异的字符串,这样我就可以尝试使用旧的翻译.

"微小差异"是什么意思？在我开始使用数据库之前,我不会知道.

你知道任何可调节的例程,它们将指示两个字符串何时相似但不相同？任何会返回一个数字的例程,表示两个字符串的不同之处？

对于Levenshtein算法,我发现了Delphi的这个实现.

我需要一个版本,一旦达到最大距离就停止,并返回到目前为止找到的距离.

我的第一个想法是在每次迭代后检查当前结果:

for i := 1 to n do
    for j := 1 to m do
    begin
      d[i, j] := Min(Min(d[i-1, j]+1, d[i,j-1]+1), d[i-1,j-1]+Integer(s[i] <> t[j]));

      // check   
      Result := d[n, m];
      if Result > max then
      begin
        Exit;
      end; 

    end;