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

ELPC网站制作推广工作室 互联网转载 不详 2007-10-8 12:43:49

呢？这正是Bar-Yossef 等人工作的主要成果所在：他们采用蒙特卡罗仿真（Monte Carlo Simulation） 算法实现了这一点

• 目标分布π(x) : D 上的等概率随机分布, π(x) = 1/|D |
• 实际采样分布p(x) : D 上的文档匹配度随机分布，p(x) = deg(x) / ∑x'∈D deg(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)一般都比较大，因此搜索结果文档被放弃的比例较高，如何进一步改进算法的复杂度是一个值得探讨的问题。 参考文献

* Ziv Bar-Yossef and Maxim Gurevich, Random Sampling from a Search Engine's Index (PDF文件和PPT文件)

<

责任编辑: 刘-高祖

相关信息

搜索引擎优化：诊断流量下降的原..[10-08]

搜索引擎优化：诊断流量下降的原..[10-08]

长尾理论和搜索引擎优化SEO[10-08]

搜索引擎优化要掌握的20条准则[10-08]

网站优化-百度搜索引擎相关[09-28]

百度搜索引擎对SEO元素的比重研究[09-28]

最新信息

Zac访谈Matt Cutts[10-08]

搜索引擎优化：诊断流量下降的原..[10-08]

搜索引擎优化：诊断流量下降的原..[10-08]

长尾理论和搜索引擎优化SEO[10-08]

搜索引擎优化要掌握的20条准则[10-08]

坚持内容为王，开发出色内容[10-08]