设计一个算法来计算两个字符串之间的编辑距离

Question

请考虑以下问题：

两个字符串s和t的编辑距离是将s转换为[=12=所需要的单个字符操作（插入、删除、替换）的最少次数].设 m 和 n 为字符串 s 和 t.

的长度

设计一个O(nm)时间和O(nm)space算法来计算s和t之间的编辑距离。

我的想法：

一次只比较两个字符串一个字符不是更容易吗:

L = maximum(length(s), length(t))
for i in L:
   if i > length(s):
      distance += length(t) - i
      break
   if i > length(t):
      distance += length(s) - i
      break
   if s[i] != t[i]:
      distance += 1

如果我错了，那么我是否应该使用编辑距离算法table？是这样，我如何设计一个O(nm)时间和O(nm)space算法？

Answer 1

考虑字符串 abcd 和 bcd。它们因一次删除而不同，但您的方法会将它们计为距离 4。

你要做的是找到最长公共子序列。这是一个众所周知的问题，您可以 google 举出很多关于它的代码示例，其中一个解决方案实际上是 O (NM)。

例如，对于字符串 abcdqef 和 xybcdzzzef，LCS 是 bcdqef。考虑两个字符串中的子序列：

a-bcd-q-ef
xy-bcd-zzz-ef

可以把a改成xy一改一插，q改成zzz一改二插。仔细想想，需要的操作次数（即距离）就是最长不属于LCS的字符串的字符数。

Answer 2

感谢@Roberto Attias 的回答，但以下是我正在寻找的完整算法：

L1 = length(string1)
L2 = length(string2)
for i in L1:
    table[i][0] = i
for i in L2:
    table[0][i] = i
for i in L1:
    for j in L2:
        m = minimum(table[i-1][j],table[i][j-1])+1
        if s[i] == t[j]: subvalue = 1
        else: subvalue = 0
        table[i][j] = minimum(m, table[i-1][j-1] + subvalue)
return table[L1][L2]

以上算法遵循编辑距离算法的策略table

设计一个算法来计算两个字符串之间的编辑距离

Designing an algorithm to calculate the edit distance between two strings

string

algorithm

big-o

edit

distance