Hamming distance

(definition)

Definition: The number of bits which differ between two binary strings. More formally, the distance between two strings A and B is ∑ | A_i - B_i |.

Aggregate parent (I am a part of or used in ...)
brute force string search with mismatches.

See also Levenshtein distance, Manhattan distance.

Note: After Ralf Rabaetje <rrabaetj@advea.com> 4 February 2000.

The Hamming distance can be interpreted as the number of bits which need to be changed (corrupted) to turn one string into the other. Sometimes the number of characters is used instead of the number of bits. Hamming distance can be seen as Manhattan distance between bit vectors.

Author: PEB

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified 31 May 2006.
HTML page formatted Mon Sep 11 09:46:03 2006.

Cite this as:
Paul E. Black, "Hamming distance", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 31 May 2006. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/HammingDistance.html