Hamming Distance

The Hamming distance between two strings of equal length is the number of positions at which their symbols differ. It is a direct way to gauge how alike two same-sized sequences are: the smaller the distance, the more they match. For instance, the binary strings 1011101 and 1001001 agree in five positions and differ in two —the third and the fifth— so their Hamming distance is 2.

Although the classic example uses bits, the definition holds for any alphabet: the words «code» and «core» differ in a single position, so their distance is 1. Mathematically it is a true metric: it is never negative, equals zero only when the strings are identical, is symmetric, and satisfies the triangle inequality. That metric property is what makes it dependable for comparing, ranking, and clustering data.

Origins: Hamming and error-correcting codes

The measure was introduced by the mathematician Richard Hamming in 1950, in his paper «Error Detecting and Error Correcting Codes», published in the Bell System Technical Journal. Working at Bell Labs, Hamming wanted a machine to detect and fix on its own the errors that crept in when data was transmitted or stored. His central insight still holds: a code's minimum distance —the smallest Hamming distance between any two of its valid words— sets its protective power. A code with minimum distance d can detect up to d−1 errors and correct up to the integer part of (d−1)/2. That is why Hamming codes and their descendants live inside today's memory chips, disks, and digital communications.

Uses in artificial intelligence

In machine learning the Hamming distance shows up wherever data is represented as fixed-length binary strings. It compares binary fingerprints and hashes: two fingerprints that are close in Hamming distance stand for similar objects. It underpins nearest-neighbor search over binary representations, retrieving the item whose fingerprint differs in the fewest positions. It also drives locality-sensitive hashing (LSH), a family of techniques that drops similar items into the same «bucket» so a system can search through millions of records without comparing every pair. Computing it is very fast —an XOR followed by a bit count— which makes it ideal at scale.

Versus edit distance

The Hamming distance should not be confused with edit distance, or Levenshtein distance, formalized by Vladimir Levenshtein in 1966. Hamming counts substitutions only and requires both strings to be the same length; Levenshtein also allows insertions and deletions, so it can compare strings of different lengths. For «code» and «core» both return 1, but for «code» and «ode» the Levenshtein distance is 1 —one deletion— while the Hamming distance is undefined, because the lengths no longer match. Choosing between them comes down to whether your data has a fixed size or can shift.