【毕业学位论文】（Word原稿）海量Web信息搜集系统优化设计-计算机系网络与分布式系统

1 海量 息搜集系统 优化设计 2 论 文 摘 要 本文首先由 起源和发展导出搜索引擎技术的出现和发展。北大天网是这类技术在中国的最早的成功产品之一，本文将大体介绍其体系结构和技术特点。 搜集端（ 天网的主要模块之一，它的搜索速度、获取网页质量是评价搜索引擎好坏的主要指标，是检索端的工作的基石。如何更快，更好的抓取网页是本人毕业设计的工作目标。在介绍完搜集端现有的体系结构之后，本文从搜索导向、相似网页、相关度权值给定三个方面阐述它的优化 策略，作为本文的重点。 最后，本文试图指出现有系统的处理能力极限和瓶颈，并在此基础上作新的体系结构的探讨。 关键词： 搜索导向 ， 3 第一章 背景介绍 源于 1989 年欧洲粒子物理研究室 ( 物理学家 1989 年 3 月提出的，第一个原型（基于文本）于 18 个月后运行。 核心技术是超文本和超媒体。通过将文本、图形、图象、音频、视频等信息的有机结合，给人们提供了丰富的信息表示空间。在十多年的时间里，信息容量巨增，根据 究院在自然上发布的数据 3，截止到1999 年 2 月， 共有网站 ，其中公开提供 务的网站280 万个；共有 页大约 8 亿页，这些网页包含了 15T 字节的数据。按照 2000 年 4 月在波士顿举行的第 5 届搜索引擎年会的会议报告 4，我们可以知道现今的网页数目已经超过了 10 亿页。 1994 年登陆中国，在到现在仅仅 6 年的时间里发展速度惊人。根据国互联网络信息中心 )在 2000 年 1 月的统计信息表明 5，中国已有上网计算机 350 万台，其中 点 15153 个；上网人数 890 万。关于网页的数目没有具体的统计数据，但根据科学杂志上提供的集合估计法 2，通过中国几个主要搜索引擎获得的搜索数据（天网、新浪、搜狐、网易），我们可以估计到当前中国拥有的网页数已经超过 1000 万页。 索引擎的出现和发展 面对浩瀚的 息资源，用户在感到进入信息社会的兴奋之后，立刻觉得不知所措 ，太多的信息使我们很难迅速定位我们真正需要的信息，而跟随超链在 漫游则会浪费大量的时间，而且很可能徒劳无功。因此，人们迫切需要有效的信息发现工具来为他们在 进行导航。 在 1994 年，第一代搜索引擎出现了，例如 时，它们还处在研究阶段，数据量少，检索速度慢是它们的突出缺点。最近这几年里，搜索引擎技术有突飞猛进的发展，出现了 成熟的搜索引擎产品，它们日趋变的好用，成为 户必不可少的工具之一。 “北大天网 ( 是 “九五”攻关项目“计算机信息网络及其应用关键技术研究”中设立了“中文编码和分布式中英文信息发现”子专题，北京大学网络研究室承担了该子专题的部分研究开发工作，设计开发了“天网”中英文搜索引擎（ 3。 1997 年 10 月 29 日，天网搜索引擎正式在 提供查询服务。软件世界（ 1998 年 7 月）将天网评为 国内最值得关注的搜索引擎， 1998 年 12 月，天网通过了 鉴定。之后，天网又进行了大量的技术创新和系统的完善。到目前为止，天网总访问量已经突破5,000,000，并且仍以每天大于 30,000 的访问量递增。 4 第二章 系统概述 天网 ”体系结构简介 天网搜索引擎 由两个主要部分组成 ,分别是搜索端和检索端 搜索端从 抓取网页，经过分析提取出必要的信息存放到数据库中去（天网目前使用的是 据库），当数据库完成一次更新后检索端便可依据数据库集端 搜集 数据库 数据库 分析器 检索端检索数据库 图 索引擎总框架 图 集端结构 5 中存放的信息对用户 的检索请求做出答复了，也就是把用户想要的网页例出。从检索的效率上考虑（数据库往往把功能作得很完善，我们宁可扔掉一部分于我们无用的功能，来换取高速的读取），搜集端不是直接从 据库中读取信息，而是从由数据库生成的中间文件中读取信息的。结构如图 本文讨论的搜集端的各部分组件及其功能如图 搜集端按如下方式工作，先由主控启动多个 程 ,并给它们逐一分配一个网上的 它们负责去网上抓取网页。 取得的网页进行分析，把结果送给主控，由主控对数据库进行操作，主控可 以从 来的结果中获得新的 分配给 于网络有时可能不能正常工作， 自己在某一时刻的工作状态纪录在共享内存里面， 程负责巡视共享内存，处理 到的各种问题，改进程为什么被称作 是因为当它发现有程由于一些网络上的原因不能正常工作时（如分配的 存在，我们称之为“死链”），由他结束该 本次任务，分配新的任务后重新开始。为了协调网络速度和 理能力的差异 ,在一台主机上启动多个 且目可以调节。 术特点 搜索引擎最早只针对于对西文，西文（如英文，法文）又一个特点是，有天然的分割语义的最小单位 词的分割符 （空格），而中文词与词之间没有空格。在现代汉语中，大部分的词都是双字节、多字节词，其中单个字的意思与整个词的意思相差甚远，尤其对大量涌入的音译外来词，如因特尔，迪士高，麦当劳等，单个字与整个词的意思基本一点关系都没有。既然词是表达意思的最小单位，“天网”通过一些切词程序，把词从网页中提取出来，网页信息以词的形式被储存。在处理用户查询时，也从词的角度对用户 输入作某种理解，再去数据库中查找。这些词被称为关键词，要求能反映文章的内容。现代汉语词类有名词、时间词、方位词、数词、量词，代词、动词、形容词、副词、介词、连词、助词、拟声词，成语等等 这些词中，助词、连词、介词等词类是不具有这种功能的，一大堆的“但是”、“虽然”、“的”、“呢”、“最”是不能让我们猜出文章的任何内容的。这些词不能代表文章的内容，却在文章中以极高的词频出现。我们把它们叫做“ 在提取关键词时把这些词滤掉。 这一点是“天网”的基本特点，也是本文将要提到的基于关键词的 “相似网页发现算法”的基础。 6 第三章 搜索导向策略探索（ 5 页） 源与目标 搜索引擎从一个（也可以是一组）起始 始，当完成这个网页 获取与分析后，它能从 提取所有出现的超链（ ,这些新的 插入到一个备搜索的 列里面去。搜索引擎以某种 顺序 从队列里面取出复前面的过程。决定这种顺序，我们称之为“搜索导向”。显而易见的提议是，先搜索最“重要”的。当我们的搜索引擎受到时间和存储空间的制约，而不能覆盖整个网落时，快速的获得“重要”的网页是非常 有用的。这一项工作几年前 人作过，他们在斯坦福大学的校园网上作了实验，对比采取导向与不采取导向搜索引擎的效果。他们最终的结果是，采用了导向机制的搜索引擎比不采用的获得“重要”网页的速度要快得多。 首先，我们需要一定的尺度去描述“重要”。由于某一篇网页是否“重要”就是由用户“主观”评价的，各种各样的用户有各种各样的需求，你不可能完全懂得用户想要什么东西，因此这个尺度不是绝对的。因此，我们后面的广义的评价网页“重要”程度的方法有某种尝试、探讨的性质。强调用户的各种需求，把搜索引擎做成针 对各个专业的，或提供分类检索，成为搜索引擎的发展方向之一。 何搜索导向 如图 的网页通过超链指向其他网页，也被其他网页的超链所指向，于是 成了一张巨大的有向图。搜索引擎在网上搜索就是一个遍历有向图的过程。对于有向图的遍历，有深度优先和广度优先两种常用方法。 当使用深度优先策略时，搜索引擎总是先搜集离初始网页距离较近的网页，这样网页搜集的质量严重依赖于初始网页的选取。 当使用深度优先的导向算法时，我们发现在网页之间的链接有这样的特点，三个站点 A， B， C （ 大圆圈表示），它们都包含了大量的网页（小圆圈表示）。存在一些超链，从一个站点中的网页指向另一个站点中的网页。但A,B,C 之间的超链远远少于指向本站点网页的网页。从北大的主站点上就可以明显的看到这种情况。在 大主页存在 68 个超链，全部指向站内网页。站点内的其他网页网页也很少有指向 站 外 的 超 链 ， 唯 一 例 外 的 是 一 篇 网 络 导 航 的 网 页 （ ），其 中含有大量的指向其他站点主页的超链。面对这种情况，如果使用深度优先策略，当搜索程序进入站点 A 时，通常是要把 中撤出。这样对目前国内的 15153 个站点图 网页的链状结构 A C D B 7 （ 000 年 1 月统计信息），天网只能搜索其中十分之一，只是非常不好的。于是我们必须采取另外的策略进行搜索导向。我们选取一些关于网页的参数，通过这些参数的大小来对网页排序决定访问的先后。参数选取的好坏直接关系到我们能不能在“天网”有限的容量里囊括所 有被用户所关心的，“重要”的网页。 我们以后的工作基于这样一个假定：通过天网 检索系统访问的越多的 户对它的倾向性就越强，我们就认为它越重要。 每一片网页被访问的次数是通过统计 天网检索端 运行一段时间的对用户查询纪录的日志得到的。由于网页在不断更新，我们在第二次搜索时，并不知道那些网页将被访问多少次，也就是说对新出现的网页，利用网页被访问次数来进行搜索导向是不可能的。于是，我们就想通过一些在搜索前或搜索中能得到的，与被访问次数有良好的正比（或反比）关系的参数来进行搜索导向。这些参数的选取、评价在以后两节有详细的讨论。 向参数选取 通过对 息组织结构的分 析，我们对下面几个参数作了考虑： 1 网页入度。 网页中出现的超链（ 成是由一个网页指向另一个网页的一条有向边，网页本身就是一个节点，这样整个 构成了一张巨大无比的有向图。可以用入度函数 I(P)来表示整个网络指向网页 P 的超链的数目。我们假设，一个网页如果被大量的其他网页链接，它就比另一个很少被链接的网页 要 重 要 。 看 上 去 是 这 样 ， 例 如 ： 1 、+编程技术的目录网页，还有其他一些书籍的目录网页经常被其他网页链接，这种网页对用户获取更多的信息是非常有用的，因此它们是很重要。 2、一些娱乐网站，提供视频点播，声讯服务等功能，也被大量的网页链接着。 3、政府部门的一些网页，象 （关于西部大开 发的宣传网页），被大量链接。 4、商业网站主页之间存在着大量的链接，主页被链接图 站间网页的链接 8 得多少，反映了商业网站的影响力。总之，只有当其他网页的编辑者认为此网页重要时，才会在他们所编辑的网页中加入指向此网页的超链。与国外的一些文章一样，我们认为网页入度最有可能被选作导向参数。 2 网页的镜像数目。 对于一则新闻，我们常常用“被多家报刊杂志转载”来形容它的被关注程度。对于网 上的各种信息，如新闻、文学作品、技术文档等，如果它真的被大量网民所关注的话，就会有很多网站把这篇网页拷贝过来，也许会略加改动。这种拷贝网页我们称之为“镜像 ”。 3 域名深度与目录深度。 域名和目录都是人们用层次结构组织信息的一种方式。网页处在这种层次结构中的深浅是否与人们对它的关心程度有某种联系？联系是什么？ 于是我们把上面三个数据作为我们研究的目标，试图发现它们与网页的最终被访问次数的关系。 验过程与结果 在 2000 年四月上旬，“天网”搜集了 1,000,000 国内网页，这 1,000,000 网页立刻作为新的数据对外提供服务。在随后的天时间里，有 141779 篇网页通过“天网”的引导被访问，总访问次数为 400641。哪些网页被访问，访问了多少次都通 过系统运行日志被记录了下来。这些信息被我们组织、统计、分析。 首先，一百万量级的数据如何在内存中组织、运算，对我们来说是一种挑战。对于单一网页，我们需要组织的信息有：网页的地址（ 128 长度字符串）、网页的入度 (网页被访问的次数 (这些信息被组织成结构(需要空间 149 字节。 成员数据 所占空间及类型 入度 4 字节 ,整数 被访问次数 4 字节 ,整数 原始 29 字节 ,字符串 散列表中的结构指针 4 字节 ,整数 访问 点的 指针 4 字节 ,整数 访问镜像网页的指针 4 字节 ,整数 成员数据 所占空间及类型 名 16 个字节，字符串 镜像数 4 字节，无符号整数 所有镜像的总访问数 4 字节，无符号整数 所有镜像的总入度 4 字节，无符号整数 所有镜像的平均目录深度 4 字节，单精浮点数 指向第一个镜像的指针 4 字节，无符号整数 散列表中下一节点的指针 4 字节，无符号整数 为了找出该网页有多少个镜像，我们采用对网页的摘要求 名的方法，记录 结构 录一组镜像的结构 9 即若两篇网页的摘要完全相同，我们就认为它们是相同的。这种方法不是最好的方 法，找出更好的发现镜像网页算法是下一章讨论的主题。对于一组镜像，我们用另一个结构 行组织 ,占用空间 40 个字节。 在实验过程中有这样的需求 ,对某一个 分别是谁。我们通过的 的 成这样的结构，如图 由于出现了对百万量级的数据进行随机访问，我们对 使用散列表来组织，散列表采用拉链法，由一个整数数组坐表头，另用一个数组作数据区。对 散列表结构如图， 成员 数据 类型 散列表表头 整数数组 可用空间指针 无符号整数 数据区 组 在 散列表中 ,我们会装入一百万个网页 ,因此其中 组的大小定为1,000,000。存取数据时对网页的地址（字符串 行散列，先把 成长度为 4 的若干短串，把这些短串放在一起作异或运算得到一个新串，这个长度为 4的新串被转化成一个无符号整数，整数模上散列表头的大小作为散列值。取一个靠近 2*数据项数目 的素数 1,999,993 作为表头数组长度。 对 散列结构类似， 成员数据 类型 散列表表头 整数数组 可用空间指针 无符号整数 数据区 组 名得到一个 16 字节长的字符串，重复同对 符串一样的操作，我们得到另一个散列函数， 的表项数同 的数目差不多，数据区数组的大小也定为 1,000,000 ,表头数组长度也为 1,999,993。 散列表 小约 42小约 157对如此巨大的数据块，普通的内存分配是无法胜任的，这里采用了文件映射的办法 (通过 。在象搜索引擎这种海量信息处理系统中，对空间的分配尤其需要注意，前面为散列表分配空间时，采用数组，而不是用 数动态分配 多次使用 数费时，且 配一小块空间 ,要占用比自身大得多的标识块首和块尾的附加空间，这在我们的系统中是不能忍受的。 我们的第一组数据是这样得到的，设 1， 000， 000 网页的被访问次数从大到小依次是 2,. . ,1000000 ，它们对应的网页入度为对 散列结构 对镜像网页的散列结构 图 3.3 关系 10 2,. . ,1000000 , 网页镜橡数为 2,.1,. . ,参照序列为 2,. .,其中 。参照序列对应对每一个 予同等重要度。 我们把数据作规格化，令 Vi = 到 V样的方法得到 Hi,Ci,Di,Si数列。 对 Hi,Ci,Di,Si求与 Vi的偏差平方和有： (Hi Vi)2 = (Di Vi)2 = (Ci Vi)2 = (Si Vi)2 = 一结果在我们的意外，尤其是我们认为网页入度最有可能与被访问次数相一致，以后可以用来做搜索导向的参数，但它与被访问次数的偏差平方和反而最大。这是为什么呢？通过对实际数据的分析，我们发现，与我们想的一样 ,国内有影响的网站的主页多获得了比 较高的入度，并且通过天网被多次访问，技术文档和书籍的目录网页也有类似的现象。这里举出两个网页： 1 ，拥有 36 个链接。 2 ，实际是书籍的目录网页，拥有 42 个链接。 我们发现，网站一般组织成类似树形的结构。如图 多数载有文章的网页（图 中的空心矩形），它们极少被外站的网页所链接，在本站一般也只被一个网页所链接。而主页（图中的椭圆），它们既有超链指向站外，也被站外网页所链接。图中的实心矩形是目录网页，如前面的 2，它们被站外网页所指向，但自己的超链不向外指。图中的三角为一些专门向外指的网站，常被命名为“网络导航”，“友情链接”之类。 所以图中空心矩阵代表的网页用其入度来评价“重要性”是失败的。这样的网页如果真的很重要的话，其他网站总是采用镜像的方法，而不是仅仅对它加一个链接。在上面的结果中，由于 身的方差大，所以导致 。在这一启发下，我们对一百万网页中一万多个主页重复求与访问次数偏差平方和的运算，得到： (Hi Vi)2 = (Di Vi)2 = (Ci Vi)2 = (Si Vi)2 = 页入度成为与用户访问次数相关度最好的网页。 对被访问了的网页，我们统计其入度、镜像度、目录深度的和，与对所有网图 内网页的树形结构 11 页的求得的总 数相比较。有， 总数 对被访问的部分求和 百分比 网页数 868357 131906 %度 2876462 589868 %像数 999999 160896 %度 6479796 947179 %后，把被访问的十多万网页按被访问次数排序，依次对每个网页把被访问数、入度、镜像数、目录深度分别在四张图上标出，得到了图 从图 上面的比例关系可以看出，被访问的网页入度、镜像度有大于平均数的趋势，而目录深度的变化不明显。从以上两组数据，我们得到的启发是：在搜索时，区分对待主页（包括目录网页）和普通网页，只对主页采取与入度相关的导向测略。前一类网页的特点是目录深度小，无文件名（如 缺省为 ,或文件名为 ？ 这样的网页对我们的搜索是非常有用 的，因为它们内部含有大量的超链，通过超链我们才能获得新的 是若目录重要的话，它里面的文章也应该重要。我们优先搜索“重要”的目录，载有“重要”的文章的 优先被提取，也就最有可能被先搜到。这样，我们搜索导向的目的就达到了。对一篇网页，在搜索正在进行时，我们用已搜部分网页对它的入度来模拟整个网络对它的入度，或采用上次搜索时得到的它的入度来模拟。 参数对被访问网页求和占总数比例 图 页入度 图 访问次数 图 像数 图 录深度 12 13 第四章 相似网页的发现与处理（ 8 页） 题的提出 我们可以把内容 上相似的网页称之为“镜像”，如果用过不消除镜像的搜索引擎的用户会发现， 实在有太多的镜像。被镜像的网页有这几类： 1 除开政府部门的法令、通告。 公安部颁布的 计算机信息网络国际联网安全保护管理办法 在国内的网站上有一百二十个镜像。 （据“天网”四月份统计） 2 重大新闻，热点新闻。中欧 七十五个镜像。 （据“天网”四月份统计） 3 技术文档。如： ) 有一百个镜像， 有九十个镜像。 4 提供一定服务的网站。 “黄金书屋”的镜像有三十个。 （据“天网”四月份统计） 这些镜像有的是没有一点改动的拷贝，有的在内容上稍作修改，比如同一文章的不同版本，一个新一点，一个老一点，有的则仅仅是网页的格式不同（如 这些镜像网页的出现，给网民带来了好处。重要网页可以有更多的机会被人们看到，并且在一些网络速度慢的地 区，人们可以从多个镜像中选择一个距离自己较近的网页进行访问。但是，对于一些要对网络资源进行存储的应用来说，过多的镜像浪费了大量的存储空间。网络上重复的信息比例达到了 20% 30%，如果能节省出这一部分空间，是非常诱人的。搜索引擎通过上一次的搜索，可以确定一些镜像的网页，而在第二次搜索时避开这些网页，只是检查一下它们有没有更新，这样在时间方面也能带来好处。在“天网”没有作消除相似网页的时候，我们听到很多用户抱怨说，有时“天网”返回的结果中出现了很多篇看上去一模一样的网页。于是对搜索引擎来说，消除相似网页是非作 不可了。 们的尝试及对多种解决方案的评测 “天网”在搜集一篇网页时，记录了网页中出现的关键词，作为网页的特征。同时，提取了网页的前 512 个字节的有效文字（指用户实际访问该网页时能看到的文字，在 其他格式的网页中，有一些用户看不到的文字，它们告诉浏览器该执行什么样的操作及如何显示网页，包括字体，颜色，排版等信息）作摘要。当用户查询时，摘要同网页的 信息一起显示给用户，供用户了解网页的内容，选择感兴趣的进行浏览。象前面提到的那样，我们对消除镜像采用的方案一是，对摘要作 名，当签名（占 16 各自节）相同时，签名算法保证摘要相同。我们假设摘要相同的文章是相同的，然后把相同的网页只保留一篇，其他的都删掉。这一假设是成立的，我们对 1000 篇摘要相同的文章人工检查，没有发现一篇整个内容不同。我们必须承认，这一假设有可能会出错，但是 14 只要有 99%的准确度，对我们就足够了。以后的各种方案都采用了类似的思想。这样，我们得到了第一种发现相似网页的方案。利用这种方案对四月下旬“天网”搜集到的数据进行了删除重复网页的操作，用户查询时，重复网页被完全消除，但还是能发现一部分“看上去是的”重复网页。 我们对此进行分析，发现第一种方案对确定近似网页的要求过于严格，两篇一样 的文章，只要在摘要中有一个字的差异，就不能被定为相似网页。 于是在“天网”存储关键词的基础上，我们引入了“关键词向量空间”的模型。在“天网”的数据库中，我们发现了一篇“计算机网络教学”的网页，其中出现的关键词有： 0 次 )， 9 次 )，协议（ 20 次），网络（ 16 次），路由器（ 10 次）， 5 次）， 。我们在一个多维空间中用一个由 30， 29， 20，16， 10， 5， 作分量的向量来做该网页的特征向量。如图 两篇 网页应的 n 维向量夹角小，长度相差也小时，我们认为找到了两篇近似网页。 在这种基于关键词的理论模型下 ,我们又得到了下面四种方案。 方案二，在按照出现频率从大到小排列的关键词序列中取前 这 这个字符串作 名相同的网页认为是近似网页。 方案三，在 2的基础上，当两篇网页的关键词串 这前 ， 两篇网页与之对应的词频序列分别是 t1,t2, ， ， 这就得到了我们想要的两个向量 、 ，然后我们用 较好反映与的夹角及它们的长度差两方面的因素，当两篇文章毫不相关时（即它们的关键词集合没有交集），与垂直， 。当两篇文章完全相同时， 值为 0。当两篇文章相似而不相同时， 值介于 0和 1 之间，于是 值成为判断两文相似度的标准。我们给定一个阀值图 键词向量空间 222|m 5 如 当 于 ，认为两篇文章相似。并且，我们可以通过阀值 令 时，要求两网页的关键词次频完全相同，几乎等于要求它们是相同网页，当令 时，即对词频不作考虑，方案三转化为方案二。 方案四，把取来的 N 个关键词先按字母排序，再取 ，考虑词频，与方案三后一部分处理相同。 方案五，把取来的 N 个关键词先按字母排序，再取 ，不考虑词频，与方案二的后一部分处理相同。 这四种方案都对理论模型作了很大的简化。 首先，我们把由在网页中出现的所有关键词组成的特征向量，如前面提到的计算机网络教学网页的特征向量（ 30， 29， 20， 16， 10， 5， 2， 1， 1， ，1， 1），从总共 N. . 标识）是网 页作者对网页内容的概括，我们认为它最能表达网页内容，要获得最大的优待。具体做法如下，对于关键词的第 i 次出现，我们给它权值 设它被 n 个标签修饰， 示标签应该获得的优待程度，在表 例出， 表 影响权值的 签（ 40 4 8 4 2 4 4 4 4 16 2 12 4 8 12 4 8 1 4 1 1 1 1 4 关键词的最终权值是 W 是 系统中使用一个无符号短整数来存储 W。因此， W 最大为 255。 提取关键词 前面我们已经利用了网页的标题来 归纳，总结网页