搜索引擎的信息覆盖率评测模型研究

北京大学计算机科学技术系·网络与分布式系统实验室·孟涛·学士论文1搜索引擎的信息覆盖率评测模型研究孟涛李晓明闫宏飞北京大学计算机科学技术系，100871摘要本文从有向图结构出发，总结分析了搜索引擎搜集子系统网页搜集不完全性的若干因素，指出信息覆盖率这一概念的研究意义，由此提出了三类比较重要的信息覆盖率概念。在对信息覆盖率建立量化研究模型之后，本文以北大天网WebInfomall平台为考察对象，以不同的方式对中国Web进行取样，用PageRank和HITS这两类典型的权值算法计算出其中的重要网页作为样本，从量和质的角度上考察webinfomall的信息覆盖率，得到合理的数量覆盖率和质量覆盖率实验数据，从而验证了WebInfomall信息覆盖率结论的合理性和信息覆盖率评测模型的可靠性。关键词搜索引擎，信息覆盖率，取样，权值计算，验证，数量覆盖率，质量覆盖率1研究背景（WorldWideWeb）自1989年诞生并于次年开始运行以来,在迄今为止的十多年里发展迅猛，已逐渐成为人类社会信息资源中的一个重要组成部分。它以超文本和超媒体为核心技术，将文本、图形、图像、音频和视频等信息有机结合起来，给人们以丰富的信息表示空间。随着Internet技术和应用的不断发展，社会的信息化进程不断加快，越来越多的社会信息资源开始选择Web作为其载体。当前，个网站，约2,500,000,000网页，包含了至少19TB以上的数据，而且这些网页正以每天净增7,500,000的速度膨胀[1][2]。而在中国，根据中国互联网络中心（CNNIC）于2002年1月进行的互联网统计报告[3]，CN下注册的域名数为127,319个，共有277,100个Web站点。到2002年为止，中国境内的Web站点共有53,432,598个网页，主要分布在约49,146个网站中[4]。面对浩瀚的互联网络资源，人们若不借助其他工具很难快速的查找到自己所需要的信息，这带来了搜索引擎的诞生。从1994年诞生的第一代搜索引擎Lycos和InfoSeek等开始，发展到当前流行的Google、Altavista等系统，它们已逐渐成为人们进行网际冲浪的重要工具之一。根据弗吉尼亚理工大学GVU中心的调查报告[5]，全世界有84.8%的用户通过搜索引擎获得自己所需网页，足见搜索引擎功用之一斑。我们将每一条独立的信息称为一个网页，它有一个唯一的资源定位地址称为URL(UniformResourceLocation)。搜索引擎便是利用URL之间的连接关系，搜集其对应的网页信息，建立索引，供用户查询。因此，搜索引擎搜集的网页集合便是用户所能得到查询结果的最大范围；这个范围越接近，搜索引擎越优秀。事实上，没有任何一个搜索引擎能搜集完的所有网页。著名的搜索引擎Google系统和WiseNut系北京大学计算机科学技术系·网络与分布式系统实验室·孟涛·学士论文2统，搜集到并提供给用户查询的网页数量分别是2,073,418,204个[6]和1,571,413,207[7]个，最多不过静态网页总数的80%。而根据GregR.Notes在200？年3月发表的搜索引擎统计数据[8]？？，这两个系统的网页数据量是最大的。网络上的信息数量巨大而且种类繁多，任何一个实际运行的搜集系统都不可能将其全部搜尽。优秀的搜索引擎总会搜集尽量多的网页，更好的满足用户的查询要求。考察搜索引擎对信息资源的搜集覆盖程度，可作为不断改进搜集系统的根据，对评价搜索引擎的性能好坏具有积极的作用。另一方面，随着社会信息化程度的不断提高，将是该阶段人类社会信息资源在网络上的投影，记录着人类社会的历史发展进程。基于搜索引擎技术开发的网络信息博物馆正以此为目的，力图通过搜索引擎的网页搜集系统不断搜集上的所有网页，若干年后能够同时在时间和空间上展示的每一个角落。因此，研究搜索引擎的信息覆盖率对验证网络信息博物馆网页资源的有效性也有着十分重大的意义。本文的研究工作基于上述目的，针对北京大学计算机系网络与分布式系统实验室开发的搜索引擎[8]及以此为基础开发的网上信息博物馆WebInfomall[9]，采取多种方法从多个角度计算其信息覆盖率，证明了该网页搜集系统获得的中国网络信息资源是基本有效的。2模型概述2.1网页搜集的不完全性如果把中的每一个网页看作一个顶点，则这个顶点以URL作为它的唯一标记；又由于网页中存在其它网页的URL，可以把这种网页间的链接看作连接顶点的边，则整个构成了一张有向图，如图1示。相应的，每一个顶点的入度和出度对应着链向该网页的网页数量和该网页链向其他网页的数量。显然，这是一张不完全图，因为里面存在很多入度或出度为0的顶点。当前的网页搜集系统都是基于对这种链接结构的理解，依据网页之间的链接关系，从某一个种子URL开始，不断的从新搜到的网页中提取出URL，从而到达其它的网页。搜集过程中，通常需要对网页重要性作初步的判断，优先搜集相对有价值的网页。在这种搜集机制里面，存在着下列问题，导致无法遍历所有的网页。北京大学计算机科学技术系·网络与分布式系统实验室·孟涛·学士论文3部分网页的入度为0，即从任何一个网页开始，都不存在到它的路径，这类网页的数量约占全体网页数量的10%[10]。选择的种子URL集合中，任何一个网页都不存在到该网页的路径。中的有向图结构中，只有约21.3%的顶点能被选取作为起始点去遍历剩下的约90%的顶点[10]。由于在网页搜集的过程中出现了优先排序，搜集系统资源本身的限制（磁盘容量和时间限量）导致部分网页直到搜集过程中止都没有被搜集，出现Starve的情况[11]。本身处于不断的膨胀过程之中，大量新出现的网页来不及搜集。搜集系统自身一般都有搜集周期，而某些网页（如实时新闻网页）的更新频率远大于搜集频率。从广义的角度而言，凡是上的信息都应该被搜集，而现在的搜索引擎一般只搜集了部分格式的网页信息。当前搜集的一般都是静态网页中类似于HTML文档的信息资源，没有考虑到包括动态网页在内的巨量深层网络文档。据估计，当前中的所有网页（包括深层网页）约有5500亿之多，搜索引擎所覆盖的不到其百分之一[12]！因此，可以肯定任何一个实际运行的网页搜集系统都不可能将当前中的所有网页全部抓尽。这种搜集性能越优异，意味着它所获得网页集合在数量和质量上越接近于实际的，网页之间的链接关系也越逼近实际的有向图结构。搜索引擎的信息覆盖率正是对这种接近程度的衡量，它体现了一个网页搜集系统所获得的网页集合及链接关系所占实际的比例。2.2几类重要的覆盖率广义的信息资源，应该定义为互联网上的一切信息，即所有存在于上的文档。这些文档有些能通过浏览器浏览，有些则不能；有些存在于网站的数据库中，经过动态的请求方能生成，有些则是静态存在的且被其它网页链接到。搜索引擎当前所能搜集的绝大多数就是这种静态的网页，且在处理过程中进一步过滤掉了某些不可浏览的部分如可执行文件等。在这里，我们所研究的搜集系统覆盖目标是上的所有静态网页，它们通常可通过浏览器显示内容，且其URL一般静态存在于其它网页中。我们可以从多个角度来考虑搜索引擎对信息资源的覆盖程度。搜集系统应该力图遍历的所有网页，在数量这一角度上达到完全覆盖的程度。这提供一个衡量搜集系统覆盖信息能力的全局标准。例如当前个[2]，Google系统的网页搜集数量是2,073,418,204个[6]，因此可以估计其数量覆盖率为百分之八十左右。如果系统的数量覆盖率足够高，我们就可以认为它基本上覆盖了上的所有信息资源。高的数量覆盖率应该是任何一个搜集系统及以此为基础的网上信息博物馆的首要目标。网上信息资源极为丰富，但也存在不少冗余，大量的广告页面和内容重复页面便是北京大学计算机科学技术系·网络与分布式系统实验室·孟涛·学士论文4此例。即使去除这些冗余后，用户感兴趣的网页通常也只是数以十亿计的数量中的极少数。因此，考虑搜集系统在质量上对网页的覆盖程度显得尤为重要。这一指标可以告诉我们，对那些用户会感兴趣的重要的网页，系统覆盖了其中的百分之几。从更深的层次来说，如果搜集系统覆盖了绝大多数的“重要”网页，它也就覆盖了当前社会信息在每一个重要主题上映射到上的部分，成为它的一个有效特征子集。类似于WebInfomall的系统如果将这些重要网页全部记录下来，以后就能通过历史网页回放来重现人类社会信息资源在时间和空间两维上的每一个角落。从信息的表现形式来看，搜集系统当前存储的信息中相当一部分日后将是不可见的。这一方面是由于存储系统的资源所限，未能搜集类似于图片影音之类的大文档；另一方面是因为搜集技术的不成熟，无法获得类似于JavaScript、Applet等格式的网页。因此，考察搜集系统对可视网上信息资源的覆盖率，也有着积极的意义。它可以告诉我们当前所搜集到的网页当中，多大比例的一部分能够在若干年后通过浏览器重新浏览。在本文的研究中，将对前面的两种进行详细的讨论和量化分析。2.3信息覆盖率评测模型我们定义搜集系统的信息覆盖率为它所收集的网页集合在中所占的比例。考虑到的链接结构，将其视为一张有向图G=（V，E），则搜集系统所获得的网页集合是G的强连通子图？？？（不一定是强连通图）G’=（V’，E’），每一个顶点都有唯一的标记URL。则信息覆盖率的表达式为：C=||||||'||VV需要加一句对公式的解释。G’的相关属性在搜集过程中已得到，但是因为搜索引擎搜集网页的不完全性，G的相关属性却只能去估计。为了得到准确的信息覆盖率数据，我们采取对取样的方法，即采取随机的方式从中获得一张子图0G=（V0，E0），考察V’中的顶点落在V0中所占V0的比例C0作为C的近似值。如果0G足够大或是随机性足够好,则C0非常接近于C。此时的C0即搜集系统的数量覆盖率。我们可以用类似的思想去计算搜集系统的质量覆盖率。考虑，我们可以用随机的办法获得某些重要网页组成的集合S作为样本，来考察搜集系统覆盖S中的子集S0所占样本容量的比例，作为近似的质量覆盖率Ci,因此质量覆盖率的表达式为：（为什么用双竖线？）Ci=||S||||||0S因此，我们需要通过对随机取样获得网页样本；需要采取某些方法得到随机的重要网页集合，这通常要利用网页之间的链接关系来对网页进行权值估算；在得到网页样本之后，再检查搜集系统的网页覆盖其中的比例，在检查过程中，必须对网页过滤，扔掉无法连接到的网页。总体的工作流程大致如下图所示：北京大学计算机科学技术系·网络与分布式系统实验室·孟涛·学士论文53数量覆盖率我们可以从不同的角度来对来进行采样。如果不考虑顶点之间的链接关系，仅从顶点的标记URL所对应的IP地址出发，可以采取随机产生IP的方法来获得一个网页集合，从而得到样本，这种考虑基于全局的视点；如果考虑到顶点之间的链接关系，则可以模仿搜索引擎搜集系统的工作方式，采取绝对广度优先的办法，从某一个顶点（种子URL）出发，逐渐扩展遍历，得到一个网页集合作为样本，这是一种从局部来进行取样的办法。3.1随机IP法在EdwardT.O’Neil和和PatrickD.M的工作[13]中，他们提出了通过随机产生IP来对进行取样的方法。首先获得地址，假设共有M个。可以利用IP的分段将它们一一映射到0到M-1之间的某个整数作为唯一标记。这样，我们可以利用随机算法产生小于M的整数，得到一个IP标记集合，再逆映射回到IP地址，即得到一组随机IP样本。如果搜集系统以域名标志网站地址，还需要将其转换为域名。这种取样原理如图3所示：3.1.1取样我们在研究工作中获得了中国国内已分配的所有IP地址分段4322个，例如162.105.0.0至162.105.255.25