《算法（第4版）》导读（下）

 

  第五章 字符串

对很多程序员更有用的其实是字符串的处理，一般算法书讲得少，觉得似乎不是特别高端，不如动态规划炫酷，但《算法（第4版）》着重讲解了这部分内容。

5.1 字符串排序，一开始讲的可以认为是针对多键(multiple keys)或者多个数据域的排序。对于字符串来说，低位优先(LSD)可以更快地对等长的字符串来排序，而不会去用快速排序这些普适算法，这样处理字符串更快，而字符串的取值空间有限特性很重要。而不等长的可以采用高位优先(MSD)，后面进一步改进成字符串的三路快速排序，深入探讨了字符串排序。

Bentley和Sedgewick的论文Fast Algorithms for Sorting and Searching Strings可以深入研究(http://www.cs.princeton.edu/~rs/strings/paper.pdf)，阐述了Multikey Quicksort的原理并分析了性能。

另外，Sedgewick的讲义Advanced Topics in Sorting(https://www.cs.princeton.edu/~rs/AlgsDS07/05AdvTopicsSorting.pdf)有关于排序的一些高级主题。

5.2 trie，也就是单词查找树。搜索框就是简单的tire，比如想输入abstract，那么依次输入a-b-s-t，先从树上走a这个分支，再走b随后走s继续走t分支，最后剩下的以abst为前缀的单词也没剩几个了，很容易找到abstract这个单词，注意这种实现需要26叉树(可用ternary search trie改进之)。trie非常有用，还有后缀树和后缀数组等内容也可以作为选学材料。

字符串的查找，所谓模式匹配，Sedgewick强调的是后面的一系列算法(当然不能绕过他老师的KMP算法)，例如Boyer-Moore算法和Rabin-Karp算法，这两种更有用而且更快。KMP强烈依赖于自我的模式，要自身重复，但很多字符串不具备这些特性，而Boyer-Moore或Rabin-Karp更适合于一般的字符串查找。

讲完上述内容就开始讨论正则表达式。又一次说明了字符串这章对实际程序员更有用，一般算法教材讲的图算法还有动态规划对于普通程序员来说，要想用好其实很难，而字符串却经常能感受到。

5.5 数据压缩，这部分是非常好的算法应用场景。像CMU的"真实世界的算法"这门课程里讲了很多数据压缩的算法(还有纠错编码和线性规划)，也就是实际算法可以看到很多字符串的处理，又比如Huffman编码用到了优先级队列，处理数据可以用到trie还有散列，形形色色算法的应用让你亲身体验算法之大用。其实，数据压缩不是太难，自己如果可以很快实现压缩软件会有一定成就感。我讲信息论课程的时候会让学生做一般文本文件的数据压缩，看看压缩和解压的效率与常用软件如Winzip或者7zip有什么性能差异，这样能极大地提升学习兴趣。此外，文本压缩还有一些字典系列的编码(7zip的体系)，还会有更多算法与数据结构的应用，特别是散列还有滑动窗的设置，如果能实现基本的LZ77和LZ78，那么算法了解和应用又能上一个台阶。我也借鉴《算法（第4版）》的一些特点，让学生实现DNA序列的压缩，这样会有趣味性，也更有针对性。

CMU的15-853: Algorithms in the Real World这门课程(http://www.cs.cmu.edu/~guyb/realworld.html)非常值得一看，非常适合进阶学习。

 

 第六章 实境

《算法（第4版）》前五章的内容很精炼，和其他算法书都不一样，也许称之为《数据结构与算法》更合适一点，因为讲数据结构的内容较多。

第6章就是讲真实的问题，并由此引出前面的算法和指导读者应该学习什么样的内容。在真实问题的背景下把前面的内容拿出来再讲，其实效果非常好。

典型例子是离散事件仿真(DES)，例如公交车的调度仿真要考虑某个线路何时发车。发车相当于一个"事件"，有很多车会发车但时间不同，我们不是按照固定时间间隔(例如分钟)向前逐个处理和方针，而是处理"事件"并将其放入优先级队列，只需按照事件发生时间先后取出并处理，最早出现的事件肯定最先出队，这样能够极大提升算法仿真速度。不能按时间间隔去逐个处理，这样特别慢，比如当前时间为6:30而如果下一个事件7:10出现，那么时间点直接推进到7:10即可。

 

 语言选用

《算法》这个系列的书最开始用C语言，可能是想让他老师Knuth的书更简单容易读，另外那个年代C还是比较流行的。后来大家用C++，Sedgewick也推出了相关版本，并且也推进到Java版本。但《算法（第4版）》不标注语言版本直接用Java，也说明Java的热度，实际上没有提到什么语言也说明不想写别的语言版本了。

不过，现在用Python也很多而且也更接近于机器学习和数据处理，这个其实很合理，一门语言学好了能做很多事情，所以都去学Python。而Sedgewick紧跟时代，又出了专门讲Python的教材，我本来觉得第5版很可能就是Python版(假设有第5版)。因为前期的Python基础的书已经有了，程序设计的知识讲过了，后面直接用Python讲算法课而且还可以做机器学习，这也是MIT多年讲《算法导论》的首选语言，大势所趋嘛，而且实现起来方便。最关键的是，很多人不愿意用复杂的语言解决问题，现在的人越来越懒:-)而且重度依赖于机器，没事不用C和C++写程序。

为了求证这个Python版本的猜测，我邮件求证了Wayne，他说暂无Python版本的写作计划，其原因是用Python写的代码远远慢于Python自身提供的库函数，这样起不到展示算法和数据结构效率的目的。

 

 排版

实际上排版是《算法（第4版）》的一大特色，第3版用LaTeX排版，而第4版居然用InDesign排版，但是双色印刷相当精美细致。主要是公式很少，所以用了InDesign。

我邮件咨询过Wayne，这么复杂的图能用LaTeX排出来么？他的回复让我很诧异，居然是用InDesign排版，另外这些精美的插图矢量图是拿AI画的，所以融合起来用Adobe一家的产品更好，保持一致。实际上从成书效果来看，排版确实美轮美奂，非常满意。

当然也是因为《算法（第4版）》的公式少，实际上这本书基本不讲公式，能不用就不用，这点节约了大家的脑力。因为数学确实会给很多人带来困扰，实际上数学让人会有特别深的恐惧感。算法再加数学更让人害怕了，所以《算法（第4版）》用到了算法运行实况(到底如何运行，一步步告诉大家)和可视化的方法。

《算法（第4版）》和前3版有将近40年的传承，而第二作者Wayne为这一版本付出了相当大的心血，这点很难得(绝大多数高校教师因为要做科研所以做不到这点，而且也没有这么多精力来精心编撰教材)，而Wayne投入了很多精力放在这本书上。不过，从绘图和排版软件的选择上来说，还是比较符合这本书的目的，主要能更好服务于普通读者，一看就不是特别难，而且又是彩色印刷，所以很能吸引眼球。

 

  Q&A

1. 先修课程是什么？有一点离散数学知识就可以了，《算法导论》后面的附录基本也就够了，可以放心学《算法（第4版）》。

2. 要学什么数学？学别的算法书，离散数学是要学的，高等数学也是要学的，概率论也是不能丢的，线性代数也得非常好才行，矩阵如果不会好多东西用不成。但《算法（第4版）》里基本没有什么矩阵，哈哈。当然，多学一点离散数学更好，但是要看个人能力而定。既然不能学复杂的内容，那就吸收点有用的东西让程序提升吧，一定要养成很好的品味，有好坏的算法之分，这点很重要。

3. 多久能看完？不要指望很快看完。

4. 应该买中文版还是英文版？英文教材和课程其实学起来还是有点难度，所以大家根据自己需要和能力范围选择购买中文版或英文版。

5. 写程序的态度应该如何？尽量少写低效的算法，甚至于低效的程序，要尽量提高程序的性能。

《算法（第4版）》，帮助你在平常而又不平凡的程序设计里找到更多乐趣！

如果你想和谢老师一起学习算法，那么你可以扫码加入谢老师的知识星球哦~ (图灵友情推荐需付费168，大家按需选择哦）

福利时间

本期为大家送出3本《算法（第4版）》，小伙伴们说说自己在平时的工作中都会用到算法的哪些知识。或者说说你在学习算法时遇到哪些困难都是怎么解决的。欢迎大家畅所欲言。

本期小鹿和大家玩一个新玩法。精选留言我们会选出2位读者获得赠书，在文章一条、二条、三条下留言都可以参与哦~ 剩下的1本，我们用微信小程序来抽出。

请大家扫描识别下图中的二维码，点击参与就能在小程序上参加抽奖啦！注：完成抽奖后会自动发送通知，获奖的小伙伴别忘了填写地址哟~ 留言和小程序同时开奖，截止日期2017年12月21日，10：00。

点击【阅读原文】购买《算法（第4版）》