Un buen algoritmo similar a la de Levenshtein, pero ponderado para teclados Qwerty?

Question

Me di cuenta de algunos puestos aquí en la cadena de coincidencia, que me recordó a un viejo problema que me gustaría solucionar.¿Alguien tiene una buena Levenshtein-como el algoritmo que se ponderados hacia teclados Qwerty?

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

Cualquier ayuda sería genial...esta característica no es esencial para mi proyecto, así que no quiero salirme en una rata-agujero, cuando debería estar haciendo algo más productivo.

Answer 1

En la bioinformática al alinear dos secuencias de ADN puede tener un modelo que tiene un coste diferente en función de si la sustitución es una transición o una transversión.Esto es exactamente lo que usted desea, pero en lugar de una matriz de 4x4, usted quiere un 40x40 matriz o algunos, me atrevería a decir que la distancia a la función?Por lo que el costo de la reposición de la matriz/función, no una constante.

ADVERTENCIA:Asegúrese de que las supresiones y las inserciones se ponderan adecuadamente aunque, por lo que no son más aceptados como mínimo.Usted va a terminar con una cadena de inserciones/deleciones/no-cambio-de sustitución de caracteres.

La nueva función está tratando de minimizar 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] )
)