python - Edit distance such as Levenshtein taking into account proximity on keyboard

Question

Is there an edit distance such as Levenshtein which takes into account distance for substitutions?

For example, if we would consider if words are equal, typo and tylo are really close (p and l are physically close on the keyboard), while typo and tyqo are far apart. I'd like to allocate a smaller distance to more likely typos.

There must be a metric that takes this kind of promixity into account?

Answer 1

the kind of distance you ask is not included in levenshtein - but you should use a helper like euclidean or manhattan distance, to get the result.my simple assumption is, q (in english qwerty layout) is cartesian (y=0; x=0) so, w will be (y=0; x=1) and so on. 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},
                      #   
                     }

assume, word qaz has a meaning. levenshtein distance between qaz and with both of waz and eaz is 1. to check out which misspell is more likely, take the differences (here (q,w) and (q,e)) and calculate euclidean distance

>>> 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

this means misspell of qaz as waz is more likley than qaz as eaz.