Hamming Distance
Die Hamming-Distanz ist die Anzahl der Positionen, an denen sich entsprechende Zeichen zweier gleich langer Zeichenketten unterscheiden; sie gilt nur für Vergleiche gleicher Länge.
Zweck
Misst die Anzahl abweichender Positionen zwischen gleich langen Zeichenketten, verwendet in der Fehlererkennung und Codierungstheorie.
Mechanismus
Für gleich lange Zeichenketten s und t gilt d = Σ(s[i] ≠ t[i]). Nur bei gleicher Länge definiert. Für Binärzeichenketten effizient per Bitoperationen (XOR + Popcount) berechenbar.
Anwendungsfälle
- Fehlererkennung und fehlerkorrigierende Codes
- Binärzeichenketten-Ähnlichkeit
- Perzeptive Differenz von Bild-Hashes
- Lehre der Informationstheorie
Beispiele
- Eingabe
karolin → kathrinOutput33 positions differ
Häufige Fehler
- Applying the Hamming distance to strings of unequal length
- Use the Levenshtein distance for variable lengths
Verwandte Begriffe
Levenshtein Distance
Die Levenshtein-Distanz ist die minimale Anzahl an Einfügungen, Löschungen und Ersetzungen einzelner Zeichen, die nötig sind, um zwei Zeichenketten identisch zu machen. GLOSSAR
Jaro-Winkler Distance
Die Jaro-Winkler-Distanz verfeinert die Jaro-Distanz, indem gemeinsame Präfixe gewichtet werden — besser geeignet für kurze Strings wie Personennamen, bei denen Präfixe zählen. GLOSSAR
Edit Distance
Die Editierdistanz ist die minimale Anzahl einzeichenlicher Editieroperationen (Einfügen, Löschen, Ersetzen), um eine Zeichenkette in eine andere umzuwandeln; die Levenshtein-Distanz ist ihre häufigste Form. GLOSSAR