23

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?

DNA
  • 42,007
  • 12
  • 107
  • 146
PascalVKooten
  • 20,643
  • 17
  • 103
  • 160
  • 5
    You mean [Damerau-Levenshtein](http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance)? – EdChum Mar 24 '15 at 13:28
  • I saw it, but hadn't realized that "transposition of adjacent characters" is actually what I meant. Though I guess I'm looking not only for adjacent characters, but more of a quadratic weighted distance (not only adjacent) Thanks! – PascalVKooten Mar 24 '15 at 13:30
  • 6
    I think adjacent in that scheme is talking about tansposing characters that are adjacent within the word (e.g. want vs wnat), rather than adjacent on a keyboard. – J Richard Snape Apr 15 '15 at 20:52
  • @JRichardSnape "Plot-twist" indeed.... – PascalVKooten Apr 15 '15 at 20:59
  • 1
    Did you try combining Damerau-Levenshtein (or replacing, if you really only want to consider keyboard "misses") with some kind of Euclidian distance as suggested in the @marmeladze answer? Seems like the way to go to me, or is there more to consider / it doesn't work for you? – J Richard Snape Apr 16 '15 at 09:37

2 Answers2

24

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.

marmeladze
  • 6,468
  • 3
  • 24
  • 45
9

http://www.melissadata.com/webhelp/ssis/updated/Components/Fuzzy_Match/Algorithms.htm mentions: "Needleman-Wunsch - A variation of the Levenshtein algorithm. Levenshtein and Needleman-Wunsch are identical except that character mistakes are given different weights depending on how far two characters are on a standard keyboard layout. For example: A to S is given a mistake weight of 0.4, while A to D is a 0.6 and A to P is a 1.0" but the Needleman-Wunsch Wikipedia article does not mention keyboard layout proximity... But maybe you should look into that.

Jean-Marc Liotier
  • 237
  • 3
  • 8