No. 25 - Edit Distance

Problem: Implement a function which gets the edit distance of two input strings. There are three types of edit operations: insertion, deletion and substitution. Edit distance is the minimal number of edit operations to modify a string from one to the other.

For example, the edit distance between “Saturday” and “Sunday” is 3, since the following three edit operations are required to modify one into the other:

1.       Saturday → Sturday (deletion of ‘a’)

2.       Sturday→ Surday (deletion of ‘t’)

3.       Surday → Sunday (substitution of ‘n’ for ‘r’)

There is no way to achieve it with fewer than three operations.

Analysis: If a function f(i, j) is defined to indicate the edit difference between the substring of the  first string ending with the j^th character and the substring of the second string ending with the i^th character. It is obvious that f(i, 0) = i, because when we delete i characters from the substring of the first string ending with the i^th character, we get an empty string (it is also the substring of the second string ending with the 0-th string). Similarly, f(0, j) = j.

Let discuss the cases when both i and j are greater than 1. If the i^th character of the second string is same as the j^th character of the first string, no edit operations are necessary. Therefore, f(i, j) = f(i-1, j-1).

When the j^th character of the first string is different from the i^th character of the second string, there are three options available: (1) Insert the i^th character of second string into the first string. In this case, f(i, j) = f(i-1, j) + 1. (2) Delete the j^th character of the first string. In this case, f(i, j) = f(i, j-1) + 1. (3) Replace the j^th character of the first string with the i^th character of the second string. In this case, f(i, j) = f(i-1, j-1) + 1. What is the final value for f(i, j)? It should be the minimal value of the three cases.

If we draw a table to show the edit distance values f(i, j) between “Saturday” and “Sunday”, it looks like the Table 1.

		S	a	t	u	r	d	a	y
	0	1	2	3	4	5	6	7	8
S	1	0	1	2	3	4	5	6	7
u	2	1	1	2	2	3	4	5	6
n	3	2	2	2	3	3	4	5	6
d	4	3	3	3	3	4	3	4	5
a	5	4	3	4	4	4	4	3	4
y	6	5	4	4	5	5	5	4	3

Table 1: Edit distance value f(i, j) between “Saturday” and “Sunday”.

The edit distance of two strings is at the right-bottom corner of the table for edit distance values.

A formal equation can be defined for this problem:

It is not difficult to develop code based on the equation above. An edit distance value table can be implemented as a 2-D array. Some sample code is shown as below:

int getEditDistance(char* str1, char* str2)

{

    if(str1 == NULL || str2 == NULL)

        return -1;

    int len1 = strlen(str1);

    int len2 = strlen(str2);

    int** distances = (int**)new int[len2 + 1];

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

        distances[i] = new int[len1 + 1];

    int editDistance = getEditDistance(str1, str2, distances, len1, len2);

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

        delete[] distances[i];

    delete[] distances;

    return editDistance;

}

int getEditDistance(char* str1, char* str2, int** distances, int len1, int len2)

{

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

        distances[i][0] = i;

    for(int j = 0; j < len1 + 1; ++ j)

        distances[0][j] = j;

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

    {

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

        {

            if(str1[j - 1] == str2[i - 1])

                distances[i][j] = distances[i - 1][j - 1];

            else

            {

                int deletion = distances[i][j - 1] + 1;

                int insertion = distances[i - 1][j] + 1;

                int substitution = distances[i - 1][j - 1] + 1;

                distances[i][j] = min(deletion, insertion, substitution);

            }

        }

    }

    return distances[len2][len1];

}

int min(int num1, int num2, int num3)

{

    int less = (num1 < num2) ? num1 : num2;

    return (less < num3) ? less : num3;

}

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages,  please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks.