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

Question

对于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;

Answer 1

我收集你想要的是找到levenstein距离,如果它在下面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;