algorithm - damerau - levenshtein distance theory

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

Question

Observé algunos mensajes aquí sobre el emparejamiento de cadenas, que me recordaron un viejo problema que me gustaría resolver. ¿Alguien tiene un buen algoritmo parecido a 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, así que no quiero desviarme hacia 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 algo, ¿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 e inserciones se ponderen correctamente, de modo que no se acepten demasiado como mínimo. Terminará con una cadena de caracteres de inserciones / eliminaciones / sin sustitución de cambios.

La nueva función que intenta 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] )
)