莱文斯坦距离极限 [英] Levenstein distance limit

问题描述

如果我有一些我不想超过的距离。例子=2。
我可以在算法完全完成之前就知道最小的允许距离吗？

If I have some distance which I do not want to exceed. Example = 2. Do I can break from algoritm before its complete completion knowing the minimum allowable distance?

也许有类似的算法可以完成它

Perhaps there are similar algorithms in which it can be done.

我有必要减少工作程序的时间。

It is necessary for me to reduce the time of work programs.

推荐答案

如果您执行自上而下的动态编程/递归+记忆，则可以将当前大小作为附加参数传递，如果超过2，则尽早返回。但是我认为这样做会很无效率，因为您将重新访问状态。

If you do top-down dynamic programming/recursion + memoization, you could pass the current size as an extra parameter and return early if it exceeds 2. But I think this will be inefficient because you will revisit states.

如果您执行自下而上的dp，则将逐行填充（只需保留最后一行和当前行）。如果最后一行的条目仅大于2，则可以提前终止。

If you do bottom-up dp, you will fill row by row (you only have to keep the last and current row). If the last row only has entries greater than 2, you can terminate early.

根据我的评论修改源代码：

Modify your source code according to my comment:

for (var i = 1; i <= source1Length; i++)
{
                for (var j = 1; j <= source2Length; j++)
                {
                    var cost = (source2[j - 1] == source1[i - 1]) ? 0 : 1;

                    matrix[i, j] = Math.Min(
                        Math.Min(matrix[i - 1, j] + 1, matrix[i, j - 1] + 1),
                        matrix[i - 1, j - 1] + cost);
                }
                // modify here:
                // check here if matrix[i,...] is completely > 2, if yes, break

}

这篇关于莱文斯坦距离极限的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！