Distance and proximity – simple edit distance

String comparison refers to techniques used to measure the similarity between two strings. We will use distance and proximity to specify how similar any two strings are. The more similar any two strings are, the lesser the distance between them, so the distance from a string to itself is 0. An inverse measure is proximity, which means that the more similar any two strings are, the greater their proximity.

We will take a look at simple edit distance first. Simple edit distance measures distance in terms of how many edits are required to convert one string to the other. A common distance measure proposed by Levenshtien in 1965 allows deletion, insertion, and substitution as basic operations. Adding in transposition is called Damerau-Levenshtien distance. For example, the distance between foo and boo is 1, as we're looking at a substitution of f with b.

Note

For more on distance metrics, refer to the Wikipedia article on distance at http://en.wikipedia...