欢迎关注Hadoop、Spark、Flink、Hive、Hbase、Flume等大数据资料分享微信公共账号:iteblog_hadoop
  1. 文章总数:960
  2. 浏览总数:11,448,481
  3. 评论:3870
  4. 分类目录:102 个
  5. 注册用户数:5828
  6. 最后更新:2018年10月13日
过往记忆博客公众号iteblog_hadoop
欢迎关注微信公众号:
iteblog_hadoop
大数据技术博客公众号bigdata_ai
大数据猿:
bigdata_ai

字符串相似度计算

  思想是编程之美上面的,我只是做了一点点优化。。。

  许多程序会大量使用字符串。对于不同的字符串,我们希望能够有办法判断其相似程序。我们定义一套操作方法来把两个不相同的字符串变得相同,具体的操作方法为:
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]变成相字符串。

  这样,很快就可以完成一个递归程序。

  但是源程序在递归调用的时候,很多过程重复计算了,这样导致时间效率很低。我们可以用一个数组记录下来已经计算了的结果,如果下一次要递归就先看看数组里面是不是非0,如果不是,则说明没有计算过,我们需要去计算;如果是,则说明程序已经计算过这个结果,不需要再次去递归,所以可以直接读取数组里面的值,然后返回。

#include<iostream>

using namespace std;
/**
*
*	Create By: w397090770
*   Data : 2012.10.14
*	Email: wyphao.2007@163.com
*
*/
int min(int a, int b){
	return a > b ? b : a;
}

int EditDistence(char *str1, int aStart, int aEnd, char *str2, int bStart, int bEnd, int temp[][100]){
	if(aStart > aEnd){
		if(bStart > bEnd){
			return 0;
		}else{
			return bEnd - bStart + 1;
		}
	}

	if(bStart > bEnd){
		if(aStart > aEnd){
			return 0;
		}else{
			return aEnd - aStart + 1;
		}
	}

	if(str1[aStart] == str2[bStart]){
		int a = 0;
		if(temp[aStart + 1][bStart + 1] != 0){
			a = temp[aStart + 1][bStart + 1];
		}else{
			a = EditDistence(str1, aStart + 1, aEnd, str2, bStart + 1, bEnd, temp);
			temp[aStart + 1][bStart + 1] = a;
		}
		return a;
	}else{
		int a, b, c;
		if(temp[aStart + 1][bStart + 1] != 0){
			a = temp[aStart + 1][bStart + 1];
		}else{
			a = EditDistence(str1, aStart + 1, aEnd, str2, bStart + 1, bEnd, temp);
			temp[aStart + 1][bStart + 1] = a;
		}

		if(temp[aStart + 1][bStart] != 0){
			b = temp[aStart + 1][bStart];
		}else{
			b = EditDistence(str1, aStart + 1, aEnd, str2, bStart, bEnd, temp);
			temp[aStart + 1][bStart] = b;
		}

		if(temp[aStart][bStart + 1] != 0){
			c = temp[aStart][bStart + 1];
		}else{
			c = EditDistence(str1, aStart, aEnd, str2, bStart + 1, bEnd, temp);
			temp[aStart][bStart + 1] = c;
		}
		return min(min(a, b), c) + 1;
	}
}

int main(){
	char *str1 = "efsdfdabcdefgaabcdefgaabcdefgaabcdefgasfabcdefgefsdfdabcdefgaabcdefgaabcdefgaabcdefgasfabcdefg";
	char *str2 = "efsdfdabcdefgaabcdefgaaefsdfdabcdefgaabcdefgaabcdefgaabcdefgasfabcdabcdefggaabcdefgasfabcdefg";

	int temp[100][100];

	memset(temp, 0, sizeof(temp));

	cout << EditDistence(str1, 0, strlen(str1), str2, 0, strlen(str2), temp) << endl;
	return 0;
}
本博客文章除特别声明,全部都是原创!
转载本文请加上:转载自过往记忆(https://www.iteblog.com/)
本文链接: 【字符串相似度计算】(https://www.iteblog.com/archives/58.html)
喜欢 (6)
分享 (0)
发表我的评论
取消评论

表情
本博客评论系统带有自动识别垃圾评论功能,请写一些有意义的评论,谢谢!