编辑距离，例如列文施泰因，同时考虑到键盘上的邻近性

Question

是否有像Levenshtein这样的编辑距离考虑了替换距离？

例如，如果我们考虑单词是否相等，typo和tylo真的很接近(p和l在键盘上物理上很接近(，而typo和tyqo相距很远。我想为更有可能的错别字分配一个较小的距离。

一定有一个指标考虑到这种混合性吗？

Answer 1

你问的距离类型不包括在Levenshtein中 - 但你应该使用像欧几里得或曼哈顿距离这样的助手，得到 result.my 简单的假设是，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这个词有一个含义。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 比 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 维基百科文章没有提到键盘布局接近度......但也许你应该研究一下。