string - Levenshtein 距离是否与最大公共子序列有关？
问题描述
我没有证据，但我有直觉，假设 s1 是需要转换为 s2 的字符串，那么我们可以保持 s1 中最大的公共子序列原样，编辑距离是我们需要替换/删除的元素数量/插入。
For example : s1 = "adjsjvnejnv"
s2 = "djpppne"
这里LCS是“djne”，现在我们需要删除“djne”右侧的3个元素字符串“jnv”，我们可以将s1中的“sjv”替换为“ppp”，我们可以从s1中删除“a”。所以总编辑距离是 3+3+1 = 7 。
想法是替换或删除 LCS 元素之间的元素，并从 LCS 的左右部分添加或删除元素。
我无法证明这一点。有人可以提供反例或证明吗？
请注意，我不是在谈论 LCS 距离（涉及删除和插入），我在谈论 LCS 并说我们可以在序列和序列的左右两侧之间填充/替换/删除。
解决方案
是的。
Levenshtein 和 LCS 距离都是称为编辑距离的一组距离的一部分。
- LCS 距离允许在字符串中插入和删除。
- Levenshtein 距离允许在字符串中插入、删除和替换。
它们都可以使用Wagner-Fischer 算法（最初由 Damerau 于 1964 年出版）计算，这是一种动态规划算法，用于计算两个字符串之间的编辑距离。
LCS 距离和 Levenshtein 距离之间的唯一区别将是动态规划中使用的最小化“成本函数”。
尽管如此，LCS 比 Levenshtein 距离更容易计算，并且存在几种 LCS 算法利用成本函数的特性来显着提高 LCS 算法的性能。