为什么“最长公共子序列”问题不允许使用编辑距离方法进行替换

Question

编辑距离是一类著名的问题，包括：

不同类型的编辑距离允许不同的字符串组 运营。例如：

1. 编辑距离允许删除、插入和替换。
2. 最长公共子序列（LCS）距离只允许插入和删除，不允许替换。
3. 汉明距离只允许替换。因此，它仅适用于相同长度的字符串。
4. Damerau-Levenshtein 距离允许插入、删除、替换以及两个相邻的转置（交换） 角色。
5. Jaro 距离仅允许换位。

来源

它提到：

最长公共子序列（LCS）距离只允许插入和删除，不允许替换。

我的疑问：

1. 我很困惑为什么它不允许替换。据我了解该算法，如果有一个字符可以与目标字符串中的字符“潜在”匹配，则它不会被替换或删除。

为什么允许删除和插入？难道不会出现匹配字符因为出现在目标字符串的后面而被删除的情况吗？
我很难理解这一点。出于分析目的，我编写了一个

算法

，它在网格中显示解决方案，如下所示（它以颜色显示轨迹，但无法在 SO 上显示）：

$ java dynamic_programming.EditDistance republicans democrats true
|  |  |d |e |m |o |c |r |a |t |s |
|  |0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |
|r |1 |2 |3 |4 |5 |6 |5 |6 |7 |8 |
|e |2 |3 |2 |3 |4 |5 |6 |7 |8 |9 |
|p |3 |4 |3 |4 |5 |6 |7 |8 |9 |10|
|u |4 |5 |4 |5 |6 |7 |8 |9 |10|11|
|b |5 |6 |5 |6 |7 |8 |9 |10|11|12|
|l |6 |7 |6 |7 |8 |9 |10|11|12|13|
|i |7 |8 |7 |8 |9 |10|11|12|13|14|
|c |8 |9 |8 |9 |10|9 |10|11|12|13|
|a |9 |10|9 |10|11|10|11|10|11|12|
|n |10|11|10|11|12|11|12|11|12|13|
|s |11|12|11|12|13|12|13|12|13|12|
=========================
12 // (New Edit Distance, Without Substitution)

Answer 1

  for j from 1 to n:
    for i from 1 to m:
      if s[i] = t[j]:
        substitutionCost := 0
      else:
        substitutionCost := 1

      d[i, j] := minimum(d[i-1, j] + 1,                   // deletion
                         d[i, j-1] + 1,                   // insertion
                         d[i-1, j-1] + substitutionCost)  // substitution

对于 Levenshtein 距离，允许替换，因此如果 

s[i] != t[j]

那么我们实际上应该在这里使用替换，因为它会产生 1 个单位的成本（换句话说，

d[i][j] - d[i-1][j-1] <= 1

）。然而，在 LCS 距离中，您可能会观察到不允许替换，并且

d[i][j] - d[i][j] <= 2

，推断从 d[i-1][j-1] 到 d[i] 可能会产生最多 2 的成本[j].如果您想象 LCS 的可追踪版本，这对于 LCS 来说直观上是正确的。让

s = "abcd", t = "abce"

，考虑

d[4][4]

。你不能神奇地转到 abcd -> abce，但你必须执行两次操作 abcd -> abc -> abce。可以看出LCS距离=|s| + |t| - 2LCS(s, t) = 4 + 4 - 3 = 2，这表明不允许替换时结果是一致的。