Levenshtein算法 – 如果编辑距离大于给定阈值,则失败快速
发布时间:2020-12-15 09:18:08 所属栏目:大数据 来源:网络整理
导读:对于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
对于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; 解决方法
我收集你想要的是找到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-1]+Integer(s[i] <> t[j])); min := Min(min,j]) end; if min >= MAX then Exit; end; (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |