在读完《改变未来的九大算法》（作者：约翰·麦考密克）后，你不会成为一名更加熟练的计算机用户。但你会更加珍视自己每天在所有计算设备上不停使用的思想的美。我们每天都会进行多次搜索查询，但是你想过这个令人惊叹的工具是如何奏效的吗？谷歌的精英管理层因为谷歌“以超乎寻常的技巧返回相关度极高的结果”而获奖，他们是怎么做到的？《改变未来的九大算法》将带你一探究竟。

Google得出的搜索结果是如何产生的？

百度为何会陷入“搜索门”，又是什么机制使然？

身处在大数据时代的我们，究竟该如何应对变化莫测的世界？

约翰·麦考密克编著的《改变未来的九大算法》第一次让我们通过简单明了的语言，生动的例证了解支撑计算机王国的灵魂支柱——9大算法，包括人工智能，数据压缩，以及Google著名的Page Rank等。《改变未来的九大算法》精彩地介绍了搜索引擎、Page Rank、公开密钥加密、纠错码、模式识别、数据压缩、数据库、数字签名等内容。

在解释这些算法的同时，作者也向我们展示了充满科学原创精神的计算机世界：因为每一种算法的提出不但延伸了虚拟世界的领域，同时也是人类智慧的彰显，可以被广泛运用于众多领域。

序

第一章 前言：计算机日常运用的卓越思想有哪些？

第二章 搜索引擎索引——在世界上最大的草垛中寻针

第三章 Page Rank——让谷歌腾飞的技术

第四章 公钥加密——用明信片传输秘密

第五章 纠错码——自纠正的错误

第六章 图形识别——从经验中学习

第七章 数据压缩——有益无害

第八章 数据库——追求一致性的征程

第九章 数字签名——这个软件究竟由谁编写？

第十章 什么可以计算？

第十一章 结论：更多在你指尖的精灵？

致谢

注释

搜索引擎对我们的生活产生了深远影响。绝大多数人每天都进行多次搜索查询，但我们极少会停下来思考这个令人惊叹的工具是如何奏效的。搜索引擎提供的海量信息以及搜索结果的速度与质量变得如此平常，如果我们搜索的问题没有在几秒内得到回答，我们就会困惑。我们倾向于忘记，每一个成功的搜索引擎都是从世界上最大的草垛——万维网——寻针。

事实上，搜索引擎提供的超级服务，不仅仅是针对搜索抛出一大堆花哨技术的结果。的确，每个大型搜索引擎公司都运营着一个由无数数据中心组成的国际网络，其中包括数以千计的服务器计算机和先进的网络设备。但没有聪明的算法来组织和检索我们请求的信息，所有这些硬件都会变得毫无用处。因此，在这一章和下一章，我们将探究这样一些算法瑰宝——每次在进行网络搜索时，我们都会用到这些算法。我们很快就会了解到，搜索引擎的两大主要任务就是匹配(matching)和排名(ranking)。这一章将讲述一种聪明的匹配技术：元词把戏(metaword trick)。在下一章，我们将转而讨论排名任务，审视谷歌公司著名的网页排名算法。

匹配和排名

当你发起一次网络搜索查询时会发生什么?以这样一种高屋建瓴的视角开始会很有帮助。我已经说过，搜索有两个主要阶段：匹配和排名。在实际中，搜索引擎将匹配和排名组合成一个流程以实现一致性。但这两个阶段在概念上是独立的，因此我们会假设在排名开始前，匹配已经完成。上图就给出了一个例子，图中查询的是“London bus timetable”(伦敦公共汽车时刻表)，而匹配阶段则回答“哪个网页与我的查询匹配”这个问题——在这个例子中就是所有提到“London bus timetable”的网页。

但现实搜索引擎中的许多查询都有数百、数千乃至数百万个“命中”。而搜索引擎用户通常只喜欢查看几个结果，最多5个或10个。因此，搜索引擎必须从大量命中里挑出最好的几个。一个好的搜索引擎不仅仅会挑出最好的几个命中，而且会以最有用的顺序显示它们——最匹配的页面排在第一，然后是匹配度排名第二的页面，依此类推。

