作者：(美)约翰·麦考密克
出版社：中信出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
改变未来的九大算法试读：
第一章 前言
——计算机日常运用的卓越思想有哪些此乃小技……为诗之诀在于有气、有势、有情、有韵、有起、有承、有[2]转、有合。——威廉姆·莎士比亚，《爱的徒劳》（Love’s Labour’s Lost）计算机科学中的伟大思想是如何诞生的？以下遴选部分思想进行介绍：• 20世纪30年代，在第一台数字计算机发明以前，一位英国天才开创了计算机科学领域。之后，这位天才继续证明，不管未来建造的计算机运行多快、功能多强大、设计得多好，仍旧有一些问题是计算机不能解决的。• 1948年，一位供职于电话公司的科学家发表了一篇论文，开创了信息理论领域。这位科学家的工作让计算机能以完美的精确度传输信息，即便大部分数据都因为被干扰而破坏。• 1956年，一群学者在达特茅斯举行会议。这次会议的目标很清晰，也很大胆，那就是开创人工智能领域。在取得了许多重大成功以及经历了无数失望之后，我们仍期待出现一个真正的智能计算机程序。• 1969年，IBM公司的一名研究人员发明了一种将信息组织进数据库中的先进方法。目前，绝大多数在线交易都使用该技术存储及检索信息。• 1974年，英国政府秘密通信实验室的研究人员发明了一种让计算机安全通信的方法，即另一台计算机可以查看在计算机之间交换的所有信息。这些研究人员为政府保密所限——不过幸运的是，三名美国专家独立开发并拓展了这项重大发明，为互联网上所有的安全通信打下了基础。• 1996年，两名斯坦福大学博士生决定联手搭建一个互联网搜索引擎。几年后，他们创办了谷歌公司——互联网时代的第一个数字巨头。
在我们享受21世纪技术惊人增长的同时，使用计算机设备——不管是现有最强大的一组机器还是最新、最时尚的手持设备——都不可避免地要依赖计算机科学的基础思想，而这些思想都诞生于20世纪。想一想：你今天做过什么令人印象深刻的事情吗？好吧，这个问题的答案取决于你怎么看。也许你搜索了包含数十亿份文档的资料库，从中选出两到三份与你的需求最相关的文档？即便有能够影响所有电子设备的电磁干扰，存储或传输了数百万条信息，也没犯一点错误？你是否成功地完成了一次在线交易，即便同时有成千上万名消费者在访问同一个服务器？你是否在能够被其他数十台计算机嗅探到的线路中传输了一些机密信息（比如信用卡卡号）？你是否运用过压缩的魔力，将数兆的照片压缩成更易于管理的大小，以便在电子邮件中发送？你是否在手持设备上触发了人工智能，自动纠正你在手持设备的小巧键盘上输入的内容？
这些令人印象深刻的壮举都依赖于之前提到的伟大发现。然而，绝大多数计算机用户每天都会多次运用这些独创想法，却从没有意识到！本书旨在面向大众解释这些概念——我们每天使用的计算机科学的伟大思想。在解释每个概念时，我都假设读者不了解任何计算机科学的任何知识。算法：指尖精灵的构件
到目前为止，我一直在谈计算机科学的伟大“思想”，但计算机科学家们将许多重要思想形容为“算法”。那么思想和算法之间有什么区别呢？究竟什么是算法？这一问题最简单的答案是，算法是一张精确的处方，按顺序详细列出了解决一个问题所需要的具体步骤。我们小时候在学校学到的一种算法就是很好的例子：将两个大数字相加的算法。如下例所示。这个算法涉及一连串步骤，开始的步骤如下：“首先，将两个数的最末位数相加，写下结果的最末位数，将剩下的数放到左侧的下一栏；接着，将下一栏的数相加，再将除结果末位数之外的数字和前一栏余下的数相加……”。依此类推。将两个数字相加的算法的前两步。
请注意算法步骤近乎机械化的感觉。事实上，这是算法的关键特点之一：每一步都必须绝对精确，没有任何人类意图或推测掺杂其中。这样，每一个完全机械化的步骤才能被编入计算机。算法的另一个重要特点是，不管输入什么，算法总能运行。我们在学校学到的相加算法就拥有这一特性：不管你想把哪两个数相加，算法最终都会得出正确答案。比如，用这一算法将两个长达1 000位的数相加，你肯定能得到答案，尽管这需要相当长的时间。
对于把算法定义为一张精确、机械化的处方的说法，你也许会略感好奇。这张处方究竟要有多精确？要进行哪些基本操作？比如，在上面的相加算法中，简单地说一句“把两个数相加”是不是就行了？还是说我们要在加法表上列出所有个位数字？这些细节看起来也许有点乏味，甚至会显得有点学究气，但其实离真相不远了：这些问题的真正答案正处于计算机科学的核心，并且也和哲学、物理学、神经科学以及遗传学有联系。有关算法究竟是什么的深层问题都归结于一个前提——也就是众所周知的邱奇—图灵论题（Church–Turing Thesis）。我们将在第十章重温这些问题，届时我们还将讨论计算的理论极限，以及邱奇—图灵论题的一些方面。同时，将算法比作一张非常精确的处方这一非正式概念效果会非常好。
现在我们知道了算法是什么，但算法和计算机有什么联系呢？关键在于，计算机需要用非常精确的指令编程。因此，在能让计算机为我们解决某个特定问题之前，我们需要为那个问题开发一个算法。在数学和物理学等其他学科中，重要的结果通常是由一个方程式获得222的。（著名的例子包括勾股定理a+b=c，或爱因斯坦的质量守恒定理E=mc2。）相反，计算机科学的伟大思想通常是形容如何解决一个问题——当然，是使用一种算法。因此，本书的主要目的是，解释让计算机成为你的个人精灵的东西——计算机每天使用的伟大算法。一个伟大的算法由什么构成？
这会引出一个刁钻的问题：什么才是真正伟大的“算法”？潜在的候选算法清单相当大，但我用几条基本标准缩减了用于本书的候选算法清单。第一条，也是最重要的一条标准是，伟大的算法要被普通计算机用户每天用到。第二条重要的标准是，伟大的算法应该能处理具体的现实问题，如压缩一个特定文件或通过一个噪声链接精确地传输文件。对于已经了解部分计算机科学的读者而言，下面的文字框解释前面两大标准的部分后果。第一条标准——要被普通计算机用户每天用到——排除了主要由计算机专业人士使用的算法，如编译器和程序验证技术。第二条标准——针对某个特定问题的具体程序——排除了许多作为计算机科学本科课程核心内容的伟大算法，如排序算法（快速排序）、图形算法（迪杰斯特拉最短路径算法）、数据结构（哈希表）。这些算法的伟大性毋庸置疑，而且很轻易地就满足了第一条标准，因为普通用户使用的绝大多数应用程序都会反复应用这些算法。但这些算法太通用了：它们能用于解决众多问题。在本书中，我决定要专注于解决特定问题的算法，因为对于普通计算机用户而言，这些算法能让他们拥有更清晰的动机。一些和本书选取算法有关的额外细节。本书读者无须具备计算机科学的任何知识。但如果读者具备计算机科学背景知识，这个文字框会解释为何这类读者之前偏好的许多内容没有出现在本书中。
第三个标准是，算法主要和计算机科学理论相关。这排除了主要和计算机硬件——如CPU、监视器以及网络——有关的技术。这条标准也减轻了对基础设施——如互联网——设计的重视。为什么我要着重于计算机科学理论？部分原因是由于公众对计算机科学认知的不平衡：有一种广泛的观点认为，计算机科学基本上就是编程（如“软件”）和设备设计（如“硬件”）。事实上，最优美的计算机科学思想中有许多是十分抽象的，并不属于以上任意一类。我希望通过着重于这些理论思想，让更多人将计算机科学的本质作为一门知识学科来理解。
你也许已经注意到了，我列出的标准可能会遗漏一些伟大的算法，但却从一开始就避免了定义伟大这个极其麻烦的问题。针对这一问题，我依赖于自己的直觉。在本书中说明的每一个算法中，其核心都是一个让整件事情奏效的精巧把戏。对我而言，当这个把戏显露出来时，那个“惊叹”时刻，会让解释这些算法成为令人愉悦的经历，我希望你也能有此感受。因为我会用到“把戏”（trick）这个词很多次，需要指出的是，我并非指那些卑劣或骗人的把戏——那种孩子可能会用在弟弟或妹妹身上的把戏。相反，本书中的把戏类似于交易诀窍或魔术：为达成目标而采用的聪明技巧，否则目标很难或不可能达成。
因此，根据直觉，我选出了自认为是计算机科学世界中最精巧、最神奇的把戏。在英国数学家高德菲·哈罗德·哈代（G. H. Hardy）的《一个数学家的辩白》（A Mathematician’s Apology）中，作者试图向公众解释数学家从事数学的原因：“美是第一道测试：丑陋的数学在这个世界中无永存之地。”这道美的测试也适用于计算机科学中蕴含的理论思想。因此，选取在本书中出现的算法的最后一条标准，就是哈代的——也许可以这么称呼——美的测试：希望我至少能成功地向读者展示部分美——我在每个算法中感觉到的美。
接下来谈谈我选择展示的这些算法。搜索引擎的巨大影响，也许是算法技术影响所有计算机用户最明显的例子，我自然也将部分互联网搜索的核心算法收入了本书中。第二章描述了搜索引擎如何使用索引寻找与请求的文件，而第三章则解释了网页排名（PageRank）算法——谷歌公司为保证匹配度最高的文件出现在搜索结果列表顶部的原始算法。
即便我们不经常想这件事情，绝大多数人也能意识得到，为提供出人意料的强大搜索结果，搜索引擎使用着一些深邃的计算机科学思想。相反，其他一些伟大的算法也经常被用到，但计算机用户对此甚至都没有意识到。第四章描述的公钥加密（public key cryptography）就是这样一种算法。用户每次访问一个安全网站（地址以https而非http开头），用户都会用到公钥加密的一个方面——也就是众所周知的密钥交换（key exchange）——来展开一段安全对话。第四章解释了密钥交换过程的实现原理。
第五章的主题是纠错码（error correcting codes），这是我们经常使用但却没有意识到的另一类算法。事实上，纠错码极有可能是有史以来唯一一个使用次数最频繁的伟大算法。纠错码可以让计算机识别并纠正在储存或传输数据中出现的错误，而不必依靠备份或再次传输。纠错码无处不在：它们被用于所有硬盘驱动器、众多网络传输、CD和DVD，甚至还存在于一些计算机的内存。不过，纠错码的能力太强了，以至于我们意识不到它们存在。
第六章稍微有点特殊，介绍了图形识别算法（pattern recognition algorithm）。图形识别算法也能进入伟大的计算机科学思想榜单，但却违背了第一条标准：要被普通计算机用户每天用到。图形识别属于计算机识别高度可变信息——如笔迹、讲话和人脸——的技术。事实上，在21世纪的第一个十年，绝大多数日常计算并没有用到这些技术。但在2011年，图形识别的重要性急剧增大：配备小型屏幕键盘的移动设备需要自动纠错，平板设备必须识别手写输入，而且所有这些设备（特别是智能手机）越来越趋向于语音操作。一些网站甚至使用图形识别来决定向用户展示哪种广告。另外，我对图形识别也有偏好，因为它是我的研究领域。因此，第六章描述了3种最有趣、最成功的图形识别技术：最近邻分类器（nearest-neighbor classifier）、决策树（decision tree）以及神经网络（neural network）。
第七章讨论了压缩算法。压缩算法组成了另一组使计算机变成我们指尖精灵的伟大思想。计算机用户的确会时不时地直接进行压缩，也许是为了节省磁盘空间，也许是为了缩减照片容量，以便用电子邮件寄出。不过在私底下，压缩使用的频率要更高：我们根本没有意识到，我们的下载或上传也可以通过压缩以节省带宽，而数据中心通常会压缩消费者的数据以降低成本。电子邮件提供商提供给你的5 GB空间，经压缩后很有可能只占据电子邮件提供商5 GB空间的很小一部分。
第八章讲到了数据库中运用的一些基础算法。这一章侧重为实现一致性——指一个数据库中的关系不互相冲突——而采用的聪明技巧。没有这些精巧的技术，我们的绝大部分在线生活（包括网络购物以及通过Facebook之类的社交网站进行互动）就会消亡于众多计算机错误中。这一章解释了一致性真正的问题是什么，以及计算机科学家是如何解决这一问题的。前提是不牺牲我们所期望的在线系统拥有的高效性。
在第九章，我们会了解理论计算机科学无可争议的瑰宝之一：数字签名。乍看之下，用数字形式“签署”一份电子文档似乎不可能。你也许会想，这种签名必须由数字信息组成，而任何想要伪造签名的人都可以毫不费力地拷贝这些信息。这一悖论的解决方案，就是计算机科学取得的最令人瞩目的成就之一。
第十章采取了截然不同的视角：与其描述一个已经存在的伟大算法，我们不如去了解一个假如存在则必然会伟大的算法。不过我们会震惊地发现，这个特别伟大的算法不可能存在。这表明计算机解决问题的能力存在一些绝对极限，而我们将简单地从哲学和生物学角度探讨这一结果的应用。
第十一章我们会总结伟大算法的一些共性，花些时间畅想未来会怎样。会有更多伟大算法出现吗？或者说，我们已经发现了所有的伟大算法？
在此，不得不提前说一下本书的风格。任何科普作品都必须清楚地告知来源，但引用会破坏文本的流畅性，并让读者产生学术的感觉。由于可读性和易读性是本书的首要目标，所以本书正文不会出现引用。不过，我清楚地记录了所有来源，并在本书末尾的“来源和延伸阅读”板块中列出，并时不时附上拓展评论。这个板块还列出了一些额外材料，以便感兴趣的读者能去寻找更多和计算机科学中伟大算法有关的东西。
既然提前说了本书的风格，我还要谈谈本书书名中采取的少量诗化。本书无疑是革命性的，但真的有九种算法吗？这一说法值得探讨，因为要取决于有多少算法被算作单独算法。让我们来算下“九”是怎么来的。除了前言和结论两章外，本书还有九章，每一章都介绍了对一种计算任务产生革命性影响的算法，例如加密、压缩、图形识别。因此，书名中的“九大算法”实际上指的是处理这九种任务的九类算法。为什么我们要关注这些伟大的算法？
希望对这些迷人思想的快速总结能让你渴望深入了解它们的运行方式。不过，也许你仍然在思考：本书的终极目标是什么？让我简短地说下本书的真正目的。这本书绝不是一本问答式操作手册。在读完本书后，你不会成为计算机安全方面的专家，也不会成为人工智能或其他领域的专家。你也许能学到一些有用的技能，这倒是真的。比如：你会对如何检查“安全”网站凭证以及“已签名”软件包了解更多；你能针对不同任务在有损和无损压缩之间做出明智选择；而且通过理解搜索引擎索引和排名技术的某些方面，你能更高效地使用搜索引擎。
在读完本书后，你不会成为一名更加熟练的计算机用户。但你会更加珍视每天在所有计算设备上不停使用的思想的美。
为什么这是件好事？我用类比的方式来说明。我肯定不是一位天文学专家——事实上，我在这个项目上相当无知，我想知道更多。但每当我注视夜空，我知道的少量天文学知识增强了我对这一经验的享受。有时，我对自己看到事物的理解，让我产生了一种满足和惊奇的感觉。希望在读完本书后，你在使用计算机时也能经常获得同样的满足和惊奇之感，这也是我殷切的希望。你将真正珍视我们时代最常见、最神秘的黑盒子：你的个人电脑，你指尖的精灵。注释[1]For some accessible, enlightening explanations of algorithms and other computer technology, I recommend Chris Bishop's 2008 Royal Institution Christmas lectures, videos of which are freely available online. The lectures assume no prior knowledge of computer science. A. K. Dewdney's New Turing Omnibus usefully amplifies several of the topics covered in the present volume and introduces many more interesting computer science concepts--but some knowledge of comPuter program-ruing is probably required to fully appreciate this book. Juraj Hromkovics Algorithmic Adventures is an excellent option for readers with a little mathematical background, but no knowledge of computer science. Among the many college-level computer science texts on algorithms three particularly readable options are Algorithms, by Dasgupta, Papadimitriou, and Vazirani; Algorithmics: The Spirit of Computing, by Harel and Feldman; and Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein.[2]选自朱生豪译本。——译者注[1]
第二章 搜索引擎索引
——在世界上最大的草垛中寻针哈克，在咱俩站着的地方的下面，你拿一根钓鱼竿就可以触到我钻出来的那个洞。看看你能不能找到。——马克·吐温，《汤姆·索亚历险记》（Tom Sawyer）搜索引擎对我们的生活产生了深远影响。绝大多数人每天都进行多次搜索查询，但我们极少会停下来思考这个令人惊叹的工具是如何奏效的。搜索引擎提供的海量信息以及搜索结果的速度与质量变得如此平常，如果我们搜索的问题没有在几秒内得到回答，我们就会困惑。我们倾向于忘记，每一个成功的搜索引擎都是从世界上最大的草垛——万维网——寻针。
事实上，搜索引擎提供的超级服务，不仅仅是针对搜索抛出一大堆花哨技术的结果。的确，每个大型搜索引擎公司都运营着一个由无数数据中心组成的国际网络，其中包括数以千计的服务器计算机和先进的网络设备。但没有聪明的算法来组织和检索我们请求的信息，所有这些硬件都会变得毫无用处。因此，在这一章和下一章，我们将探究这样一些算法瑰宝——每次在进行网络搜索时，我们都会用到这些算法。我们很快就会了解到，搜索引擎的两大主要任务就是匹配（matching）和排名（ranking）。这一章将讲述一种聪明的匹配技术：元词把戏（metaword trick）。在下一章，我们将转而讨论排名任务，审视谷歌公司著名的网页排名算法。匹配和排名
当你发起一次网络搜索查询时会发生什么？以这样一种高屋建瓴的视角开始会很有帮助。我已经说过，搜索有两个主要阶段：匹配和排名。在实际中，搜索引擎将匹配和排名组合成一个流程以实现一致性。但这两个阶段在概念上是独立的，因此我们会假设在排名开始前，匹配已经完成。上图就给出了一个例子，图中查询的是“London bus timetable”（伦敦公共汽车时刻表），而匹配阶段则回答“哪个网页与我的查询匹配”这个问题——在这个例子中就是所有提到“London bus timetable”的网页。网络搜索的两个阶段：匹配和排名。在第一阶段（匹配）后可能会出现数千或数百万个匹配结果，这些结果必须按照相关度在第二阶段（排名）进行排序。
但现实搜索引擎中的许多查询都有数百、数千乃至数百万个“命中”。而搜索引擎用户通常只喜欢查看几个结果，最多5个或10个。因此，搜索引擎必须从大量命中里挑出最好的几个。一个好的搜索引擎不仅仅会挑出最好的几个命中，而且会以最有用的顺序显示它们——最匹配的页面排在第一，然后是匹配度排名第二的页面，依此类推。
以正确顺序挑选出最好的几个命中被称为“排名”。排名是关键的第二个阶段，紧随最开始的匹配阶段。在搜索行业的残酷世界中，搜索引擎的生死由其排名系统的质量决定。2002年，美国前三大搜索引擎的市场份额基本相当，谷歌、雅虎和MSN在美国的市场份额都在30%以下。[MSN随后被重新包装成Live Search，之后又被命名为必应（Bing）。]之后几年，谷歌的市场份额迅速扩大，同时将雅虎和MSN的市场份额打压到了20%以下。人们普遍认为，谷歌迅速上升为搜索行业冠军是得益于其排名算法。因此，毫不夸张地说，搜索引擎的生死由其排名系统的质量决定。不过，正如我已经提到的，我们将在下一章探讨排名算法。至于现在，让我们专注于匹配阶段吧。AltaVista：第一个互联网级别的匹配算法
搜索引擎匹配算法的故事从哪里开始？一个很显然却错误的回答会说从谷歌——21世纪初期最伟大的技术成功故事——开始。事实上，谷歌最初只是两位斯坦福大学研究生的博士学位项目，这个故事不仅温暖人心，而且令人印象深刻。拉里·佩奇（Larry Page）和谢尔盖·布林（Sergey Brin）在1998年组装了一堆计算机硬件来运行一种新的搜索引擎。不到10年，他们的公司成为了互联网时代崛起的最伟大的数字巨人。
不过，互联网搜索的想法已经存在很多年了。最早的商业应用是Infoseek和Lycos（两者都于1994年推出），以及于1995年推出搜索引擎的AltaVista。20世纪90年代中期的几年中，AltaVista是搜索引擎的王者。当时我还是一名计算机科学研究生，我清楚地记得自己惊叹于AltaVista搜索结果的成熟度。有史以来第一次，有一个搜索引擎能完全索引互联网上每一个页面的全部文本。更可贵的是，眨眼间就能返回结果。要继续理解这个令人回味的技术突破，我们要从接触一个古老的（毫不夸张）概念——索引——开始。古老的索引
索引的概念是所有搜索引擎背后最基础的思想。但索引并非由搜索引擎发明：事实上，索引的思想几乎和书写本身一样古老。比如，人类学家发现了一座具有五千年历史的巴比伦神庙图书馆，里面按学科对楔形文字泥版进行了分类。因此，索引可以称得上是计算机科学中最古老的有用思想。
如今，“索引”这个词通常指参考书最后的一个板块。你可能想要查看的所有概念都以固定顺序（通常是按字母排序）列出，每一个概念下都列出了这个概念出现的位置（通常是页码）。因此，一本和动物有关的书也许会有一个像“cheetah 124，156”的索引项。这个索引项意味着“cheetah”（猎豹）这个词在第124页和第156页出现过。（让你做个相当有趣的练习，你可以在本书的索引中查询“index”这个词。你应该可以找到这一页。）一个假想的万维网，由编号为1、2和3的三个页面组成。一个用页码表示的简单索引。
互联网搜索引擎的索引和一本书的索引有着相同的工作原理。书“页”现在成了万维网上的网页，而搜索引擎则给互联网上的每个网页分配了一个不同的页码。（是的，互联网上虽然有很多网页——最新的数据显示有成百上千亿个——但计算机很擅长处理大数字。）上图给出了一个会让整个过程更具体的例子。想象万维网只由上面显示的3个短网页组成，它们分别分配到了页码1、2和3。
计算机可以为这三个网页创建一个索引：首先要为出现在任一页面上的所有单词创建一个列表，然后按字母表顺序整理这张列表。我们可以将结果称为单词表（word list）——在这个例子中是“a、cat、dog、mat、on、sat、stood、the、while”。然后计算机会一个单词一个单词地搜遍所有页面。计算机会标注每个单词所在的页码，然后再标注单词表中下一个单词的位置。最终结果显示在上图中。比如，你可以立即看到单词“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）这个列表的通用元素。
就目前来看，搭建一个搜索引擎听起来相当容易。最简单的索引技术似乎运行得很好，即便对多词查询也是如此。不幸的是，这种简单方法完全不能满足现代搜索引擎的需要。出现这种情况的原因有几个，不过现在我们只会关注其中之一：如何做短语查询。短语查询是指寻找一个确切短语的查询，而非凑巧一些单词出现在页面中的某些[2]地方。比如，“cat sat”查询和cat sat查询的意义截然不同。cat sat查询寻找的是在任何位置包含“cat”和“sat”两个单词的页面，不考虑顺序；而“cat sat”查询寻找的是包含单词“cat”之后紧跟单词“sat”的页面。在上面那个由三个网页组成的简单例子中，cat sat查询结果命中第1页和第3页，但“cat sat”查询只返回一次命中，就在第1页。
一个搜索引擎如何才能有效地进行一次短语查询呢？继续说“cat sat”这个例子。第一步和平常的多词查询cat sat一样，从单词表中获取每个单词出现的网页列表，在这个例子中就是出现在第1页和第3页的“cat”；“sat”也一样，出现在第1页和第3页。不过搜索引擎到这里就卡住了。搜索引擎很确切地知道两个单词同时出现在页面1和页面3上，但没有办法来分辨这些单词是否以正确的顺序紧挨着彼此出现。你也许会想，搜索引擎可以返回查看原网页，看这个短语是否存在。这的确是个可能的解决方案，但效率却非常非常低。这需要遍历每一个可能包含这个短语的网页的全部内容，而且可能有海量这样的网页。记住，我们在这里打交道的是一个只由三个页面组成的极小的例子，真正的搜索引擎必须从数百亿个网页中找出正确的结果。词位置把戏
这一问题的解决方案是让现代搜索引擎运行良好的首个、真正精巧的思想：索引应该不单单存储页码，还要存储页面内的位置。这些位置并不神秘：它们只是代表了一个词在页面中的位置。第3个词的位置是3，第29个词的位置是29，依此类推。例子中三个页面组成的数据集如下页图所示，还加上了词位置。图下面的是索引——由存储页码和词位置中得出的结果组成。我们称这种创建索引的方法为“词位置把戏”（word location trick）。举几个例子，以确保大家理解了词位置把戏。索引的第一行是“a3-5.”。这意味着词“a”只在数据集中出现过一次，是第3页的第5个单词。索引中最长的一行是“the 1-1 1-5 2-1 2-5 3-1”。这一行可以让你知道，这个数据集中所有出现单词“the”的具体位置。它在第1页出现过两次（位置1和5），第2页出现过两次（位置1和5），第3页出现过1次（位置1）。
你还记得介绍页内词位置的目的吗？是为了解决如何有效地进行短语查询这个问题。让我们来看看如何用这个新索引做一次短语查询。还是和前面一样，查询短语“cat sat”。第一步和使用旧索引时一样：从索引中提取单个词的位置，“cat”的位置是1-2、3-2，“sat”的位置是1-3、3-7。到这里还好：我们知道短语查询“cat sat”唯一可能的命中就是在第1页和第3页。但与之前一样，我们还不确定相同的短语是否出现在了这些页面中——有可能这两个单词的确出现了，但并不是以正确的顺序彼此相邻。幸运的是，从位置信息中确认这一点很容易。首先从第1页开始。根据索引信息，我们知道“cat”出现在第1页的位置2（这就是1-2的含义）。我们还知道“sat”出现在第1页的位置3（这是1-3的含义）。但如果“cat”在位置2，“sat”在位置3，我们就知道“sat”紧挨着出现在“cat”之后（因为2之后立即就是3）——因此我们寻找的整个短语“cat sat”必定出现在第1页，并从位置2开始。3个网页加上了页内词位置。同时包含页码和页内词位置的新索引。
我知道自己在这点上谈得很多，但巨细无遗、从头至尾地研究这个例子，是为了让读者真正地理解为了获得答案究竟使用了哪些信息。注意，我们已经为短语“cat sat”找到了一次命中，仅仅是通过查看索引信息（“cat”的位置1-2、3-2，“sat”的位置1-3、3-7），而非原始网页。这很关键，因为我们只需查看索引中的两个项，而非遍历所有可能包含命中的页面——而在进行真正短语查询的真正的搜索引擎中，可能有数百万个这样的页面。总之：通过在索引中加入页内词位置，我们只需通过查看索引中的几行，就能找到一次短语查询命中，而非遍历海量页面。这个简单的词位置把戏是让搜索引擎奏效的关键之一。
事实上，我还没讲完“cat sat”这个例子。我们完成了对第1页信息的处理，但第3页还没处理。对第3页的推理和第1页的处理方式很相似：“cat”出现在第3页的位置2，“sat”出现在位置7，因此它们不可能相邻——因为紧跟2之后出现的不是7。这样我们就知道，第3页并不是短语查询“cat sat”的命中，尽管它是多词查询cat sat的命中。
顺便说一下，词位置把戏不仅仅对短语查询重要。举个例子，思考一下寻找相邻单词的问题。在一些搜索引擎中，用户可以在查询中使用“NEAR”关键词做到这一点。事实上，AltaVista搜索引擎在早期就提供了这一功能，在本书写作时仍然提供。作为一个特殊的例子，假设在一些特别的搜索引擎中，查询cat NEAR dog会找到“dog”前后五个位置之内出现“cat”的页面。我们如何才能在数据集中有效地执行这种查询？使用词位置，会使查询变得很容易。“cat”的索引项是1-2、3-2，而“dog”的索引项是2-2、3-6。可以立刻看出，第3页是唯一可能的命中。而在第3页，“cat”出现在位置2，“dog”出现在位置6。因此这两个词之间的距离是6－2，结果是4。因此，“cat”的确出现在“dog”前后五个位置之内，而第3页则是查询cat NEAR dog的命中。和前面一样，请注意这次查询的执行是多么高效：无须遍历任何网页的实际内容——相反，只参考了索引中的两个项。
不过，在实际中，NEAR查询对搜索引擎用户并不非常重要。几乎没人使用NEAR查询，绝大多数主要搜索引擎甚至不支持它们。尽管如此，能执行NEAR查询的能力实际上对现实中的搜索引擎至关重要。这是因为搜索引擎不断地在后台执行NEAR查询。要理解其中的原因，我们首先不得不研究现代搜索引擎面临的主要问题之一：排名的问题。排名和邻度
到目前为止，我们一直专注于匹配阶段：为一个给出的查询高效地找出所有命中的问题。不过正如之前强调的，第二个阶段“排名”对于一个高质量的搜索引擎是绝对必不可少的：这是挑选出前几个命中并展示给用户的阶段。
让我们更细致地来检验排名的概念。一个网页的“排名”究竟取决于什么？真正的问题不是“这个网页和查询匹配吗”，而是“这个网页和查询相关吗”。计算机科学家们使用“相关度”（relevance）这个术语来形容一个结果网页和某个特定查询有多么相配或多么有用。
举个具体的例子，假设你对导致疟疾的原因感兴趣，并在一个搜索引擎中输入查询malaria cause（导致疟疾）。简化考虑，假设搜索引擎对这一查询只有两个命中——下图显示的两个网页。现在来看看这两个网页。作为人类，你很快就知道第1页和疟疾起因有关，而第2页似乎是对刚刚发生的一些军事行动的描述，只不过恰巧使用了“cause”和“malaria”这两个词。因此，和第2页相比，第1页无疑和查询malaria cause更具相关性。可计算机不是人，让计算机理解这两页的主题也很难，似乎不可能让搜索引擎正确地对这两个命中进行排名。两个提及疟疾的样本网页。从上方两个网页中创建的索引的一部分。
不过，事实上，有一种很简单的方法让这个例子中的排名正确。查询词彼此相邻的网页比那些查询词相距很远的网页相关度更高。在疟疾这个例子中，“malaria”和“cause”在第1页中仅相距1个词，而在第2页中则相距17个词。（记住，搜索引擎只通过查看索引项就能高效地发现这一点，无须返回查看网页。）因此，尽管计算机并不真正地“理解”查询的主题，它也能猜测网页1比网页2更具相关性，因为网页1查询词之间的距离要比网页2更近。
总而言之，尽管人们不经常使用NEAR查询，搜索引擎也在不断地使用和邻度有关的信息，提高搜索排名。而它们能高效地做到这点的原因则是，它们使用词位置把戏。一个网页范例集，每个网页都有一个标题和一段正文。
我们已经了解到，早在距今5 000年以前，巴比伦人就开始使用索引。而词定位把戏也不是由搜索引擎发明的：这是互联网出现以前，另一种信息检索中用到的著名技术。不过，在下一部分，我们将了解一个看起来的确是由搜索引擎设计者发明的新把戏：元词把戏（metaword trick）。对这一把戏和众多相关思想的精巧运用，使AltaVista搜索引擎在20世纪90年代晚期迅速成为搜索行业的领头羊。元词把戏
到目前为止，我们一直都在使用极其简单的网页示例。然而，绝大多数网页拥有众多结构，包括标题、标头、链接和图片，可我们还一直认为网页只是普通的词表。接下来，我们将探索搜索引擎如何处理网页中的结构。不过，为了尽可能保持简单，我们只会引入一层结构：网页的顶部会有一个标题，之后是页面的正文。上图显示了我们熟悉的三页示例，并附加了一些标题。
实际上，要像搜索引擎一样分析网页结构，我们需要了解更多编写网页的知识。网页是由一种特殊语言编写的，以便网络浏览器能用很好的格式展示它们。（编写网页最常用的语言被称为HTML，不过HTML的细节对本次讨论不重要。）标头、标题、链接、图片等格式化结构是用被称为元词的特殊单词编写的。比如，网页标题开始使用的元词也许是
看一下上面的图。这张图展示的内容和前一张图一样，但显示的是实际编写网页的样子，而非在网络浏览器中显示的样子。绝大多数网络浏览器都能让用户检验网页的原始内容，这需要选择名为“查看网页源代码”的菜单选项——我建议你下次有机会试验一下。（注意，在这里使用的元词，如
在创建一份索引时，囊括所有元词是件很简单的事。无须新把戏：你只要像存储正常单词一样存储元词位置就行。下页的图显示了从带有元词的三个网页中创建的索引。看一下这张图，确保自己理解了其中所有的奥秘。比如，“mat”的项是1-11、2-11，表示“mat”是第1页的第11个词，也是第2页的第11个词。元词位置的解读也一样，“
我们称这种和索引普通单词一样索引元词的简单把戏为“元词把戏”。这个把戏也许看起来简单得可笑，但元词把戏在让搜索引擎执行精确搜索和高质量排名上扮演了至关重要的角色。举个简单例子证明。假设在某个时候，有个搜索引擎支持使用IN关键词的特殊查询，因此像boat IN TITLE这样的查询只会返回在网页标题中包含了单词“boat”的网页，而查询giraffe IN BODY则会找到在正文中包含“giraffe”（长颈鹿）的网页。请注意，绝大多数搜索引擎并不完全按照这种方法提供IN查询，但一些搜索引擎可以通过让你点击“高级搜索”选项，详细说明查询词必须出现在标题或一份文件的特定位置来实现同样的效果。我们假定IN关键词存在，以便更容易解释。事实上，在写作本书时，谷歌已经可以让用户通过使用关键词intitle进行标题搜索：因此，在谷歌中查询intitle:boat，将找到标题中带有“boat”的网页。自己试试！上一张图中的网页（包括元词）的索引。搜索引擎如何执行搜索dog IN TITLE。
让我们来看看，在上面两张图中由三个网页组成的示例里，搜索引擎如何有效地执行查询dog IN TITLE。首先，搜索引擎提取“dog”的索引项，也就是2-3、2-7和3-11。然后（这可能有点出人意料，但请忍耐片刻）搜索引擎会同时提取
之后，搜索引擎开始扫描“dog”的索引项，检查其命中，看是否有哪个命中发生在标题内。“dog”的第一个命中是圈起来的项2-3，代表其是第2页的第3个词。通过一并扫描
我们目前已知的所有东西都被图中圈住的项总结了。它们告诉我们第2页的标题从第1个词开始，到第4个词结束，而“dog”这个词是第3个词。最后一步很简单：因为3大于1，小于4，我们肯定“dog”的这次命中确实出现在一个标题中，因此第2页应该是查询dog IN TITLE的命中。
现在搜索引擎可以转向寻找“dog”的第二个命中，也就是2-7（第2页的第7个词），但因为我们已经知道第2页是命中，因此可以忽略2-7这个项，转向下一个命中3-11（由一个框标记）。这表示“dog”是第3页第11个词。于是我们开始跳过被圈住的
元词把戏能让搜索引擎以极端高效的方式回应有关一个文件结构的查询。上面的例子只是搜索页面标题内，但类似的技术能让用户搜索超链接、图片描述和网页其他有用部分内的词。而且所有这类查询都可以像上面的例子一样得到高效回应。正如我们之前讨论过的查询，搜索引擎无须返回查看原始网页：搜索引擎只需查阅小部分索引项，就能回应查询。同样重要的是，搜索引擎只需遍历每个索引项一次。还记得我们在完成处理第2页的首个命中后，转向第3页的可能命中时发生了什么吗？搜索引擎并没有返回索引项
标题查询和其他取决于网页结构的“结构查询”类似于之前讨论的NEAR查询，虽然人们极少执行结构查询，但搜索引擎无时无刻不在内部使用它们。原因之前提过：搜索引擎的生死由其排名的质量决定，而通过利用网页结构，排名质量能够得到大幅提升。比如，标题中有“dog”的网页包含与狗有关信息的可能性，要比在网页正文中提及“dog”的网页大得多。因此，当一名用户输入简单的查询dog，搜索引擎能在内部执行一个dog IN TITLE查询（即便用户并未详细地要求这一点），以寻找最有可能与狗有关的网页，而非只是恰好提到狗的网页。索引和匹配把戏并非是全部内容
搭建一个搜索引擎并不是一件容易的事情。最终成品就像一个巨大的复杂机器，带有许多不同的轮子、发动机和杠杆。这些装置都必须安装正确，系统才能有用。因此，单靠在本章中出现的两个把戏并不能解决创建一个高效搜索引擎索引的问题，意识到这一点很重要。不过，词位置把戏和元词把戏无疑展现了真正的搜索引擎构建和使用索引的“风味”。
元词把戏的确帮助过AltaVista——其他搜索引擎则失败了——成功地在整个互联网中寻找有效匹配。我们之所以知道这一点，是因为AltaVista在1999年递交的美国专利文件《索引的限制搜索》（Constrained Searching of an Index）中描述了元词把戏。不过，AltaVista超级精巧的匹配算法并不足以让其从搜索行业波涛汹涌的早期脱颖而出。正如我们已经知道的，有效匹配只是一个高效搜索引擎的一半，另一大挑战是对匹配网页进行排名。正如我们将在下一章中看到的，一种新排名算法的出现足以让AltaVista相形见绌，并让谷歌一跃进入网络搜索世界的最前沿。注释[1]The original AltaVista patent covering the metaword trick is U.S. patent 6105019, "Constrained Searching of an index, "by Mike Burrows (2000). For readers with a computer science background, Search Engines: Information Retrieval in Practice, by Croft, Metzler, and Strohman, is a good option for learning more about indexing and many other aspects of search engines.[2]注意英文单词的双引号。——译者注[1]
第三章 PageRank
——让谷歌腾飞的技术《星际迷航》（Star Trek）中的计算机并不特别让人感兴趣。他们向计算机提问题，计算机还要想一会儿。我觉得我们能做得更好。——拉里·佩奇（谷歌联合创始人）从建筑学的角度来说，车库基本上是个简陋的地方。但在硅谷，车库有一种特殊的创业含义：许多伟大的硅谷技术公司在此诞生或至少从车库中孵化而来。这一趋势并非从20世纪90年代的互联网泡沫开始。在互联网泡沫出现的50多年前，也就是1939年，当世界经济仍未从大萧条的影响中走出来时，惠普（Hewlett-Packard）就在加利福尼亚州帕洛阿尔托（Palo Alto）戴夫·休利特（Dave Hewlett）的车库中逐渐成形了。几十年之后，史蒂夫·乔布斯（Steve Jobs）和史蒂夫·沃兹尼亚克（Steve Wozniak）于1976年在加利福尼亚州洛斯拉图斯乔布斯的车库中创业，之后创建了今天传奇的苹果计算机公司。（尽管传说苹果公司创办于车库，乔布斯和沃兹尼亚克一开始其实是从一间卧室开始的。空间很快就不够用了，于是他们转移到了车库。）不过，和惠普和苹果的成功故事相比，一个名为谷歌的搜索引擎的创办过程更令人惊叹。谷歌从加利福尼亚州门洛帕克市的一间车库开始，并于1998年9月注册成立公司。
那时，谷歌事实上已经运营自己的搜索引擎一年多了——最开始是在斯坦福大学的服务器上，谷歌的两位联合创始人都是斯坦福博士生。直到斯坦福大学再也不能承受这一日益受欢迎的服务所需要的带宽，拉里·佩奇和谢尔盖·布林才把公司转移到了如今著名的门洛帕克车库。他们肯定做了些正确的事，因为在他们正式成立公司3个月后，美国《个人计算机杂志》（PC Magazine）就宣布谷歌是1998年美国排名前一百的网站之一。
这也是我们的故事真正开始的地方：在当年《个人计算机杂志》的评论中，谷歌的精英管理层因为谷歌“以超乎寻常的技巧返回相关度极高的结果”而获奖。你也许还记得上一章提到过，第一个商业搜索引擎于4年前的1994年发布。还在车库里的谷歌怎么能弥补4年的巨大差距，在搜索质量上超越已经很受欢迎的Lycos和AltaVista呢？这一问题的答案可不简单。但最重要的因素之一——尤其是在网络搜索早期——就是谷歌用来对其搜索结果进行排名的创新算法：一个被称为PageRank的著名算法。“PageRank”是个双关词：它既是一种对网页排名的算法，也是其主要发明者拉里·佩奇的排名算法。佩奇和布林在1998年的一篇学术会议论文《解析大规模超文本网络搜索引擎》（the Anatomy of a Large-Scale Hypertextual Web Search Engine）中发表了这一算法。正如论文标题所暗示的，这篇论文的内容不止是描述PageRank。事实上，这是对1998年存在的谷歌系统的完整描述。但藏在这一系统技术细节中的，是对也许是21世纪出现的第一个算法瑰宝的描述：PageRank算法。在本章，我们将探索这一算法如何以及为什么能在草垛中寻针，并持续为搜索查询提供最相关的结果——也是排名最靠前的命中。超链接把戏
你很有可能已经知道了超链接是什么：超链接是网页上的一个短语，当你点击它时，你将被带到另一个网页。绝大多数网络浏览器用蓝色底线显示超链接，以便能轻易识别。
令人意外的是，超链接也是老想法。1945年——大约在同时开始开发电子计算机——美国工程师范内瓦·布什（Vannevar Bush）发表了一篇极具前瞻性的论文《诚若所思》。在这篇涉猎广泛的论文中，布什描述了大量可能的新技术，包括一台被称作麦麦克斯（memex）的机器。麦麦克斯可以存储文件并自动进行索引，但其功能远不止这些。麦麦克斯允许“关联索引……任何被选中的东西都能立即自动选择另一个东西”——换句话说，一种早期的超链接。超链接把戏（the hyperlink trick）的原理。上面显示了6个网页，每个框都代表1个网页。其中2个网页是炒蛋菜谱，其余4个网页都有这些菜谱的超链接。超链接把戏认为伯特的网页比欧尼的网页排名高，因为伯特有三个链入链接（incoming link），而欧尼的只有一个。
超链接自1945年就已出现。它们是搜索引擎用来进行排名最重要的工具之一，而且是谷歌PageRank技术的基础。接下来，我们将开始以最大的热情探索PageRank技术。
理解PageRank的第一步是一个名为超链接把戏的简单想法。用一个例子就能非常容易地解释这个把戏。假设你对学习如何制作炒蛋感兴趣，并且用网络搜索了这一主题。如今，任何一次真正搜索炒蛋的网络搜索都会出现数百万个命中，但为方便起见，让我们想象只有两个网页出现：其中一个是“欧尼的炒蛋菜谱”，而另一个则是“伯特的炒蛋菜谱”。这两个网页都出现在上图中，与之一道的是拥有这些菜谱超链接的网页。还是为了方便起见，让我们想象这四个包含超链接的网页是整个互联网上仅有的链接到两个菜谱网页之一的网页。图中底部画线的文字就代表超链接，而箭头则表示链接的指向。
问题是，这两个命中哪个排名应该更高？伯特还是欧尼？人们在阅读链向这两份菜谱的网页并作出评价上不会有太大的问题。看起来这两份菜谱都很合理，但人们对伯特菜谱的反响要更为热烈一些。因此，在没有给出其他信息的情况下，伯特的菜谱比欧尼的菜谱排名更高可能会更合理。
不幸的是，计算机并不擅长理解网页的真实意思，因此搜索引擎检查这四个链向命中的网页，并对每份菜谱获推荐的强烈程度进行评估也不太可能。另外，计算机在计算方面非常优秀。一种简单方法就是只计算链向每份菜谱的网页数——在这个例子中，一个网页链向欧尼的菜谱，三个网页链向伯特的菜谱——并根据这些菜谱的链入链接数对菜谱排名。当然，这种方法远不如让人阅读所有页面并手动排名精确，但无疑是一种有用的方法。如果你没有其他信息，一个网页的链入链接数可以成为该网页可能会多有用或多有“权威性”的指标。在这个例子中，伯特的菜谱得分为3，欧尼的菜谱得分为1，因此在搜索引擎向用户展示的结果中，伯特的网页排名比欧尼的高。
你可能已经发现了一些在排名上使用这种“超链接把戏”的问题。一个很明显的问题就是，有时候链接被用来显示差网页，而非好网页。比如，假设有个链接欧尼菜谱的网页上写着：“我试了下欧尼的菜谱，很糟糕。”像这样批评而非推荐一个网页的链接，的确会导致超链接把戏将网页的排名拔高。不过，在现实中，超链接更多是用于推荐而非批评。因此，尽管有这个明显的缺陷，超链接把戏仍然很有用。权重把戏
你可能已经在想，为什么要对网页的所有链入链接一视同仁。来自专家的推荐肯定就要比菜鸟的推荐更有价值？要细致地理解这一点，我们继续研究上面的炒蛋例子，不过研究的是另一组链入链接。下页的图对链入链接进行了重新设置：现在，伯特和欧尼的菜谱的链入链接数相等了（只有一个），但欧尼的链入链接来自我的主页，而伯特的则来自于著名主厨艾利斯·沃特斯。
如果没有其他信息，你更喜欢哪个菜谱？很显然，选择由一位著名主厨推荐的菜谱，要比选择由一名计算机科学相关书籍作者推荐的菜谱更好。我们称这一基本原则为“权重把戏”（the authority trick）：来自高“权重”网页的链接排名要比来自低“权重”网页链接的排名高。权重把戏的原理。这里显示了四个网页：两个炒蛋菜谱网页和两个链向菜谱的网页。其中一个链接来自于本书作者（不是著名主厨），而另一个链接来自著名主厨艾利斯•沃特斯的主页。权重把戏将伯特的网页排在欧尼的菜谱之前，因为伯特的链入链接“权重”比欧尼的链入链接大。
这个原则很好，但其实际形式对搜索引擎而言一点用都没有。计算机如何才能自动判定艾利斯·沃特斯在炒蛋方面比我更具有权威性呢？有个想法对此也许会有所帮助：让我们把超链接把戏和权重把戏结合起来。所有网页的初始权重值（authority score）都是1，但如果一个网页有链入链接，在计算该网页权重时就要加入指向其的网页的权重。也就是说，如果X和Y网页链向Z网页，那么Z网页的权重就是X网页和Y网页权重相加的值。
下面的图在计算这两个炒蛋菜谱网页的权重值上很详细。终值显示在圆圈中。图中有两个网页链向我的主页；这些网页本身没有链入链接，因此权重值为1。我的主页的权重值是所有链入链接权重值的总和，相加得2。艾利斯·沃特斯的主页有100个链入链接，每个链入链接的权重值为1，因此它的权重是100。欧尼的菜谱只有一个链入链接，但这个链入链接的权重值是2，因此将其所有链入链接的权重值相加（这个例子中只有一个数可加），欧尼菜谱网页的权重值为2。伯特菜谱网页也只有一个链入链接，但其权重值为100，因此伯特菜谱网页的权重值为100。而因为100大于2，所以伯特的网页排名要比欧尼的高。对两个炒蛋菜谱网页“权重值”的简单计算。权重值显示在圆圈中。随机访问者把戏
就自动计算权重值来说，我们似乎拥有了一个真正奏效的策略，无须计算机真正地理解网页内容。不幸的是，这种方法有个大问题。超链接很有可能形成被计算机科学家称为“循环”（cycle）的东西。循环指访问者可以通过点击超链接返回出发时的网页。
下图就是个例子。图中有A、B、C、D、E五个网页。如果从A开始，我们可以通过A访问B，然后又从B访问E，而从E我们又能点回A，也就是回到了出发点。这也意味着A、B和E三个网页组成了一个循环。超链接循环的一个例子。网页A、B和E组成了一个循环，你可以从A开始，点击到B，然后到E，再返回到A的出发点。循环造成的问题。网页A、B和E永远需要更新，它们的权重值会一直增加下去。
看来，在遇到循环时，目前“权重值”的定义（将超链接把戏和权重把戏结合起来）就碰到大麻烦了。看看在这个特例中会发生什么事情。网页C和D没有链入链接，因此其权重值为1。网页C和D都链向网页A，因此A的权重值是网页C和D权重值的和，也就是1+1=2。B网页从A获得的权重值为2，而E又从B获得权重值2。（这里谈到的情况都由上图左侧部分所体现。）但现在A的权重值要更新了：A从C和D各得到权重值1，但也从E得到权重值2，相加为4。于是B的权重值也需要更新：从A获得权重值4。然后E的权重值也要更新，它从B获得了权重值4。（现在谈到的情况都由上图右侧部分所体现。）依此类推：于是A的权重值变为6，B为6，E为6，于是A的权重值变为8……你懂了吧？随着循环进行，网页的权重值会一直增加。
这样计算权重值，会产生“鸡生蛋，还是蛋生鸡”的问题。如果我们知道A网页真正的权重值，我们就能计算B网页和E网页的权重值。而如果我们知道B网页和E网页真正的权重值，我们就能计算A网页的权重值。但由于这些网页彼此依赖，似乎这样计算根本行不通。随机访问者模式。被访问者访问的网页用灰色表示，虚线箭头代表随机重新开始访问（restart）。实线箭头从网页A开始，指向随机选择的超链接，并被两个随机重新开始访问箭头所打乱。
幸运的是，我们可以通过被称为随机访问者把戏（the random surfer trick）的技术解决这个“鸡生蛋，还是蛋生鸡”的问题。注意：对随机访问者把戏的初始描述，和到目前为止探讨的超链接及权重把戏没有任何关联。一旦了解了随机访问者把戏的基本原理，我们就会做一些分析，揭示其令人瞩目的品质：随机访问者把戏结合了超链接及权重把戏令人喜爱的属性，但在出现超链接循环时也行得通。
这个把戏从假想一个随机访问互联网的人开始。确切地说，访问者随机从万维网上的一个网页开始访问，然后检查该网页上的所有超链接，之后随机挑选出其中一个超链接进行点击。用户再检查打开的新网页，随机选择一个超链接打开。这个过程会持续进行，每一个网页都是通过随机选择前一个网页上的链接打开的。上图就是个例子。在这个例子中，我们假设整个万维网只有16个网页。框代表网页，箭头代表网页之间的超链接。其中标记了四个网页以便稍后进行参考。被访问者访问的网页用灰色表示，黑色箭头代表访问者点击的超链接，虚线箭头代表随机重新开始访问，这个在之后会讲到。
整个过程有一个转折点：每次访问一个网页时，都有一个固定的重新访问概率（大概是15%），让访问者不从已有的超链接中挑选一个并点击。相反，访问者会重新开始这一过程，从互联网上随机选择一个网页点击。你也可以认为访问者有15%的概率对任何已有网页厌倦，导致其点击另一组链接，这么想也许会有帮助。要想找些例子，请仔细观察上图。这个特定的访问者从网页A开始，在对网页B厌倦前连续点击了三个随机超链接，并在网页C重新开始。在下次重新开始前，访问者又点击了两个随机超链接。（顺便说一句，本章中所有随机访问者例子中的重新开始概率都为15%，这也是谷歌联合创始人拉里·佩奇和谢尔盖·布林在描述其搜索引擎原型的原始论文中使用的值。）
用计算机模拟这一过程很容易。我为此写了一个程序并运行了它，直到访问者访问了1 000个网页。（当然，这并不意味着是1 000个不重复的网页。对同一网页的多次访问也被纳入了计算当中，在这个例子中，所有网页都被访问了多次。）这1 000次模拟访问的结果显示在下图（顶图）中。你可以看到，网页D的访问次数最多，有144次。
就像民意调查一样，我们可以通过增加随机样本的数目来提高模拟精度。我重新运行了一次模拟，直到访问者访问了一百万个网页。（也许你会想这花了多长时间，在我电脑上运行只花了不到半秒！）考虑到访问量如此巨大，还是用百分比表示结果更好。这也就是你将在下图（底图）中看到的情形。和之前的结果一样，网页D的访问次数最频繁，占总访问量的15%。
随机访问者模型和权重把戏之间有什么联系可以被我们用于网页排名呢？从随机访问者模拟中计算得出的百分比，正好就是我们在衡量一个网页的权重时所需要的。因此，让我们将网页的访问者权重值（surfer authority score）定义为一名随机访问者花在访问该网页的时间比例。值得注意的是，访问者权重值能和前两个对网页重要性进行排名的把戏配合良好。我们会逐一审视这些把戏。
首先，让我们来审视一下超链接把戏：超链接把戏的主要思想是，一个有许多链入链接的网页应该有高排名。这在随机访问者模型中也适用，因为一个有许多链入链接的网页被访问的概率较大。下图（底图）中的网页D就是个好例子：它有五个链入链接——比模拟中的其他网页都多——访问者权重值也最高（15%）。
其次，让我们来看看权重把戏。权重把戏的主要思想是，和来自低权重网页的链入链接相比，一个来自高权重网页的链入链接应该更能证明一个网页的排名。随机访问者模型也包含这一点。为什么？因为和一个来自不知名网页的链接相比，访问者更有可能继续点击一个来自知名网页的链入链接。要在我们的模拟中找这样一个例子，请比较上面底图中的网页A和C：这两个网页都有一个链入链接，但网页A的访问者权重值要高得多（13%VS 2%），这主要取决于其链入链接的质量。随机访问者模拟。1 000次访问模拟中各网页的访问次数。随机访问者模拟。100万次访问模拟中各网页的访问次数占比。
注意，随机访问者模型天生能同时和超链接把戏及权重把戏相配合。换句话说，每个网页链入链接的质量和数量都会被纳入考虑范围。网页B就展示了这些：网页B的访问者权重值相对较高（10%），得益于三个链入链接所在的网页拥有适中的访问者权重值，从4%到7%不等。前文炒蛋例子中各网页的访问者权重值。伯特的菜谱网页和欧尼的菜谱网页都只有一个链入链接传入权重，但伯特的网页在网络搜索查询“scrambled eggs”（炒蛋）时排名会更高。
随机访问者把戏的美妙之处在于，和权重把戏不同，不管超链接有没有形成循环，随机访问者把戏都能完美地运作。回到早前的炒蛋例子，我们能轻易地运行一次随机访问者模拟。在数百万次访问之后，我的模拟产生了如上图所示的访问者权重值。请留意，和之前使用权重把戏进行的计算一样，伯特的网页访问者权重值要比欧尼的网页高很多（28%VS 1%）——尽管这两个网页都只有一个链入链接。因此，伯特的网页在网络搜索查询“scrambled eggs”（炒蛋）中排名更高。
现在让我们再转向前文中更困难的例子：对于最初的权重把戏而言，由于超链接循环的存在，第39页的图产生了一个不可解的问题。和前面一样，运行一次随机访问者的计算机模拟很容易，于是产生了如上图所示的访问者权重值。由这一模拟判定的访问者权重值给出了网页的最终排名，这些排名会被搜索引擎在返回结果时使用：网页A排名最高，之后是B和E，C和D的排名同列最后一名。早前超链接循环例子（第39页）的访问者权重值。随机访问者把戏在计算合理的分值上没有问题，尽管存在一个循环（A→B→E→A）。实际中的PageRank
谷歌的两位联合创始人于1998年在他们著名的会议论文《解析大规模超文本网络搜索引擎》中描述了随机访问者把戏。通过和其他许多技术结合，这一把戏的变体仍被主流搜索引擎所使用。不过，由于众多复杂因素，应用在现代搜索引擎中的实际技术和本章描述的随机访问者把戏略有不同。
其中一个复杂因素直击PageRank的核心：有时候，假设超链接传输的合法权威性有争议。我们先前已了解到，尽管超链接能代表批评而非推荐，但这在现实中并不是个很大的问题。另一个更加严重的问题是，人们可以滥用超链接把戏，人为地提高自己网页的排名。假设你运营着一个名为BooksBooksBooks.com的网站来售书（惊讶吧）。通过使用自动化技术，创建一大堆不同的网页——比如一万个——并让这些网页都链向BooksBooksBooks.com，做到这一切相对很容易。因此，如果搜索引擎和本章描述的一样来计算PageRank权重，BooksBooksBooks.com的权重值就能比其他书店高数千倍，进而有更高的排名和更多的销售额，而这都不是BooksBooksBooks.com应得的。
搜索引擎称这种滥用为网络垃圾（web spam）。（这一术语是和电子邮件垃圾
因此，搜索引擎和网络垃圾制造者在进行一场军备竞赛。搜索引擎不断尝试完善算法，以便返回真实排名。在完善PageRank算法的驱动下，孕育了大量针对其他使用互联网超链接结构进行网页排名的算法的学术和行业研究。这类算法通常被称为基于链接的排名算法（link-based ranking algorithms）。
另一个复杂因素与PageRank计算的高效性有关。访问者权重值是通过运行随机模拟来计算的，但在整个互联网上运行这类模拟耗时太长，不能进行实际运用。因此，搜索引擎并非通过模拟随机访问者来计算PageRank值：它们使用能像随机访问者模拟一样给出相同答案的数学技巧，但计算成本要低很多。我们研究访问者模拟技术是因为它直观的吸引力，也因为它描述了搜索引擎计算什么，而非如何计算。
另外，值得一提的还有，商业搜索引擎中用来判定排名的算法，要比PageRank这类基于链接的排名算法多得多。即便是在他们于1998年发表的描述谷歌的原始论文中，谷歌的联合创始人也提到了多种对搜索结果排名有贡献的功能。正如你所想的，这项技术已经进步了：在写作本书时，谷歌官网上声明“有超过200个信号”被用于评估一个网页的重要性。
除了现代搜索引擎的众多复杂性之外，PageRank核心的优美思想——权威性网页通过超链接向其他网页传输权重——仍然有效。正是这一思想帮助谷歌击败了AltaVista，让谷歌从一家小型创业企业几年后成长为搜索之王。没有PageRank的核心思想，绝大多数搜索引擎查询都将被成千上万命中但不相关的网页海洋所淹没。PageRank的确是一块算法瑰宝，能让针毫不费力地冒到草垛的顶端。注释[1]The opening quotation by Larry Page is taken from an interview by Ben Elgin, published in Businessweek, May 3, 2004. Vannevar Bush's "As We May Think" was, as mentioned above, originally published in The Atlantic magazine (July 1945). Bishop's lectures (see above) contain an elegant demonstration of PageRank using a system of water pipes to emulate hyperlinks. The original paper describing Google's architecture is "The Anatomy of a Large-Scale Hypertextual Web Search Engine," written by Google's co-founders, Sergey Brin and Larry Page, and presented at the 1998 World Wide Web conference. The paper includes a brief description and analysis of PageRank. A much more technical, wide-ranging analysis appears in Langville and Meyer's Google's PageRank and Beyond--but this book requires college-level linear algebra. John Battelle's The Search begins with an accessible and interesting history of the web search industry, including the rise of Google. The web spam mentioned on page 36 is discussed in "Spam, Damn Spam, and Statistics: Using Statistical Analysis to Locate Spam Web Pages," by Fetterly, Manasse, and Najork, and published in the 2004 WebDB conference.[1]
第四章 公钥加密
——用明信片传输秘密谁知道我这些最隐秘的事情？它们就藏在这个世界中。——鲍勃·迪伦，《立约的女人》（Covenant Woman）人们喜欢传谣，也喜欢了解秘密。而由于加密的目的就是传输秘密，所以我们都是天生的密码员。但人类进行秘密沟通要比计算机容易。如果你想向朋友透露一个秘密，你只需在朋友耳边低声说就行。计算机要做到这一点就不那么容易了。一台计算机没有办法“低声”向另一台计算机透露一张信用卡的卡号。如果计算机由互联网相连，它们控制不了信用卡卡号的流向，也无法控制会有哪些计算机知道卡号。在本章，我们会探究计算机如何应对这一问题——通过运用永远都称得上最精巧、最具影响力的计算机科学思想之一：公钥加密（public key cryptography）。
读到这里，你也许会想，为什么本章的标题中会提到“用明信片传输秘密”？下页图会给出答案：可以用通过明信片传输作为类比，以展示公钥加密的威力。在现实生活中，如果你想要发送一份机密文件给某人，你自然会在发送前将文件封存在一个安全的密封的信封内。这并不能保证机密性，但却是正确方向上的一个合理步骤。相反，如果在发送机密消息前，将机密信息写在明信片背面，很明显，这违背了机密性：任何一个接触过明信片的人（比如邮局工作人员）都只需查看明信片，就能读到这条消息。
这也正是计算机在互联网上尝试相互进行机密通信时面临的问题。因为互联网上的所有消息都会通过无数被称为路由器的计算机，消息的内容可以为任何访问路由器的人所见，而这也包括潜在的恶意窃听者。因此，每一块离开你计算机并进入互联网的数据，就好像写在明信片上！明信片类比：很显然，通过邮政系统寄出一张明信片不能保证明信片内容的秘密性。基于同样的理由，如果没有恰当地加密，从你的笔记本电脑上将一张信用卡的卡号发送给Amazon.com，很容易就会被一名窃听者窥探到。
针对这个明信片问题，你也许已经想到了一个快速补救方案。在将消息写到明信片上之前，为什么我们不使用密码对每条消息进行加密呢？实际上，如果你已经知道接收明信片的人，这个方法还能奏效，因为在过去某个时刻，你们就使用哪种密码已经达成一致。真正的问题出现在你给不认识的人寄明信片时。如果你在明信片上使用密码，邮局工作人员就不能读取你的消息，收信人当然也不能！公钥加密的真正威力在于，它允许你应用只有接收方才能解密的密码——除非你不能就使用哪种密码达成一致。
注意，计算机在和不“认识”的接收方通信时会面临相同的问题。比如，你第一次用信用卡在Amazon.com上购物时，你的计算机必须将你的信用卡卡号传输给亚马逊的服务器。但你的计算机之前从未和亚马逊的服务器联系过，因此这两台计算机在过去没有机会就密码达成一致。而它们之间尝试达成的任何协议都会被互联网上所有的路由器注意到。
让我们回到明信片的类比。的确，这种情况听起来像个悖论：接收方看到的信息和邮局工作人员看到的一样，但接收方却有某种手段能解码消息，而邮局工作人员却没有这种手段。公钥加密为这一悖论提供了一个解决方案。本章将解释其工作原理。用共享密钥加密
让我们从一个非常简单的思想实验开始。我们将放弃明信片类比，用一些更简单的来代替：在一个房间内的口头交流。具体情况是，你和朋友阿诺德以及敌人伊芙待在一个房间里。你想要秘密地传输一条消息给阿诺德，但又不能让伊芙理解这条消息。这条消息可能是一张信用卡的卡号，但为方便起见，假设这是一个极其短的信用卡卡号，只是1到9之间的一个数字。而你只能通过大声说话和阿诺德联系，好让伊芙听到。不得偷偷摸摸地耍小把戏，比如小声说或传纸条。
具体来说，让我们假设你试图传输的信用卡卡号为7。有一种方法可以让你达成目标：首先，尝试想一些阿诺德知道而伊芙不知道的数字；比如，你和阿诺德成为朋友很久了，从孩提时就生活在同一条街上。事实上，假设你俩经常在你家前院玩耍，门牌号是愉快街322号。其次，假设伊芙并不是从小就认识你，特别是她不知道你和阿诺德过去经常玩耍的房屋地址。你就能对阿诺德说：“嘿，阿诺德，记得我在愉快街的家的门牌号吗？我们过去一起玩耍的地方。如果你用门牌号，加上我现在想到的信用卡卡号中的一个数，你会得到329。”相加把戏：通过将消息7和共享密钥322相加，消息7被加密了。阿诺德可以通过减去共享密钥提取消息7，但伊芙却不能。
现在，只要阿诺德能正确地记得房屋门牌号，他就可以通过将你告诉他的总数329和房屋门牌号相减，得到信用卡卡号。他用329减去322得7，这也是你试图向他传输的信用卡卡号。同时，伊芙却不知道信用卡卡号是多少，尽管她能听到你跟阿诺德说的每个词。上图显示了整个过程。
为什么这种方法能奏效？因为你和阿诺德有一样东西，也就是计算机科学家们所谓的共享密钥：数字322。因为你俩都知道这个数字，但伊芙却不知道，你可以使用这个共享密钥秘密地传输任何数字，只要和共享密钥相加，说出总数，让另一方减去共享密钥即可。听到总数对伊芙没有任何用处，因为她不知道要减去哪个数字。
不管你是否相信，如果理解了这个简单的“相加把戏”——将一个共享密钥和如一张信用卡的卡号这类私人消息相加——你就理解了互联网上绝大多数加密真正的运作原理！计算机不断地运用着这一把戏，但要真正实现保密性，还有一些细节需要注意。
首先，计算机使用的共享密钥要比房屋门牌号322长很多。如果密钥太短，任何窃听对话的人都可以试遍所有可能性。比如，假设我们使用相加把戏，用一个3位数房屋门牌号来加密一个真正的16位数信用卡卡号。注意，3位数房屋门牌号有999种可能，那么像伊芙这样窃听了对话的敌人可以列出一个包含所有999个可能数字的表，而其中肯定有一个数字是信用卡卡号。而计算机几乎不用费什么时间就能试遍999个信用卡卡号，因此为了共享密钥能起作用，我们需要用远长于3位数的数字来作为共享密钥。
事实上，当你听到某种加密是一个特定位数的数字，比如“128位加密”，这实际上说的是共享密钥的长度。共享密钥通常被称为“钥”，是因为它能用于解锁或“解密”一条消息。如果你解开了钥匙数位的30%，这也就告诉了你钥匙的大致数位。因为128的30%大约[2]是38，我们就知道128位加密使用的钥匙是一个38位的数。一个38位数要比10的36次方还要大，而又因为这需要任何现存的计算机花费数十亿年时间来试遍这么多可能性，一个38位数的共享密钥被认为非常安全。
这个简单相加把戏要在现实生活中奏效还要克服一个困难：加法得出的结果能用于统计分析，这意味着一些人能通过分析大量你的加密消息来得到钥匙。相反，被称为“分块密码”（block cipher）的现代加密技术使用了相加把戏的变体。
首先，长消息被分解成固定大小（通常是10~15个字母）的小“块”。其次，和简单地将一块消息与钥匙相加不同的是，每个块都会根据一系列固定规则转换数次。这些规则类似于加法，但会让消息和钥匙更紧密地混合在一起。比如，规则可以是“将钥匙的前半部分和这块消息的后半部分相加，倒置结果，再将钥匙的第二部分和这块消息的前半部分相加”——不过在现实中，这些规则要更加复杂一些。现代分块密码基本上会进行10“轮”或更多类似操作，即操作列表会被反复应用。在转换的轮数足够多时，原始消息会真正地混合好，并能抵御统计攻击，但任何知道钥匙的人都能用相反的步骤运行所有操作，以获得最初的、解密的消息。
在写作本书时，最流行的分块密码是高级加密标准（Advanced Encryption Standard ），或称AES。AES能配合多种不同配置使用，但标准配置是使用16个字母的块，配备128位密钥，进行10轮混合操作。公开建立一个共享密钥
到目前为止，一切情况良好。我们已经知道互联网上绝大多数加密技术的运作原理：将消息分成块，使用加法把戏变体加密每个块。但这是加密简单的地方。难点在于一开始要建立一个共享密钥。在上面的例子中，在你和阿诺德及伊芙待的房间里，其实我们做点了弊——我们利用了你和阿诺德从小玩到大的事实，因此阿诺德知道共享密钥（你家的房屋门牌号）而伊芙不可能知道。如果你、阿诺德和伊芙都是陌生人，我们怎么玩同样的游戏？你有没有办法和阿诺德建立一个伊芙不知道的共享密钥？（记住，不能作弊——你不能低声跟阿诺德说任何事情或给阿诺德一张伊芙看不到的纸条。所有沟通都必须公开。）
乍一看，要做到这一点似乎不可能，但还是有个精巧的办法能解决这个问题。计算机科学家们称这一解决方案为迪菲—赫尔曼密钥交换（Diffie-Hellman key exchange），但我们把它称作颜料混合把戏（paint-mixing trick）。颜料混合把戏
要理解这一把戏，我们先不管传输信用卡卡号的事，而是假设你想要分享的密钥是一种特殊颜色的颜料。（的确，这有点诡异，但我们很快会看到，用这种方法来思考这个问题非常有用。）现在假设你和阿诺德、伊芙待在一个房间内，每人都有大量不同的颜料桶。你们都拥有相同的颜色选择——有多种不同颜色，每个人都拥有多桶相同颜色的颜料。这样就不存在用完颜料的问题了。每一桶颜料都清楚地标示了其颜色，因此在具体指导其他人混合不同颜色的颜料上就很容易了：你只要说些如“将一桶‘天蓝色’颜料和六桶‘淡黄褐色’颜料以及五桶‘碧绿色’颜料混合在一起”的话即可。但在每一块已知的色板（shade）上都有上百或上千种颜色，因此，不可能只通过看颜色就知道其中混合了哪些具体的颜色。而且也不可能通过试错发现混合颜色中加入了哪些具体的颜色，因为可以尝试的颜色太多了。
现在要改变一下游戏规则。你们三人各占据房屋的一角，每个角落都出于隐私考虑加以屏障，你可以在其中存放颜料，在其他人看不到的情况下混合颜料。但沟通规则和之前一样：在你、阿诺德和伊芙之间的任何沟通都必须公开。你不能邀请阿诺德进入你的私人混合区域！另一条规则规定了你分享颜料混合配方的方式。你可以给屋内其他人一批颜料，但只能把颜料放到房间中央的地板上，等其他人来捡起它。这也意味着，你永远也不能确定谁会捡起你放的颜料。最好的办法是，为每个人提供足够多的颜料，然后在房间中央留下数批分开的颜料。这样，任何想要你颜料的人都可以拿取。这条规则其实只是所有沟通都必须公开的补充：如果你给了阿诺德某种混合颜料，却没有给伊芙，你就和阿诺德进行了某种“私密”沟通，这违反了规则。
记住，这个颜料混合游戏旨在解释如何建立一个共享密钥。在这时，你也许在想混合颜料和加密有什么关系，请不要着急。你将了解到一个令人惊奇的把戏，计算机使用这一把戏在像互联网这样的公共场合建立共享密钥！
首先，我们要知道这个游戏的目标。目标是让你和阿诺德都能制作相同的混合颜料，而不能让伊芙知道如何生产。如果你达成了这一目标，我们就能说你和阿诺德建立了一种“共享的秘密混合颜料”。你可以随心所欲地进行尽可能多的公开对话，你也可以携带颜料桶多次往返于房间中央及你的私人混合区域之间。
现在我们要开始探访公钥加密背后精巧思想的旅程了。我们的颜料混合把戏分为四步：第一步：你和阿诺德各自选择一种“私人颜色”。
你的私人颜色与你最终将制造的共享秘密混合颜料不同，但它将是共享秘密混合颜料的成分之一。你可以选择任何一种颜色作为私人颜料，但你必须记住这种颜色。很显然，你的私人颜色几乎肯定会和阿诺德的私人颜色不同，因为可供选择的颜色太多了。假设你选了淡紫色作为私人颜色，阿诺德选了深红色作为私人颜色。第二步：选择一种新的不同的颜色成分并公开宣布，我们称这种颜色为“公开颜色”。
和之前一样，你可以选择任何颜色。假设你宣布的公开颜色是雏菊黄。注意只能有一种公开颜色（而不是你和阿诺德各选一种公开颜色），伊芙自然也知道这种公开颜色，因为你公开宣布了。第三步：你和阿诺德各用一桶公开颜色和一桶私人颜色制造一种混合颜色。这就是你的“公开—私人混合颜色”。
很显然，阿诺德的公开—私人混合颜色会和你的不同，因为他的私人颜色和你的不同。如果继续使用上面的例子，你的公开—私人混合颜色会包含一桶淡紫色和一桶雏菊黄，而阿诺德公开—私人混合颜色会包含一桶深红色和一桶雏菊黄。
到这时，你和阿诺德会想给彼此公开—私人混合颜色的样品，但记住，直接给房间中一个人混合颜料是违反规则的。给其他人一种混合颜色的唯一方法是制作数批该种颜料，并把它们放到房间中央，以便任何想要的人拿取。这也正是你和阿诺德所做的：你们俩都制作数批公开—私人混合颜色，并把它们放到房间中央。如果伊芙想要的话，她可以偷走一到两批，但我们很快就会了解到，这些颜料对伊芙没有任何用处。下页的图显示了颜料混合把戏第三步之后的情况。
现在到达关键点了。如果在这时仔细想一会儿，你可能会知道最后的把戏会让你和阿诺德制造出同一种共享的秘密混合颜色，而不让伊芙知道秘密。答案如下：颜料混合把戏第三步：任何想要的人都可以拿取公开—私人混合颜色。第四步：你选取一批阿诺德的公开—私人混合颜色，拿回自己的角落。现在加入一桶私人颜色。同时，阿诺德选取一批你的公开—私人混合颜色，拿回他的角落，在那里他再加入一桶他的私人颜色。
神奇吧，你俩制作了同样的混合颜色！让我们来检验一下：你将自己的私人颜色（淡紫色）加入阿诺德的公开—私人混合颜色（深红色和雏菊黄），得到的最终混合颜色是：一桶淡紫色、一桶深红色和一桶雏菊黄。阿诺德最终得到的混合颜色呢？他将自己的私人颜色（深红色）加入你的公开—私人混合颜色（淡紫色和雏菊黄），得到的最终混合颜色是：一桶深红色、一桶淡紫色和一桶雏菊黄。这正和你得到的最终混合颜色一样，也恰好是一种共享秘密混合颜色。下页的图显示了颜料混合把戏最后一步的情形。颜料混合把戏第四步：只有你和阿诺德能制作这种共享秘密颜色，如箭头所示组合混合颜色。
那伊芙呢？为什么她不能制作一份这种共享秘密混合颜色呢？原因是她不知道你或阿诺德的私人颜色，而她至少需要其中一种来制作共享秘密混合颜色。你和阿诺德打败了她，因为你从未在房间中央公开过自己的私人颜色。相反，你在公开前将自己的私人颜色和公开颜色混合在一起，而伊芙没有办法“分开”公开—私人混合颜色，也就不能获得其中一种私人颜色的纯正样本。
因此，伊芙只能获取两种公开—私人混合颜色。如果她将一桶你的公开—私人混合颜色和一桶阿诺德的公开—私人混合颜色混合在一起，结果是包含了一桶深红色、一桶淡紫色和两桶雏菊黄。换句话说，和共享秘密混合颜色相比，伊芙的混合颜色多了一份雏菊黄。她的混合颜色太黄了，而因为没有办法“分开”颜料，她不能移除多余的黄色。你也许会想，伊芙可以通过加入更多深红色和淡紫色来达到目的，但要记住，伊芙不知道你的私人颜色，因为她不会知道这些颜色还需要加入的颜色。她只能加入深红色配雏菊黄的组合或淡紫色配雏菊黄的组合，而这会导致她的混合颜色太黄。用数字进行颜料混合把戏
如果你理解了颜料混合把戏，你就会理解计算机在互联网上建立共享密钥的核心机制。当然，它们并不真的使用颜料。计算机使用数字，而要混合数字，它们会运用数学。计算机实际使用的数学并不会太复杂，但也复杂到让人第一眼看上去就会感到困惑。因此，作为理解共享密钥如何在互联网上建立的下一步，我们将用到一些“伪装”数学。真正的要点在于，要将颜料混合把戏转化成数字，我们需要一种单向操作（one-way action）：可以做一些事情，但不能取消做过的事。颜料混合把戏中的单向操作是“混合颜料”。将一些颜料混合起来形成一种新颜色很容易，但要“分开”它们并获得原来的颜料则不可能。这也是为什么颜料混合是单向操作的原因。
我们在前面提到过，将会用到一些伪装数学。下面就是我们要伪装的：将两个数相乘是一项单向操作。我敢肯定，你已经意识到了，这绝对是个借口。乘法的反面是除法，只需要用除法就能惊奇地取消乘法。比如，如果我们从数字5开始，然后乘以7，得到35。要取消这个乘法很容易，只要从35开始，除以7就可以了。这会得到我们一开始时的数字5。
但除此以外，我们将坚持使用这一伪装，在你、阿诺德和伊芙之间玩另一个游戏。这一次，我们将假设你们都知道如何将数相乘，但你们都不知道如何用一个数除以另一个数。目标和前面的游戏几乎一样：你和阿诺德试图建立一个共享密钥，但这次共享密钥将是一个数，而非一种颜料。此前的沟通规则也适用：所有联系必须公开进行，这样伊芙就能听到你和阿诺德之间的任何对话。
好，现在我们要做的事情就是将颜料混合把戏转换成数字：第一步：和选择一种“私人颜色”不同的是，你和阿诺德选择一个“私人数字”。
假设你选择了4，阿诺德选择了6。现在回想颜料混合把戏剩余的步骤：宣布公开颜色，制作公开—私人混合颜色，公开地将你的公开—私人混合颜色与阿诺德的公开—私人混合颜色交换，最后将你的私人颜色加入阿诺德的公开—私人混合颜色，以获得共享秘密颜色。要理解如何将这些步骤转换成数字，并用乘法作为单向操作取代颜料混合也不至于太难。在继续往下读之前，花几分钟看看你能否自行理解这个例子。
遵照这个解决方案并不太难；你和阿诺德都选择了自己的私人数字（4和6），下一步就是：第二步：你们其中一个人宣布“公开数字”（取代颜料混合把戏中的公开颜色）。
假设你选择了7作为公开数字。
颜料混合把戏的下一步是制作一份公开—私人混合颜色。但我们已经决定，用将数字相乘来代替混合颜料。因此，你要做的就是：第三步：将你的私人数字（4）和公开数字（7）相乘，得到“公开—私人数字”28。
你可以公开地宣布，这样阿诺德和伊芙就都知道了你的公开—私人数字是28（无须再携带颜料桶了）。阿诺德对自己的私人数字做了同样的事：他将自己的私人数字和公开数字相乘，并宣布他的公开—私人数字是42。下面的图显示了整个流程到达这一点的情形。数字混合把戏第三步：任何想要的人都能获取公开—私人数字。
还记得颜料混合把戏的最后一步吗？你拿走阿诺德的公开—私人混合颜色，加入一桶你的私人颜色，以制作共享秘密颜色。这里发生的事情也一模一样，用乘法代替颜料混合：第四步：你把阿诺德的公开—私人数字（42）和你的私人数字（4）相乘，结果是共享秘密数字168。
同时，阿诺德用你的公开—私人数字28和他的私人数字6相乘，并令人惊讶地得到了共享秘密数字168。最终结果显示在下图中。数字混合把戏第四步：只有你和阿诺德能得到共享密钥数字，通过将途中箭头所示的数字相乘。
事实上，当你用正确的方法思考时，这一点都不令人惊讶。阿诺德和你都制作出了相同的共享秘密颜色的原因是，你将相同的三种原始颜色混合在了一起，但却使用不同的顺序：你俩各自保留了一种私人颜色，把它和由其他两种颜料组成的公开混合颜料组合在一起。同样的事也发生在数字上。你俩通过将同样的三个数4、6和7相乘，得到了相同的共享密钥。（你可以自己查证，4×6×7=168。）但你之所以能达到这一目标，是通过用私人数字4和由6乘7得出的公开混合数字“混合”（相乘）得出的，而阿诺德也宣布了这个混合数字。另一方面，阿诺德通过用私人数字6和由4乘7得出的公开混合数字“混合”（相乘）得出共享密钥，而你也宣布了这个混合数字。
就和我们在颜料混合把戏中做的一样，让我们来验证伊芙不能得到共享密钥。每个公开—私人数字的值在宣布时都能被伊芙听到。她听到你说28，阿诺德说42。她还知道公开数字是7。因此，如果伊芙知道如何做除法，她就能马上知道你所有的密钥，只需要观察到28 ÷ 7=4和42 ÷ 7=6即可。而她可以继续通过计算4×6×7=168算出共享密钥。不过，幸运的是，我们在游戏中使用的是伪装数学：我们假设乘法是一种单向操作，因此伊芙不知道如何相除。于是她被数字28、42和7难住了。她可以将其中一些数相乘，但结果和共享密钥无关。比如，如果她将28×42=1 176，那就大错特错了。就和颜料混合游戏中她的结果太黄了一样，在这里，她的结果中有太多7。共享密钥中只有一个7，因为168=4×6×7。但伊芙想要破解密钥的要素中有两个7，因为1 176=4×6×7×7。而且她还没有办法去掉多余的7，因为她不知道如何做除法。现实生活中的颜料混合把戏
我们现在已经讲完了计算机在互联网上建立共享密钥所需的所有基本概念。使用数字的颜料混合机制的唯一缺陷是，它使用的是“伪装数学”，在其中我们假设没有任何一方能做除法。要完成整个流程，我们需要一个在现实生活中容易做到（比如颜料混合），但在实际中又不可能取消（比如分离颜料）的数学操作。当计算机在现实生活中进行这些操作时，混合操作就是离散指数（discrete exponentiation），而分离操作则被称为离散对数（discrete logarithm）。由于还没有一种方法能让计算机高效地计算离散对数，离散指数就成了我们寻找的那类单向操作。要恰当地解释离散指数，我们需要两个简单的数学概念。我们还需要写几个公式。如果你不喜欢公式，请直接忽略余下的部分——你几乎了解了和这个主题有关的所有东西。另外，如果你真的想知道计算机如何做这件神奇的事，接着往下读。
我们需要的第一个重要的数学概念被称为钟算（clock arithmetic）。这倒是我们都熟悉的东西：钟上有12个数字，每次当时针路过12时，都会从1开始重新计数。一个从10点钟开始、持续4小时的活动会在2点钟结束，也就是说，在这个12小时钟系统中，10+4=2。在数学中，钟算也是这样运行的，除了两个细节：（1）钟的大小可以是任何数（而非一个普通的钟上熟悉的12个数字），（2）数字从0而不是从1开始计数。
下面图中的例子用的是大小为7的钟。注意，钟上的数字是0、1、2、3、4、5和6。用钟大小为7的钟做钟算，只要像平常一样将数字相加相乘即可，不过不管结果如何，你只要取除以7所得的余数即可。计算12+6，我们首先像平常一样相加，得到18。然后我们注意到18中有两个7（即14），余4。因此最终答案是：12+6=4（钟大小为7）
在下面的例子中，我们将钟大小调为11。（稍后将讨论到，现实应用中的钟大小要大很多。我们使用小的钟大小是为了让解释尽可能简单。）在将结果除以11后取余并不太难，因为11的倍数都是像66和88这样重复的数。下面是几个用钟大小为11进行计算的例子：7+9+8=24=2 （钟大小为11）8×7=56=1 （钟大小为11）左图：当钟大小为7时，数字12被简化为数字5——从0开始，按图中箭头所示顺时针方向计算12个单位。右图：钟大小仍为7，我们发现12+6=4——从5开始，这也是左图结束的地方，再在顺时针方向添加另外6个单位。
我们需要的第二个数学概念是幂函数（power notation）。这个概念一点也不花哨：就是写下许多相同数字相乘的快捷方法。和写下64×6×6×6不同的是，你可以写成6，这就是指6乘以本身4次。你可以将幂函数和钟算结合起来。比如：43=3×3×3×3=81=4 （钟大小为11）27=7×7=49=5 （钟大小为11）
下页的表格显示了钟大小为11时数字2、3和6的前10个幂。这在我们将要研究的例子中非常有用。在继续深入前，请你确保自己认可这张表格的生成方式。让我们来看看最后一栏。这一栏的第一项是6，12也就是6。下一项代表6，即36，但由于我们使用的钟大小为11，36比33大3，因此这一项是3。要计算这一栏的第三项，你也许会认为3我们要计算6=6×6×6，但有个更简单的方法。我们已经用自己感兴23趣的钟大小计算了6，结果是3。要得到6，我们只需要将先前的结果乘6。也就是3×6=18=7（钟大小为11）。下一项是7×6=42=9（钟大小为11），依此类推，直到该栏最后一项。
最后，我们终于要准备建立一个计算机在现实生活中使用的共享密钥了。和之前一样，你和阿诺德将尝试分享一个密钥，而伊芙窃听并试图算出密钥。第一步：你和阿诺德各自单独选择一个私人数字。这张表显示了钟大小为11时数字2、3和6的前10个幂。正如上文所解释的，每个项都能通过一些非常简单的算术从上一项中算出。
为保证数学尽可能简单，我们将在这个例子中使用非常小的数字。因此，假设你选择8作为私人数字，而阿诺德选择9。这两个数字——8和9——都不是共享密钥，而是像你在颜料混合把戏中选择的私人颜色，这些数字将被用作“混合”一个共享密钥的成分。第二步：你和阿诺德公开就两个公开数字达成一致：钟大小（本例中使用11）和另一个被称为基数的数字（选2为基数）。
这些公开数字——11和2——像公开颜色一样，你和阿诺德在颜料混合把戏一开始就对此达成了一致。注意，颜料混合类比与本例有点不同：在颜料混合中，我们只需一种公开颜色，而在这个例子中，我们需要两个公开数字。第三步：通过使用幂符号和钟算，你和阿诺德各自将自己的私人数字和公开数字相混，分别得到一个公开—私人数字（public–private number，PPN）。
具体来说，混合是按照公式来完成的：
PPN=base私人数字（钟大小）
这个公式用文字写出来可能会显得有点诡异，但在实际中却很简单。在我们的例子中，我们能通过参考上一页的表格来得出答案：8
你的PPN=2=3 （钟大小为11）9
阿诺德的PPN=2=6 （钟大小为11）
在这一步之后，你可以在下页的图中查看这一步。这些公开—私人数字正相当于你在颜料混合把戏第三步中制作的“公开—私人混合颜色”。在那一步中，你将一桶公开颜色和一部分你的私人颜色相混合，制作你的公开—私人混合颜色。在这里，你使用幂符号和钟算将自己的私人数字和公开数字相混合。第四步：你和阿诺德各自单独获得对方的公开—私人数字，再和自己的私人数字相混合。
这可以按照下面的公式完成：私人数字
共享密钥=其他人的PPN（钟大小）
和前面的公式一样，用文字写出来会显得有点诡异，但通过参考前一页的表格，很容易就能得到答案：8
你的共享密钥=6=4 （钟大小为11）9
阿诺德的共享密钥=3=4 （钟大小为11）
最终解决方案显示在第71页的图中。现实生活数字混合第三步：任何想要公开—私人数字（3和6）的人——使用幂和钟算88计算得出——都可以获取到。3下面的“2”提醒了我们3是如何计算的，但3=2使用9的钟大小为11这个事实却并未公开。类似的，6下面的“2”也仍然保持私密。
自然，你的共享密钥和阿诺德的共享密钥相同（这个例子中是4）。取得这个结果依靠了例子中的一些复杂算术，但基本概念和前面一样：尽管你按照不同的顺序混合了各种成分，但你和阿诺德都使用了相同的成分，因此也得到了相同的共享密钥。
和这个把戏的早前版本一样，伊芙被排除在外。她知道这两个公开数字（2和11），她也知道这两个公开—私人数字（3和6）。但她不能使用任何知识来计算共享密钥数字，因为她不能获取你和阿诺德持有的秘密成分（私人数字）。实际中的公钥加密
颜料混合把戏的最终版本——运用幂和钟算混合数字——就是计算机在互联网上建立共享密钥的实际方法之一。本章描述的方法被称为迪菲—赫尔曼密钥交换机制。这一机制以怀特菲德·迪菲（Whitfield Diffie）和马丁·赫尔曼（Martin Hellman）的名字命名，他俩于1976年首次发表了这一算法。每次你访问一个安全网站（以“https:”而非“http:”开头），你的计算机和其通信的网站服务器之间都会建立一个共享密钥，使用的方法是迪菲—赫尔曼机制或工作原理类似的替代方法之一。而一旦建立了共享密钥，这两台电脑就能使用之前描述的相加算法的变体对所有通信进行加密。现实生活数字混合第四步：只有你和阿诺德能得到共享密钥数字，通过使用幂和钟算计算将如箭头所示的元素组合起来。
还有很重要的一点值得注意，当迪菲—赫尔曼机制在现实中运用时，实际涉及的数字要远比我们在例子中使用的数字大。我们使用的钟大小很小（11），因此计算起来就很简单。但如果你选择的公开钟大小很小，那么可能的私人数字也会很小（因为你只能使用比钟大小小的私人数字）。而这也意味着有人可以使用计算机试出所有可能的私人数字，直到找到一个数字生成你的公开—私人数字。在上面的例子中，只有11个可能的私人数字，因此这个系统非常轻易就能被破解。相反，迪菲—赫尔曼机制在现实中运用时通常会使用有几百个数位长的钟大小，这让可能的私人数字多得令人不可想象（比一万亿的一万亿次方还多得多）。即便如此，也需要小心选取公开数字，以确保它们具有正确的数学性质——如果你感兴趣的话，请看下页的文字框。迪菲—赫尔曼公开数字最重要的属性是，钟大小必须是一个素数——只有1和其自身两个除数。另一个有趣的要求是，基数必须是钟大小的本原根（primitive root）。这也意味着基数的幂最终将循环遍钟上每一个可能的值。再看看前文提到的表，你会注意到2和6都是11的本原根，但3却不是——3的幂循环到的值有3、9、5、4和1，却没有2、6、7、8和10。在为迪菲—赫尔曼机制选择一个钟大小和基数时，钟大小和基数必须满足特定的数学性质。
本章描述的迪菲—赫尔曼方法只是通过（电子）明信片通信的多种绝妙技巧之一。计算机科学家们称迪菲—赫尔曼方法为密钥交换算法（key exchange algorithm）。其他公钥算法的运作方式不同，能让你使用接收方宣布的公开信息，直接向潜在的接收方加密一条消息。相反，密钥交换算法能让你使用来自接收方的公开信息，建立一个共享密钥，但加密过程通过加法把戏来完成。对于互联网上绝大部分通信而言，后面的选项——我们在本章中了解到的这种方法——要更容易让人接受，因为它需要的计算能力要少很多。
但也有一些程序需要用到完整的公钥加密。这类程序中最有趣的可能要算数字签名了，我们将在第九章谈到它。在你阅读第九章时会发现，完整版公钥加密的思想类似于我们已经了解到的：机密信息和公开信息用一种在数学上不可逆的方式“混合”在一起，就像混合在一起的颜料一样，再也分不开。最著名的公钥加密系统是RSA，这个名字由首次发表该系统的三位发明者姓的首字母组合而成：罗纳德·李维斯特（Ronald Rivest）、阿迪·沙米尔（Adi Shamir）和雷奥纳德·阿德尔曼（Leonard M.Adlemen）。第九章用RSA作为解释数字签名如何运行的主要例子。
在这些早期公钥算法发明的背后，都有一个迷人而复杂的故事。迪菲和赫尔曼的确是发表迪菲—赫尔曼机制的第一批人，时间是1976年。李维斯特、沙米尔和阿德尔曼也的确是发表RSA的第一批人，时间是1978年。但这并不是故事的全部！人们后来发现，英国政府在数年前就已经知道类似系统。不幸的是，那些发明迪菲—赫尔曼机制和RSA的先驱们是英国政府通信实验室GCHQ的数学家。他们工作的结果被记录在内部机密文件中，直到1997年才解密。
RSA、迪菲—赫尔曼机制和其他公钥加密系统不仅仅是绝妙的思想。它们还发展成了商业技术和互联网标准，对商业和个人有着极其重要的意义。没有公钥加密，我们每天使用的绝大部分在线交易都不可能安全地完成。RSA的发明者在20世纪70年代为自己的系统申请了专利，而他们的专利直到2000年年末才失效。在专利失效的那天晚上，美国旧金山市的美国音乐大剧院举行了一次庆祝晚会——也许是为庆祝公钥加密将永久为人们服务这一事实。注释[1]Simon Singh's The Code Book contams superb, accessible descriptions of many aspects of cryptography, including public key. It also recounts in detail the story of the secret discovery of public key cryptography at GCHQ in Britain. Bishop's lectures (see above) contain a clever practical demonstration of the paint-mixing analogy for public key crypto.[2]对于了解计算机数字系统的人而言，我在这里说的是小数位数，而非二进制数。对于了解对数的人而言，将二进制数转化为小数位数的转换比例230%来自于log10≈0.3。[1]
第五章 纠错码
——自纠正的错误告诉一个人他犯了错是一回事，让他掌握真理则是另一码事。——约翰·洛克（John Locke），《人类理智论》（Essay Concerning Human Understanding）如今，我们已习惯于在有需要时随时使用计算机。20世纪40年代在贝尔电话公司实验室工作的研究员理查德·汉明（Richard Hamming）就没这么幸运了：其他部门使用着他所需要的公司计算机，只有周末才轮到他用。因此，你可以想象，由于计算机在读取自身数据时出错从而导致频繁崩溃后，他有多么沮丧。汉明谈到这个问题时是这样说的：我要轮两周才能进去一次，却发现我所有的东西都被清空了，什么都没得到。我真的很生气，因为我想要这些答案，而且还浪费两个周末的时间。于是我说：“去他的，如果计算机能侦测到错误，为什么它不能对错误定位并进行纠正？”
要说明发明纠错码的必要性，还有另外几起很鲜明的例子。汉明很快就创造了第一批纠错码：一种近乎神奇的能侦测并纠正计算机数据中错误的算法。没有纠错码，我们的计算机和通信系统会比现在慢很多，功能上弱许多，可靠性也会差很多。错误侦测及纠正的需求
计算机有三项基本工作。最重要的工作是执行计算，即给予计算机一些输入数据，计算机必须用某种方法转化数据，并得出一个有用的答案。但如果没有计算机执行的另外两项非常重要的工作：存储数据和传输数据，计算答案的能力基本上也没用。（计算机通常在内存和磁盘驱动器上存储数据，基本上是通过互联网传输数据。）要深入理解这一点，想象一台既不能存储也不能传输信息的计算机。这样的计算机自然不会有什么用。的确，你可以做一些复杂计算（比如，准备一份复杂的财务报表，详细说明公司预算），但你不能将结果发送给同事，甚至不能保存结果以便返回继续操作。因此，传输和存储数据对现代计算机是真正的至关重要。
但传输和存储数据要面临一个巨大挑战：数据必须丝毫无差——因为在许多情况下，哪怕一丁点错误也会让数据变得毫无用处。作为人，我们也熟悉在不出错的情况下存储和传输信息的需求。比如，如果你写下某人的电话号码，按正确的顺序无误地记录下每位数至关重要。哪怕其中有一位数出错，那个电话号码对你或其他人都毫无用处。在一些情况中，数据出错的后果要比毫无用处更糟。比如，存储一个计算机软件的文件中有一个错误，这会导致程序崩溃或让程序做一些原本不应该做的事。（程序甚至可能会删除一些重要文件，或在你保存工作前崩溃。）而在一些计算机化的金融记录中出错，可能会导致实际的金钱损失。（假如你以为自己在买每股5.34美元的股票，而这只股票的实际价格是每股8.34美元。）
不过，人们需要存储的无误信息相对较少，而且在知道一些信息——如银行账号、密码、电子邮件地址等——很重要的情况下，通过仔细检查避免错误也不是太难。而另一方面，计算机要无误地存储和传输的信息量绝对是海量。为了让你对信息量级有概念，想想下列情形。假设你有一个存储容量是100 GB的计算设备。（在写作本书时，这是低价笔记本电脑的标准容量。）这100 GB相当于1 500万页文本。因此，即便计算机存储系统每100万页犯一个错误，在设备容量填满时（平均）也会有15个错误。这一情况也适用于传输数据：如果你下载一个20兆的软件，你的计算机每接收100万个字符就会出错一次，下载的软件中也会有逾20个错误——在你不曾预料到的情况下，每一个错误都有可能导致成本巨大的崩溃。
这个故事的教训是，对于计算机而言，精确度达到99.999 9%也还是不够好。计算机必须能在存储和传输数十亿块信息的情况下，不犯任何一个错误。但和其他设备一样，计算机也必须处理通信问题。电话就是个好例子：显然电话不能完美地传输信息，因为电话对话经常要遭遇失真、静电噪声或其他类型的噪声。但电话并不是遭遇这类情况的唯一设备：电线受所有种类的波动影响；无线通信无时无刻不受干扰；硬盘、CD（激光唱盘）和DVD（数字视频光盘）等物理媒体会由于灰尘或其他物理干扰的影响，被划伤、受损或不能读取。面临如此显然的通信错误，我们怎么能希望实现数十亿分之一的错误率呢？本章将揭示让这一奇迹发生的绝妙计算机科学背后的思想。结果证明，如果你运用正确的把戏，即便是极端不可靠的通信频道也可以以极低的错误率传输数据。而且这个错误率是如此之低，以至于在实际当中，错误基本上完全被消除了。
试读结束[说明：试读内容隐藏了图片]