Um bom algoritmo semelhante ao Levenshtein, mas ponderada para teclados Qwerty?
-
09-06-2019 - |
Pergunta
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.
Solução
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] )
)