Levenshtein（编辑）距离的标准化差异？

Question

如果两个字符串之间的Levenshtein距离，s并且t由下式给出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距离Wikipedia页面建议使用规范化方法2，但没有提及方法1。这两种方法是否同样有效？只是想知道是否有数学上的理由来使用一种方法。

另外，方法1和方法3有什么区别？

用下面的例子：

s = "Hi, my name is"

t = "Hello, my name is"

L(s,t) = 4

length(s) = 14 （包括空格）

length(t) = 17 （包括空格）

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

1. 4 /（14 + 17）= 0.129

2. 4 /（17）= 0.235

3. （4 * 2）/（14 + 17）= 0.258

Answer 1

两种变体的效果应该几乎相同。第二项涵盖从零（字符串相等）到一（完全不同）的范围，而第一个变体中的上限取决于字符串的长度。如果长度几乎相等，则上限为 0.5，并且随着长度之间的较大差异而增加。