设为首页收藏本站

LUPA开源社区

 找回密码
 注册
文章 帖子 博客
LUPA开源社区 首页 业界资讯 技术文摘 查看内容

程序员编程艺术第二十八~二十九章:最大连续乘积子串、字符串编辑距离 ...

2013-3-28 14:32| 发布者: 红黑魂| 查看: 3841| 评论: 0|原作者: v_JULY_v|来自: CSDN博客

摘要: 前言    时间转瞬即逝,一转眼,又有4个多月没来更新blog了,过去4个月都在干啥呢?对的,今2013年元旦和朋友利用业余时间一起搭了个方便朋友们找工作的编程面试算法论坛:为学论坛http://www.51weixue.com/。最近 ...

类似

    上述问题类似于编程之美上的下述一题「以下内容摘自编程之美第3.3节」:

许多程序会大量使用字符串。对于不同的字符串,我们希望能够有办法判断其相似程度。我们定义了一套操作方法来把两个不相同的字符串变得相同,具体的操作方法为:

  1. 修改一个字符(如把“a”替换为“b”);
  2. 增加一个字符(如把“abdd ”变为“aebdd ”);
  3. 删除一个字符(如把“travelling”变为“traveling”)。
    比如,对于“abcdefg”和“abcdef ”两个字符串来说,我们认为可以通过增加/减少一个“g”的方式来达到目的。上面的两种方案,都仅需要一次操作。把这个操作所需要的次数定义为两个字符串的距离,而相似度等于“距离+1”的倒数。也就是说,“abcdefg”和“abcdef”的距离为1,相似度为1 / 2 = 0.5。
给定任意两个字符串,你是否能写出一个算法来计算出它们的相似度呢?


    这样,很快就可以完成一个递归程序,如下所示:

  1. Int CalculateStringDistance(string strA, int pABegin, int pAEnd,    
  2.    string strB, int pBBegin, int pBEnd)     
  3. {    
  4.      if(pABegin > pAEnd)    
  5.      {    
  6.           if(pBBegin > pBEnd)    
  7.                return 0;     
  8.           else    
  9.      
  10.                return pBEnd – pBBegin + 1;    
  11.      }    
  12.     
  13.      if(pBBegin > pBEnd)    
  14.      {    
  15.           if(pABegin > pAEnd)    
  16.                return 0;    
  17.           else    
  18.                return pAEnd – pABegin + 1;    
  19.      }    
  20.     
  21.      if(strA[pABegin] == strB[pBBegin])    
  22.      {    
  23.           return CalculateStringDistance(strA, pABegin + 1, pAEnd,    
  24.             strB, pBBegin + 1, pBEnd);    
  25.      }    
  26.      else    
  27.      {    
  28.           int t1 = CalculateStringDistance(strA, pABegin, pAEnd, strB,     
  29.             pBBegin + 1, pBEnd);    
  30.           int t2 = CalculateStringDistance(strA, pABegin + 1, pAEnd,     
  31.             strB,pBBegin, pBEnd);    
  32.           int t3 = CalculateStringDistance(strA, pABegin + 1, pAEnd,    
  33.             strB,pBBegin + 1, pBEnd);    
  34.           return minValue(t1,t2,t3) + 1;    
  35.      }    
  36. }    

    上面的递归程序,有什么地方需要改进呢?在递归的过程中,有些数据被重复计算了。比如,如果开始我们调用CalculateStringDistance(strA,1, 2, strB, 1, 2),下图是部分展开的递归调用。

     可以看到,圈中的两个子问题被重复计算了。为了避免这种不必要的重复计算,可以把子问题计算后的解存储起来。如何修改递归程序呢?还是DP!请看此链接:http://www.cnblogs.com/yujunyong/articles/2004724.html。 


