如何将 Levenshtein 距离归一化为 0 到 1

Question

我必须将 0 到 1 之间的 Levenshtein 距离归一化。我看到 SO 中漂浮着不同的变化。

我正在考虑采用以下方法：

如果有两个字符串，s1 和 s2
len = max(s1.length(), s2.length());
normalized_distance = float(len - levenshteinDistance(s1, s2)) / float(len);

那么最高分1.0表示完全匹配，0.0表示不匹配

但我在这里看到了变化： two whole texts similarity using levenshtein distance 其中 1- distance(a,b)/max(a.length, b.length)

Explanation of normalized edit distance formula

我想知道 Java 中是否有规范的代码实现？我知道 org.apache.commons.text 只实现了 LevenshteinDistance 而不是标准化的 LevenshteinDistance。

https://commons.apache.org/proper/commons-text/apidocs/org/apache/commons/text/similarity/LevenshteinDistance.html

Answer 1

您的第一个答案以“两种变体的效果应该几乎相同”开头。归一化 LevenshteinDistance 不存在的原因是因为您（或其他人）认为不适合实施它。此外，一旦有了 Levenshtein 距离，这似乎就变得微不足道了：

private double normalizedLevenshteinDistance(double levenshtein, String s1, String s2) {
    if ((s1.length() > s2.length() || (s1.length() == s2.length()) {
        return levenshtein/s1.length();
    }
    else if (s2.length() > s1.length()) {
        return levenshtein/s2.length();
    }
}

3 天后，一旦它被彻底撕成碎片，我将把它作为 Github 问题添加到 commons-text。

Answer 2

您似乎需要相似度的度量，而不是距离的实际度量。

正确的距离测量应该遵守metric like the Javadoc of the interface EditDistance in Commons Text所说的规则。 Commons Text 不包含标准化 Levenshtein 距离的实现是有原因的。它可以正确完成，但我怀疑结果是否有用。

但是，使用 Levenshtein 距离来定义相似性度量 就像您建议的那样。

Apache Commons Text 已经有一些用于测量相似性的实现。也许 JaroWinklerSimilarity 符合要求。

我会考虑像您建议的那样使用 Levenshtein 距离为 SimilarityScore 接口编写一个实现。它会产生与 JaroWinklerSimilarity 略有不同的结果。将接口用于您自己的实现将允许轻松地将其更改为 Commons Text 提供的任何实现。您可以轻松比较不同的算法。

在检查 max(s1.length, s2.length) 不为零之前，请确保不要除以 max(s1.length, s2.length)！

Answer 3

我使用了我认为非常有用的归一化编辑距离或相似性 (NES)，由 Daniel Lopresti 和 Jiangyin Zhou 在他们工作的等式 (6) 中定义：http://www.cse.lehigh.edu/~lopresti/Publications/1996/sdair96.pdf.

python中的NES是：

import math
def normalized_edit_similarity(m, d):
    # d : edit distance between the two strings
    # m : length of the shorter string
    return ( 1.0 / math.exp( d / (m - d) ) )

print(normalized_edit_similarity(3, 0))
print(normalized_edit_similarity(3, 1))
print(normalized_edit_similarity(4, 1))
print(normalized_edit_similarity(5, 1))
print(normalized_edit_similarity(5, 2))

1.0
0.6065306597126334
0.7165313105737893
0.7788007830714049
0.513417119032592

更多例子可以在上述论文的Table2中找到。

上述函数中的变量 m 可以替换为较长字符串的长度以满足您的需要。

另请参阅：（我还不熟悉如何用相同的答案回答类似的问题）。

如何将 Levenshtein 距离归一化为 0 到 1

How to normalize Levenshtein distance between 0 to 1

java

levenshtein-distance