问题
许多程序会大量使用字符串。对于不同的字符串,我们希望能够有办法判断其相似程度。我们定义了一套操作方法来把两个不相同的字符串变得相同,具体的操作方法为:
1.修改一个字符(如把“a”替换为“b”)。
2.增加一个字符(如把“abdd”变为“aebdd”)。
3.删除一个字符(如把“travelling”变为“traveling”)。
比如,对于“abcdefg”和“abcdef”两个字符串来说,我们认为可以通过增加/减少一个“g“的方式来达到目的。上面的两种方案,都仅需要一次操作。把这个操作所需要的次数定义为两个字符串的距离,给定任意两个字符串,你是否能写出一个算法来计算出它们的距离?
分析与解法
不难看出,两个字符串的距离肯定不超过它们的长度之和(我们可以通过删除操作把两个串都转化为空串)。虽然这个结论对结果没有帮助,但至少可以知道,任意两个字符串的距离都是有限的。
我们还是应该集中考虑如何才能把这个问题转化成规模较小的同样的问题。如果有两个串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[1,…,lenA]和B[2,…,lenB]变成相同字符串。
3.一步操作之后,再将A[2,…,lenA]和B[2,…,lenB]变成相同字符串。
这样,很快就可以完成一个递归程序。
代码实现:
int calStringDis(string strA, int pABegin,int pAEnd,string strB, int pBBegin,int pBEnd)
{
if (pABegin > pAEnd)
{
if (pBBegin > pBEnd)
return 0;
else
return pBEnd - pBBegin + 1;
}
if (pBBegin > pBEnd)
{
if(pABegin > pAEnd)
return 0;
else
return pAEnd - pABegin + 1;
}
if (strA[pABegin] == strB[pBBegin])
{
return calStringDis(strA,pABegin+1,pAEnd,strB,pBBegin+1,pBEnd);
}
else
{
int t1 = calStringDis(strA,pABegin+1,pAEnd,strB,pBBegin+2,pBEnd);
int t2 = calStringDis(strA,pABegin+2,pAEnd,strB,pBBegin+1,pBEnd);
int t3 = calStringDis(strA,pABegin+2,pAEnd,strB,pBBegin+2,pBEnd);
return minValue(t1,t2,t3)+1;
}
}
以上解法来自《编程之美》,有什么地方需要改进的呢?问题在于:在递归的过程中,有些数据被重复计算了。
很经典的可使用动态规划方法解决的题目,和计算两字符串的最长公共子序列相似。
设Ai为字符串A(a1a2a3 … am)的前i个字符(即为a1,a2,a3 … ai)
设Bj为字符串B(b1b2b3 … bn)的前j个字符(即为b1,b2,b3 … bj)
设 L(i,j)为使两个字符串和Ai和Bj相等的最小操作次数。
当ai==bj时 显然 L(i,j) = L(i-1,j-1)
当ai!=bj时
若将它们修改为相等,则对两个字符串至少还要操作L(i-1,j-1)次
若删除ai或在bj后添加ai,则对两个字符串至少还要操作L(i-1,j)次
若删除bj或在ai后添加bj,则对两个字符串至少还要操作L(i,j-1)次
此时L(i,j) = min( L(i-1,j-1), L(i-1,j), L(i,j-1) ) + 1
显然,L(i,0)=i,L(0,j)=j, 再利用上述的递推公式,可以直接计算出L(i,j)值。
代码实现:
int calculateStringDistance(string strA, string strB) { int lenA = (int)strA.length()+1; int lenB = (int)strB.length()+1; int **c = new int*[lenA]; for(int i = 0; i < lenA; i++) c[i] = new int[lenB]; // Record the distance of all begin points of each string //初始化方式与背包问题有点不同 for(int i = 0; i < lenA; i++) c[i][0] = i; for(int j = 0; j < lenB; j++) c[0][j] = j; c[0][0] = 0; for(int i = 1; i < lenA; i++) { for(int j = 1; j < lenB; j++) { if(strB[j-1] == strA[i-1]) c[i][j] = c[i-1][j-1]; else c[i][j] = minValue(c[i][j-1], c[i-1][j], c[i-1][j-1]) + 1; } } int ret = c[lenA-1][lenB-1]; for(int i = 0; i < lenA; i++) delete [] c[i]; delete []c; return ret; }
参考:
http://www.cnblogs.com/yujunyong/articles/2004724.html
http://www.cnblogs.com/flyinghearts/archive/2011/03/22/1991988.html
相关推荐
Java 实现推荐系统 两个字符串 余弦相似度 算法。
主要介绍了java字符串相似度算法,是Java实现比较典型的算法,具有一定参考借鉴价值,需要的朋友可以参考下
,用于计算两个字符串之间的归一化距离或相似度分数。 0.0 分表示两个字符串绝对不相似,1.0 表示绝对相似(或相等)。 介于两者之间的任何内容都表示两个字符串的相似程度。例子在这个简单的例子中,我们想要计算...
两个字符串的相似度算法实现——编辑距离之Levenshtein距离
“成本”列给出了计算成本的估算值,以分别计算长度为m和n的两个字符串之间的相似度。 归一化? 公制? 类型 成本 典型用法 距离 没有 是 O(米* n) 1 距离相似 是 没有 O(米* n) 1 距离 没有 没有 O(米* n...
Java之词义相似度计算(语义识别、词语情感趋势、词林相似度、拼音相似度、概念相似度、字面相似度)
对输入的两个字符串的相似度进行计算,并给出运行时间,采用java和jsp实现
判断两个字符串的相似度 java 相似度 string
java根据不同的比较条件对比两个或两个以上的字符之间的相似度
使用java调用HanLP分词器实现两个文本相似度对比,可以很快对比出百分率(1=100%)
通过编辑距离算法对两字符串相似度对比后顺序取出所有公共子串
java上机试题 非常经典 SQL 编程 不限制语言于不同的字符串,我们希望能有办法判断相似程度,我们定义了一套操作方法来把两个不相同的字符串变得...给定任意两个字符串,你是否能写出一个算法来计算出它们的相似度呢?
使用java实现对两个字符串进行比较分析其相似度。
字符串相似度.NET Java字符串相似性的.NET端口: : 一个... “成本”列给出了计算成本的估算值,以分别计算长度为m和n的两个字符串之间的相似度。 归一化? 公制? 类型成本距离没有是O(米* n) 1距离相似是没有O
4. 请给出Java代码,实现两个字符串的相似度计算方法。5. 请简述Java中的多线程编程,并给出一个实例。 6. 请给出Java代码,实现从一个文本文件中读取数据并排序的过程。 7. 请简述Java中的集合框架,并给出一个实例...
Levenshtein Distance算法可以看作动态规划 它的思路就是从两个字符串的左边开始比较 记录已经比较过的子串相似度 实际上叫做距离 然后进一步得到下一个字符位置时的相似度 用下面的例子: GUMBO和GAMBOL 当算到矩阵D...
NLP-作业 两个给定文本之间的余弦相似度 在终端上运行程序: $ javac CosineSimilarity.java $ java CosineSimilarity.... 在此之后,输入两个字符串文本。 程序将生成向量映射表,然后是文本之间的余弦相似度得分。
简单的代码相似度检测,使用Java编写。 算法步骤: S1:剔除程序中所有注释、空行、空格 S2:剔除程序中所有变量、函数名 ...S4:两个特征串之间,使用字符串适量距离(Levenshtein Distance)计算相似度。
而衡量两个字符串的相似性有很多种方法,如最直接的利用hashcode,以及经典的主题模型或者利用词向量将文本抽象为向量表示,再通过特征向量之间的欧式距离或者皮尔森距离进行度量。本文围绕文本相似性度量的主题,从...
D:\002 我的工具类\012 计算地球两个经纬度之间距离\CoordinateUtil.java D:\002 我的工具类\014 json D:\002 我的工具类\014 json\JsonUtils.java D:\002 我的工具类\015 cookie D:\002 我的工具类\015 cookie\...