标准化编辑距离

Question

我有一个问题，我们能否通过将编辑距离（levenshtein edit distance）的值除以两个字符串的长度来进行归一化呢？ 我之所以问这个问题是因为，如果我们比较两个长度不相等的字符串，那么它们长度之间的差异也会被计算在内。 例如： ed('has a', 'has a ball') = 4 和 ed('has a', 'has a ball the is round') = 15。 如果我们增加字符串的长度，即使它们相似，编辑距离也会增加。 因此，我无法确定一个好的编辑距离应该是什么数值。

- Naufal Khalid

Answer 1

是的，对编辑距离进行归一化是将字符串之间的差异放在从“相同”到“没有共同点”的单一尺度上的一种方法。

需要考虑以下几点：

1. 是否归一化距离更好地衡量字符串之间的相似性取决于应用。如果问题是“这个单词很可能是那个单词的拼写错误吗？”，则归一化是一个好方法。如果问题是“自上次版本以来该文档变化了多少？”，原始编辑距离可能是更好的选择。
2. 如果希望结果在区间[0, 1]内，则需要将距离除以给定长度的两个字符串之间的最大可能距离。即对于LCS距离是length(str1)+length(str2)，对于Levenshtein距离是max(length(str1), length(str2))。
3. 归一化距离不是一个度量，因为它违反了三角不等式。

- Anton

---

我想做的是根据单词的编辑距离进行排名，所以在我的情况下，标准化的编辑距离更好。如果它违反了三角不等式，是否有更好的方法来找到它？我正在阅读一些论文，例如：标准化编辑距离，但不理解所使用的算法。谢谢！ - Naufal Khalid

@NaufalKhalid 违反三角不等式并不一定是问题，尤其是如果你只关心成对差异（而不是，比如一个字符串集合的直径）的话。我会从归一化的Levenshtein距离开始，并且只有在遇到特定问题时才切换到其他方法。 - Anton

@NaufalKhalid，你提供的论文描述了一种不同类型的规范化。虽然距离除以最长字符串的长度可以粗略地描述为“错误率”（每个字符的差异数），但距离除以编辑路径的长度可以衡量平均错误的严重程度。如果你的Levenshtein距离变化中所有操作的成本相同，则对于所有非相同的字符串，“W(P)/L(P)”将是相同的。 - Anton

好的，我明白了。谢谢！ - Naufal Khalid

为什么这种方法比 fDist = float(len - levenshteinDistance(s1, s2)) / float(len) 更好呢？看起来这里是在说 normalizedLevensteinDistance 是 levenshteinDistance(s1, s2)/max(s1.length(), s2.length())？ - Exploring

Answer 2

我成功地使用了以下内容:

len = std::max(s1.length(), s2.length());
// normalize by length, high score wins
fDist = float(len - levenshteinDistance(s1, s2)) / float(len);

然后选择最高分。1.0表示完全匹配。

- Martin

---

只是想指出，这将输出限制在0和1之间，因为Levenshtein距离永远不会大于最长字符串的长度（也不会小于零）。除非您改变更改的成本（某些应用程序可能会认为添加字符比编辑字符更改了字符串，并使用修改后的算法）。 - grofte

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

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

上述函数中的变量m可以根据您的应用程序替换为较长字符串的长度。

- Sam Tseng