Um bom algoritmo semelhante ao Levenshtein, mas ponderada para teclados Qwerty?

Question

Eu notei algumas postagens aqui na cadeia de correspondência, o que me fez lembrar de um antigo problema que eu gostaria de resolver.Alguém tem uma boa Levenshtein-como o algoritmo que é ponderado para teclados Qwerty?

Quero comparar duas cadeias de caracteres, e e permitir erros de digitação.Levenshtein é bom, mas eu prefiro também de aceitar erros de ortografia, com base na distância física entre as teclas no teclado Qwerty.Em outras palavras, o algoritmo deve preferir "yelephone" para "zelephone" desde o "y" está localizado perto a tecla "t" do que para a tecla "z" na maioria dos teclados.

Qualquer ajuda seria ótimo...esse recurso não é central para o meu projeto, então eu não quero veer fora em um rato-buraco quando eu deveria estar fazendo algo mais produtivo.

Answer 1

Em bioinformática quando você alinhar duas seqüências de DNA, você pode ter um modelo que tem um custo diferente se a substituição é uma transição ou um transversion.Isso é exatamente o que você quer, mas em vez de uma matriz 4x4, você quer um 40x40 da matriz ou de alguns, eu digo função de distância?Assim, o custo de uma substituição é a partir da matriz/função, e não uma constante.

RESSALVA:Certifique-se de que deleções e inserções são ponderadas devidamente embora, então eles não são mais aceitos como mínimo.Você vai acabar com uma seqüência de inserções/deleções/não-alteração de substituição de caracteres.

A nova função que você está tentando minimizar seria:

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