c++ - 更快的编辑距离算法

Closed. This question needs to be more focused。它当前不接受答案。












想改善这个问题吗？更新问题，使其仅关注editing this post的一个问题。

6年前关闭。



Improve this question




问题:我知道琐碎的编辑距离DP公式和O(mn)中分别针对大小为n和m的2个字符串的计算。但是我最近才知道，如果我们只需要计算编辑距离f的最小值并且以| f |
如果这是基于DP的，请说明其背后的dp公式，或说明算法。

查看以下内容的improved algorithm部分
链接:http://en.wikipedia.org/wiki/Edit_distance。

关于改进的UKKONEN算法http://www.berghel.net/publications/asm/asm.php的另一个链接

提前致谢。

最佳答案

您可以使用下一个简单的想法以O(min(n，m)* s)时间计算编辑距离:

考虑DP表中的第i个字符串。

因此，如果我们知道答案
例如，假设我们知道，“abacaba”和“baadba”之间的编辑距离小于3。

因此，我们可以跳过红色单元格，因为它们的值大于s。

算法O(min(n，m)* s)的渐近性，因为我们在主对角线的左侧和右侧计算了s个像元。