编辑距离是一类著名的问题,包括:
不同类型的编辑距离允许不同的字符串组 运营。例如:
- 编辑距离允许删除、插入和替换。
- 最长公共子序列(LCS)距离只允许插入和删除,不允许替换。
- 汉明距离只允许替换。因此,它仅适用于相同长度的字符串。
- Damerau-Levenshtein 距离允许插入、删除、替换以及两个相邻的转置(交换) 角色。
- Jaro 距离仅允许换位。
它提到:
最长公共子序列(LCS)距离只允许插入和删除,不允许替换。
我的疑问:
我很困惑为什么它不允许替换。据我了解该算法,如果有一个字符可以与目标字符串中的字符“潜在”匹配,则它不会被替换或删除。
,它在网格中显示解决方案,如下所示(它以颜色显示轨迹,但无法在 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)
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[ 可能会产生最多 2 的成本我][j]。如果您想象 LCS 的可追踪版本,这对于 LCS 来说直观上是正确的。让s = "abcd", t = "abce"
,考虑
d[4][4]
。
如果不允许替换,你就不能神奇地走到abcd -> abce,而是必须进行两次操作abcd -> abc -> abce,成本是2。