Hammingdistans

Hammingdistans, or Hamming distance, is a measure of difference between two strings of equal length over a finite alphabet. It is defined as the number of positions at which the corresponding symbols are different. For example, the distance between 1011101 and 1001001 is 2, since they differ in positions 3 and 5.

Mathematically, for two strings x and y in Sigma^n, the Hamming distance d_H(x,y) equals the cardinality of the set {i in {1,...,n} : x_i ≠ y_i}.

Properties: It is a metric on the set of length-n strings: non-negative, equals zero only when x = y, symmetric, and satisfies the triangle inequality. It is commonly used for binary strings but generalizes to any finite alphabet.

Applications: In coding theory, Hamming distance is central to error detection and correction. Hamming codes are a family of linear error-correcting codes that can detect up to two errors and correct single-bit errors. The distance also supports nearest-neighbor search, data deduplication, and comparison of DNA sequences and other symbolic data.

Limitations and generalizations: The distance is defined only for strings of the same length; comparing strings of different lengths requires padding or using other measures such as the edit (Levenshtein) distance. Extensions include the concept of Hamming space with multiple symbols and more general metrics.

Historia: The concept is named after Richard Hamming, who introduced it in his work on error detection and correction codes in the 1950s.