搜索引擎索引——在世界上最大的草垛中寻针(1)

哈克,在咱俩站着的地方的下面,你拿一根钓鱼竿就可以触到我钻出来的那个洞。看看你能不能找到。

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

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

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

匹配和排名

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

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

上一章

读书导航