编辑距离，例如 Levenshtein，考虑键盘上的接近度

Question

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

例如，如果我们考虑单词是否相等，

typo

和

tylo

非常接近（

p

和

l

在键盘上物理上很接近），而

typo

和

tyqo

则相距很远。我想为更可能出现的拼写错误分配更小的距离。

一定有一个衡量标准来考虑这种邻近性吗？

Answer 1

您要求的距离类型不包含在编辑中 - 但您应该使用欧几里得距离或曼哈顿距离等帮助器来获得结果。我的简单假设是， 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 维基百科文章没有提到键盘布局邻近性......但也许你应该研究一下。