两个字符串之间的删除距离

Question

我有困难理解这个问题的算法。我将粘贴问题描述和我的求解方法，尽管它不是正确的解决方案。这类似于编辑距离算法，我使用了相同的方法，但有些不对劲，我无法确定确切的原因。

两个字符串之间的删除距离是你需要在这两个字符串中删除的字符的ASCII值的最小总和，以便得到相同的字符串。cat和at之间的删除距离为99，因为你只需删除cat的第一个字符，并且'c'的ASCII值为99。cat和bat之间的删除距离为98 + 99，因为你需要删除两个单词的第一个字符。当然，两个字符串之间的删除距离不能大于它们的总ASCII值之和，因为你可以完全删除这两个字符串。实现一个高效的函数来查找两个字符串之间的删除距离。如果需要，您可以参考维基百科上关于编辑距离算法的文章，那里的算法与此处所需的算法不完全相同，但很相似。

这是我的代码。我使用了动态规划的方法。我认为最后一个“else”后面的一行需要更改，但请随意纠正任何错误。

def delete_distance(s1, s2):
    m = [[0 for j in range(len(s2)+1)] for i in range(len(s1)+1)]
    for i in range(len(s1)+1):
        for j in range(len(s2)+1):
            if i == 0:
                m[i][j] = sum(bytearray(s2[:j]))
            elif j == 0:
                m[i][j] = sum(bytearray(s1[:i]))
            elif s1[i-1] == s2[j-1]:
                m[i][j] = m[i-1][j-1]
            else:
                m[i][j] = ord(s1[i-1]) + ord(s2[j-1]) + min(m[i-1][j-1], m[i-1][j], m[i][j-1])
    return m[len(s1)][len(s2)]

我知道这是错误的，因为delete_distance('cat', 'cbat')的输出结果是197，而正确结果应该是98，因为我们只需要删除ASCII值为98的字母 b。

- user1967422

Answer 1

如前面Ken Y-N所说的，else部分应该是最少3个操作成本。这个答案唯一的变化是：它被重新表述以适应你的问题。

这3个操作是：

- S1删除 - S2删除 - S1和S2都删除

以下应该可以解决问题 - 我猜：

def delete_distance(s1, s2):
    m = [[0 for j in range(len(s2)+1)] for i in range(len(s1)+1)]
    for i in range(len(s1)+1):
        for j in range(len(s2)+1):
            if i == 0:
                m[i][j] = sum(bytearray(s2[:j]))
            elif j == 0:
                m[i][j] = sum(bytearray(s1[:i]))
            elif s1[i-1] == s2[j-1]:
                m[i][j] = m[i-1][j-1]
            else:
                s1del = ord(s1[i-1])
                s2del = ord(s2[j-1])
                s1s2del = s1del + s2del
                m[i][j] = min(m[i-1][j-1] + s1s2del, m[i-1][j] + s1del, m[i][j-1] + s2del)
    return m[len(s1)][len(s2)]

希望这能有所帮助！

- arunk2

Answer 2

看了一下相关的维基页面，我发现最后一个else:应该是到目前为止距离的最小值，再加上插入/删除/替换的成本。因此，重新计算这个术语并使用中间值，希望能更好地说明这一点，我们得到：

else:
    wdel = ord(s1[i-1])
    wins = ord(s2[j-1])
    wsub = wdel + wins
    m[i][j] = min(m[i-1][j-1] + wsub, m[i-1][j] + wdel, m[i][j-1] + wins)

请注意，如果您使用wdel = wins = wsub = 1和m[i][j] = len(s1)或s2，您将得到经典的Levenshtein距离。

- Ken Y-N

---

这似乎是正确的，稍作修改即可。第一个字符串或第二个字符串中的字符被删除，或者两者都被删除，正如Arun Kumar所述。将wdel和wins更改为s1del和s2del，或类似的名称，将清楚地显示算法应该执行的操作。 谢谢，Ken Y-N！现在一切都清楚了。 - user1967422

啊，我明白了，原来只是删除操作；正如@Arun所说，他们使用了正确的术语和变量名，尽管效果相同，但另一个答案更好。 - Ken Y-N