Modifica distanza come Levenshtein tenendo conto della prossimità sulla tastiera

Question

Esiste una distanza di modifica come Levenshtein che tiene conto della distanza per le sostituzioni?

Ad esempio, se ci consideriamo se le parole sono uguali, e typotylo sono molto vicini (p e l sono fisicamente vicino sulla tastiera), mentre typo e tyqo sono distanti. Mi piacerebbe allocare una distanza minore a errori più probabili.

Ci deve essere una metrica che tenga conto di questo tipo di promissività?

Answer 1

il tipo di distanza si chiede non è incluso nel levenshtein - ma si dovrebbe usare un aiutante come euclidea o Manhattan distanza, per ottenere il result.my semplice presupposto è, q (nel layout QWERTY inglese) è cartesiana (y = 0; x = 0) quindi, w sarà (y = 0; x = 1) e così via. 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}, 
         # 
        } 

assumere, parola qaz ha un significato. distanza tra il Levenshtein qaz e con entrambi waz e eaz è 1. di verificare che Misspell è più probabile, prendere le differenze (qui (q, w) e (q, e)) e calcolare la distanza euclidea

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

questo significa misspell di qaz come waz è più likley di qaz come eaz.

Answer 2

http://www.melissadata.com/webhelp/ssis/updated/Components/Fuzzy_Match/Algorithms.htm menzioni: "Needleman-Wunsch - Una variante dell'algoritmo Levenshtein Levenshtein e Needleman-Wunsch sono identiche tranne che gli errori di carattere sono dati pesi differenti a seconda di quanto due caratteri sono su un layout standard, ad esempio.. : A a S ha un errore di peso di 0,4, mentre da A a D è uno 0,6 e A a P è un 1,0 "ma lo Needleman-Wunsch Wikipedia article non menziona la vicinanza del layout della tastiera ... Ma forse dovresti esaminarlo.