编辑距离算法（例如Levenshtein算法）考虑键盘上的接近程度。

Question

是否存在类似Levenshtein的编辑距离方法，该方法考虑了替换操作中字符的相对距离？

例如，如果我们认为单词是相等的，则typo和tylo非常接近（键盘上的p和l物理上靠近），而typo和tyqo则相距较远。我想分配更小的距离给更可能的打字错误。

必须有一种指标考虑这种相对接近程度吧？

- PascalVKooten

---

您是指Damerau-Levenshtein距离吗？ - EdChum

我看到了，但没有意识到“相邻字符的转置”实际上是我想要的。虽然我猜我不仅仅是寻找相邻字符，而是更多的二次加权距离（不仅仅是相邻）。谢谢！ - PascalVKooten

在这个方案中，我认为"adjacent"指的是调换单词内相邻的字符（例如，want和wnat），而不是键盘上相邻的字符。 - J Richard Snape

@JRichardSnape "情节反转" 的确如此.... - PascalVKooten

你是否尝试过将Damerau-Levenshtein（或替换，如果您只想考虑键盘“错误”）与@marmeladze答案中建议的某种欧几里得距离相结合？ 在我看来，这似乎是正确的方法，还是有其他要考虑的因素/它对您不起作用？ - J Richard Snape

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 的Levenshtein距离均为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更可能。

- marmeladze

Answer 2

http://www.melissadata.com/webhelp/ssis/updated/Components/Fuzzy_Match/Algorithms.htm提到：“Needleman-Wunsch - 是Levenshtein算法的一个变体。Levenshtein和Needleman-Wunsch是相同的，只是字符错误根据标准键盘布局上两个字符之间的距离给予不同的权重。例如：A到S的错误权重为0.4，而A到D的错误权重为0.6，A到P的错误权重为1.0。”但是Needleman-Wunsch维基百科文章没有提到键盘布局的接近程度... 但也许你应该研究一下。

- Jean-Marc Liotier