Un bon algorithme similaire à Levenshtein mais pondéré pour les claviers Qwerty ?

Question

J'ai remarqué quelques articles ici sur la correspondance de chaînes, qui m'ont rappelé un vieux problème que j'aimerais résoudre.Est-ce que quelqu'un a un bon Levenshtein-un algorithme de type axé sur les claviers Qwerty ?

Je souhaite comparer deux chaînes et autoriser les fautes de frappe.Levenshtein va bien, mais je préférerais également accepter les fautes d'orthographe basées sur la distance physique entre les touches du clavier Qwerty.En d'autres termes, l'algorithme devrait préférer « yelephone » à « zelephone » puisque la touche « y » est située plus près de la touche « t » que de la touche « z » sur la plupart des claviers.

Toute aide est la bienvenue...cette fonctionnalité n'est pas au cœur de mon projet, donc je ne veux pas me retrouver dans un trou à rat alors que je devrais faire quelque chose de plus productif.

Answer 1

En bioinformatique, lorsque vous alignez deux séquences d'ADN, vous pouvez avoir un modèle qui a un coût différent selon que la substitution est une transition ou une transversion.C'est exactement ce que vous voulez mais au lieu d'une matrice 4x4, vous voulez une matrice 40x40 ou autre, oserais-je dire fonction de distance ?Le coût d’un remplacement provient donc de la matrice/fonction, et non d’une constante.

MISE EN GARDE:Assurez-vous cependant que les suppressions et les insertions sont correctement pondérées, afin qu'elles ne soient pas trop acceptées comme minimum.Vous vous retrouverez avec une chaîne de caractères d'insertion/suppression/sans changement.

La nouvelle fonction que vous essayez de minimiser serait :

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