Levenshtein（编辑）距离归一化的差异？

Difference in normalization of Levenshtein (edit) distance?

如果两个字符串 s 和 t 之间的 Levenshtein 距离由 L(s,t),

给出

以下两种不同的归一化方法对所得启发式的影响有何不同？

  1. L(s,t) / [length(s) + length(t)]

  2. L(s,t) / max[length(s), length(t)]

  3. (L(s,t)*2) / [length(s) + length(t)]

我注意到 Levenshtein distance Wikipedia 页面推荐了归一化方法 2，但没有提及方法 1。这两种方法是否同样有效？只是想知道是否有一些数学上的理由来使用一个而不是另一个。

另外，方法一和方法三有什么区别？

用下面的例子：

s = "Hi, my name is"
t = "Hello, my name is"
L(s,t) = 4
length(s) = 14 # (includes white space)
length(t) = 17 # (includes white space)

上述三种归一化算法给出的 Levenshtein 距离为：

[Approach 1]   4  /(14+17) = 0.129
[Approach 2]   4  /(17)    = 0.235
[Approach 3] (4*2)/(14+17) = 0.258

两种变体的效果应该几乎相同。

  • 第二种方法涵盖了从0（字符串相等）到1（完全不同）...
  • 而第一个变体的上限取决于字符串的长度：如果长度几乎相等，则上限为 0.5，并且随着字符串之间的较大差异而增加长度。