搜索引擎信息覆盖率评测模型研究报告doc.doc

搜索引擎的信息覆盖率评测模型研究孟涛 李晓明 闫宏飞大学计算机科学技术系 ，100871摘 要 本文从有向图构造出发，总结分析了搜索引擎搜集子系统网页搜集不完全性的假设干因素，指出信息覆盖率这一概念的研究意义，由此提出了三类比拟重要的信息覆盖率概念在对信息覆盖率建立量化研究模型之后，本文以北大天网WebInfomall平台为考察对象，以不同的方式对中国Web进展取样，用PageRank和HITS这两类典型的权值算法计算出其中的重要网页作为样本，从量和质的角度上考察webinfomall的信息覆盖率，得到合理的数量覆盖率和质量覆盖率实验数据，从而验证了WebInfomall信息覆盖率结论的合理性和信息覆盖率评测模型的可靠性关键词 搜索引擎，信息覆盖率，取样，权值计算，验证，数量覆盖率，质量覆盖率1 研究背景〔World Wide Web〕自1989年诞生并于次年开场运行以来,在迄今为止的十多年里开展迅猛，已逐渐成为人类社会信息资源中的一个重要组成局部它以超文本和超媒体为核心技术，将文本、图形、图像、音频和视频等信息有机结合起来，给人们以丰富的信息表示空间随着Internet技术和应用的不断开展，社会的信息化进程不断加快，越来越多的社会信息资源开场选择Web作为其载体。

当前，上大约有8,745,000个，约2,500,000,000网页，包含了至少19TB以上的数据，而且这些网页正以每天净增7,500,000的速度膨胀[1] [2]而在中国，根据中国互联网络中心〔NIC〕于2002年1月进展的互联网统计报告[3]，下注册的域名数为127,319个，共有277,100个Web站点到2002年为止，中国境内的Web站点共有53,432,598个网页，主要分布在约49,146个中[4]面对浩瀚的互联网络资源，人们假设不借助其他工具很难快速的查找到自己所需要的信息，这带来了搜索引擎的诞生从1994年诞生的第一代搜索引擎Lycos和InfoSeek等开场，开展到当前流行的Google、Altavista等系统，它们已逐渐成为人们进展网际冲浪的重要工具之一根据弗吉尼亚理工大学GVU中心的调查报告[5] ，全世界有84.8%的用户通过搜索引擎获得自己所需网页，足见搜索引擎功用之一斑我们将每一条独立的信息称为一个网页，它有一个唯一的资源定位地址称为URL(Uniform Resource Location)搜索引擎便是利用URL之间的连接关系，搜集其对应的网页信息，建立索引，供用户查询。

因此，搜索引擎搜集的网页集合便是用户所能得到查询结果的最大范围；这个范围越接近，搜索引擎越优秀事实上，没有任何一个搜索引擎能搜集完的所有网页著名的搜索引擎Google系统和WiseNut系统，搜集到并提供应用户查询的网页数量分别是2,073,418,204个[6]和1,571,413,207[7]个，最多不过静态网页总数的80%而根据Greg R.Notes在200.年3月发表的搜索引擎统计数据[8]..，这两个系统的网页数据量是最大的网络上的信息数量巨大而且种类繁多，任何一个实际运行的搜集系统都不可能将其全部搜尽优秀的搜索引擎总会搜集尽量多的网页，更好的满足用户的查询要求考察搜索引擎对信息资源的搜集覆盖程度，可作为不断改良搜集系统的根据，对评价搜索引擎的性能好坏具有积极的作用另一方面，随着社会信息化程度的不断提高，将是该阶段人类社会信息资源在网络上的投影，记录着人类社会的历史开展进程基于搜索引擎技术开发的网络信息博物馆正以此为目的，力图通过搜索引擎的网页搜集系统不断搜集上的所有网页，假设干年后能够同时在时间和空间上展示的每一个角落因此，研究搜索引擎的信息覆盖率对验证网络信息博物馆网页资源的有效性也有着十分重大的意义。

