Distance Hamming vs. Levenshtein

Question

Pour le problème, je travaille sur, trouver les distances entre les deux séquences pour déterminer leur similitude, l'ordre de séquence est très importante. Cependant, les séquences que j'ai ne sont pas tous de la même longueur, donc pad I des chaînes déficientes avec des points vides de telle sorte que les deux séquences sont la même longueur afin de satisfaire à l'exigence de distance de Hamming. Y at-il problème majeur avec moi le faire, car tout ce que je me soucie de sont le nombre de transpositions (pas des insertions ou des suppressions comme Levenshtein ne)?

J'ai trouvé que la distance de Hamming est beaucoup, beaucoup plus rapide que Levenshtein comme une distance métrique pour les séquences de plus grande longueur. Quand doit-on utiliser la distance Levenshtein (ou dérivés de la distance Levenshtein) au lieu de la distance de Hamming beaucoup moins cher? distance de Hamming peut être considérée comme la limite supérieure pour les distances possibles Levenshtein entre deux séquences, donc si je compare les deux séquences pour une similitude biaisée ordre métrique plutôt que le nombre minimal absolu de mouvements pour faire correspondre les séquences, il n'y a pas apparente raison pour moi de choisir Levenshtein sur Hamming comme une métrique, est-il?

Answer 1

Cette question dépend vraiment des types de séquences que vous êtes correspondant, et ce résultat que vous voulez.

Si ce n'est pas un problème « 1234567890 » et « 0123456789 » sont considérés comme la distance totalement différente, en effet Hamming est très bien.

Answer 2

En plus de la bonne réponse Johan, le rembourrage peut être problématique.

Par exemple, lorsque vous comparez 123 à 123456 il est différent si vous pad soit à la fin de la chaîne ou au début de la chaîne. La similitude des ___123 avec 123456 est égal à 0, mais la similarité des 123___ avec 123456 est 3.