我有一个问题，我们可以通过将 e.d 值除以两个字符串的长度来归一化 levenshtein 编辑距离吗？ 我问这个是因为，如果我们比较两个长度不等的字符串，那么两者的长度之差也会被计算在内。 例如: ed('has a', 'has a ball') = 4 and ed('has a', 'has a ball the is round') = 15. 如果我们增加字符串的长度，即使它们相似，编辑距离也会增加。 因此，我无法设置一个值，一个好的编辑距离值应该是多少。
最佳答案
是的，归一化编辑距离是将字符串之间的差异放在从“相同”到“没有共同点”的单一尺度上的一种方法。
需要考虑的几件事:
- 归一化距离是否能更好地衡量字符串之间的相似性取决于应用。如果问题是“这个词有多大可能是那个词的拼写错误？”，规范化是一种可行的方法。如果是“此文档自上一版本以来更改了多少？”，原始编辑距离可能是更好的选择。
- 如果您希望结果在
[0, 1]范围内，您需要将距离除以给定长度的两个字符串之间的最大可能距离。即，LCS distance 的length(str1)+length(str2)和max(length(str1), length(str2))对于 Levenshtein distance . - 归一化距离不是度量标准，因为它违反了 triangle inequality .
关于algorithm - 归一化编辑距离，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45783385/