已迁移到:http://www.wypblog.com/archives/58
思想是编程之美上面的,我只是做了一点点优化。。。
许多程序会大量使用字符串。对于不同的字符串,我们希望能够有办法判断其相似程序。我们定义一套操作方法来把两个不相同的字符串变得相同,具体的操作方法为:
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;
}
分享到:
相关推荐
Levenshtein Distance-两字符串相似度计算...
比较两个字符串的相似度,利用Levenshein算法计算出两个字符串的最小编辑距离,根据最小编辑距离得出相似度,例如: 字符串1:1234 字符串2:51234,则他们的相似度为:4/5。
#region 计算字符串相似度 /// /// 计算字符串相似度 /// /// ”str1″>字符串1 /// ”str2″>字符串2 /// 相似度 public static float Levenshtein(string str1, string str2) {
基于Hadoop的文本相似度计算的代码 是用TFIDF 和向量空间模型,IKAnlayze来弄的 有代码,只是用来参考的 只是一个算法的演示,用于保存,以后查看的
输入2个中文字符串,计算2个字符串的相似度,用于相似度排序。
针对传统字符串相似度算法复杂的局限,在向量空间模型(VSM)的基础上,提出一种同时考虑字符相邻位置关系和词序的字符串相似度计算模型。通过计算VSM中向量的汉明距离来描述字符串相邻程度,并以向量的曼哈顿距离...
java 计算字符串相似度
Levenshtein算法python也是用的这个对比字符串相似度的,还不错
针对中西文混合字符串,采用了将汉字作为西文字符的等价单位计算编辑距离的方法,并从输入法的角度提出了采用拼音编码和五笔编码计算编辑距离的方法,最后给出了融合三种编辑距离计算字符串相似度的算法。...
Delphi计算或比较两组字符串的相似程度 对字符串进行挨个读取并进行比对,取得相似度
Strutil strutil提供了用于计算字符串相似度的字符串度量标准以及其他字符串实用程序功能。 完整文档可在以下找到: : 。安装 go get github.com/adrg/strutil字符串指标杰罗·温克勒史密斯·沃特曼·高图索伦森-...
比较两个字符串的相似度,利用LCS算法计算出两个字符串的最长公序列,根据最长公序列得出相似度,例如: 字符串1:1234 字符串2:51234,则他们的相似度为:4*2/(4+5)。
用途:可用于论文抄袭检测、DNA等。...算法实现思路:通过对一个字符串插入、删除、替换转变成另一个字符串所需要的步骤称为距离,计算两个字符串之间的距离,从而可以得到两个字符串之间的相似度。
主要介绍了java字符串相似度算法,是Java实现比较典型的算法,具有一定参考借鉴价值,需要的朋友可以参考下
两个字符串,计算出两个字符串的相似度,用于模糊匹配,很简单的小例子
Java 实现推荐系统 两个字符串 余弦相似度 算法。
Oracle字符相似度函数。在sql语句中直接用该函数来计算2个字符串相似度。
C#中文文本匹配,字符串匹配,中文词语匹配,计算2个句子相似度 中文匹配C#中文文本匹配,字符串匹配,中文词语匹配,计算2个句子相似度 C#中文文本匹配,字符串匹配,中文词语匹配,计算多个句子相似度 C#中文文本...
自己开发的Excel函数,可以判定两个字符串的相似度。