Изменить расстояние, например, Левенштейна с учетом близости на клавиатуре

Есть ли расстояние редактирования, такое как Levenshtein, которое учитывает расстояние для замещений?

Например, если мы будем рассматривать, если слова равны, typo и tylo действительно близки (p и l физически закрыты на клавиатуре), а typo и tyqo - далеко друг от друга. Я хотел бы выделить меньшее расстояние для более вероятных опечаток.

Должна быть метрика, учитывающая этот вид promixity?

Ответ 1

вид расстояния, который вы просите, не включен в levenshtein, но вы должны использовать помощника, например, эвклидовое или манхэттенское расстояние, чтобы получить результат. Простое предположение: q (на английском языке qwerty layout ) является декартовым (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 имеет значение. levenshtein расстояние между 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.

Ответ 2

http://www.melissadata.com/webhelp/ssis/updated/Components/Fuzzy_Match/Algorithms.htm упоминает: "Needleman-Wunsch - вариант алгоритма Левенштейна. Левенштейн и Игламан-Вунш идентичны, за исключением ошибок персонажа даны разные веса в зависимости от того, насколько далеко два символа находятся на стандартной раскладке клавиатуры. Например: от A до S задается ошибка с ошибкой 0,4, а от A до D - 0,6, а от A до P - 1,0 дюйма, но Статья Needleman-Wunsch Wikipedia не упоминает близость раскладки клавиатуры... Но, возможно, вы должны изучить это.