Nine Algorithms

最近看了John MacCormick写的Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today’s Computers。此书为科普读物,适合对计算机不太熟悉但感兴趣的人阅读。国内中信出版社已发行中译版

Intro

Nine algorithms that changed future

书中提到的九大算法:

  1. 搜索引擎索引:如何在海量网页中进行关键字搜索;
  2. Page Rank:如何决定网页搜索中的排名高低;
  3. 公钥加密:如何通过公开的信息传递加密的信息而不被其他人获知;
  4. 纠错码:如何一定程度上校正信息传递过程中发生的错误;
  5. 图形识别:图像识别算法的基本原理;
  6. 数据压缩:如何无损或者有损的压缩数据;
  7. 数据库:如何保证在对数据库操作过程中同时保证数据库的一致性;
  8. 数字签名:如何进行数字签名并能保证不被人伪造;
  9. 可计算性:通过反证法推论能发现所有软件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操作,又适用于通信领域的信令面流程。应用的广泛程度,着实让人震惊。学习的深度是一方面,广度也可以让人接触到其他领域优秀的方式方法,反过来优化自己工作的领域。