编辑距离,如Levenshtein考虑到键盘上的接近度

Question

是否有一个编辑距离,如Levenshtein考虑到替换的距离？

举例来说,如果我们会考虑的话,如果是平等的,typo并且tylo是非常接近(p并l物理上靠近键盘上),而typo与tyqo相距甚远.我想为更可能的错别字分配更小的距离.

必须有一个指标考虑到这种主张吗？

Answer 1

你问的距离不包括在levenshtein中 - 但是你应该使用像欧几里得或曼哈顿距离这样的帮助来得到结果.我的简单假设是,q(在英文qwerty布局中)是笛卡尔坐标(y = 0; x = 0)所以,w将是(y = 0; x = 1),依此类推.整个清单在这里

keyboard_cartesian= {
                     'q': {'y': 0, 'x': 0},
                     'w': {'y': 0, 'x': 1},
                     'e': {'y': 0, 'x': 2},   
                     'r': {'y': 0, 'x': 3},    
                      # ...
                     'a': {'y': 1, 'x': 0}, 
                      #...
                     'z': {'y': 2, 'x': 0},
                     'x' : {'x':1, 'y':2},
                      #   
                     }

假设,单词qaz有意义.之间Levenshtein距离qaz ,并与二者的waz和eaz是1.签出该拼错的可能性更大,取差(这里(Q,W)和(Q,E)),并且计算欧几里得距离

>>> from math import *
>>> def euclidean_distance(a,b):
...     X = (keyboard_cartesian[a]['x']-keyboard_cartesian[b]['x'])**2
...     Y = (keyboard_cartesian[a]['y']-keyboard_cartesian[b]['y'])**2
...     return sqrt(X+Y)
... 
>>> euclidean_distance('q', 'w')
1.0 
>>> euclidean_distance('q', 'e')
2.0

这意味着的拼错qaz作为WAZ不止likley qaz如EAZ.

Answer 2

http://www.melissadata.com/webhelp/ssis/updated/Components/Fuzzy_Match/Algorithms.htm提到:" Needleman-Wunsch - Levenshtein算法的一种变体.Levenshtein和Needleman-Wunsch是相同的,除了给出了字符错误不同的权重取决于标准键盘布局上两个字符的距离.例如:A到S的错误权重为0.4,而A到D为0.6,A到P为1.0 "但是Needleman-Wunsch维基百科文章没有提到键盘布局接近......但也许你应该研究一下.