本文的研究工作基于上述目的，针对大学计算机系网络与分布式系统实验室开发的搜索引擎[8]及以此为根底开发的网上信息博物馆WebInfomall[9]，采取多种方法从多个角度计算其信息覆盖率，证明了该网页搜集系统获得的中国网络信息资源是根本有效的2 模型概述2.1 网页搜集的不完全性如果把中的每一个网页看作一个顶点，则这个顶点以URL作为它的唯一标记；又由于网页中存在其它网页的URL，可以把这种网页间的看作连接顶点的边，则整个构成了一张有向图，如图1示相应的，每一个顶点的入度和出度对应着链向该网页的网页数量和该网页链向其他网页的数量显然，这是一张不完全图，因为里面存在很多入度或出度为0的顶点当前的网页搜集系统都是基于对这种构造的理解，依据网页之间的关系，从*一个种子URL开场，不断的从新搜到的网页中提取出URL，从而到达其它的网页搜集过程中，通常需要对网页重要性作初步的判断，优先搜集相对有价值的网页在这种搜集机制里面，存在着以下问题，导致无法遍历所有的网页l 局部网页的入度为0，即从任何一个网页开场，都不存在到它的路径，这类网页的数量约占全体网页数量的10%[10] l 选择的种子URL集合中，任何一个网页都不存在到该网页的路径。

中的有向图构造中，只有约21.3%的顶点能被选取作为起始点去遍历剩下的约90%的顶点[10]l 由于在网页搜集的过程中出现了优先排序，搜集系统资源本身的限制〔磁盘容量和时间限量〕导致局部网页直到搜集过程中止都没有被搜集，出现Starve的情况[11]l 本身处于不断的膨胀过程之中，大量新出现的网页来不及搜集搜集系统自身一般都有搜集周期，而*些网页〔如实时新闻网页〕的更新频率远大于搜集频率l 从广义的角度而言，但凡上的信息都应该被搜集，而现在的搜索引擎一般只搜集了局部格式的网页信息当前搜集的一般都是静态网页中类似于HTML文档的信息资源，没有考虑到包括动态网页在内的巨量深层网络文档据估计，当前中的所有网页〔包括深层网页〕约有5500亿之多，搜索引擎所覆盖的不到其百分之一[12]！因此，可以肯定任何一个实际运行的网页搜集系统都不可能将当前中的所有网页全部抓尽这种搜集性能越优异，意味着它所获得网页集合在数量和质量上越接近于实际的，网页之间的关系也越逼近实际的有向图构造搜索引擎的信息覆盖率正是对这种接近程度的衡量，它表达了一个网页搜集系统所获得的网页集合及关系所占实际的比例2.2 几类重要的覆盖率广义的信息资源，应该定义为互联网上的一切信息，即所有存在于上的文档。

这些文档有些能通过浏览器浏览，有些则不能；有些存在于的数据库中，经过动态的请求方能生成，有些则是静态存在的且被其它网页到搜索引擎当前所能搜集的绝大多数就是这种静态的网页，且在处理过程中进一步过滤掉了*些不可浏览的局部如可执行文件等在这里，我们所研究的搜集系统覆盖目标是上的所有静态网页，它们通常可通过浏览器显示内容，且其URL一般静态存在于其它网页中我们可以从多个角度来考虑搜索引擎对信息资源的覆盖程度搜集系统应该力图遍历的所有网页，在数量这一角度上到达完全覆盖的程度这提供一个衡量搜集系统覆盖信息能力的全局标准例如当前上的网页估计约为2,500,000,000个[2] ，Google系统的网页搜集数量是2,073,418,204个[6] ，因此可以估计其数量覆盖率为百分之八十左右如果系统的数量覆盖率足够高，我们就可以认为它根本上覆盖了上的所有信息资源高的数量覆盖率应该是任何一个搜集系统及以此为根底的网上信息博物馆的首要目标网上信息资源极为丰富，但也存在不少冗余，大量的广告页面和内容重复页面便是此例即使去除这些冗余后，用户感兴趣的网页通常也只是数以十亿计的数量中的极少数因此，考虑搜集系统在质量上对网页的覆盖程度显得尤为重要。

