Skip to content

HammingDistance

Status: Stable

documented, exercised by the test suite and/or worked examples, with no known limitations recorded.

Description

HammingDistance[u, v]

Gives the number of positions at which two equal-length strings or lists differ. Returns unevaluated when the lengths differ.

Examples (4)

Every input below was run against the current Mathilda build and its output recorded.

Basic examples (4)

In[1]:= EditDistance["GGTTT", "GGGGT"]
Out[1]= 2

In[2]:= EditDistance["kitten", "sitting"]
Out[2]= 3

In[3]:= EditDistance[{1, 2, 3}, {1, 3}]
Out[3]= 1

In[4]:= HammingDistance["GGTTT", "GGGGT"]
Out[4]= 2

Implementation notes

  • Protected.
  • Elements are compared with structural equality, so the same routine serves strings (character by character) and lists of arbitrary expressions: EditDistance[{1, 2, 3}, {1, 3}] is 1.
  • Strings are compared byte by byte, so a multi-byte UTF-8 character counts as several elements.
  • HammingDistance requires equal lengths and leaves the call unevaluated otherwise, matching Mathematica's ::idim.
  • EditDistance costs O(m n) time and O(min(m, n)) memory (two DP rows).

Attributes: Protected.

References

See also: EditDistance