24

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

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

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

4

1 回答 1

20

在生物信息学中，当您比对两条 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] )
)
于 2008-09-08T17:14:07.967 回答