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 0th 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(i1, j1).
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(i1, j) + 1. (2) Delete the j^{th} character of the first string. In this case, f(i, j) = f(i, j1) + 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(i1, j1) + 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 rightbottom 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 2D 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.
When the jth character of the first string is different from the ith character of the second string, there are three options available: (1) Insert the ith character of second string into the first string. In this case, f(i, j) = f(i1, j) + 1. (2) Delete the jth character of the first string. In this case, f(i, j) = f(i, j1) + 1. (3) Replace the jth character of the first string with the ith character of the second string. In this case, f(i, j) = f(i1, j1) + 1. What is the final value for f(i, j)? It should be the minimal value of the three cases.
ReplyDeleteWhy only three options available options?
Case (4) Insert the jth character of first string into the second string. In this case, f(i, j) = f(i1, j) + 1. Case (5) Delete the ith character of the second string. In this case, f(i, j) = f(i, j1) + 1.
there should be an assumption that you can only modify the first.
DeleteCheck this also for c# interview questions @ http://skillgun.com
ReplyDeleteThis comment has been removed by the author.
ReplyDeletemade csharp site on csharp code examples
ReplyDelete