machine-learning - 将 Levenshtein 距离转换为错误率

Question

他们是一种将莱文斯坦距离转换为错误率的方法吗？

错误率是序列中不完全相同的部分。

Answer 1

您的意思是要将 Levenshtein 距离标准化为 [0, 1]？那是

d(a,b) / max(len(a), len(b))

分母是 Levenshtein 距离的上限，因此这给出了一个介于 0 和 1 之间的数字。证明：假设（不失一般性）len(a) > len(b)，那么你总是可以通过替换字符和删除它们来转换a为，总共操作。blen(b)len(a) - len(b)len(a) - len(b) + len(b) = len(a)