归一化编辑距离

Question

我有一个问题，我们可以用ed值除以两个字符串的长度来归一化levenshtein编辑距离吗？我之所以这样问是因为，如果我们比较两个长度不相等的字符串，那么两个长度之间的差异也将被计算在内。例如：ed（'has a'，'has a ball'）= 4，而ed（'has a'，'has a ball the round'）=15。如果我们增加字符串的长度，则编辑距离即使它们相似，也会增加。因此，我无法设置一个值，好的编辑距离值应该是多少。

Answer 1

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

需要考虑的几件事：

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

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 表示完全匹配。