在不少冗余，大量的广告页面和内容重复页面便是此例。即使去除这些冗余后，用户感兴趣的网页通常也只是数以十亿计的数量中的极少数。因此，考虑搜集系统在质量上对网页的覆盖程度显得尤为重要。这指标可以告诉我们，对那些用户会感兴趣的重要的网页，系统覆盖了其中的百分之几。从更深的层次来说，如果搜集系统覆盖了绝大多数的重要网页，它也就覆盖了当前社会信息在每个重要主题上映射到上的部分，成为它的个有效特征子集。类似于的系统如果将这些重要网页全部记录下来，以后就能通过历史网页回放来重现人类社会信息资源在时间和空间两维上的每个角落。从信息的表现形式来看，搜集系统当前存储的信息中相当部分日后将是不可见的。这方面是由于存储系统的资源所限，未能搜集类似于图片影音之类的大文档另方面是因为搜集技术的不成熟，无法获得类似于等格式的网页。因此，考察搜集系统对可视网上信息资源的覆盖率，也有着积极的意义。它可以告诉我们当前所搜集到的网页当中，多大比例的部分能够在若干年后通过浏览器重新浏览。在本文的研究中，将对前面的两种进行详细的讨论和量化分析。信息覆盖率评测模型我们定义搜集系统的信息覆盖率为它所收集的网页集合在中所占的比例。考虑到的链接结构，将其视为张有向图则搜集系统所获得的网页集合是的强连通子图不定是强连通图每个顶点都有唯的标记。则信息覆盖率的表达式为需要加句对公式的解释。的相关属性在搜集过程中已得到，但是因为搜索引擎搜集网页的不完全性，的相关属性却只能去估计。为了得到准确的信息覆盖率数据，我们采取对取样的方法，即采取随机的方式从中获得张子图考察中的顶点落在中所占的比例作为的近似值。如果足够大或是随机性足够好,则非常接近于。此时的即搜集系统的数量覆盖率。我们可以用类似的思想去计算搜集系统的质量覆盖率。考虑中的所有重要网页构成的连通子图，我们可以用随机的办法获得些重要网页组成的集合作为样本，来考察搜集系统覆盖中的子集所占样本容量的比例，作为近似的质量覆盖率,因此质量覆盖率的表达式为为什么用双竖线因此，我们需要通过对随机取样获得网页样本需要采取些方法得到随机的重要网页集合，这通常要利用网页之间的链接关系来对网页进行权值估算在得到网页样本之后，再检查搜集系统的网页覆盖其中的比例，在检查过程中，必须对网页过滤，扔掉无法连接到的网页。总体的工作流程大致如下图所示数量覆盖率我们可以从不同的角度来对来进行采样。如果不考虑顶点之间的链接关系，仅从顶点的标记所对应的地址出发，可以采取随机产生的方法来获得个网页集合，从而得到样本，这种考虑基于全局的视点如果考虑到顶点之间的链接关系，则可以模仿搜索引擎搜集系统的工作方式，采取绝对广度优先的办法，从个顶点种子出发，逐渐扩展遍历，得到个网页集合作为样本，这是种从局部来进行取样的办法。随机法在和和的工作中，他们提出了通过随机产生来对进行取样的方法。首先获得上已经分配使用的所有地址，假设共有个。可以利用的分段将它们映射到到之间的个整数作为唯标记。这样，我们可以利用随机算法产生小于的整数，得到个标记集合，再逆映射回到地址，即得到组随机样本。如果搜集系统以域名标志网站地址，还需要将其转换为域名。这种取样原理如图所示取样我们在研究工作中获得了中国国内已分配的所有地址分段个，例如至为其中个分段，被分配给北京大学使用。如果统用点分十进制表示所有网络地址，则所有的分段可以表示如下其中，和都为到之间的整数。可见这些分段不相交，统计出每个分段中的地址数量，则可以找到映射使得地址位于中的函数值为于是我们将每个都对应到个整数，便可以用随机算法在其中选取若干，逆映射转变为地址，便得到个地址集合。去掉此集合中不提供服务包括与网络无连接的元素，就得到了个网站样本。由于大约的网站通过端口提供服务，我们可以顺次扫描这些网络地址上的端口。得到的存在服务的地址集合经反向域名解析便可得到样本集合。通过对中国国内的进行随机取样并进行扫描，我们得到了如下结果编号随机数存在数表格中间线太粗，而且第三条应该是不可见的在上面的统计中，我们选取了多组不同数量的随机，得到的存在服务的地址数量与随机数大致成比例，说明选出的地址具有很好的随机性。验证由于搜集系统般以包含域名的来记录网页，我们要检验这些网页是否已被覆盖，应该将其转化算法上图中的正是我们用算法进行权值计算的对象。对于中的任意个元素，设表示其目录型权值，表示其权威型权值是链到的网页是从链出的网页，则和可以从下面的式子计算同算法类似，我们可以将所有的网页的目录型权值看作矢量，将所有网页的权威型权值看作矢量，设样本中所有网页及链接关系构成的有向图的邻接矩阵为，考虑到两个之间最多有个链接使得若存在网页到网页的链接则,否则那么上面的式子可以写成由此两式可得，即实际上是的特征向量同理是的特征向量，我们因此也可以用幂法或算法等来通过迭代来求得和的值。但考虑到系统内存对初始样本容量的限制，若数量很大的时候需要分块对两个矩阵进行迭代。试验结果在我们的研究工作中，我们没有通过计算特征向量而采取了根据前组公式直接进行迭代计算和值的办法，具体的实现算法如下采集初始样本时将所有的编号存入数据库，同时存入之间的链接关系创建相关的数据结构存储每个的和权值及链接关系，从数据库中导出所有属性并填充到数据结构中给予和个初始值，分别计算和，直至和的距离足够小为止分别对和值进行冒泡排序，输出前若干个到文件中。在确定重要网页的界限时，我们选取的是初始网页样本中权值排在前面约左右的部分，大致与搜索引擎响应查询词返回的网页数量相当。即搜索引擎就此主题返回个重要网页，我们经过计算后也给出个真正重要的网页，检查搜集系统覆盖其中的比例作为质量覆盖率。对于具有较高权值的重要网页，实验的数据如下样本编组查询词北京大学考研股票江泽民教程联想集团三个代表世界杯初始数量取数覆盖数量覆盖率八组样本所得的质量覆盖率分别为表几所示，它们的均值和方差分别为和，前者即为搜集系统对型重要网页的覆盖率。对于具有较高权值的重要网页，实验的数据如下样本编组查询词北京大学考研股票江泽民教程联想集团三个代表世界杯初始数量取数覆盖数量覆盖率八组样本所得的质量覆盖率分别为，它们的均值为，表几所示方差为和，前者即为搜集系统对型重要网页的质量覆盖率。修正与分析在上述的算法中，我们将所有链接的地位视为平等，而事实上并非如此，我们可以从它的导向词与查询词的匹配度的不同处着手，这在和的工作中有论述。这里的导向词指的是该链接出现在网页源文件的地方前后约个字符之内的信息，它们般含有该链接网页内容或属性的说明。即，个网页中两个链接和，如果的导向词中出现北京大学次，而的导向词中未出现此字眼，在查询的主题是北京大学时，的地位要高于。我们称以此为基础的算法为扩展算法。假定查询词是，存在网页到的链接，提取出网页中的导向词，设,为在导向词中匹配的次数，则可以对算法作如下修正,,我们用这种算法对上述的组初始样本进行计算，然后分别选取权值和权值在前若干位的重要网页作为重要网页样本，从和两个角度求得的搜集系统信息质量覆盖率均值分别为和。从实验数据可以看出，广度优先法和主题查询法所求得的质量覆盖率数据能够很好的符合，的搜集系统对普通的重要网页覆盖率在左右。如果对重要网页的标准提高些，则质量覆盖率的数据还要更高。结论本文针对搜索引擎搜集子系统对的信息覆盖能力，创建了信息覆盖率的量化研究模型。在这个模型中，我们提出两套取样办法，采取了两类典型的网页权值算法，分别从量和质的角度上分析计算搜集系统的信息覆盖率。运用这个模型，我们针对中国进行样本采集，从而对北大天网系统的平台所存储的中国国内网页数据的信息覆盖率进行评估。得到的数据显示，在数量上平台覆盖了中国国内网页总数的，而在质量上覆盖了重要网页总数的左右。这个数据也显示天网的覆盖率与国际上诸如的几个大搜索引擎系统相当，尤其是在数量覆盖率这方面。对于同类型的信息覆盖率，采用不同取样和权值计算方法所验证得到的数据能够很好的符合，证明了信息覆盖率模型的正确性以及所获得平台信息覆盖率的准确性。实验结果肯定了天网搜集系统的较强搜集能力，并对进步改进这种搜集能力及相关平台的性能提供了重要的客观依据。本文不足之处在于对网页重要性的定性标准不够严密，对于算法，我们选取了权值位于前的网页作为重要网页而对于算法计算的查询所得扩展网页集合，我们选取重要的标准是和初始返回结果相等的量，约占权值排序后前面的如文中所述，在实验中通过对其中两组样本改变重要性标准，我们得到了不同的质量覆盖率，这也是对上述不足的些修正。在未来的工作中，我们可以加大各组信息覆盖率评测方法中样本的容量和样本组数，从而能够得到更准确的覆盖率数据，减小误差。另外，以此为基础，研究搜集系统对可视信息的覆盖率也将具有积极的意义。参考文献,中国互联网络信息中心，第九次中国互联网络发展状况统计报告阎宏飞，李晓明，关于中国的大小形状和结构搜索引擎的信息覆盖率评测模型研究孟涛李晓明闫宏飞北京大学计算机科学技术系，摘要本文从有向图结构出发，总结分析了搜索引擎搜集子系统网页搜集不完全性的若干因素，指出信息覆盖率这概念的研究意义，由此提出了三类比较重要的信息覆盖率概念。在对信息覆盖率建立量化研究模型之后，本文以北大天网平台为考察对象，以不同的方式对中国进行取样，用和这两类典型的权值算法计算出其中的重要网页作为样本，从量和质的角度上考察的信息覆盖率，得到合理的数量覆盖率和质量覆盖率实验数据，从而验证了信息覆盖率结论的合理性和信息覆盖率评测模型的可靠性。关键词搜索引擎，信息覆盖率，取样，权值计算，验证，数量覆盖率，质量覆盖率研究背景自年诞生并于次年开始运行以来,在迄今为止的十多年里发展迅猛，已逐渐成为人类社会信息资源中的个重要组成部分。它以超文本和超媒体为核心技术，将文本图形图像音频和视频等信息有机结合起来，给人们以丰富的信息表示空间。随着技术和应用的不断发展，社会的信息化进程不断加快，越来越多的社会信息资源开始选择作为其载体。当前，上大约有个网站，约,网页，包含了至少以上的数据，而且这些网页正以每天净增的速度膨胀。而在中国，根据中