字符串相似度计算.pdf

记忆过往
总有一个人需要这些知识。本博客信息正在迁往
/
[置顶] 字符串相似度计算
分类: C Program Cplusplus Program Algorithms 2012-10-14 22:33 10427人阅读评论(0) 收藏举报
email算法编程优化c
已迁移到:hives/58
思想是编程之美上面的,我只是做了一点点优化。。。
许多程序会大量使用字符串。对于不同的字符串,我们希望能够有办法判断其相似程序。我们定义一套操作方法来
把两个不相同的字符串变得相同,具体的操作方法为:
(如把“a”替换为“b”);
(如把“abdd”变为“aebdd”);
(如把“travelling”变为“traveling”);
比如,对于“abcdefg”和“abcdef”两个字符串来说,我们认为可以通过增加/减少一个“g”的方式来达到目
的。上面的两种方案,都仅需要一次。把这个操作所需要的次数定义为两个字符串的距离,而相似度等于“距离
+1”的倒数。也就是说,“abcdefg”和“abcdef”的距离为1,相似度为1/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[2,...,lenA]和B[2,...,lenB]变成相字符串。
,再将A[1,...,lenA]和B[2,...,lenB]变成相字符串。
这样,很快就可以完成一个递归程序。
但是源程序在递归调用