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

我注意到这里有一些关于字符串匹配的帖子,这让我想起了我想要解决的一个老问题.有没有人有一个像Qwerty键盘那样的Levenshtein算法呢？

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

任何帮助都会很棒......这个功能对我的项目来说并不重要,所以当我应该做一些更有成效的事情时,我不想转向一个老鼠洞.

1> nlucaroni..：

---

在生物信息学中,当您对齐两个DNA序列时,您可能会根据替换是转换还是颠换来获得具有不同成本的模型.这正是你想要的,但你想要一个40x40矩阵或者一些,我敢说距离函数,而不是4x4矩阵.因此,替换的成本来自矩阵/函数,而不是常量.

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

---

cpan撰稿人Kyle R. Burton实际上在Perl中实现了[这个距离函数](http://search.cpan.org/~krburton/String-KeyboardDistance-1.01/KeyboardDistance.pm).他用一张桌子来计算体重.请参阅他的文档以获取完整的表格.