Hamming Distance
La distance de Hamming est le nombre de positions où diffèrent les caractères correspondants entre deux chaînes de même longueur ; elle ne s'applique qu'aux comparaisons de même longueur.
Objectif
Mesure le nombre de positions différentes entre chaînes de même longueur, utilisée dans la détection d'erreurs et la théorie des codes.
Mécanisme
Pour des chaînes s et t de même longueur, d = Σ(s[i] ≠ t[i]). Définie seulement si les longueurs sont égales. Pour les chaînes binaires, elle se calcule efficacement par opérations bit à bit (XOR + popcount).
Cas d’usage
- Détection d'erreurs et codes correcteurs
- Similarité de chaînes binaires
- Différence perceptuelle de hachages d'images
- Enseignement de la théorie de l'information
Exemples
- entrée
karolin → kathrinOutput33 positions differ
Erreurs courantes
- Applying the Hamming distance to strings of unequal length
- Use the Levenshtein distance for variable lengths
Termes associés
Levenshtein Distance
La distance de Levenshtein est le nombre minimal d'insertions, de suppressions et de substitutions d'un seul caractère nécessaires pour rendre deux chaînes identiques. GLOSSAIRE
Jaro-Winkler Distance
La distance de Jaro-Winkler est un raffinement de la distance de Jaro qui pondère les préfixes communs, la rendant plus adaptée à l'appariement de chaînes courtes comme les noms de personne où le préfixe compte. GLOSSAIRE
Edit Distance
La distance d'édition est le nombre minimal d'opérations d'édition d'un seul caractère (insertion, suppression, substitution) nécessaires pour transformer une chaîne en une autre ; la distance de Levenshtein en est la forme la plus courante. GLOSSAIRE