kNN in Linguistics

The next example comes from computer linguistics. We show how we can use a k-nearest neighbor classifier to recognize misspelled words.

We will measure the distance between two words with the Levenshtein distance. The minimum edit distance between two strings is the minimum numer of editing operations needed to convert one string into another. The editing operations can consist of insertions, deletions and substitutions.

The Levenshtein distance has the following properties:

• It is zero if and only if the strings are equal.
• It is at least the difference of the sizes of the two strings.
• It is at most the length of the longer string.
• Triangle inequality: The Levenshtein distance between two strings is no greater than the sum of their Levenshtein distances from a third string.