类似 上述问题类似于编程之美上的下述一题「以下内容摘自编程之美第3.3节」: 许多程序会大量使用字符串。对于不同的字符串,我们希望能够有办法判断其相似程度。我们定义了一套操作方法来把两个不相同的字符串变得相同,具体的操作方法为:
- 修改一个字符(如把“a”替换为“b”);
- 增加一个字符(如把“abdd ”变为“aebdd ”);
- 删除一个字符(如把“travelling”变为“traveling”)。
比如,对于“abcdefg”和“abcdef ”两个字符串来说,我们认为可以通过增加/减少一个“g”的方式来达到目的。上面的两种方案,都仅需要一次操作。把这个操作所需要的次数定义为两个字符串的距离,而相似度等于“距离+1”的倒数。也就是说,“abcdefg”和“abcdef”的距离为1,相似度为1 / 2 = 0.5。 给定任意两个字符串,你是否能写出一个算法来计算出它们的相似度呢?
这样,很快就可以完成一个递归程序,如下所示:
- Int CalculateStringDistance(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 CalculateStringDistance(strA, pABegin + 1, pAEnd,
- strB, pBBegin + 1, pBEnd);
- }
- else
- {
- int t1 = CalculateStringDistance(strA, pABegin, pAEnd, strB,
- pBBegin + 1, pBEnd);
- int t2 = CalculateStringDistance(strA, pABegin + 1, pAEnd,
- strB,pBBegin, pBEnd);
- int t3 = CalculateStringDistance(strA, pABegin + 1, pAEnd,
- strB,pBBegin + 1, pBEnd);
- return minValue(t1,t2,t3) + 1;
- }
- }
上面的递归程序,有什么地方需要改进呢?在递归的过程中,有些数据被重复计算了。比如,如果开始我们调用CalculateStringDistance(strA,1, 2, strB, 1, 2),下图是部分展开的递归调用。 
深入- 详细读者朋友们也已经看到了,百度/Google经常喜欢出这个字符串编辑距离,实际上,关于这个“编辑距离”问题在搜索引擎中有着重要的作用,如搜索引擎关键字查询中拼写错误的提示,如下图所示,当你输入“Jult”后,因为没有这个单词“Jult”,所以搜索引擎猜测你可能是输入错误,进而会提示你是不是找“July”:
 但这个拼写错误检查的原理是什么呢?Google是基于贝叶斯统计推断的方法,相关原理详情可以看下Google的研发总监Peter Norvig写的这篇文章:http://norvig.com/spell-correct.html,以及fuanyif写的这篇:http://www.ruanyifeng.com/blog/2012/10/spelling_corrector.html。- 关于什么是“编辑距离”:一个快速、高效的Levenshtein算法实现,这个是计算两个字符串的算法,Levenshtein距离又称为“编辑距离”,是指两个字符串之间,由一个转换成另一个所需的最少编辑操作次数。当然,次数越小越相似。这里有一个BT树的数据结构,挺有意思的:http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees;
- 最后,Lucene中也有这个算法的实现(我想,一般的搜索引擎一般都应该会有此项拼写错误检查功能的实现),下面是lucene的源码(并没有太多优化,与实际工程中java注重实用性的原则并不背离):
- public final class LevensteinDistance {
-
- public LevensteinDistance () {
- }
-
-
-
-
- public float getDistance (String target, String other) {
- char[] sa;
- int n;
- int p[];
-
- int d[];
-
- int _d[];
-
-
- sa = target.toCharArray();
- n = sa.length;
- p = new int[n+1];
- d = new int[n+1];
-
- final int m = other.length();
- if (n == 0 || m == 0) {
- if (n == m) {
- return 1;
- }
- else {
- return 0;
- }
- }
-
-
- int i;
-
- int j;
-
-
- char t_j;
-
-
- int cost;
-
-
- for (i = 0; i<=n; i++) {
- p[i] = i;
- }
-
- for (j = 1; j<=m; j++) {
- t_j = other.charAt(j-1);
- d[0] = j;
-
- for (i=1; i<=n; i++) {
- cost = sa[i-1]==t_j ? 0 : 1;
-
-
- d[i] = Math.min(Math.min(d[i-1]+1, p[i]+1), p[i-1]+cost);
- }
-
-
-
- _d = p;
- p = d;
- d = _d;
- }
-
-
-
-
-
- return 1.0f - ((float) p[n] / Math.max(other.length(), sa.length));
- }
-
- }
扩展 当然,面试官还可以继续问下去,如请问,如何设计一个比较两篇文章相似性的算法?这个问题的讨论可以看看这里: http://t.cn/zl82CAH。OK,字符串编辑距离这个问题实用性很强,限于篇幅,详情读者自己深入吧。
参考文献及推荐阅读后记 有种人喜欢远观代码,以欣赏代码的角度阅读代码,所谓如镜中美女只可远观不可亵玩焉,发现自己也陷入了这种境地。昨天买的一本《提高C++性能的编程技术》,书不错,推荐给大家。 想看编程面试算法题的讲解,就进本 blog;想参与笔试面试题的讨论,就上 为学论坛;想在线刷笔试面试题,就上 英雄会,祝各位好运,享受生活,享受工作,享受思考和编码的乐趣。 July、二零一三年三月二十一日。
http://blog.csdn.net/v_july_v/article/details/8701148 |