Levenshtein算法 - 如果编辑距离大于给定阈值，则快速失败

Question

对于Levenshtein算法，我找到了this implementation for 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; 

Answer 1

我收集你想要的是找到编辑距离，如果低于MAX，对不对？

如果是这样，达到一个大于MAX的值是不够的，因为它只意味着一些路径比那更长，但不是不存在更短的路径。为了确保找不到比MAX短的路径，必须监视直到当前点的路径的最小可能长度，即距离表中列的最小值。

我不擅长德尔福，但我认为代码应该是这个样子：

for i := 1 to n do 
begin; 
    min := MAX + 1 
    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])); 
     min := Min(min, d[i,j]) 
    end; 
    if min >= MAX then 
     Exit; 
end;