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;