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

Question

问题：我知道两个大小分别为 n 和 m 的字符串在 O(mn) 中的微不足道的编辑距离 DP 公式和计算。但是我最近才知道，如果我们只需要计算编辑距离f的最小值并且它是有界的|f|<=s，那么我们可以在O(min(m,n) + s^2)中计算它或 O(s*min(m,n)) [wikipedia] 时间。

如果这是基于 DP 的，请解释其背后的 dp 公式或解释算法。

查看链接improved algorithm部分 ： http ://en.wikipedia.org/wiki/Edit_distance 。

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

提前致谢。

Answer 1

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

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

因此，如果我们知道答案 <= s，那么我们就会对坐标为 (i, i - s)、(i, i - s + 1)、...、(i, i + s) 的单元格感兴趣。因为在其他单元格中，答案严格大于 s。

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

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

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