A distance, or metric between two strings s and t is a bivariate function distance(s, t) which satisfies the following conditions:

• distance(s, t) ≥ 0,
• distance(s, s) = 0 if and only if s = t, and
• distance(s, t) = distance(t, s),
• distance(s, u) ≤ distance(s, t) + distance(t, u).

The last condition is called the triangle inequality which can be easily understood through analogy: the distance from Waterloo to Toronto is less than the distance from Waterloo to Hamilton plus the distance from Hamilton to Toronto.

Four distances, in order of complexity, are given:

• The Hamming distance (1950),
• The Levenshtein distance (1964), and
• The Damerau-Levenshtein distance (1964).