这一指标可以告诉我们，对那些用户会感兴趣的重要的网页，系统覆盖了其中的百分之几从更深的层次来说，如果搜集系统覆盖了绝大多数的"重要〞网页，它也就覆盖了当前社会信息在每一个重要主题上映射到上的局部，成为它的一个有效特征子集类似于WebInfomall的系统如果将这些重要网页全部记录下来，以后就能通过历史网页回放来重现人类社会信息资源在时间和空间两维上的每一个角落从信息的表现形式来看，搜集系统当前存储的信息中相当一局部日后将是不可见的这一方面是由于存储系统的资源所限，未能搜集类似于图片影音之类的大文档；另一方面是因为搜集技术的不成熟，无法获得类似于JavaScript、Applet等格式的网页因此，考察搜集系统对可视网上信息资源的覆盖率，也有着积极的意义它可以告诉我们当前所搜集到的网页当中，多大比例的一局部能够在假设干年后通过浏览器重新浏览在本文的研究中，将对前面的两种进展详细的讨论和量化分析2.3 信息覆盖率评测模型我们定义搜集系统的信息覆盖率为它所收集的网页集合在中所占的比例考虑到的构造，将其视为一张有向图G=〔V ，E〕，则搜集系统所获得的网页集合是G的强连通子图...〔不一定是强连通图〕G’=〔V’，E’〕，每一个顶点都有唯一的标记URL。

则信息覆盖率的表达式为：C=需要加一句对公式的解释G’的相关属性在搜集过程中已得到，但是因为搜索引擎搜集网页的不完全性，G的相关属性却只能去估计为了得到准确的信息覆盖率数据，我们采取对取样的方法，即采取随机的方式从中获得一张子图=〔V，E〕，考察V’中的顶点落在V中所占V的比例C作为C的近似值如果足够大或是随机性足够好,则C非常接近于C此时的C即搜集系统的数量覆盖率我们可以用类似的思想去计算搜集系统的质量覆盖率考虑中的所有重要网页构成的连通子图G，我们可以用随机的方法获得*些重要网页组成的集合S作为样本，来考察搜集系统覆盖S中的子集S所占样本容量的比例，作为近似的质量覆盖率C,因此质量覆盖率的表达式为：〔为什么用双竖线.〕C=因此，我们需要通过对随机取样获得网页样本；需要采取*些方法得到随机的重要网页集合，这通常要利用网页之间的关系来对网页进展权值估算；在得到网页样本之后，再检查搜集系统的网页覆盖其中的比例，在检查过程中，必须对网页过滤，扔掉无法连接到的网页总体的工作流程大致如以下图所示：3 数量覆盖率我们可以从不同的角度来对来进展采样如果不考虑顶点之间的关系，仅从顶点的标记URL所对应的IP地址出发，可以采取随机产生IP的方法来获得一个网页集合，从而得到样本，这种考虑基于全局的视点；如果考虑到顶点之间的关系，则可以模仿搜索引擎搜集系统的工作方式，采取绝对广度优先的方法，从*一个顶点〔种子URL〕出发，逐渐扩展遍历，得到一个网页集合作为样本，这是一种从局部来进展取样的方法。

3.1 随机IP法在Edward T.O’Neil和和 Patrick D.M的工作[13]中，他们提出了通过随机产生IP来对进展取样的方法首先获得上已经分配使用的所有IP地址，假设共有M个可以利用IP的分段将它们一一映射到0到M-1之间的*个整数作为唯一标记这样，我们可以利用随机算法产生小于M的整数，得到一个IP标记集合，再逆映射回到IP地址，即得到一组随机IP样本如果搜集系统以域名标志地址，还需要将其转换为域名这种取样原理如图3所示：3.1.1取样我们在研究工作中获得了中国国内已分配的所有IP地址分段4322个，例如162.105.0.0至162.105.255.255为其中一个分段，被分配给大学使用如果统一用点分十进制表示所有网络地址，则所有的IP分段可以表示如下èA1’.B1’.C1’.D1’èA2’.B2’.C2’.D2’……An.Bn..DnèAn’.Bn’.’.Dn’èAt’.Bt’.Ct’.Dt’中〕的函数值为：F(a.b.c.d)=+〔a-At〕*+(b-Bt)*+ (c-Ct)*+ (d-Dt)于是我们将每一个IP都对应到一个整数，便可以用随机算法在其中选取假设干，逆映射转变为I。