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

概述我注意到这里有一些字符串匹配的帖子，这让我想起了一个我想解决的老问题。有没有人有一个很好的类似 Levenshtein的算法，被称为Qwerty键盘？ 我想比较两个字符串，并允许输入错误。 Levenshtein是好的，但是我也希望根据Qwerty键盘上的键之间的物理距离接受拼写错误。换句话说，由于“y”键位于比“t”键更靠近大多数键盘上的“z”键，所以该算法应该更喜欢“yelephone”到“z 我注意到这里有一些字符串匹配的帖子，这让我想起了一个我想解决的老问题。有没有人有一个很好的类似 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] ))

总结

以上是内存溢出为你收集整理的与Levenshtein类似的一个很好的算法,但对Qwerty键盘进行了加权？全部内容，希望文章能够帮你解决与Levenshtein类似的一个很好的算法,但对Qwerty键盘进行了加权？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。