一个类似于 Levenshtein 但对 Qwerty 键盘加权的好算法？-解网

问：

我注意到这里有一些关于字符串匹配的帖子，这让我想起了一个我想解决的老问题。有没有人有一个好的类似 Levenshtein 的算法，它对 Qwerty 键盘加权？

我想比较两个字符串，并允许拼写错误。Levenshtein 还可以，但我更愿意接受基于 Qwerty 键盘上按键之间的物理距离的拼写错误。换句话说，算法应该更喜欢“yelephone”而不是“zelephone”，因为“y”键比大多数键盘上的“z”键更靠近“t”键。

任何帮助都会很棒......这个功能不是我项目的核心，所以我不想在我应该做一些更有成效的事情时转向老鼠洞。

算法字符串文本比较

在生物信息学中，当你对齐两个DNA序列时，你可能会有一个模型，该模型具有不同的成本，这取决于替换是过渡还是转化。这正是您想要的，但不是 4x4 矩阵，而是 40x40 矩阵或其他矩阵，我敢说距离函数吗？因此，替换的成本来自矩阵/函数，而不是常数。

注意：不过，请确保删除和插入的权重正确，因此它们不会被过度接受为最小值。您最终会得到一串插入/删除/无更改替换字符。

您尝试最小化的新函数是：

d[i, j] := minimum(
    d[i-1, j] + del_cost,
    d[i, j-1] + ins_cost,
    d[i-1, j-1] + keyboard_distance( s[i], t[j] )
)

一个类似于 Levenshtein 但对 Qwerty 键盘加权的好算法？