Edit Distance

When a spell checker encounters a possible misspelling, it looks in its dictionary for other words that are close by. What is the appropriate notion of closeness in this case?

A natural measure of the distance between two strings is the extent to which they can be aligned, or matched up. Technically, an alignment is simply a way of writing the strings one above the other. For instance, here are two possible alignments of SNOWY and SUNNY:

The - indicates a “gap”, any number of these can be placed in either string. The cost of an alignment is the number of columns in which the letters differ. And the edit distance between two strings is the cost of their best possible alignment.

Edit distance is so named because it can also be thought of as the minimum number of edits—insertions, deletions, and substitutions of characters—needed to transform the first string into the second.

Dynamic Programming Solution:

Our goal is to find the edit distance between two strings x[1...m] and y[1...n]. So we need to find out the sub-problem, it should go part of the way toward solving the whole problem, so how about looking at the edit distance between some prefix of the first string, x[1...i], and some prefix of the second, y[1...j]? Call this sub-problem E(i, j). Our objective is to compute E(m, n).

where diff(i, j) = 0 if x[i] = y[j] and 1 otherwise.

Example:

Implementation in C#:

    public int MinDistance(string word1, string word2)

    {

        int len1 = word1?.Length ?? 0;

        int len2 = word2?.Length ?? 0;

        if (len1 == 0)

        {

            return len2;

        }

        if (len2 == 0)

        {

            return len1;

        }

        int[,] distance = new int[len1 + 1, len2 + 1];

        for (int i = 0; i <= len1; ++i)

        {

            distance[i, 0] = i;

        }

        for (int i = 0; i <= len2; ++i)

        {

            distance[0, i] = i;

        }  

        for (int i = 1; i <= len1; ++i)

        {

            for (int j = 1; j <= len2; ++j)

            {

                int diff = word1[i - 1] == word2[j - 1] ? 0 : 1;

                distance[i, j] = Math.Min(Math.Min(distance[i - 1, j] + 1,

                                                   distance[i, j - 1] + 1),

                                          distance[i -1, j - 1] + diff);

            }

        }

        return distance[len1, len2];

    }

Time Complexity: O(mn)