第二章 搜索引擎索引 在世界上最大的草垛中寻针 ALGORITHMS 哈克，在咱俩站着的地方的下面，你拿一根钓鱼 竿就可以触到我钻出来的那个洞。看看你能不能 找到。 一马克·吐温， 《汤持索亚历险记》(Tom Sawyer
PDF电子书基地http:/dayol982.400gb.com
PDF电子书基地 http://dayo1982.400gb.com
搜索引擎对我们的生活产生了深远影响。绝大多数人每天都进行多次 搜索查询，但我们极少会停下来思考这个令人惊叹的工具是如何奏效的 搜索引擎提供的海量信息以及搜索结果的速度与质量变得如此平常，如果 我们搜索的问题没有在几秒内得到回答，我们就会困惑。我们倾向于忘记， 每一个成功的搜索引擎都是从世界上最大的草垛一万维网—寻针。 事实上，搜索引擎提供的超级服务，不仅仅是针对搜索抛出一大堆花 哨技术的结果。的确，每个大型搜索引擎公司都运营着一个由无数数据中 心组成的国际网络，其中包括数以千计的服务器计算机和先进的网络设 备。但没有聪明的算法来组织和检索我们请求的信息，所有这些硬件都会 变得毫无用处。因此，在这一章和下一章，我们将探究这样一些算法瑰 宝一每次在进行网络搜索时，我们都会用到这些算法。我们很快就会了 解到，搜索引擎的两大主要任务就是匹配(matching)和排名(ranking). 这一章将讲述一种聪明的匹配技术：元词把戏(metaword trick)。在下一 章，我们将转而讨论排名任务，审视谷歌公司著名的网页排名算法
改喜素*的九大算法 匹配和排名 当你发起一次网络搜索查询时会发生什么？以这样一种高屋建瓴的视 角开始会很有帮助。我已经说过，搜索有两个主要阶段：匹配和排名。在 实际中，搜索引擎将匹配和排名组合成一个流程以实现一致性。但这两个 阶段在概念上是独立的，因此我们会假设在排名开始前，匹配已经完成。 上图就给出了一个例子，图中查询的是“London bus timetable”(伦敦公 共汽车时刻表)，而匹配阶段则回答“哪个网页与我的查询匹配”这个问 题一在这个例子中就是所有提到“London bus timetable'”的网页。 匹配后的网页 排名后的网页 国图圖 1 查询 伦敦公共汽车时刻表 匹配 排名 3 网络搜索的两个阶段：匹配和排名。在第一阶段（匹配）后可能会出现数千或数百万个匹配 结果，这些结果必须按照相关度在第二阶段（排名）进行排序。 但现实搜索引擎中的许多查询都有数百、数千乃至数百万个“命中”。 而搜索引擎用户通常只喜欢查看几个结果，最多5个或10个。因此，搜 索引擎必须从大量命中里挑出最好的几个。一个好的搜索引擎不仅仅会挑 出最好的几个命中，而且会以最有用的顺序显示它们一最匹配的页面排 在第一，然后是匹配度排名第二的页面，依此类推。 以正确顺序挑选出最好的几个命中被称为“排名”。排名是关键的第 二个阶段，紧随最开始的匹配阶段。在搜索行业的残酷世界中，搜索引 PDF电子书基地http:/dayol982.400gb.com
PDF电子书基地 http://dayo1982.400gb.com
第二章搜术引黎紫引一在世界上最大的草垛中寻针 擎的生死由其排名系统的质量决定。2002年，美国前三大搜索引擎的市 场份额基本相当，谷歌、雅虎和MSN在美国的市场份额都在30%以下。 [MSN随后被重新包装成Live Search,之后又被命名为必应(Bing)。]之 后几年，谷歌的市场份额迅速扩大，同时将雅虎和MSN的市场份额打压 到了20%以下。人们普遍认为，谷歌迅速上升为搜索行业冠军是得益于 其排名算法。因此，毫不夸张地说，搜索引擎的生死由其排名系统的质量 决定。不过，正如我已经提到的，我们将在下一章探讨排名算法。至于现 在，让我们专注于匹配阶段吧。 AltaVista:第一个互联网级别的匹配算法 搜索引擎匹配算法的故事从哪里开始？一个很显然却错误的回答会 说从谷歌—21世纪初期最伟大的技术成功故事一开始。事实上，谷 歌最初只是两位斯坦福大学研究生的博士学位项目，这个故事不仅温暖 人心，而且令人印象深刻。拉里·佩奇(Larry Page)和谢尔盖·布林 (Sergey Brin)在1998年组装了一堆计算机硬件来运行一种新的搜索引擎。 不到10年，他们的公司成为了互联网时代崛起的最伟大的数字巨人。 不过，互联网搜索的想法已经存在很多年了。最早的商业应用是 Infoseek和Lycos（两者都于1994年推出)，以及于1995年推出搜索引擎 的Alta Vista。.20世纪90年代中期的几年中，AltaVista是搜索引擎的王者。 当时我还是一名计算机科学研究生，我清楚地记得自己惊叹于AltaVista搜 索结果的成熟度。有史以来第一次，有一个搜索引擎能完全索引互联网上 每一个页面的全部文本。更可贵的是，眨眼间就能返回结果。要继续理 解这个令人回味的技术突破，我们要从接触一个古老的（毫不夸张）概 念索引开始。 17