algorithm - Levenshtein algorithm - fail-fast if edit distance is bigger than a given threshold

Question

For the Levenshtein algorithm I have found this implementation for Delphi.

I need a version which stops as soon as a maximum distance is hit, and return the distance found so far.

My first idea is to check the current result after every iteration:

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可以找到的路径更短的路径，必须监视到当前点的路径的最小可能长度，即距离表中一列的最小值。

我不擅长 Delphi，但我认为代码应该是这样的：

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;