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

Question

Существует ли расстояние редактирования, такое как Левенштейн, которое учитывает расстояние для подстановок?

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

Должна быть метрика, которая принимает во внимание этот тип распущенности?

Answer 1

Тип расстояния, который вы спрашиваете, не включен в levenshtein - но вы должны использовать помощник, такой как евклидово или манхэттенское расстояние, чтобы получить результат. Мое простое предположение: 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 as waz более похожа на qaz as eaz.

Answer 2

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