string - Levenshtein 距离与最大公共(public)子序列有关吗？

Question

我没有证据，但我有直觉，假设 s1 是需要转换为 s2 的字符串，那么我们可以保留 s1 中的最大公共(public)子序列，编辑距离是我们需要的元素数替换/删除/插入。

For example : s1 = "adjsjvnejnv"
              s2 = "djpppne"

这里LCS是“djne”，现在我们需要去掉“djne”右边的3个元素字符串“jnv”，我们可以替换“sjv”在 s1 中带有“ppp”，我们可以从 s1 中删除“a”。所以总编辑距离是 3+3+1 = 7 。

想法是在LCS的元素之间替换或删除元素，添加或删除元素来自 LCS 的左右部分。

我无法证明。有人可以提供反例或证明吗？

请注意，我不是在谈论 LCS 距离(涉及删除和插入)，我在谈论 LCS 并说我们可以在序列与序列的左侧和右侧之间填充/替换/删除。

Answer 1

是的，是的。
Levenshtein 和 LCS 距离都是称为 edit distances 的一组距离的一部分。 .

• LCS 距离允许在字符串中插入和删除。
• 编辑距离允许在字符串中插入、删除和替换。

它们都可以使用 Wagner-Fischer algorithm 来计算(最初由 Damerau 于 1964 年发表)是一种计算两个字符串之间的编辑距离的动态规划算法。
LCS 距离和 Levenshtein 距离之间的唯一区别将是动态规划中用于最小化的“成本函数”。

尽管如此，LCS 比 Levenshtein 距离更容易计算，并且存在多种 LCS 算法利用成本函数的特性来显着提高 LCS 算法的性能。