动态规划：计算字符串相似度

古城微笑少年丶 2022-08-08 05:23 169阅读 0赞

《编程之美》第223页。

# 题目描述 #

许多程序会大量使用字符串。对于不同的字符串，我们希望能够有办法判断其相似程序。我们定义一套操作方法来把两个不相同的字符串变得相同，具体的操作方法为：  
1.修改一个字符（如把“a”替换为“b”）;　　  
2.增加一个字符（如把“abdd”变为“aebdd”）;  
3.删除一个字符（如把“travelling”变为“traveling”）;  
比如，对于“abcdefg”和“abcdef”两个字符串来说，我们认为可以通过增加/减少一个“g”的方式来达到目的。上面的两种方案，都仅需要一 次 。把这个操作所需要的次数定义为两个字符串的距离，而相似度等于“距离+1”的倒数。也就是说，“abcdefg”和“abcdef”的距离为1，相似度 为1/2=0.5。  
给定任意两个字符串，你是否能写出一个算法来计算它们的相似度呢？

# 采用递归方法求解 #

原文的分析与解法　　  
　　不难看出，两个字符串的距离肯定不超过它们的长度之和（我们可以通过删除操作把两个串都转化为空串）。虽然这个结论对结果没有帮助，但至少可以知道，任意两个字符串的距离都是有限的。我们还是就住集中考虑如何才能把这个问题转化成规模较小的同样的子问题。如果有两个串A=xabcdae和B=xfdfa，它们的第一个字符是 相同的，只要计算A\[2,...,7\]=abcdae和B\[2,...,5\]=fdfa的距离就可以了。但是如果两个串的第一个字符不相同，那么可以进行 如下的操作（lenA和lenB分别是A串和B串的长度）。

1.删除A串的第一个字符，然后计算A\[2,...,lenA\]和B\[1,...,lenB\]的距离。  
2.删除B串的第一个字符，然后计算A\[1,...,lenA\]和B\[2,...,lenB\]的距离。  
3.修改A串的第一个字符为B串的第一个字符，然后计算A\[2,...,lenA\]和B\[2,...,lenB\]的距离。  
4.修改B串的第一个字符为A串的第一个字符，然后计算A\[2,...,lenA\]和B\[2,...,lenB\]的距离。  
5.增加B串的第一个字符到A串的第一个字符之前，然后计算A\[1,...,lenA\]和B\[2,...,lenB\]的距离。  
6.增加A串的第一个字符到B串的第一个字符之前，然后计算A\[2,...,lenA\]和B\[1,...,lenB\]的距离。  
在这个题目中，我们并不在乎两个字符串变得相等之后的字符串是怎样的。所以，可以将上面的6个操作合并为：  
1.一步操作之后，再将A\[2,...,lenA\]和B\[1,...,lenB\]变成相字符串。  
2.一步操作之后，再将A\[2,...,lenA\]和B\[2,...,lenB\]变成相字符串。  
3.一步操作之后，再将A\[1,...,lenA\]和B\[2,...,lenB\]变成相字符串。

通过以上1和6,2和5，3和4的结合操作，最后两个字符串每个对应的字符会相同，但是这三种操作产生的最终的两个字符串是不一样的。我们不知道通过上述的三种结合那种使用的操作次数是最少的。所以我们要比较操作次数来求得最小值。

下面这幅图是摘自编程之美：从中我们可以看出一些信息。

![1355029218_9181.jpg][]

可以看到，在计算的过程中，有索引越界的情况，抓住这个特点，就可以尽早的结束程序，同时还有重复计算的情况，比如(strA, 2, 2, strB, 2, 2).

# 动态规划方法求解 #

利用二维数组代替函数递归调用。

# 代码    #

#include <string>
    #include <iostream>
    #include <vector>
    using namespace std;
    
    //求三个数的最小值
    int min(int a, int b, int c) {
    	if (a > b) {
    		if (b > c)
    			return c;
    		else
    			return b;
    	}
    	if (a > c) {
    		if (c > b)
    			return b;
    		else
    			return c;
    	}
    	if (b > c) {
    		if (c > a)
    			return a;
    		else
    			return c;
    	}
    }
    
    //使用动态规划求解方法
    int StringDistance(string &str1, int start1, int end1,
    	string &str2, int start2, int end2) {
    	if (start1 > end1) {
    		if (start2 > end2)
    			return 0;
    		else
    			return end2 - start2 + 1;
    	}
    
    	if (start2 > end2) {
    		if (start1 > end1)
    			return 0;
    		else
    			return end1 - start1 + 1;
    	}
    
    	if (str1[start1] == str2[start2])
    		return StringDistance(str1, start1 + 1, end1, str2, start2 + 1, end2);
    	else {
    		int t1 = StringDistance(str1, start1 + 1, end1, str2, start2, end2);
    		int t2 = StringDistance(str1, start1, end1, str2, start2 + 1, end2);
    		int t3 = StringDistance(str1, start1 + 1, end1, str2, start2 + 1, end2);
    		return min(t1, t2, t3) + 1;
    	}
    }
    
    //递归求解方法
    int StringDistance(string &str1, string &str2) {
    	int len1 = str1.length(), len2 = str2.length();
    	vector<vector<int> > ivec(len1 + 1, vector<int>(len2 + 1));
    
    	//下面初始化的含义：
    	//当str1长度为0时，那么两个字符串的距离就是str2的长度
    	//同样，当str2长度为0， 那么两个字符串距离就是str1的长度
    	for (int i = 0; i < len1 + 1; ++i)
    		ivec[i][0] = i;
    	for (int i = 0; i < len2 + 1; ++i)
    		ivec[0][i] = i;
    
    	for(int i = 1; i <= len1; ++i) {
    		for (int j = 1; j <= len2; ++j) {
    			if (str1[i - 1] == str2[j - 1])
    				ivec[i][j] = ivec[i - 1][j -1];
    			else
    				ivec[i][j] = min(ivec[i][j - 1], ivec[i - 1][j], ivec[i - 1][j - 1]) + 1;
    		}
    	}
    	return ivec[len1][len2];
    }
    int main() {
    	string str1, str2;
    	cin >> str1 >> str2;
    	//int dis = StringDistance(str1, 0, str1.length() - 1,	str2, 0, str2.length() - 1);
    	int dis = StringDistance(str1, str2);
    	cout << dis << endl;
    }

[http://blog.csdn.net/zzran/article/details/8274735][http_blog.csdn.net_zzran_article_details_8274735]

[1355029218_9181.jpg]: https://img-my.csdn.net/uploads/201212/09/1355029218_9181.jpg
[http_blog.csdn.net_zzran_article_details_8274735]: http://blog.csdn.net/zzran/article/details/8274735