Minimum Edit Distance (Levenshtein Distance)

Suppose we have two strings — how do we measure how "similar" they are? For example, between naxt and exnt, which one is more similar to next? To answer this, we need a unified criterion.

To establish such a unified criterion, someone proposed the concept of 编辑距离 (Edit distance or Levenshtein distance).

What is edit distance? As the name suggests, it's the number of edits required to transform string a (source) into string b (target). Each edit can only add / delete / replace one character. Computing the minimum edit distance from a to b gives us a measure of the similarity between the two strings.

When string a and string b are identical, the edit distance is 0; the greater their differences, the larger the edit distance.

How It Works

In general, computing the edit distance uses a two-dimensional array of size a's length × b's length as the computation area, and applies 动态规划 (Dynamic Programming, DP for short) to solve it.

The specific steps are:

1. Build an m×n matrix, where m = len(a) + 1, n = len(b) + 1. Thus the 2D array covers matrix[0...n-1][0...m-1].
2. Assign matrix[0][0...m-1] the values 0...m-1, and assign matrix[0...n-1][0] the values 0...n-1.
3. Traverse matrix[1...n-1][1...m-1], setting each element's value to:

Here $COST_{insert}$ and $COST_{delete}$ are both fixed values (you can set them to 1, 2, or whatever you like). And $COST_{sub:i->j}$ is the value that needs to be evaluated. When $i$ and $j$ are equal in value, $COST_{sub:i->j}$ is 0; otherwise $COST_{sub:i->j}$ is a predefined weight.

Finally, the value of matrix[n-1][m-1] is the minimum edit distance between the two strings.

Improvement When $source_i$ and $target_i$ have the same value, the value of SUBSTITUTE_COST is 0, which is necessarily the minimum. So we first check whether the two characters are equal; if they are, we can directly set matrix[i][j]=matrix[i-1][j-1] and move on to the next one. This saves a great deal of computation.

Implementation

Predefinitions

#ifndef INSERT_COST
#define INSERT_COST 1
#endif // INSERT_COST

#ifndef DELETE_COST
#define DELETE_COST 1
#endif // DELETE_COST

#ifndef SUBSTITUTE_COST 
#define SUBSTITUTE_COST 2
#endif // SUBSTITUTE_COST

Utility Macro

#ifndef _MIN
#define _MIN(x,y,z) ((x<y)?((x<z)?x:z):((y<z)?y:z))
#endif // _MIN(x,y,z)

Main Logic

int editDistance(const char *t,const char * s) //compare target && src
{
	int m = strlen(s)+1; // length of source + 1 for j in 0,1,2...m
	int n = strlen(t)+1; // length of dest + 1 for i in 0,1,2...n
	int matrix[n][m];// distance matrix
	int i;
	int j;
	for(i = 0 ; i < n ; i ++)
	{
		memset(matrix[i],0,m*sizeof(int));
		matrix[i][0] = i;
	}
	for(i = 0 ; i < m;i++) matrix[0][i] = i;
	for(i = 1 ; i < n ; i ++ )
	{
		for(j = 1 ; j < m ; j ++)
		{
			if(t[i-1] == s[j-1])
			{
				matrix[i][j] = matrix[i-1][j-1];
			}else
			{
				matrix[i][j] = _MIN(matrix[i][j-1] + INSERT_COST, // insert cost
						matrix[i-1][j] + DELETE_COST, // delete cost 
						matrix[i-1][j-1] + SUBSTITUTE_COST); // substitute cost
			}
		}
	}
	return matrix[n-1][m-1];
}

Extensions

The highlighted part on L18 is exactly the check for whether the characters t[i-1] and s[j-1] are equal. If we have any special requirements, we can tamper with this spot. For example, suppose we want 'a' and 'b' to be treated as the same thing. Then we write a predicate function

inline int isSame(char a, char b)
{
	return (a<b?(a=='a'&&b=='b'):(a=='b'&&b=='a'))|| a==b;
}

and modify L18 to

if(isSame(t[i-1],s[j-1]))

References

• 如何计算最小编辑距离
• Minimum Edit Distance