将 SATURDAY 转换为 SUNDAY 的 Levenshtein 距离是 3。一种方法是，删除位置 2 的 A，删除位置 3 的 T，将位置 5 的 R 替换为N.
如果我以仓位编号作为仓位的权重，则成本为:
2 + 3 + 5 = 10
类似地，如果我将 SUNDAY 转换为 SATURDAY，它需要在位置 2 进行 2 次插入，在位置 3 进行 1 次替换，成本将为:
2 + 2 + 3 = 7
如您所见，这个修改后的 Levenshtein 不是对称的。
请注意，位置是相对于原始字符串的，即使在插入之后也是如此。
有没有办法考虑字母的位置，并保持 Levenshtein 对称，以便 lev(x,y) = lev(y,x)？
我看到了一些已经发布的问题，但它们并没有真正帮助: Modifying Levenshtein Distance for positional Bias
提前致谢。
最佳答案
采用不对称属性并使其对称的一种方法是使用它们的平均值(或其他度量):d'(x,y) = d'(y,x) = (d(x ,y) + d(y,x))/2
这种技术的一个常见用法是制作 KL-Divergence通过应用相同的技术对称。这被称为 Jensen-Shannon Diversion
关于algorithm - 修改 Levenshtein 距离以考虑位置，同时是对称的，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27617196/