编辑距离

编辑距离(edit distance)

当你在搜索引擎的搜索框中输入单词的时候,有没有发现,搜索引擎会返回一系列相关的关键词,方便你直接点击。甚至,当你某个单词输入有误的时候,搜索引擎依旧会返回正确的搜索结果。搜索下拉提示和关键词纠错,这两个功能其实就是查询推荐,常用 编辑距离 来作为判断

操作:

1.插入

2.移除

3.替换

上面的操作都使得编辑距离 +1

例子:

下面是将 str1 转化为 str2 所需要的动作数

Input:   str1 = "dailenote", str2 = "daileinote"
distance:  1
插入 i

Input:   str1 = "cat", str2 = "cut"
distance:  1
将 a 替换为 u

Input:   str1 = "sunday", str2 = "saturday"
Output:  3
将 n 替换为 r 插入 t 插入 a

下面是代码实现的例子

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define min(a,b) ((a) > (b) ? (b) : (a))

int recursion;

int get_min(int x, int y, int z)
{
	return min(min(x,y), z);
}

int get_edit_distance(char *str1, int m, char *str2, int n)
{
	int x,y,z;

	recursion++;

	// 如果其中一个字符串长度为 0,那么编辑距离为 另一个字符串长度
	if (n == 0)
		return m;
	if (m == 0)
		return n;

	// 如果两个字符串最后一个字符相同,那么去掉最后一个字符相同字符,继续超找子串的距离
	if (str1[m-1] == str2[n-1])
		return get_edit_distance(str1, m-1, str2, n-1);

	//插入 (m+1,n) => (m, n-1)
	x = get_edit_distance(str1, m, str2, n-1);

	//移除(m,n) => (m-1, n)
	y = get_edit_distance(str1, m-1, str2, n);

	//替换(m,n) => (m-1, n-1)
	z = get_edit_distance(str1, m-1, str2, n-1);

	return 1 + get_min(x,y,z);
}

int main(int argc, char **argv)
{
	int 	distance;

	if (argc != 3)
		return 1;

	char *str1 = argv[1];
	char *str2 = argv[2];

	distance = get_edit_distance(str1, strlen(str1), str2, strlen(str2));
	printf("recursion:%d distance: %d\n", recursion, distance);
	return 0;
}
[root@dldl ccc]# ./a.out dailenote daileinote
recursion:686 distance: 1
[root@dldl ccc]# ./a.out dailnote daileinote
recursion:454 distance: 2
[root@dldl ccc]# ./a.out dailnot daileinote
recursion:48436 distance: 3
[root@dldl ccc]# ./a.out aaaaaa bbbbbb
recursion:13483 distance: 6

上面这个写法当两个字符串完全不同是,时间复杂度会达到O(3^m)

我们可以看到 (2,2) 处理了3次,出现了重叠子问题

下面是利用动态规划的表格法来避免子问题被重复解决

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define min(a,b) ((a) > (b) ? (b) : (a))

int recursion;

int get_min(int x, int y, int z)
{
	return min(min(x,y), z);
}

int get_edit_distance(char *str1, int m, char *str2, int n)
{
	int 	i,j;
	int 	dp[m+1][n+1];

	//这i代表str1长度,j代表str2的长度
	// dp[x][y] 代表当 str1 长度为x,str2 长度为y时的编辑距离

	for (i = 0; i <= m; i++) {
		for (j = 0; j <= n; j++) {
			recursion++;

			if (i == 0) {
				dp[i][j] = j;
				continue;
			}

			if (j == 0) {
				dp[i][j] = i;
				continue;
			}

			// 如果两个字符串最后一个字符相同
			// 那么当前的编辑距离即为
			if (str1[i-1] == str2[j-1]) {
				dp[i][j] = dp[i-1][j-1];
				continue;
			}

			dp[i][j] = 1 + get_min(dp[i][j-1],		//插入
								   dp[i-1][j],		//移除
								   dp[i-1][j-1]);	//替换
		}
	}

	return dp[m][n];
}


int main(int argc, char **argv)
{
	int 	distance;
	size_t 	 m, n;

	if (argc != 3)
		return 1;

	char *str1 = argv[1];
	char *str2 = argv[2];

	m = strlen(str1);
	n = strlen(str2);

	distance = get_edit_distance(str1, m, str2, n);
	printf("recursion:%d distance: %d\n", recursion, distance);
	return 0;
}
[root@dldl ccc]# ./a.out dailenote daileinote
recursion:110 distance: 1
[root@dldl ccc]# ./a.out dailnote daileinote
recursion:99 distance: 2
[root@dldl ccc]# ./a.out dailnot daileinote
recursion:88 distance: 3
[root@dldl ccc]# ./a.out aaaaaa bbbbbb
recursion:49 distance: 6

优化后时间复杂度为O(m*n)


参考:

https://www.geeksforgeeks.org/edit-distance-dp-5/

上一篇: 动态规划
下一篇: 最长上升子序列
作者邮箱: 203328517@qq.com