string - Levenshtein 距离和三角不等式

Question

我对 Levenshtein 距离和三角不等式感到困惑。维基百科和其他文章说 Levenshtein 距离遵循三角不等式。

三角不等式状态x+y>z，但对于 Levenshtein 距离，在我看来x+y可以等于z。例如kitten-> sitting=3，kitten->sittin=2和sittin->sitting=1。我在这里想念什么？

编辑

三角不等式不在欧几里德空间，而是在度量空间。在度量空间中，三角不等式是d(x,z)<= d(x,y)+d(y,z)

Answer 1

三角不等式状态x+y>=z。

Answer 2

我想提一下，很多任务都使用了归一化的 Levenshtein 距离，反之亦然。像长度为 4 和 10 的单词之间的距离 2 意味着更多 50% 和 80% 的相似度。在很多情况下，归一化的 Levenshtein 距离不满足三角不等式。因此，从数学的角度来看，它不是一个度量。

然而，可以通过对 Levenshtein 距离的正确归一化来实现三角不等式。

Let be Generic Levenshtein Distance (GLD) 是归一化的 Levenshtein 距离。GLD 是一个在 [0, 1] 中取值的度量。给定长度为 |X| 的两个字符串 X 和 Y 和 |Y|。归一化方程如下：

GLD(X,Y) = 2*d(X,Y) / (|X|,|Y| + d(X,Y))

其中 d(X,Y) 是列文斯坦距离。

这种归一化满足文章 [1] 的结果的三角形不等式。

我还在我创建的 Nuget 包中使用了 - BlueSimilarity[2] 通用归一化，它违反了三角不等式 (1 - d(X,Y)/max(|X|,|Y|))。

你的例子

X =“小猫”，Y =“坐着”，Z =“坐着”

GLD(X,Z) <= GLD(X,Y)+ GLD(Y,Z)

2* d(X,Y) / (|X|,|Y| + d(X,Y)) + 2* d(Y,Z) / (|Y|+|Z| + d(Y,Z) ) >= 2*d(X,Z) / (|X|,|Z| + d(X,Z))

2 3 /(6+7+3) + 1 - 2 1/(6+7+1) >= 2*2/(6+6+2)

0.375 + 0.143 >= 0.286

参考：

[1] 李玉健，刘波；归一化的 Levenshtein 距离度量；IEEE 模式分析和机器智能汇刊，2007

[2] 罗齐内克，翁德雷；蓝色相似度； https://www.nuget.org/packages/BlueSimilarity/