en>DynamoDegsy at 10:48, 24 December 2010

2010-12-24T10:48:04Z

New page

{| align="right"
|-
| [[Image:Hamming distance 3 bit binary.svg|thumb|140px|3-bit binary [[cube]] for finding Hamming distance]]
| [[Image:Hamming distance 3 bit binary example.svg|thumb|140px|Two example distances: 100→011 has distance 3 (red path); 010→111 has distance 2 (blue path)]]
|-
|colspan=2 | [[Image:Hamming distance 4 bit binary.svg|thumb|280px|4-bit binary [[tesseract]] for finding Hamming distance]]
|-
|colspan=2 | [[Image:Hamming distance 4 bit binary example.svg|thumb|280px|Two example distances: 0100→1001 has distance 3 (red path); 0110→1110 has distance 1 (blue path)]]
|}

In [[information theory]], the '''Hamming distance''' between two [[String (computer science)|string]]s of equal length is the number of positions at which the corresponding symbols are different. In another way, it measures the minimum number of ''substitutions'' required to change one string into the other, or the minimum number of ''errors'' that could have transformed one string into the other.

==Examples==
The Hamming distance between:
* "'''toned'''" and "'''roses'''" is 3.
* '''1011101''' and '''1001001''' is 2.
* '''2173896''' and '''2233796''' is 3.

==Special properties==
For a fixed length ''n'', the Hamming distance is a [[Metric (mathematics)|metric]] on the vector space of the words of length n, as it fulfills the conditions of non-negativity, identity of indiscernibles and symmetry, and it can be shown by [[complete induction]] that it satisfies the [[triangle inequality]] as well. The Hamming distance between two words ''a'' and ''b'' can also be seen as the [[Hamming weight]] of ''a''−''b'' for an appropriate choice of the − operator.

For '''binary strings''' ''a'' and ''b'' the Hamming distance is equal to the number of ones ([[Hamming weight|population count]]) in ''a'' [[Exclusive or|XOR]] ''b''. The metric space of length-''n'' binary strings, with the Hamming distance, is known as the ''Hamming cube''; it is equivalent as a metric space to the set of distances between vertices in a [[hypercube graph]]. One can also view a binary string of length ''n'' as a vector in <math>R^n</math> by treating each symbol in the string as a real coordinate; with this embedding, the strings form the vertices of an ''n''-dimensional [[hypercube]], and the Hamming distance of the strings is equivalent to the [[Manhattan distance]] between the vertices.

==History and applications==

The Hamming distance is named after [[Richard Hamming]], who introduced it in his fundamental paper on [[Hamming code]]s ''Error detecting and error correcting codes'' in 1950.<ref>{{harvtxt|Hamming|1950}}.</ref> It is used in [[telecommunication]] to count the number of flipped bits in a fixed-length binary word as an estimate of error, and therefore is sometimes called the '''signal distance'''. Hamming weight analysis of bits is used in several disciplines including [[information theory]], [[coding theory]], and [[cryptography]]. However, for comparing strings of different lengths, or strings where not just substitutions but also insertions or deletions have to be expected, a more sophisticated metric like the [[Levenshtein distance]] is more appropriate.
For ''q''-ary strings over an [[alphabet]] of size ''q'' ≥ 2 the Hamming distance is applied in case of orthogonal [[modulation]], while the [[Lee distance]] is used for phase modulation. If ''q'' = 2 or ''q'' = 3 both distances coincide.

The Hamming distance is also used in [[systematics]] as a measure of genetic distance.<ref name="pmid18351799">{{harvtxt|Pilcher|Wong|Pillai|2008}}.</ref>

On a grid such as a chessboard, the Hamming distance is the minimum number of moves it would take a rook to move from one cell to the other.

== Algorithm example ==
The [[Python (programming language)|Python]] function <code>hamming_distance()</code> computes the Hamming distance between
two strings (or other [[Iterator|iterable]] objects) of equal length, by creating a sequence of Boolean values indicating mismatches and matches between corresponding positions in the two inputs, and then summing the sequence with False and True values being interpreted as zero and one.
{{-}}

<syntaxhighlight lang="python">
def hamming_distance(s1, s2):
"Return the Hamming distance between equal-length sequences."
if len(s1) != len(s2):
raise ValueError("Undefined for sequences of unequal length")
return sum(ch1 != ch2 for ch1, ch2 in zip(s1, s2))
</syntaxhighlight>

The following [[C (programming language)|C]] function will compute the Hamming distance of two integers (considered as binary values, that is, as sequences of bits). The running time of this procedure is proportional to the Hamming distance rather than to the number of bits in the inputs. It computes the [[bitwise operation|bitwise]] [[exclusive or]] of the two inputs, and then finds the [[Hamming weight]] of the result (the number of nonzero bits) using an algorithm of {{harvtxt|Wegner|1960}} that repeatedly finds and clears the lowest-order nonzero bit.

<syntaxhighlight lang="c">
unsigned hamdist(unsigned x, unsigned y)
{
unsigned dist = 0, val = x ^ y; // XOR

// Count the number of set bits
while(val)
{
++dist;
val &= val - 1;
}

return dist;
}
</syntaxhighlight>

==See also==
{{Portal|Mathematics}}
* [[Closest string]]
* [[Damerau–Levenshtein distance]]
* [[Euclidean distance]]
* [[Jaccard index]]
* [[String metric]]
* [[Sørensen similarity index]]
* [[Word ladder]]

==Notes==
{{Reflist}}

==References==
*{{FS1037C}}
*{{citation
| last = Hamming | first = Richard W. | author-link = Richard W. Hamming
| mr = 0035935
| issue = 2
| journal = [[Bell System Technical Journal]]
| pages = 147–160
| title = Error detecting and error correcting codes
| url = http://wayback.archive.org/web/20060525060427/http://www.caip.rutgers.edu/~bushnell/dsdwebsite/hamming.pdf
| volume = 29
| year = 1950}}.
*{{citation
| last1 = Pilcher | first1 = C. D.
| last2 = Wong | first2 = J. K.
| last3 = Pillai | first3 = S. K.
| date = March 2008
| doi = 10.1371/journal.pmed.0050069
| issue = 3
| journal = PLoS Med.
| page = e69
| pmid = 18351799
| title = Inferring HIV transmission dynamics from phylogenetic sequence relationships
| volume = 5
| pmc = 2267810}}.
*{{citation
| last = Wegner | first = Peter | author-link = Peter Wegner
| doi = 10.1145/367236.367286
| issue = 5
| journal = [[Communications of the ACM]]
| page = 322
| title = A technique for counting ones in a binary computer
| volume = 3
| year = 1960}}.

[[Category:String similarity measures]]
[[Category:Coding theory]]
[[Category:Articles with example Python code]]
[[Category:Articles with example C++ code]]
[[Category:Metric geometry]]
[[Category:Cubes]]

Guided ray - Revision history

en>DynamoDegsy at 10:48, 24 December 2010