我在这里注意到一些有关字符串匹配的文章，这让我想起了我想解决的一个老问题。有没有人有一个很好的类似于Levenshtein的算法，可以将其加权为Qwerty键盘？

我想比较两个字符串，并允许输入错误。 Levenshtein可以，但我也希望根据Qwerty键盘上按键之间的物理距离接受拼写错误。换句话说，由于大多数键盘上的" y"键比" z"键更靠近" t"键，因此该算法应更喜欢" yelephone"而不是" zelephone"。

任何帮助都将是非常有用的...此功能对于我的项目而言并不重要，因此当我应该做更有生产力的事情时，我不想陷入麻烦。

解决方案

回答

在生物信息学中，当我们比对两条DNA序列时，我们可能会拥有一个模型，该模型的成本取决于替代是转变还是颠覆。这正是我们想要的，但不是40x40矩阵，而是40x40矩阵，我敢说距离函数吗？因此，替换的成本来自矩阵/函数，而不是常量。

CAVEAT：请确保适当地对删除和插入进行加权，以使它们不会被接受为最小值。我们最终将得到一串插入/删除/无更改替换字符。

我们尝试最小化的新功能将是：

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] )
)