改变未来的九大算法

    [美]约翰·麦考密克 著

    管策 译

    中信出版集团目录

    所获赞誉

    序

    前言 计算机日常运用的卓越思想

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

    第二章 PageRank ——让谷歌腾飞的技术

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

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

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

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

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

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

    第九章 并非万能的算法 ——有些程序不可能存在

    结语 更多在你指尖的“精灵”注释

    致谢所获赞誉

    荣获美国出版商协会“2012年计算机与信息科学最佳专业

    学术图书奖”

    作者解释了数亿人每天使用的一些算法，不是如算术和排

    序这类简单的算法，而是更复杂的事情——如何确定网页的重

    要性，以及无法被计算的问题。我强烈推荐这本书。

    ——查克·塞克(Chuck Thacker)，“图灵奖”得主

    长久以来，没有哪本书能让我像十几岁时阅读霍金和费曼

    的书时那样让我兴奋，而这本书做到了，它提醒了我，为什么

    我喜欢计算机科学。

    ——安德鲁·菲茨吉本(Andrew Fitzgibbon)，“艾美奖”得主(相机软件开发者)

    作者揭示了计算机科学家对算法着迷的原因：它们如此实

    用、美观和优雅。

    ——保罗·柯曾(Paul Curzon)，《科学》(Science)一本关于关键算法的指南，阅读起来愉悦且轻松。它传达

    出一种奇妙的感觉——让电脑发挥魔力的是美丽的科学，而非

    技术。

    ——安德烈亚斯·特拉辛格(Andreas Trabesinger)，《自然物理学》(Nature Physics)

    尽管人们对计算机充满兴趣，但并不了解其核心思想。这

    本书在向大众展示计算机科学这一艰巨的任务中取得了非凡的

    成就。

    ——欧内斯特·戴维斯(Ernest Davis)，SIAM News(美国工业和应用数学学会的新闻期刊)

    大多数人对电子支付的安全性，或者电影如何被“塞

    进”光盘知之甚少，也不太关心，但作者认为它们富含惊人的

    独创性和创造力。

    ——罗伯特·马修斯(Robert Matthews)，《BBC聚焦》(BBC Focus，英国一本关于科学和技术的月刊)

    作者用日常类比巧妙地解读核心算法，这对没有数学背景

    的读者来说很有用。想钻研算法的数学和计算机科学的学生也

    会感到受益颇深……这本书应该被图书馆珍藏。

    ——阿特·吉特尔曼(Art Gittleman)，就职于美国数学协会(MAA)计算机专业人士和非专业人士都会对这本书感兴趣。作者

    并没有试图“用科学迷惑我们”，也没有“卖弄”其数学才

    能。相反，他采用了我们都能理解的简单类比。比如，作者用

    混合彩色颜料来类比公钥密码的原理，这非常精彩。

    ——克莱夫·马克斯菲尔德(Clive Maxfield)，《电子工程时报》(EE Times)

    这本书适合对信息系统的工作原理感兴趣的人。

    ——约翰·吉尔比(John Gilbey)，就职于泰晤士高等教育出版社(Times Higher Education)序

    计算机行业正在改变我们的社会，正如物理学和化学在前

    两个世纪给社会带来的巨大改变一样。的确，数字技术几乎影

    响甚至颠覆了我们生活的方方面面。鉴于计算机行业对现代社

    会的重要性，人们对让这一切成为可能的基本概念却知之甚

    少，这显得有点儿自相矛盾。对这些概念的研究是计算机科学

    的核心，而麦考密克的这本新书则是向大众展示这些概念的少

    数书籍之一。

    人们较少视计算机科学为一门学科，其中一个原因是，高

    中极少开设计算机科学这门课程。虽然人们通常认为要强制开

    设物理学和化学这两门基础课程，但作为独立学科的计算机科

    学，却通常只在大学阶段才被开设。况且，学校讲授的“计算

    机”或“信息与通信技术”知识，通常只是略高于使用软件的

    技能训练。因此，学生们认为计算机学科枯燥也并不意外；而

    他们在娱乐和通信上使用计算机技术的天然热情，也因为实现

    这类技术的学术深度而有所消退。这些问题被认为是导致过去

    10年大学计算机科学专业学生人数下降一半的主要原因。考虑

    到数字技术对现代社会的极度重要性，让人们重新领略计算机

    科学的奇妙之处已经刻不容缓。

    2008年，我很荣幸地被选为第180届英国皇家科学院圣

    诞讲座(Royal Institution Christmas Lectures)的演讲人，该讲座由迈克尔·法拉第(Michael Faraday)于1826

    年发起。2008年圣诞讲座的主题首次涉及计算机科学。在准

    备这些讲座时，我花了很多时间来思考如何向大众解释计算

    机科学，却发现能提供解决这一需求问题的资源很少，几乎

    没有关于计算机科学的畅销书。因此，我特别高兴能看到麦

    考密克的这本书。

    麦考密克在面向大众介绍计算机科学的复杂思想方面做得

    非常好。这其中的许多思想极其新颖，仅从这点上来看，它们

    就很值得关注。举个例子：电子商务的爆炸式增长之所以成为

    可能，是因为它具备了能在互联网上秘密、安全地发送机密信

    息(如信用卡卡号)的能力。数十年来，建立在“开放”通道

    上的保密通信被认为是一个科学难题。当人们发现解决方法

    时，他们才发觉保密通信是精美的艺术。而麦考密克也以精确

    的类比进行了解释，读者无须拥有计算机科学知识就能理解。

    这些优点使这本书在科普读物领域做出了不可估量的贡献，我

    极力推荐这本书。

    克里斯·毕晓普(Chris Bishop)

    微软剑桥研究院资深科学家

    大不列颠皇家学院副院长

    爱丁堡大学计算机科学教授

    数在线交易都使用该技术存储及检索信息。

    发明了一种在数据库中组织信息的先进方法。目前，绝大多

    ● 1969年，IBM(国际商业机器公司)的一名研究人员

    望之后，我们仍期待出现一个真正的智能计算机程序。

    能领域的研究。在取得了许多重大成功，也经历了无数次失

    议。这次会议的目标很清晰，也很大胆，那就是开创人工智

    ● 1956年，一群学者在达特茅斯(Dartmouth)举行会

    干扰而遭受破坏。

    算机能以完美的精确度传输信息，即便大部分数据都因为被

    文，由此开创了信息理论研究领域。这位科学家的工作让计

    ● 1948年，一位供职于电话公司的科学家发表了一篇论

    大、设计得多好，仍旧有一些问题将是计算机不能解决的。

    继 续 证 明 了 ， 不 管 未 来 建 造 的 计 算 机 运 行 多 快 、 功 能 多 强

    位英国天才开创了计算机科学研究领域。之后，这位天才还

    ● 20世纪30年代，在第一台数字计算机被发明以前，一

    进行介绍：

    计算机科学中的伟大思想是如何诞生的？以下遴选部分思想

    计算机日常运用的卓越思想

    前言● 1974年，英国政府秘密通信实验室的研究人员发明了

    一种让计算机实现安全通信的方法，即另一台计算机可以查

    看在计算机之间交换的所有信息。这些研究人员为政府保密

    所限——不过幸运的是，三名美国专家独立开发并拓展了这

    项重大发明，为互联网上所有的安全通信打下了基础。

    ● 1996年，斯坦福大学的两名博士生决定联手搭建一个

    互联网搜索引擎。几年后，他们创办了谷歌公司——互联网

    时代的第一个数字“巨头”。

    我们在享受21世纪技术惊人增长的同时，使用计算机设备

    ——不管是现有最强大的一组机器，还是最新、最时尚的手持设

    备——不可避免地要依赖计算机科学的基础思想，而这些思想都

    诞生于20世纪。想一想：你今天做过什么令人印象深刻的事情

    吗？好吧，这个问题的答案取决于你怎么看。也许是你搜索了包

    含数十亿份文档的资料库，从中选出两三份与你的需求最相关的

    文档？即便有能够影响所有电子设备的电磁干扰，你在存储或传

    输数百万条信息的过程中，也没犯一点儿错误？你是否成功地完

    成了一次在线交易，即便同时有成千上万名消费者在访问同一个

    服务器？你是否在能够被其他数十台计算机嗅探到的线路中传输

    了一些机密信息(比如信用卡卡号)？你是否运用过压缩的魔

    力，将数兆的照片压缩成更易于管理的大小，以便附在电子邮件

    中发送？你是否在手持设备上触发了人工智能，以自动纠正你在

    手持设备的小巧键盘上输入的内容？

    这些令人印象深刻的壮举都有赖于之前提到的伟大发明或发

    现。然而，绝大多数计算机用户每天都会多次运用这些天才的想

    法，却从没有意识到!本书旨在向大众解释这些观点——我们每天使用的计算机科学的伟大思想。在解释每一个观点时，我都假

    设读者不了解有关计算机科学的任何知识。

    算法：指尖“精灵”的构件

    到目前为止，我一直在谈计算机科学的伟大“思想”，但计

    算机科学家们会将许多重要思想形容为“算法”。那么思想和算

    法之间有什么区别？究竟什么是算法？这一问题最简单的答案

    是，算法是一张精确的处方，它按顺序详细列出了解决一个问题

    所需要的具体步骤。我们小时候在学校学到的一种算法就是很好

    的例子：将两个大数字相加的算法。如下例所示。这个算法涉及

    一连串的步骤，开始的步骤如下：“首先，将两个数的最末位数

    相加，写下结果的最末位数，将剩下的数放到左侧的下一栏；接

    着，将下一栏的数相加，再将除了结果末位数的数字和前一栏余

    下的数相加……”依此类推。

    图1 将两个数字相加的算法的前两步

    请注意算法步骤近乎机械化的感觉。事实上，这是算法的关

    键特点之一：每步都必须绝对精确，没有任何人类意图或推测掺

    杂其中。这样，每个完全机械化的步骤才能被编入计算机。算法的另一个重要特点是，不管输入什么，算法总能运行。我们在学

    校学到的相加算法就拥有这一特性：不管你想把哪两个数相加，运用算法最终都会得出正确答案。比如，用这一算法将两个长达

    1 000位的数相加，你肯定能得到答案，尽管这需要相当长的时

    间。

    对把算法定义为一张精确的机械化的处方的说法，你也许会

    略感好奇。这张处方究竟要多精确？要进行哪些基本操作？比

    如，在上面的相加算法中，简单地说一句“把两个数相加”是不

    是就行了？还是说我们要在加法表上列出所有位的数字？这些细

    节看起来也许有点儿乏味，甚至会显得有点儿学究气，但它们其

    实离真相不远了：这些问题的真正答案正处于计算机科学的核

    心，并且也和哲学、物理学、神经科学及遗传学有联系。有关算

    法究竟是什么的深层问题都归结于一个前提——众所周知的邱奇

    –图灵论题(Church-Turing thesis)。我们将在第九章重温这

    些问题，届时我们还将讨论计算的理论极限，以及邱奇–图灵论

    题的一些方面。同时，将算法比作一张非常精确的处方这一非正

    式观点，其效果会非常好。

    现在我们知道了什么是算法，但算法和计算机有什么联系

    呢？关键在于，计算机需要用非常精确的指令编程。因此，在能

    让计算机为我们解决某个特定问题之前，我们需要为那个问题开

    发一种算法。在数学和物理学等其他学科中，重要的结果通常是

    由一个方程式获得的。(著名的例子包括勾股定理a2+b2=c2或爱

    因斯坦的质量守恒定理E=mc2。)相反，计算机科学的伟大思想

    通常是来形容如何解决一个问题的——当然，是使用一种算法。因此，本书的主要目的是，解释让计算机成为你的个人天赋的东

    西——计算机每天使用的伟大算法。

    一种伟大的算法由什么构成？

    这会引出一个刁钻的问题：什么才是真正伟大的“算法”？

    潜在的候选算法清单相当长，但我用几条基本标准缩减了用于本

    书的候选算法清单。第一条也是最重要的一条标准是，伟大的算

    法要被普通计算机用户每天用到。第二条重要的标准是，伟大的

    算法应该能处理具体的现实问题，如压缩一个特定文件或通过一

    个噪链精确地传输文件。对已经了解部分计算机科学的读者而

    言，第XIII页文字框中的内容将解释前面两大标准的部分后果。

    第三个标准是，算法主要和计算机科学理论相关。这排除了

    主要和计算机硬件——如CPU(中央处理器)、监视器，以及网

    络——有关的技术。这条标准也减轻了对基础设施——如互联网

    ——设计的重视。为什么我要着重于计算机科学理论？部分原因

    是公众对计算机科学认知的不平衡：有一种广泛的观点认为，计

    算机科学基本上就是编程(如“软件”)和设备设计(如“硬

    件”)。事实上，最美妙的计算机科学思想中有许多是十分抽象

    的，并不属于以上任意一类。我希望通过强调这些理论思想，让

    更多人将计算机科学作为一门知识学科来理解。

    你也许已经注意到了，我列出的标准可能会遗漏一些伟大的

    算法，但我从一开始就避免了定义“伟大”这个极其麻烦的问

    题。针对这一问题，我依赖于自己的直觉。在本书说明的每种算

    法中，其核心都是一个让整件事情奏效的精巧把戏(trick)。对 我 而 言 ， 当 这 个 把 戏 显 露 出 来 时 ， 那 个 “ 啊 哈 时

    刻”(即“aha”moment，指用户体验产品时眼前一亮的那一

    刻)会让解释这些算法成为令人愉悦的经历，我希望你也能有此

    感受。我会用到“把戏”这个词很多次，需要指出的是，我并非

    指那些卑劣或骗人的把戏——孩子可能会用在弟弟或妹妹身上的

    那种把戏。相反，本书中的把戏类似于交易诀窍或魔术：为达成

    目标而采用的聪明技巧，否则目标很难达成或根本不可能达成。

    因此，根据直觉，我选出了自认为是计算机科学世界中最精

    巧、最神奇的把戏。在英国数学家高德菲·哈罗德·哈代

    (G.H.Hardy)的《一个数学家的辩白》(A Mathematician’s

    Apology)中，作者试图向公众解释数学家从事数学的原因

    ——“美是第一道测试：丑陋的数学在这个世界中无永存之

    地”。这道“美的测试”也适用于在计算机科学中蕴含的理论思

    想。因此，选取在本书中出现的算法的最后一条标准，就是哈代

    的——也许可以这么称呼——“美的测试”：我希望至少能成功

    地向读者展示部分美——我在每种算法中感受到的美。

    第一条标准——要被普通计算机用户每天用到——排除

    了主要由计算机专业人士使用的算法，如编译器和程序验证

    技术。第二条标准——解决某个特定问题的具体程序——排

    除了许多作为计算机科学本科课程核心内容的伟大算法，如

    排序算法(快速排序等)、图形算法(迪杰斯特拉最短路径

    算法等)、数据结构(哈希表等)。这些算法的伟大性毋庸

    置疑，而且很轻易地就满足了第一条标准，因为普通用户使

    用的绝大多数应用程序都会反复应用这些算法。但这些算法

    太通用了：它们能被用来解决众多问题。在本书中，我决定要专注于解决特定问题的算法，因为对普通计算机用户而

    言，这些算法能让他们拥有更清晰的动机。

    接下来我将谈谈选择展示的这些算法。搜索引擎的巨大影

    响，也许是算法技术影响所有计算机用户最明显的例子，我自然

    也将部分互联网搜索的核心算法收在了本书中。第一章描述了搜

    索引擎如何使用索引寻找与请求匹配的文件，而第二章则解释了

    网页排名(PageRank)算法——谷歌公司为保证匹配度最高的文

    件出现在搜索结果列表顶部的原始算法。

    即便我们不经常想这件事情，绝大多数人也能意识得到，为

    提供出人意料的强大搜索结果，搜索引擎会落实一些深邃的计算

    机科学思想。相反，其他一些伟大的算法也经常被用到，但计算

    机用户对此甚至都没有意识到。第三章描述的公钥加密(Public

    Key Cryptography)就是这样一种算法。用户每次访问一个安全

    网站(地址以https而非http开头)，都会用到公钥加密的一个

    方面——众所周知的密钥交换(key exchange)——来展开一段

    安全对话。第三章就是在解释密钥交换过程的实现原理。

    第四章的主题是纠错码(Error Correcting Codes)，这是

    我们经常使用但没有意识到的另一类算法。事实上，纠错码极有

    可能是有史以来唯一一种使用次数最频繁的伟大算法。纠错码可

    以让计算机识别并纠正在储存或传输数据时出现的错误，而不必

    依靠备份或再次传输。纠错码无处不在：它们被用于所有硬盘驱

    动器、众多网络传输、CD(数字光盘)和DVD(高密度数字视频

    光盘)，甚至还存在于一些计算机的内存中。不过，纠错码的能

    后很有可能只占据电子邮件提供商5 GB空间的很小一部分。

    子邮件提供商提供给你的5GB(计算机存储单位)空间，经压缩

    节省带宽，而数据中心通常会压缩消费者的数据以降低成本。电

    高：我们根本没有意识到，我们的下载或上传也可以通过压缩以

    量，以便用电子邮件发出。不过在私底下，压缩使用的频率要更

    接进行压缩，也许是为了节省磁盘空间，也许是为了缩减照片容

    成我们“指尖精灵”的伟大思想。计算机用户的确会时不时地直

    第六章讨论了压缩算法。压缩算法组成了另一组使计算机变

    (Neural Network)。

    Classifier)、“决策树”(Decision Tree)，以及神经网络 趣、最成功的图形识别技术：最近邻分类器(Nearest-neighbor 偏好，因为它是我的研究领域。因此，第五章描述了三种最有

    图形识别来决定向用户展示哪种广告。另外，我对图形识别也有

    (特别是智能手机)越来越趋向于语音操作。一些网站甚至使用

    需要自动纠错，平板设备必须识别手写输入，而且所有这些设备 年，图形识别的重要性急剧增大：配备小型屏幕键盘的移动设备

    个十年里，绝大多数日常计算并没有用到这些技术。但在2010

    ——如笔迹、讲话和人脸——的技术。事实上，在21世纪的第一

    计算机用户每天用到。图形识别属于计算机识别高度可变信息

    伟大的计算机科学思想榜单，但它违背了第一条标准：要被普通

    (Pattern Recognition Algorithm)。图形识别算法也能进入

    第 五 章 稍 微 有 点 儿 特 殊 ， 它 介 绍 的 是 图 形 识 别 算 法 力太强了，以至于我们意识不到它们的存在。第七章讲到了数据库中运用的一些基础算法。这一章侧重为

    实现一致性——指一个数据库中的关系不互相冲突——而采用的

    聪明技巧。没有这些精巧的技术，我们的绝大部分在线生活[包

    括网络购物以及通过Facebook(“脸书”)之类的社交网站进行

    互动]就会消亡于众多计算机错误中。这一章解释了一致性真正

    的问题是什么，以及计算机科学家是如何解决这一问题的。前提

    是不牺牲我们所期望的在线系统拥有的高效性。

    在第八章，我们会了解理论计算机科学无可争议的瑰宝之

    一：数字签名。乍看之下，用数字形式“签署”一份电子文档似

    乎不可能。你也许会想，这种签名必须由数字信息组成，而任何

    想要伪造签名的人都可以毫不费力地拷贝这些信息。这一悖论的

    解决方案，就是计算机科学取得的最令人瞩目的成就之一。

    第九章采取了截然不同的视角：与其描述一种已经存在的伟

    大算法，我们不如去了解一种假如存在则必然会伟大的算法。不

    过我们会震惊地发现，这种特别伟大的算法不可能存在。这表明

    计算机解决问题的能力存在绝对极限，而我们将简单地从哲学和

    生物学角度探讨这一结果的应用。

    在结语部分，我们会总结伟大算法的一些共性，花些时间畅

    想未来会怎样。会有更多伟大算法出现吗？或者说，我们已经发

    现了所有伟大的算法？

    在此，不得不提前说一下本书的风格。任何科普作品都必须

    清楚地告知读者信息来源，但引用会破坏文本的流畅性，并让读

    者产生阅读学术著作的感觉。由于可读性和易读性是本书的首要

    目标，所以本书正文不会出现引用。不过，我清楚地记录了所有来源，并在本书末尾的“注释”板块中列出，还时不时地附上拓

    展评论。这个板块还列出了一些额外材料，以便感兴趣的读者能

    去寻找更多和计算机科学中伟大算法有关的信息。

    为什么我们要关注这些伟大的算法？

    希望对这些迷人思想的快速总结能让你渴望深入了解它们的

    运行方式。不过，也许你仍然在思考：本书的终极目标是什么？

    让我简短地介绍一下本书的真正目的。这本书绝不是一本问答式

    操作手册。在读完本书后，你不会成为计算机安全方面的专家，也不会成为人工智能或其他领域的专家。你也许能学到一些有用

    的技能，这倒是真的。比如：你会对如何检查“安全”网站凭证

    以及“已签名”软件包了解更多；你能在有损和无损压缩之间针

    对不同任务做出明智选择；通过理解搜索引擎索引和排名技术的

    某些方面，你能更高效地使用搜索引擎。

    然而，这些相对于本书真正的目的不过是微小的红利。在读

    完本书后，你不会成为一名更加熟练的计算机用户，但你会更加

    珍视每天在所有计算设备上不停使用的思想的美。

    为什么这是件好事？我用类比的方式来说明。我肯定不是一

    位天文学专家——事实上，我在这个领域里相当无知，我想知道

    更多。但每当我注视夜空时，我知道的少量天文学知识增强了我

    此刻的享受。有时，我对所见事物的理解，让我产生了一种满足

    和惊奇的感觉。希望在读完本书后，你在使用计算机时也能经常

    获得同样的满足和惊奇之感，这也是我殷切的希望。你将真正珍视我们时代最常见、最神秘的黑盒子：你的个人电脑，你指尖

    的“精灵”。第一章

    搜索引擎索引

    ——在世界上最大的草垛中寻针哈克，在咱们俩站着的地方的下面，你拿一根钓鱼竿就

    可以触到我钻出来的那个洞。看看你能不能找到它。

    ——马克·吐温，《汤姆·索亚历险记》(Tom Sawyer)

    搜索引擎对我们的生活产生了深远影响。绝大多数人每天都

    进行多次搜索查询，但我们极少会停下来思考这个令人惊叹的工

    具是如何奏效的。搜索引擎提供的海量信息以及搜索结果的速度

    与质量变得如此平常，如果我们搜索的问题没有在几秒内得到回

    答，我们就会感到困惑。我们倾向于忘记，每个成功的搜索引擎

    都是从世界上最大的草垛——万维网(www)——中寻针的。

    事实上，搜索引擎提供的超级服务，不仅仅是针对搜索抛出

    花哨技术产生的一大堆结果。的确，每家大型搜索引擎公司都运

    营着一个由无数数据中心组成的国际网络，其中包括数以千计的

    计算机服务器和先进的网络设备。但若没有聪明的算法来组织和

    检索我们要寻找的信息，所有这些硬件都会变得毫无用处。因

    此，在这一章和下一章，我们将探究这样一些算法瑰宝——每次

    在进行网络搜索时，我们都会用到这些算法。我们很快就会了解

    到，搜索引擎的两大主要任务就是匹配(matching)和排名

    (ranking)。这一章将讲述一种聪明的匹配技术：元词把戏

    (Metaword Trick)。在下一章，我们将转而讨论排名任务，审

    视谷歌公司著名的网页排名算法。匹配和排名

    当你发起一次网络搜索查询时会发生什么？以这样一种高屋

    建瓴的视角开始会很有帮助。我已经说过，搜索有两个主要阶

    段：匹配和排名。在实际运行中，搜索引擎将匹配和排名组合成

    一个流程以实现一致性。但这两个阶段在概念上是独立的，因此

    我们会假设在排名开始前，匹配已经完成了。下图就给出了一个

    例子，图中查询的是“London bus timetable”(伦敦公共汽车

    时刻表)，而匹配阶段则回答了“哪个网页与我的查询匹配”这

    个 问 题 —— 在 这 个 例 子 中 就 是 所 有 提 到 “London bus

    timetable”的网页。

    图2 网络搜索的两个阶段：匹配和排名。在第一阶段(匹配)后可能会出现数千

    或数百万个匹配结果，这些结果必须按照相关度在第二阶段(排名)进行排序

    现实搜索引擎中的许多查询都有数百、数千，乃至数百万

    个“命中”，而搜索引擎用户通常只喜欢查看几个结果，5个或

    最多10个。因此，搜索引擎必须从大量“命中”里挑出最好的几

    个。一个好的搜索引擎不仅会挑出最好的几个“命中”，而且会以最有用的顺序显示它们——将最匹配的页面排在第一，然后是

    匹配度排名第二的页面，其后依此类推。

    以正确顺序挑选出最好的几个“命中”，这被称为“排

    名”。排名是第二个关键阶段，紧随最开始的匹配阶段。在搜索

    行业的残酷世界中，搜索引擎的生死由其排名系统的质量决定。

    2002年，美国前三大搜索引擎的市场份额基本相当，谷歌、雅虎

    和MSN(微软公司旗下的门户网站)在美国的市场份额都在30%以

    下。MSN随后被重新包装成实时搜索引擎，之后又被命名为必应

    (Bing)。之后几年，谷歌的市场份额迅速扩大，同时将雅虎和

    MSN的市场份额分别打压到了20%以下。人们普遍认为，谷歌迅速

    上升为搜索行业冠军是得益于其排名算法。因此，毫不夸张地

    说，搜索引擎的生死由其排名系统的质量决定。不过，正如我已

    经提到的，我们将在下一章探讨排名算法。至于现在，让我们专

    注于匹配阶段吧。

    AltaVista[1]：互联网级别的第一种匹配算法

    搜索引擎匹配算法的故事从哪里开始？一个很显然却错误的

    回答是从谷歌——21世纪初期最伟大的技术成功故事——开始。

    事实上，谷歌最初只是斯坦福大学两位学生的博士学位项目，这

    个故事不仅温暖人心，而且令人印象深刻。拉里·佩奇(Larry

    Page)和谢尔盖·布林(Sergey Brin)在1998年组装了一堆计

    算机硬件来运行一种新的搜索引擎。不到10年，他们的公司就成

    了互联网崛起时代最伟大的“数字巨人”。不过，互联网搜索的想法已经存在很多年了。最早的商业应

    用是Infoseek和Lycos(两者都于1994年被推出)，以及于1995

    年推出搜索引擎的AltaVista。20世纪90年代中期，AltaVista是

    搜索引擎的王者。当时我还是一名计算机科学专业的研究生，我

    清楚地记得自己惊叹于AltaVista搜索结果的成熟度。有史以来

    第一次，有一个搜索引擎能完全索引互联网上每个页面的全部文

    本。更可贵的是，眨眼间它就能返回结果。要继续理解这个令人

    回味的技术突破，我们就要从接触一个古老的(毫不夸张)概念

    ——索引——开始。

    古老的索引

    索引的概念是所有搜索引擎背后最基础的思想。但索引并非

    由搜索引擎发明：事实上，索引的思想几乎和书写本身一样古

    老。比如，人类学家发现了一座具有五千年历史的古巴比伦神庙

    图书馆，里面按学科对楔形文字泥版进行了分类。因此，索引可

    以称得上是计算机科学中最古老的有用思想。

    如今，“索引”这个词通常指参考书的最后一个板块。你可

    能想要查看的所有概念都以固定顺序(通常是按字母排序)被列

    出，每个概念下都列出了这个概念出现的位置(通常是页码)。

    因此，一本和动物有关的书也许会有一个像“cheetah(猎豹)

    124，156”的索引项。这个索引项意味着“cheetah”这个词在

    第124页和第156页出现过。图3 一个假想的万维网，由编号为1、2和3的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页。现代搜索引擎对结

    果的组织很合理，只摘取了返回页面的少许片段，不过，我们基

    本上会忽略这样的细节，而将精力集中在搜索引擎如何知道页

    面“符合”用户输入的查询上。

    图4 一个用页码表示的简单索引

    再 举 一 个 非 常 简 单 的 例 子 ， 让 我 们 来 检 查 一 下 查

    询“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

    查询的意义截然不同[2]。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个词的位置是3，第29个词的位置是29，依此类推。例子

    中3个页面组成的数据集如下页图所示，我们还加上了词位置。

    图下面的是索引——由存储页码和词的位置得出的结果组成。我

    们称这种创建索引的方法为“词位置把戏”(Word-location

    Trick)。举几个例子，以确保大家理解了词位置把戏。索引的

    第一行是“a 3–5”。这意味着词“a”只在数据库里集中出现

    过一次，是第3页的第5个单词。索引中最长的一行是“the 1–1

    1–5 2–1 2–5 3–1”。这一行可以让你知道，这组数据集中

    了出现单词“the”的所有具体位置。它在第1页出现过2次(位

    置1和5)，在第2页出现过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开始。

    图5 上图：在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。因此这

    两个词之间的距离是4。因此，“cat”的确出现在“dog”前后

    五个位置之内，而第3页则是查询cat NEAR dog的“命中”。和前面一样，请注意这次查询的执行是多么高效：无须遍历任何网

    页的实际内容——相反，只参考了索引中的两个项。

    不过，在实际中，NEAR查询对搜索引擎用户并不非常重要。

    几乎没人使用NEAR查询，绝大多数主要搜索引擎甚至不支持它

    们。尽管如此，能执行NEAR查询的能力实际上对现实中的搜索引

    擎至关重要。这是因为搜索引擎不断地在后台执行NEAR查询。要

    想理解其中的原因，我们先要研究现代搜索引擎面临的主要问题

    之一：排名。

    排名和邻度

    到目前为止，我们一直专注于匹配阶段：为一个给出的查询

    高效地找出所有“命中”的问题。不过正如之前强调的，第二个

    阶段“排名”对一个高质量的搜索引擎是必不可少的，它是挑选

    出前几个“命中”并展示给用户的阶段。

    让我们更细致地来检验“排名”的概念。一个网页的“排

    名”究竟取决于什么？真正的问题不是“这个网页和查询匹配

    吗”，而是“这个网页和查询相关吗”。计算机科学家们使

    用“相关度”(relevance)这个术语来形容一个结果网页和某

    个特定查询有多么相配或这个网页多么有用。

    举个具体的例子，假设你对导致疟疾的原因感兴趣，并在一

    个搜索引擎中输入查询malaria cause(导致疟疾)。简化考

    虑，假设搜索引擎对这一查询只有两个“命中”——下图显示的

    两个网页。现在来看看这两个网页。作为人类，你很快就知道第1页和疟疾起因有关，而第2页似乎是对刚刚发生的一些军事行动

    的描述，只不过恰巧使用了“cause”和“malaria”这两个词。

    因此，和第2页相比，第1页无疑和查询malaria cause更相关。

    可计算机不是人，让计算机理解这两页的主题也很难，似乎不可

    能让搜索引擎正确地对这两个“命中”进行排名。

    图6 上两图：两个提及疟疾的样本网页；下图：从上方两个网页中创建的索引的

    一部分

    不过，事实上，有一种很简单的方法让这个例子中的排名正

    确。查询词彼此相邻的网页比那些查询词相距很远的网页相关度

    更高。在疟疾这个例子中，“malaria”和“cause”在第1页中

    仅相距1个词，而在第2页中则相距17个词。(记住，搜索引擎只

    通过查看索引项就能高效地发现这一点，无须返回查看网页。)

    因此，尽管计算机并不真正地“理解”查询的主题，它也能猜测网页1比网页2更具相关性，因为网页1查询词之间的距离要比在

    网页2中更近。

    总而言之，尽管人们不经常使用NEAR查询，搜索引擎也在不

    断地使用和邻度有关的信息，以提高搜索排名。而它们能高效地

    做到这点的原因则是，它们使用了词位置把戏。

    我们已经了解到，早在距今5 000年以前，古巴比伦人就开

    始使用索引。而词定位把戏也不是由搜索引擎发明的：这是互联

    网出现以前，在另一种信息检索中用到的著名技术。不过，在下

    一部分，我们将了解一个看起来的确是由搜索引擎设计者发明的

    新把戏：元词把戏。对这一把戏和众多相关思想的精巧运用，使

    AltaVista搜索引擎在20世纪90年代晚期迅速成为搜索行业

    的“领头羊”。

    元词把戏

    到目前为止，我们一直都在使用极其简单的网页示例。然

    而，绝大多数网页拥有众多结构，包括标题、标头、链接和图

    片，可我们还一直认为网页只是普通的词表。接下来，我们将探

    索搜索引擎如何处理网页中的结构。不过，为了尽可能地保持简

    单，我们只会引入一层结构：网页的顶部会有一个标题，之后是

    页面的正文。下图显示了我们熟悉的三页示例，并附加了一些标

    题。图7 一个网页范例集，每个网页都有一个标题和一段正文

    实际上，要像搜索引擎一样分析网页结构，我们就需要了解

    更多编写网页的知识。网页是由一种特殊语言编写的，以便网络

    浏览器能用很好的格式展示它们。编写网页最常用的语言被称为

    HTML，不过HTML的细节对本次讨论来说不重要。标头、标题、链

    接、图片等格式化结构是用被称为元词的特殊单词编写的。比

    如，网页标题开始使用的元词也许是，而结束这个

    标题的元词可能是。类似的，网页正文可能是以

    开始，以结束。不要纠结于“<”“>”这

    些符号。它们出现在绝大多数计算机键盘上，人们通常只知道这

    些符号的数学意义是“小于”和“大于”。不过在这里，这些符

    号和数学没有任何关系，只是方便将这些元词和网页中的正常单

    词区分开来。

    请看图8。这张图展示的内容和图7一样，但这次显示的是实

    际编写网页的样子，而非在网络浏览器中显示的样子。绝大多数

    网络浏览器都能让用户检验网页的原始内容，这需要选择名

    为“查看网页源代码”的菜单选项——我建议你下次有机会试验

    一下。在这里使用的元词，如和，是帮

    助你理解虚构的、易于辨认的示例。在真实的HTML中，元词被称

    作标签(tag)。HTML中开启和结束标题的标签是