搜索引擎索引的等概率随机采样：
对于搜索引擎等概率随机采样的研究已经有了相当长的历史，具体的背景文献我们不准备在这里一一探讨。我们希望通过对Bar-Yossef等人最近工作的介绍，把一种比较客观、科学的测试方法推介给读者。我们也会探讨他们的方法对于中文索引的局限性和一些解决方案。
图3 一个简化的搜索引擎索引
图3给出了一个简化了的搜索引擎索引示例，假定关键字“news”将返回4个结果：www.cnn.com、news.google.com、www.foxnews.com和news.bbc.co.uk。
首先我们给出一组定义
● 关键字搜索结果集合：results(q) = { 搜索关键字 q所返回的全部结果文档之集合}
● 文档关键字集合：queries(x) = { 所有能返回文档x的搜索关键字之集合}
● 搜索关键字池P：一组理论上能够覆盖所有文档的搜索关键字集合
o 例如图3中P= {news, bbc, maps, google}
● 关键字搜索结果量：card(q) = |results(q)|，搜索关键字 q所返回的全部结果文档之数量
o 例如图3中 card(“news”) = 4，card(“bbc”) = 3
● 文档匹配度:deg(x) = |queries(x)| ，全体能够匹配文档x的搜索关键字数量
o 例如图3中deg(www.cnn.com) = 1，deg(news.bbc.co.uk) = 2
当我们通过搜索框对搜索引擎的索引进行采样，所获得的结果实际上偏向于匹配度高的文档。对于图3所示的搜索引擎，如果我们从搜索关键字池P = {news, bbc, maps, google}中任意选取一个关键字，然后在所得搜索结果中任意选取一个文档，那么选到某一个具体文档的概率与它的匹配度成正比，例如，p(news.bbc.co.uk) = 2/13 ，p(www.cnn.com) = 1/13
因此，通过关键字对搜索引擎的索引进行采样，实际上是对文档匹配度概率分布在作随机抽样。具体地说，如果相对于一个给定的搜索关键字池P，该索引的全部文档匹配度的总和为deg(D) = ∑x∈Ddeg(x)，那么通过搜索框对引擎采样获取具体一个文档x的概率是deg(x)/ deg(D)。
如何通过对文档匹配度分布的随机抽样而获得我们所期望的等概率随机采样呢？这正是Bar-Yossef 等人工作的主要成果所在：他们采用蒙特卡罗仿真（Monte Carlo Simulation）算法实现了这一点
● 目标分布π(x) :D上的等概率随机分布, π(x) = 1/|D|
● 实际采样分布p(x) :D上的文档匹配度随机分布，p(x) = deg(x) / ∑x'∈Ddeg(x')
● 偏差权值: w(x) = π(x)/p(x) ∝1/deg(x)
采样过程，参见图4
● 选定一个搜索关键字池P
● 随机选取q ∈P
● 在搜索结果中随机选取一个文档x ∈results(q)
● 计算该文档对P 的匹配度deg(x)
● 产生一个0~1的随机数r，如果r ≤ 1/deg(x)保留该文档，否则放弃
● 重复上述过程直到获得N个有效采样点
图4 通过蒙特卡罗仿真（Monte Carlo Simulation）算法实现对索引的等概率随机采样
问题和讨论
上述算法在数学上非常严谨优美，但是在具体的实现过程中仍然有相当多的困难，尤其是对于中文搜索引擎，有一些特殊的问题需要探讨。
● 搜索关键字池P的选取
P选择的条件是（1）要保证p(x) = 0，即索引中文档不匹配任何一个关键字q ∈P的概率足够小。如果这个概率太高，测试只能局限于索引的一小部分，测试的结果就失去了意义。（2）关键字搜索结果量card(q)最好要比较小，这样可以尽可能地避免搜索结果超过搜索引擎允许返回结果的上限。作者提出的方案是通过抓取和分析一个大型的网上文库，例如维基百科全书，选择其中所有的英文单词的集合或者所有K个相连单词的集合作为P。这对于没有分词问题的英文而言是容易实现的，但对于汉语等需要分词的语种，这个方法似乎并不很合适。我们建议直接采用GBK字库中的全部字符，或者采用中文分词标准中所有词汇的集合。
● 如何计算文档对P的匹配度deg(x)？
文档匹配度deg(x)必须离线计算，通过查询获得是不现实的。对英文文档来说，只要计算文档中覆盖了多少个关键字q ∈P。但是对中文而言，不同引擎包含了不同的搜索逻辑，例如四个汉字以下的搜索通常采取词组搜索，长搜索词有些引擎可能采取与或逻辑。不同引擎对于汉语分词的处理也有较大的差异。在索引文档时，有些引擎可能考虑了繁简汉字的转换。所有这些都会对匹配度产生一定程度的影响。
实际上，匹配度deg(x)的计算并不一定要十分精确，一些近似处理是可以接受的，只要误差不至于太大。我们建议用GBK字库的单个汉字集合作为P，这样可以避免分词的差异。而此时文档的匹配度就是一个文档包含不同GBK字符的个数。
● 搜索引擎对搜索最大返回结果的限制。
这一点Bar-Yossef 等人的文章中有比较详细的讨论，他们认为这个限制对于测试结果的影响并不太大。
● 该算法的计算复杂度比较高。
从计算量上考虑，由于deg(x)一般都比较大，因此搜索结果文档被放弃的比例较高，如何进一步改进算法的复杂度是一个值得探讨的问题。
相关阅读：
