algorithm - 插入、删除和替换有什么区别

Question

我即将解决关于 Levenshtein 距离的编程问题。根据我的工作表上给出的定义，它指出 Lenveshtein 距离等于两个字符串之间的替换、插入和删除的数量。但是，替换不只是删除然后插入吗？我在这里想念什么？

Answer 1

可以通过插入加删除来实现替换的效果，是的。但是，如果您仅将自己限制为插入和删除，则以这种方式创建的每个此类“替换”都会花费您 2 而不是 1。这对于某些应用程序来说可能是现实的，但有时假设替换成本相同/与插入或删除一样可能，而不是成本的两倍/一半。

[编辑]

事实上，发明比标准 Levenshtein 距离更通用的编辑距离是可能的，有时也很有用。您可以为插入、删除和替换赋予任意成本。您甚至可以扩展操作集以包括转置（更改ab为ba对于某些固定成本）或块操作（对于某些固定成本，“插入从位置 i 开始的长度为 j 的子字符串的副本”）。转置的效果当然可以在没有使用删除加插入的特殊“转置”移动的情况下实现，但这再次导致移动的成本高于单独的删除或插入。如果您的应用程序是您想找到一个人在键入一个不在字典中的单词时最有可能“表示”的英语单词，您可能更愿意使用换位成本较低的距离，因为这是一个常见的打字错误。