与Levenshtein类似的一个很好的算法,但对Qwerty键盘进行了加权？

发布时间：2020-12-14 21:50:18 所属栏目：资源来源：网络整理

导读：我注意到这里有一些字符串匹配的帖子，这让我想起了一个我想解决的老问题。有没有人有一个很好的类似 Levenshtein的算法，被称为Qwerty键盘？我想比较两个字符串，并允许输入错误。 Levenshtein是好的，但是我也希望根据Qwerty键盘上的键之间的物理距离接受

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

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

任何帮助将是伟大的…这个功能不是我的项目的核心，所以当我应该做一些更有成效的事情，我不想变成一个鼠洞。

在生物信息学中，当您对齐两个DNA序列时，您可能会有一个具有不同成本的模型，这取决于替代是否为转换或颠换。这正是你想要的，而不是一个4×4的矩阵，你想要一个40×40的矩阵或一些，我敢说距离函数？所以替换的代价是从矩阵/函数，而不是常数。

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!