以正确顺序挑选出最好的几个命中被称为“排名”。排名是关键的第二个阶段，紧随最开始的匹配阶段。在搜索行业的残酷世界中，搜索引擎的生死由其排名系统的质量决定。2002年，美国前三大搜索引擎的市场份额基本相当，谷歌、雅虎和MSN在美国的市场份额都在309／0以下。[MSN随后被重新包装成Live Search，之后又被命名为必应(Bing)。]之后几年，谷歌的市场份额迅速扩大，同时将雅虎和MSN的市场份额打压到了20％以下。人们普遍认为，谷歌迅速上升为搜索行业冠军是得益于其排名算法。因此，毫不夸张地说，搜索引擎的生死由其排名系统的质量决定。不过，正如我已经提到的，我们将在下一章探讨排名算法。至于现在，让我们专注于匹配阶段吧。

AltaVista：第一个互联网级别的匹配算法

搜索引擎匹配算法的故事从哪里开始?一个很显然却错误的回答会说从谷歌——21世纪初期最伟大的技术成功故事——开始。事实上，谷歌最初只是两位斯坦福大学研究生的博士学位项目，这个故事不仅温暖人心，而且令人印象深刻。拉里·佩奇(Larry Page)和谢尔盖·布林(sergey Brin)在1 998年组装了一堆计算机硬件来运行一种新的搜索引擎。不到10年，他们的公司成为了互联网时代崛起的最伟大的数字巨人。

不过，互联网搜索的想法已经存在很多年了。最早的商业应用是Infoseek和Lycos(两者都于1994年推出)，以及于1995年推出搜索引擎的AltaVista。20世纪90年代中期的几年中，AltaVista是搜索引擎的王者。当时我还是一名计算机科学研究生，我清楚地记得自己惊叹于AltaVista搜索结果的成熟度。有史以来第一次，有一个搜索引擎能完全索引互联网上每一个页面的全部文本。更可贵的是，眨眼间就能返回结果。要继续理解这个令人回味的技术突破，我们要从接触一个古老的(毫不夸张)概念——索引——开始。

古老的索引  索引的概念是所有搜索引擎背后最基础的思想。但索引并非由搜索引擎发明：事实上，索引的思想几乎和书写本身一样古老。比如，人类学家发现了一座具有五千年历史的巴比伦神庙图书馆，里面按学科对楔形文字泥版进行了分类。因此，索引可以称得上是计算机科学中最古老的有用思想。

如今，“索引”这个词通常指参考书最后的一个板块。你可能想要查看的所有概念都以固定顺序(通常是按字母排序)列出，每一个概念下都列出了这个概念出现的位置(通常是页码)。因此，一本和动物有关的书也许会有一个像“cheetah 124，156”的索引项。这个索引项意味着“cheetah”(猎豹)这个词在第124页和第156页出现过。(让你做个相当有趣的练习，你可以在本书的索引中查询“index”这个词。你应该可以找到这一页。)

互联网搜索引擎的索引和一本书的索引有着相同的工作原理。书“页”现在成了万维网上的网页，而搜索引擎则给互联网上的每个网页分配了一个不同的页码。(是的，互联网上虽然有很多网页——最新的数据显示有成百上千亿个——但计算机很擅长处理大数字。)上图给出了一个会让整个过程更具体的例子。想象万维网只由上面显示的3个短网页组成，它们分别分配到了页码l、2和3。

计算机可以为这三个网页创建一个索引：首先要为出现在任一页面上的所有单词创建一个列表，然后按字母表顺序整理这张列表。我们可以将结果称为单词表(word list)——在这个例子中是“a、cat、dog、mat、on、sat、stood、the、whi：le”。然后计算机会一个单词一个单词地搜遍所有页面。计算机会标注每个单词所在的页码，然后再标注单词表中下一个单词的位置。最终结果显示在上图中。比如，你可以立即看到单词“cat”出现在第1页和第3页，却不在第2页。而单词“’while”只出现在第3页。

通过这种简单方法，搜索引擎就已经能回答许多简单的查询。比如，假设你输入查询词“cat”，搜索引擎能很快跳转到单词表中的“cat”项。(因为字母表是按字母排序的，计算机能很快找到任何项，就像我们可以很快找到词典中的一个单词一样。)一旦计算机找到“cat”项，搜索引擎就能给出该项的页面列表——在这个例子中就是第1页和第3页。现代搜索引擎对结果的组织很合理，只摘取了返回页面的少许片段，不过，我们基本上会忽略这样的细节，将精力集中在搜索引擎如何知道页面“符合”用户输入的查询上。

