计算字符串的相似度.pdf

该【计算字符串的相似度 】是由【和合】上传分享，文档一共【6】页，该文档可以免费在线阅读，需要了解更多关于【计算字符串的相似度 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。写书评,赢取《编程之美——微软技术面试心得》
计算字符串的相似度
许多程序会大量使用字符串。对于不同的字符串,我们希望能够有办法判断其相似
程度。我们定义了一套操作方法来把两个不相同的字符串变得相同,具体的操作方法为:
(如把“a”替换为“b”)。
(如把“abdd”变为“aebdd”)。
(如把“travelling”变为“traveling”)。
比如,对于“abcdefg”和“abcdef”两个字符串来说,我们认为可以通过增加/减少一个“g”
的方式来达到目的。上面的两种方案,都仅需要一次操作。把这个操作所需要的次数定
义为两个字符串的距离,而相似度等于“距离+1”的倒数。也就是说,“abcdefg”和“abcdef”
的距离为1,相似度为1/2=。
给定任意两个字符串,你是否能写出一个算法来计算出它们的相似度呢?
2写书评,赢取《编程之美——微软技术面试心得》
分析与解法
不难看出,两个字符串的距离肯定不超过它们的长度之和(我们可以通过删除操作
把两个串都转化为空串)。虽然这个结论对结果没有帮助,但至少可以知道,任意两个
字符串的距离都是有限的。
我们还是应该集中考虑如何才能把这个问题转化成规模较小的同样的问题。如果有
两个串A=xabcdae和B=xfdfa,它们的第一个字符是相同的,只要计算A[2,…,7]=abcdae
和B[2,…,5]=fdfa的距离就可以了。但是如果两个串的第一个字符不相同,那么可以
进行如下的操作(lenA和lenB分别是A串和B串的长度):
,然后计算A[2,…,lenA]和B[1,…,lenB]的距离。
,然后计算A[1,…,lenA]和B[2,…,lenB]的距离。
,然后计算A[2,…,lenA]和B[2,…,
lenB]的距离。
,然后计算A[2,…,lenA]和B[2,…,
lenB]的距离。
,然后计算A[1,…,lenA]和
B[2,…,lenB]的距离。
,然后计算A[2,…,lenA]和
B[1,…,lenB]的距离。
写书评,赢取《编程之美——微软技术面试心得》
在这个题目中,我们并不在乎两个字符串变得相等之后的字符串是怎样的。所以,
可以将上面6个操作合并为:
,再将A[2,…,lenA]和B[1,…,lenB]变成相同字符串。
,再将A[1,…,lenA]和B[2,…,lenB]变成相同字符串。
,再将A[2,…,lenA]和B[2,…,lenB]变成相同字符串。
这样,很快就可以完成一个递归程序:
4写书评,赢取《编程之美——微软技术面试心得》
代码清单3-6
IntCalculateStringDistance(stringstrA,intpABegin,intpAEnd,stringstrB,
intpBBegin,intpBEnd)
{
if(pABegin>pAEnd)
{
if(pBBegin>pBEnd)
return0;
else
returnpBEnd–pBBegin+1;
}
if(pBBegin>pBEnd)
{
if(pABegin>pAEnd)
return0;
else
returnpAEnd–pABegin+1;
}
if(strA[pABegin]==strB[pBBegin])
{
returnCalculateStringDistance(strA,pABegin+1,pAEnd,strB,
pBBegin+1,pBEnd);
}
else
{
intt1=CalculateStringDistance(strA,pABegin+1,pAEnd,strB,
pBBegin+2,pBEnd);
intt2=CalculateStringDistance(strA,pABegin+2,pAEnd,strB,
pBBegin+1,pBEnd);
intt3=CalculateStringDistance(strA,pABegin+2,pAEnd,strB,
pBBegin+2,pBEnd);
returnminValue(t1,t2,t3)+1;
}
}
上面的递归程序,有什么地方需要改进呢?在递归的过程中,有些数据被重复计算
了。比如,如果开始我们调用CalculateStringDistance(strA,1,2,strB,1,2),
图3-4是部分展开的递归调用:
写书评,赢取《编程之美——微软技术面试心得》
图3-4
可以看到,圈中的两个子问题被重复计算了。为了避免这种不必要的重复计算,可以
把子问题计算后的解存储起来。如何修改递归程序呢?这个问题就留给读者自己完成吧!
6写书评,赢取《编程之美——微软技术面试心得》