¿Un buen algoritmo similar a Levenshtein pero ponderado para teclados Qwerty?

Question

Observé algunas publicaciones aquí en la coincidencia de cadenas, que me recordaron un viejo problema que me gustaría resolver. ¿Alguien tiene un buen algoritmo de tipo Levenshtein que tenga en cuenta los teclados Qwerty?

Quiero comparar dos cadenas y permitir los errores tipográficos. Levenshtein está bien, pero preferiría también aceptar errores ortográficos en función de la distancia física entre las teclas del teclado Qwerty. En otras palabras, el algoritmo debería preferir "yelephone" a "zelephone" ya que la tecla "y" se encuentra más cerca de la tecla "t" que de la tecla "z" en la mayoría de los teclados.

Cualquier ayuda sería genial ... esta característica no es central en mi proyecto, por lo que no quiero virar en un agujero de rata cuando debería estar haciendo algo más productivo.

Answer 1

En bioinformática, cuando alinea dos secuencias de ADN, puede tener un modelo que tenga un costo diferente en función de si la sustitución es una transición o una transversión. Esto es exactamente lo que quieres, pero en lugar de una matriz de 4x4, quieres una matriz de 40x40 o alguna, me atrevo a decir la función de distancia. Entonces el costo de un reemplazo es de la matriz/función, no una constante.

CAVEAT: Asegúrese de que las eliminaciones y las inserciones se ponderan correctamente, por lo que no se aceptan demasiado como mínimo. Terminará con una cadena de caracteres de inserciones/eliminaciones/sin sustitución de cambios.

La nueva función que está intentando reducir al mínimo sería:

d[i, j] := minimum(
    d[i-1, j] + del_cost, 
    d[i, j-1] + ins_cost, 
    d[i-1, j-1] + keyboard_distance(s[i], t[j]) 
)