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

Question

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

例如，如果我们考虑单词是否相等，typo 和 tylo 非常接近(p 和 l 在键盘上物理距离很近)，而 typo 和 tyqo 相距很远。我想为更可能出现的拼写错误分配更小的距离。

必须有一个指标来考虑这种邻近性吗？

Answer 1

你问的那种距离不包括在 levenshtein - 但你应该使用像欧几里德或曼哈顿距离这样的助手来获得结果。我的简单假设是，q(英文 qwerty 布局) 是笛卡尔坐标 (y=0; x=0) 所以，w 将是 (y=0; x=1) 等等。 whole list here

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。