再举另一个非常简单的例子，让我们来检查一下查询“dog”的步骤。在这个例子中，搜索引擎很快会找到“dog”项，并返回页码2和3。如果查询多个单词，如“cat dog”呢?这表示你正在寻找同时包含单词“cat”和“dog”的页面。通过已有的索引，搜索引擎也能很容易查到结果。搜索引擎首先会单独查找这两个单词，找出它们分别在哪些页面中。结果是“cat”在第1页和第3页，“dog”在第2页和第3页。之后，计算机能快速扫描这两个命中列表，寻找同时出现在两个列表中的页码。在这个例子中，第1页和第2页被排除了，但第3页同时出现在两个列表中，因此最终答案就是第3页上的一次单独命中。与之极其相似的一个策略也适用于超过两个单词的查询。比如，查询“cat the sat”会返回第1页和第3页为命中，因为它们是“cat”(1，3)、“the”(1，2，3)和“sat”(1，3)这个列表的通用元素。

就目前来看，搭建一个搜索引擎听起来相当容易。最简单的索引技术似乎运行得很好，即便对多词查询也是如此。不幸的是，这种简单方法完全不能满足现代搜索引擎的需要。出现这种情况的原因有几个，不过现在我们只会关注其中之一：如何做短语查询。短语查询是指寻找一个确切短语的查询，而非凑巧一些单词出现在页面中的某些地方。比如，“cat sat”查询和cat sat查询的意义截然不同①。cat sat查询寻找的是在任何位置包含“cat”和“sat”两个单词的页面，不考虑顺序；而“cat sat”查询寻找的是包含单词“cat”之后紧跟单词“sat”的页面。在上面那个由三个网页组成的简单例子中，cat sat查询结果命中第1页和第3页，但“cat sat”杏询只返回一次命中，就在第1页。P15-20

计算机行业正在改变我们的社会，正如物理学和化学在前两个世纪给社会带来的巨大改变一样。的确，数字技术几乎影响甚至颠覆了我们生活的方方面面。鉴于计算机行业对现代社会的重要性，人们对让这一切成为可能的基本概念却知之甚少，这显得有点自相矛盾。对这些概念的研究是计算机科学的核心，而这本麦考密克的新书则是向大众展示这些概念的少数书籍之一。

人们较少视计算机科学为一门学科，其中一个原因是，高中极少开设计算机科学这门课程。虽然人们通常认为要强制开设物理学和化学基础，但作为独立学科的计算机科学，通常只有在大学阶段才开设此课程。况且，学校讲授的”计算机”或”信息与通信技术“知识，通常只是略高于使用软件的技能训练。因此．学生们认为计算机学科枯燥也并不意外；而他们在娱乐和通信上使用计算机技术的天然热情，也被创造这类技术缺乏学术深度的印象所减弱。这些问题被认为是导致过去10年大学计算机科学专业学生人数下降一半的核心原因。考虑到数字技术对现代社会的极度重要性，让人们重新领略计算机科学的奇妙之处已经刻不容缓。

2008年，我很荣幸地被选为第180届英国皇家学院圣诞讲座(RoyalInstimtion Christmas Lectures)的演讲人，该讲座由迈克尔·法拉第(Michael Faraday)于1826 ff-C2Cg。2008年圣诞讲座的主题首次涉及计算机科学。在准备这些讲座时，我花了很多时间来思考如何向大众解释计算机科学，却发现满足这一需求的资源很少，几乎没有关于计算机科学的畅销书。因此，我特别高兴能看到麦考密克的这本新书。

麦考密克在面向大众介绍计算机科学的复杂思想上做得非常好。这其中许多思想极其新颖，仅从这点上来看，它们就很值得关注。举个例子：电子商务的爆炸式增长之所以成为可能，是因为具备了能在互联网上秘密、安全地发送机密信息(如信用卡卡号)的能力。数十年来，建立在“开放”通道上的保密通信被认为是一个科学难题。当人们发现解决方法时，才发觉保密通信极度优雅，而麦考密克也以精确的类比进行了解释，无须读者拥有计算机科学知识。这些优点使这本书对科普读物做出了不可估量的贡献，我极力推荐本书。

《星际迷航》（Star Trek）中的计算机并不特别让人兴奋。他们向计算机问问题，计算机还要想一会儿。我觉得我们能做得更好。

——拉里·佩奇（谷歌联合创始人）