如何测试搜索引擎的索引量大小（前篇）

sowang

出自：雅虎搜索日志    作者：陈朝晖 雅虎美国工程师   


          背景知识：搜索引擎的质量指标一般包括相关性（Relevance）、时效性（Freshness）、全面性（Comprehensiveness）和可用性（Usability）等四个方面，今天我们要谈的索引量就属于完整性指标的范畴。

         首先需要注意的是，对于搜索引擎，网页的索引量和抓取量是不同的概念。搜索引擎的网页抓取数量一般都要远大于索引量，因为抓取的网页中包括很多内容重复或者作弊等质量不高的网页。搜索引擎需要根据算法从抓取的网页当中取其精华，去其糟粕，挑选出有价值的网页进行索引。因此，对用户而言，搜索引擎的索引量大小才更有意义。

         其次，无限制增大索引量并不一定能保证搜索质量的提升。一方面，在全面性指标中，除索引量外，还需要考虑到收录网页的质量和不同类型网页的分布。另一方面，搜索引擎的质量指标体系要保证四方面的均衡发展，不是依靠单个指标的突破就可以改善的。目前包括雅虎中国在内的主流中文搜索引擎的网页索引量都在20亿量级，基本上可以满足用户的日常查询需求。

         然而，由于从外部无法直接测算出搜索引擎网页索引量的绝对值大小，很多搜索引擎服务商喜欢对外夸大自己的收录网页数，作为市场噱头。从1998年开始，Krishna Bharat和Andrei Broder就开始研究，如何通过第三方来客观比较不同搜索引擎索引量的大小。8年后，在今年5月份的WWW2006大会上，来自以色列的Ziv Bar-Yossef和Maxim Gurevich由于这方面的出色研究成果夺得了大会唯一的最佳论文奖。他们的研究算出了主流英文搜索引擎的索引量相对大小：雅虎是Google的1.28倍，Google是MSN的1.36倍。他们是如何算出这些数字的呢？下面我们将为搜索引擎爱好者介绍这个算法，以及探讨在中文搜索引擎上是如何应用的。


概述

         搜索引擎的索引量或称覆盖率对搜索结果的相关性、时效性和找到率都具有深远的影响。出于市场运作的考虑，各大互联网搜索引擎不时对外公布自己索引的文档数量，然而这些数据往往不同程度地被加入了一些水份，可信度上有一个问号。因此，如何通过搜索引擎的公共接口，也就是通常所说的搜索框，比较客观、准确地测试它的索引量就成为了一个令人关注的问题。


图1，对搜索引擎的索引采样


        每一个搜索引擎的索引都覆盖了互联网上全部文档的一个子集。如果我们把测试作为对这个集合的采样，那么问题的关键就在于如何实现一个近似的等概率随机采样（uniform search engine url sampler），参见图1。具体地说，假定一个搜索引擎S总共索引了|D|个文档，那么我们希望采样得到某一个具体文档的概率是1/|D|。

      一旦实现了通过搜索框对索引的等概率随机采样，我们就可以在统计意义上比较有把握地估计搜索引擎索引量的相对大小。如下图所示：



图2，比较搜索引擎索引的相对大小


       我们先对引擎S1随机采样N1个url。然后，通过url查询获知引擎S2索引了其中的N12个url，而没有索引另外N10个。换句话说，N1 = N10+N12 。同样地，如果我们对引擎S2随机采样N2个url，发现其中N21被S1收录而N20没有收录，N2=N20+N21。那么我们可以估计S1与S2的相对大小为：

|D1|/|D2|
≌(N12+N10) / (N12+N12N20/N21)
＝(N1N21)/(N2N12)
＝N21/N12 (如果N1══N2)

待续...