类似于 Levenshtein 但针对 Qwerty 键盘进行加权的好算法？

Question

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

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

任何帮助都会很棒...此功能不是我的项目的核心，因此当我应该做一些更有成效的事情时，我不想陷入困境。

Answer 1

在生物信息学中，当您比对两个 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] )
)