Nine Algorithms
21 Sep 2014 Category: Reading最近看了John MacCormick写的Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today’s Computers。此书为科普读物，适合对计算机不太熟悉但感兴趣的人阅读。国内中信出版社已发行中译版。
Intro
书中提到的九大算法：
- 搜索引擎索引：如何在海量网页中进行关键字搜索；
- Page Rank：如何决定网页搜索中的排名高低；
- 公钥加密：如何通过公开的信息传递加密的信息而不被其他人获知；
- 纠错码：如何一定程度上校正信息传递过程中发生的错误；
- 图形识别：图像识别算法的基本原理；
- 数据压缩：如何无损或者有损的压缩数据；
- 数据库：如何保证在对数据库操作过程中同时保证数据库的一致性；
- 数字签名：如何进行数字签名并能保证不被人伪造；
- 可计算性：通过反证法推论能发现所有软件crash bug的程序是不存在的；
My interests
Encoding
这几大算法中，和我工作直接相关的，就是“纠错码”，如UMTS中常用的Turbo编码和convolutional编码。而各种编码机制的原理，简而言之，就是用冗余换取信息传递时的损耗。好的编码算法，可以传递尽量少的冗余信息，但仍能最大程度的还原传递过程中，被破坏过的原始信息。实际使用中，并不是冗余度越低越好。因为不是所有产品对纠错要求都这么高，而这种算法相对复杂，对计算能力和功耗要求较高，因此未必适合所有产品。应基于产品应用场景和实际硬件，选择最合适的编码算法。
Encryption
其他算法中，个人感兴趣的有“公钥加密”，“数据压缩”，“数字签名”和“可计算性”。其中“公钥加密”和“数字签名”都涉及到RSA加密算法，该算法核心是欧拉定理。而至今它都未被破解的原因，在于现今仍无法找到有效的方式分解一个大的整数的因子，只能暴力破解。如大家一眼可以看出，14的两个因子是2和7。而如果是9709549，你可能要花上一番功夫才能知道，它的两个质数因子分别是2719和3571。如长度更大，想分析出它的因子难度将更大，甚至用最强劲的计算机也无法暴力破解。
Compression
“数据压缩”的基本原理是找到数据中重复的pattern，然后用更精简的方式(shorter symbol)替代那些重复的信息比特。和编码相反，它的原理是尽可能的消除冗余。也就是说，如果信息是完全随机杂乱，无任何规律可循，那么它的可压缩度就为0。最初的压缩算法是香农(Claude Shannon)1948年在贝尔实验室提出的。（又见香农！）
Computable
“可计算性”涉及到图灵机(Turing machine)，作者通过简单的反证法，先验证了无法找到一种程序，可以在“输入的程序在输入自己时，若crash就输出yes；若不crash输出就直接crash”。反推出“能找到所有软件crash bug的程序”是不存在的。这里之所以我会感兴趣，说明希望一劳永逸能用机器寻找出所有程序bug是不存在的，起码在一段时间内，测试人员还是有口饭吃的。但以后机器变得更加智能，就不好说了。
Database consistency
对Database不是很熟悉，此书介绍的主要集中在如何保证数据库的一致性上，因为一旦出现不一致，就可能发生数据死锁(dead-lock)的情况。为了保证一致性，这里提到了一种方法，竟然在我工作中也经常使用，就是prepare-then-commit。因为数据库可能分散在多个备份中，一旦其中一份(primary)发生了更新，其他几份也要相应更新。使用prepare-then-commit方式，可以最大限度的将准备工作在各个备份处先做好，然后commit时同时生效即可。如果在prepare过程中，某个备份出了问题，可以很轻易对已经prepare好的其他备份执行cancel即可。
这个原理使用在UMTS中，就是NBAP协议中存在prepare/commit/cancel message，保证了各网元以及Node B各子模块系统在重配过程中能协同生效。
Summary
看这本书主要为了消遣，最大的收获是作者讲解技术问题时的方式，有些算法的原理不算复杂。但一旦涉及到如何实现和应用，就会有非常多的技术名词和细节。不过作者通过一些精巧设计的例子，如通过“染色”讲解“公钥加密”，“锁和钥匙”解释“数字签名”等，将复杂的理论化解为普通人也能看懂的道理，相当了不起。上半年做过一次某feature的workshop，为了让大家能更深入地了解其中的原理，也做过类似的尝试。想用更生动活泼的例子来解释，但效果并不算好。发现要找到合适的例子，最好是基本原理互通但浅显还不生硬，还真是不容易！
另外一点启发就是，有些算法，起初都不复杂，如“搜索引擎”、“图像识别”和“压缩”最初的原理非常简单直观。但能将生活中的发现提炼成算法，却不容易。而能将算法实现和演进，并真正应用到实际中，又是一次大的飞跃。
而算法的普适性也让我非常吃惊，不用说现在计算机领域广泛应用的加密，压缩，编码等算法，就是上文提到的“prepare-then-commit”这种方法，既应用于database操作，又适用于通信领域的信令面流程。应用的广泛程度，着实让人震惊。学习的深度是一方面，广度也可以让人接触到其他领域优秀的方式方法，反过来优化自己工作的领域。