深入

  1. 详细读者朋友们也已经看到了,百度/Google经常喜欢出这个字符串编辑距离,实际上,关于这个“编辑距离”问题在搜索引擎中有着重要的作用,如搜索引擎关键字查询中拼写错误的提示,如下图所示,当你输入“Jult”后,因为没有这个单词“Jult”,所以搜索引擎猜测你可能是输入错误,进而会提示你是不是找“July”:
  2. 但这个拼写错误检查的原理是什么呢?Google是基于贝叶斯统计推断的方法,相关原理详情可以看下Google的研发总监Peter Norvig写的这篇文章:http://norvig.com/spell-correct.html,以及fuanyif写的这篇:http://www.ruanyifeng.com/blog/2012/10/spelling_corrector.html
  3. 关于什么是“编辑距离”:一个快速、高效的Levenshtein算法实现,这个是计算两个字符串的算法,Levenshtein距离又称为“编辑距离”,是指两个字符串之间,由一个转换成另一个所需的最少编辑操作次数。当然,次数越小越相似。这里有一个BT树的数据结构,挺有意思的:http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees
  4. 最后,Lucene中也有这个算法的实现(我想,一般的搜索引擎一般都应该会有此项拼写错误检查功能的实现),下面是lucene的源码(并没有太多优化,与实际工程中java注重实用性的原则并不背离):
    1. public final class LevensteinDistance {  
    2.    
    3.     public LevensteinDistance () {  
    4.     }  
    5.       
    6. // Compute Levenshtein distance:   
    7. // see org.apache.commons.lang.StringUtils#getLevenshteinDistance(String, String)  
    8.       
    9.     public float getDistance (String target, String other) {  
    10.       char[] sa;  
    11.       int n;  
    12.       int p[];   
    13. //'previous' cost array, horizontally  
    14.       int d[];   
    15. // cost array, horizontally  
    16.       int _d[];   
    17. //placeholder to assist in swapping p and d  
    18.    
    19.         sa = target.toCharArray();  
    20.         n = sa.length;  
    21.         p = new int[n+1];   
    22.         d = new int[n+1];   
    23.          
    24.         final int m = other.length();  
    25.         if (n == 0 || m == 0) {  
    26.           if (n == m) {  
    27.             return 1;  
    28.           }  
    29.           else {  
    30.             return 0;  
    31.           }  
    32.         }   
    33.           
    34. // indexes into strings s and t  
    35.         int i;   
    36. // iterates through s  
    37.         int j;   
    38. // iterates through t  
    39.    
    40.         char t_j;   
    41. // jth character of t  
    42.    
    43.         int cost;   
    44. // cost  
    45.    
    46.         for (i = 0; i<=n; i++) {  
    47.             p[i] = i;  
    48.         }  
    49.    
    50.         for (j = 1; j<=m; j++) {  
    51.             t_j = other.charAt(j-1);  
    52.             d[0] = j;  
    53.    
    54.             for (i=1; i<=n; i++) {  
    55.                 cost = sa[i-1]==t_j ? 0 : 1;  
    56.                   
    57. // minimum of cell to the left+1, to the top+1, diagonally left and up +cost  
    58.                 d[i] = Math.min(Math.min(d[i-1]+1, p[i]+1),  p[i-1]+cost);  
    59.             }  
    60.    
    61.               
    62. // copy current distance counts to 'previous row' distance counts  
    63.             _d = p;  
    64.             p = d;  
    65.             d = _d;  
    66.         }  
    67.    
    68.           
    69. // our last action in the above loop was to switch d and p, so p now  
    70.           
    71. // actually has the most recent cost counts  
    72.         return 1.0f - ((float) p[n] / Math.max(other.length(), sa.length));  
    73.     }  
    74.    
    75. }  

扩展

    当然,面试官还可以继续问下去,如请问,如何设计一个比较两篇文章相似性的算法?这个问题的讨论可以看看这里:http://t.cn/zl82CAH。OK,字符串编辑距离这个问题实用性很强,限于篇幅,详情读者自己深入吧。


参考文献及推荐阅读

  1. 参与最大乘积连续子串问题的讨论:http://www.51weixue.com/thread-246-1-1.html,在线提交你的代码:http://hero.pongo.cn/Question/Details?ID=19&ExamID=19
  2. 参与字符串编辑距离问题的讨论:http://www.51weixue.com/thread-482-1-1.html,在线提交你的代码:http://hero.pongo.cn/Question/Details?ID=20&ExamID=20
  3. 编程之美;
  4. 程序员第一~二十九章集锦:http://blog.csdn.net/v_JULY_v/article/details/6460494
  5. http://www.bjwilly.com/archives/395.html

后记

    有种人喜欢远观代码,以欣赏代码的角度阅读代码,所谓如镜中美女只可远观不可亵玩焉,发现自己也陷入了这种境地。昨天买的一本《提高C++性能的编程技术》,书不错,推荐给大家。
    想看编程面试算法题的讲解,就进本blog;想参与笔试面试题的讨论,就上为学论坛;想在线刷笔试面试题,就上英雄会,祝各位好运,享受生活,享受工作,享受思考和编码的乐趣。
    July、二零一三年三月二十一日。

http://blog.csdn.net/v_july_v/article/details/8701148

酷毙

雷人

鲜花

鸡蛋

漂亮
  • 快毕业了,没工作经验,
    找份工作好难啊?
    赶紧去人才芯片公司磨练吧!!

最新评论

关于LUPA|人才芯片工程|人才招聘|LUPA认证|LUPA教育|LUPA开源社区 ( 浙B2-20090187 浙公网安备 33010602006705号   

返回顶部