【毕业学位论文】（Word原稿）Web数据模型以及获取、存储方法研究-计算机网络技术

北京大学硕士学位论文 据模型以及获取、存储方法研究 1 摘 要 信息就像一条河流，从我们身边不停流过。已经有很多人认识到这些信息的价值，从而展开了对 息多方面的研究。本文阐述的内容就是基于这些研究，并希望能够对他人的相关工作带来方便。文章围绕的中心是 此也专门研究了信息在 大量重复出现的现象和原因。 本文的主要内容包括： (1) 有关 息状况的一些统计数据，结合一些 基本概念，这些数据让读者对 观上能有一些具体的认识。这是理解本文其他部分的基础， (2) 提出了同义主机的概念。在 有很多不同的域名代表着相 同的主机，负责获取网页的系统如果不知道这种信息，就会重复的获取这台主机上的网页。这样导致网络资源和机器资源的浪费，并且对相应的 务器也造成额外负担，本文通过分析 址与域名的关系，总结出哪些主机名有同义关系，从而避免了网页的重复获取；另外，对于消除 存在的重复或相似的网页，本文提出了多种算法，一一进行评测，并选择最好的用于实际的网页消重中。 (3) 本文还具体的讨论了 据获取系统的设计目标，并给出了计算系统效率的方法。然后参照这些设计目标，比较了两种具体的收集系统结构。 (4) 同时，论文还基于 目标，给出了一种海量网页存储系统的设计方案以及实现的种种考虑。 关键词 ： 页搜集系统，同义主机，重复网页，网上信息博物馆 北京大学硕士学位论文 据模型以及获取、存储方法研究 2 eb is a of by us to is on It to to as as eb 1 be in 2 It is a on If a is of on be As a is is we P a so be To of or a 3 so is in is We of 4 At of a is 京大学硕士学位论文 据模型以及获取、存储方法研究 3 目 录 第一章 绪 论 . 1 究背景 . 1 容 . 1 接 . 2 户对 构的影响 . 2 数据集 . 3 究方法 . 3 文主要贡献 . 4 第二章 同义 主机 . 5 同义主机的定义 . 5 义主机的验证 . 7 同义主机的几种情况 . 8 系统实现 . 11 第三章 网页消重 . 13 题的提出 . 13 网系统目前使用的方法 . 14 分段签名算法的比较。 . 18 第四章 搜集系统的效率 . 20 集系统设计目标 . 20 基于数量的效率 . 21 效率极限 . 23 基于质量的效率 . 23 如何搜索导向 . 24 导向参数选取 . 25 实验过程与结果 . 26 第五章 “天网” 搜集系统比较 . 32 绍 . 32 两种搜集系统的对比 . 32 第六章 一种 据存储系统的实现 . 35 系统目标 . 35 任务估计 . 35 系统模型 . 36 北京大学硕士学位论文 据模型以及获取、存储方法研究 4 介 . 37 散列算法选取 . 38 对 定制 . 39 第七章 总结与展望 . 41 总结 . 41 展望 . 42 参考文献 . 43 在读期间参与的科研项目和发表的成果 . 45 北京大学硕士学位论文 据模型以及获取、存储方法研究 1 第一章 绪 论 究背景 我们通过不同的网络协议访问 特网，也称互联网）上的各种资源，这些协议有 等。我们今天谈论的万维网 (也简称为 具有多媒体功能的一部分，它也是发展最为迅猛，最主要的一部分，以至有人把它等同于 文所关心的是 以 页形式存在的信息，具体讨论为了建立这种信息的历史档案，用以大量获取它们的方法、存储它们的技术。 容 源主要通过 议进行访问，这些资源分为不同的类型，在 来标识，有 等，包含了文字、图像、声音、视频 、以及各种 件。在最简单的 览器 (，仅仅可以看到文字，而比较完善的 览器（ 等）能直接打开大多数的资源类型（其他的可以下载到本地，由其他应用程序处理）。通过给浏览器增加新的插件，它能够直接打开的资源种类会增多，我们看到的 会越来越丰W e b 资源类型的分布情况66%16%14%1% 1% 2%t e x t / h t m li m a g e / g i fi m a g e / j p e gt e x t / p l a i na p p l i c a t i o n / p d fo t h e 源类型的分布情况 北京大学硕士学位论文 据模型以及获取、存储方法研究 2 富多采。从 2001 年的数据看， 存在的资源种类（按照上述 三千多种（有些是由于错误的拼写造成的），主要的几种分布比例如 2： 接 在 存在的多种形式的信息中， 式的文本资源是其最主要的部分。我们通常看到的网页，就是 档加上嵌入其中的其他媒体资源。但在只处理文本信息的 览器中，有时也把 档与网页等价。 重要的特征就是能够在文档中引用其他的资源。如今的 富多彩，被人们方便的使用着，大受欢迎，在很大程度上要归功于 这一特征。在 档中引用其他资源可以分为两种情况： 嵌入其他的媒体，如图象、动画等等， 档负责组织它们，与 成 用户看到的网页。 指向其他的网页。 通过用户的点击动作，浏览器再去打开所指的资源 。如果所指也是一个 档时，它对应的网页就成为当前页面。用户可以通过不断的点击动作，从一个网页跳到另外一个网页，寻找他感兴趣的东西。这种行为被叫做“网上冲浪”。 用户在“网上冲浪”的时候，在链接附近往往有 对被链接资源的文字或图形说明，通过他们的引导，用户可以方便的找到自己想要的东西。这种网页之间的互相链接（指向），使得整个 成了一张有向图。 的网页 就是图中的节点， 如果在网页 A 上有一条指向网页 B 的链接，对应到图 中就有一条从节点A 到节点 B 的有向边。我们可以依此来定义两个网页的距离：从网页 A 最少通过几次链接到达网页 B，称为从 A 网页到 B 网页的距离。 户对 构的影响 不论是 是 在他们 最初被一群学者、科学家发明的时候，用户的范围也局限在这群精英的圈子里面。这么多年过去了，情形已经大不一样，尤其是 于 使用上比较简单，并且容纳各种不同表现形式的信息，导致当今社会各种职业、各种年龄、各种文化程度的人都在使用 由于网站主页的地址比较短，便于记忆和录入， 人们在浏览一台主机时，一般来说都是从它的主页开始的。如果有兴趣的话再顺着主页上的链接，到达该主北京大学硕士学位论文 据模型以及获取、存储方法研究 3 机的其他页面。如果你对主机上的东西已经很熟悉，可以直接访问你所感兴趣的页面，但这种情况总归是少数。在对站点的访问中主页占去了相当大的一部分，站点的管理者考虑到这一点，便把最重要或者最新的东西，放在主页上，或者离主页距离比较近的位置。 数据集 2002 年 9 月 12 月北大天网对中国 行了一次搜集 ，得到网页（ 式） 122,946,077 个 8。涉及到的 有效（能够访问到的）域名 541,808个 ，其中能够提供 10 个以上网页的域名的有 12 万个 ，称 这 12 万个域名组成的集合为 2002 年月的研究表明，千万的网页数量能够达到 37%的 盖率， 所以我们可以认为现在使用的 网页数据是一个相当大的数据集，可以足够真实的反映 性。 在 541,808 个有效域名中，有大量类似于：样的域名， 这些域名代表的主机可能是网站管理者无意之中临时建立的 ，往往只提供一个 务器安装完毕后缺省的主 页访问，这样的域名对 户没有什么用处。所以在后面的讨论中，经常用到的是域名集合 不是总数的 541,808 个域名。在122,946,077 个网页中， 盖了其中的 上。 究方法 务器的行为以及 户端（浏览器）的行为，都需要遵守 议，但协议本身却给 务器留下了相当大的空间。 务器的具体实现和用户对它的配置很大程度上决定着 务器的行为。如果我们需要研究每一种可能的情况的话，将会面临一个异常复杂、琐碎的工作。庆幸的是，少数的几种的行为方 式占据了实际 且 他们都是 户能够经常见到的 ，至于其他的一些情况，可能只有这方面的专家才能有所了解。 我们的研究把重点放在了大多数情况上。有一些现象只是由于人们的习惯形成的，并没有明显的道理可讲。我们通过对真实数据的统计，希望来发现这些现象。也许这种发现只在一定的范围、一定的时间内有效，但对于一个全新的领域，这些零星的、琐碎的小发现，是以后更大发现的基础。同时这些小的发现，也可以被我们利用来改进系统，有时效果还相当的不错。这一点，也是我们工作意义的所在。 北京大学硕士学位论文 据模型以及获取、存储方法研究 4 文主要贡献 1. 解 决了主机重复搜索的问题 由于同一个主机可能有不同的名字，进一步导致在一台主机上的资源有多个 之对应。我们称 据获取系统为网页搜集系统 (如果搜集系统不能识别它们的话，就会重复的搜集该主机上的 文通过对搜集到的 据进行分析，研究造成主机重复搜集的各种情况，找出了 域名之间对应的规律。认识这些规律可以发现哪些主机名字可能代表相同的主机，从而在根本上解决了主机重复搜集的问题 2. 实现了重复网页的消除，评测了各种算法。 在互联网上存在大量内容重复的网页，它们占所有网页 的比例达到了 23以上。内容重复的网页可能会严重影响搜索引擎服务，因为内容重复的网页对特定用户查询的相关程度一般相同，用户查询结果（网页）按照相关度排序，分页输出。如果没有消除这些重复网页（或者对它们作上标记），它们会出现在同一个输出页面上。用户认为这是搜索引擎的一个严重缺陷。本文提出了消除这些重复网页的一些算法，并综合其他算法，给出了对他们的评测。依据评测的结果，实现了网页消重系统。 3. 重新设计了网页搜集系统。 在旧的天网使用的网页搜集系统的基础之上，根据我们的具体需求和实际情况，本文总结了好的网页搜集系 统应该具有的一些特性，针对这些特性重新设计了的搜集系统。 4. 实现了 第一个版本 由北大 985 资金支持的一个项目，目的是定期保存全中国的网页，以后作为一个中国网上信息的博物馆，并支持在这种海量数据之上的各种研究活动。本文通过对系统效率、可扩展性以及使用的方便性多方面进行了分析，权衡出一个比较好的方案。在文章中详细阐述了该方案和方案在系统实现时的情况。系统已经在 提供服务，取得了良好的社会效应。 北京大学硕士学位论文 据模型以及获取、存储方法研究 5 . . 第二章 同义 主机 同义主机的定义 在 搜集系统 对 行大规模抓取的时候，我们希望尽可能抓的“全”，不要遗漏一些网页；同时抓的“快”，以较短的时间完成任务。在实际的 取过程中我们发现，通过以下 到 际上是完全一样的： 1. 、 际上是同一个主机的不同表示 用域名或者 80 端口是缺省的 口。在前面 4 个 面再加上相同的本地路径的话，我们仍然会得到相同的网页。如果我们的搜集系统不知道这些，认为它们代表着不同的资源，分别抓取“ 四个主机”上的资源的话，相当于进行了 300%的重复劳动，严重违背了“快”的原则。更坏的是，还有可能让搜集系统产生对目标 务器的“攻击“行为：为了不对 务器造成负担，我们规定搜集系统在同一时刻与一个 务器之间只能有一个 接，但如果碰到前面的情况，我们有可能与 务器之间同时建立四个 接。 上面所举的例子只是 域名关系问题中比较简单的一个，围绕 源获取还会有一些更加复杂的情况。这些情况在我们设计一个搜集系统的时候都必须予以考虑。每个 主机 名 (本地路径 (者简称 成。这里先描述一下通过 议获取 对应的 源的过程，示： 有下面几个步骤： 1. 抓取进程先解析 后利用该 址（以及相应端口）与 接。 2. 通过该 接发送 求，请求中必须有的内容有 京大学硕士学位论文 据模型以及获取、存储方法研究 6 下面是一个对北大主页的 求，省略号代表实际请求中还可能附带的其他一些信息。 3. 等待 务器的 答，接收应答数据流。应答数据流的第一部分是本次 求的应答头，从应答头中我们可以得到这一次 求的返回状态。如果为成功状态的话，所请求的资源紧随应答头，也在应答数据流中。 从这一过程可以看出，最终我们得到什么样的 源由 址、 址由 过 数得到，表示如下： 我们可以看到用两种形式的 1、域名，这是比较常见的情况； 2、 址是给 的主机分配的地址（在不同的地方使用不同的表示方法，他们之间可以 互相转化）， 传输的数据包中记载了发送主机和接受主机的 址，路径上的路由器们按照数据包的 址转发数据包，让其到达目的地。域名是用来标识 的主机（以及网络）的另一种名字，主要是为是为了网络用户的方便，把网络组织成一种树林状的等级结构。树中的节点称做域（ 它的命名有一定的含义，便于记忆。一连串用 .分隔的域组成为一个域名（可以看成是从树根到一个节点的路径）。把 照域的这),(),()( lo c a lh o s tR s c a lh o s s cR c sh o s 图 京大学硕士学位论文 据模型以及获取、存储方法研究 7 种（多层次）划分方式倾向于反映网络上的一种逻辑组织结构，它可以与组成网络的物理布局完全没有关系。从上面获取一个 源的过程可以看出，建立 接必须使用 址， 是一种把域名转换为 址的服务。 我们现在的目标是想知道在搜集系统遇到的 多种表示中，哪些是“同义”的 就是说在后面加上相同的 得到相同的资源。 为了讨论的方便，定义： |,| 是一个域名地址是一个 ， | ho 的是 , 则有 ; 我们把 的元素作为字符串处理，继承字符串 的比较运算 ， =。进一步有 ， 等等。 A义 ) = x,满足 yHS(xy)。 我们所求的“同义”可以描述为 的二元关系 ) ) ,(),(|, l o c a s cl o c a s cl o c a 它具有自反性，对称性，传递性，是一种等价关系。 址一样，并不能够说明两台主机同义。也不能如果需要完全求解 要在把 的资源抓取下来之后，对所有的 两进行比较，这样的计算量非常大，几乎是一个不可能完成的任务。我们希望找到其他一些和 关的、比较简单的关系，在一定程 度上模拟 义主机的验证 对于给定的两个主机名 A, B，问它们是不是同义主机。可以按照定义，把两个主机上的资源（具体到每个网页）进行比对，但在实际中这样做不是太必要。并且一个中等规模站点上的网页就会上万 ，进行上万个网页的比较，需要的时间为十几秒到一分钟。这种运算如果只是偶尔发生的话，倒无关紧要，但在下面我们的分析中， 可能需要验证成千上万个主机的同义关系，这就需要我们另想些快一点的办法了。 前面提到，站点主机上一般是主页被访问的次数最多，然后网页离主页的距离越远，被访问的可能性越低。因为主页最 能代表站点在人们心中的形象，所以在我们想区别两台主机时，也是首先从主页开始。 这样我们验证两个主机是否“同义”，采取了下面的办法：主机上的网页 按照 小到大的顺序分别把 A 与 B 中的网页排序，各取前十个进行比较。如北京大学硕士学位论文 据模型以及获取、存储方法研究 8 果前十个网页都相等的话，我们就认为 A 与 B 满足 们命名这个算法为用 验证 于算法里要求每个主机必须有十个网页，可以看出为什么我们要使用 不是所有的 541,808 个域名。 同义主机的几种情况 我们从 务能够提供的信息着手：当我们提交一个域名的时候， 函数为例）：域名对应的官方名（ 若干个别名（ 地址类型与长度、若干个 址。 为有些域名是代表同一主机的不同名字。代表同一个主机的一组域名之间互为别名（ 并从他们中选择一个作为官方名（ 址的别名只有它自己。为了讨论问题的方便，定义函数： (1) 的官方名 N N S )(_,:_ 。 有如下性质：当 时， S )(_ ;当 时， N S )(_ 。 (2) 的所有别名的集合。 I A S E I A S E S )(_,2:_ 有如下性质： )(_ E 。 ;)(_ E x 时，当 。时，当 E )(_ 足如下的 关系： )(_)(_)(_)(_ I A S E I A S E N N S (3) 。地址相关联的所有与 )(_,2:_ D D S I P S 有如下的性质： 。时，当 )(_ D x 下面是我们从 息中发现的 关系 。 1. 定义 的二元关系 : 。)(_)(_|,_ N N I 样，也是一种等价关系。 以及 新 浪 网 内 的 域 是满足 系的北京大学硕士学位论文 据模型以及获取、存储方法研究 9 例子。但是通过实际测试发现，访问 得到完全相同的内容，也就是说他们满足 过 以访问新浪新闻网，而访问 返回 403 错误，就是说不允许对 访问。这样， 于模拟我们的 有用处吗？ 2. 定义 的二元关系 ： 。) ) (_,(|,_ D 从对 定义可以看出：由于 x,xx)=x，所以 足自反性； x,y = y,x，所以 满足对称性。但是， 一定满足传递性。 我们解析一个域名，希望得到对应的 址。在有些情况下，与单个域名对应的 址不是一个，而是多个。这是因为有一些域名代表的 点访 问量巨大，单台服务器想要承担如此大的负担，有点力不从心。面对这种情况有两种选择，一是更换高性能的服务器；还有便是想办法把负载分摊，用多台相对低档的服务器共同承担负载。后一种办法在价格上占有很明显的优势。于是在 P 地址的情况（每个 址对应一台服务器主机）。由 户端随机选择一个 址（主机）进行访问，这样来把对一个域名的访问分摊。被随机选择的 间满足 3. 定义 的二元关系 : 。)(_)(_|,_ D D 访问 满足 域名，意味着可能访问到同一台主机。这样的例子有：访问域名 问的其实都是主机 4. 定义 的二元关系 ： 。 D )(_|,_ 其中 的恒等关系。同 样， 足自反，对称性，但不满足传递性。 映的是域名与其解析到的 间的关系。 上述的 四个二元关系是比较容易得到的 ， 抓取进程对 源进行获取的时候 访问 务，同时记录这三个关系。扫描整个 程结束时，我们也得到了完整的 后我们把 据集 一个样本，通过统计分析来得到 京大学硕士学位论文 据模型以及获取、存储方法研究 10 关系。 在 12 万个域名中 ， 5%存在别名，但是它们的别名大部分没有出现在 。域名 别名 是这样的一个例子，当试图以 式访问 ，返回 403 错误代码（意思为禁止访问）。我们定义谓词 果 问某 H首页，返回的状态码为 200 或 203（代表得到正确结果），则有 H)为真。 大概只有 1%的域名有别名，并且本身和别名都满足 件。对这一部分域名进行验证，发现他们与其别名全部等价。现在我们修订 = |xDSyx)y)x)=y) 有 _ 。 三个关系同时与 域名有关，就显得比较复杂。下面是 站内几个主机域名与 点分十进制表示中，它们的前两个十进制数都是 里略去）的对应关系： ( ( ( ( ( ( ( ( ( ( ( ( ( ( 应的 全相同，而内容完全不一样。这样， 破坏了。在考虑 ，发现这些 统不能以 式直接进行访问（返回 403，禁止访问错误代码）。 我们希望能够排除这种以外的情况，在讨论 求涉及的 足 订后得到 如下： = |xyzx,yz)x)y); = |xDSyzx)y)(z); = ,|xDSyx) z) 在 基础上对他们一一进行验证，同样得到： ( 四个关系在有了 息之北京大学硕士学位论文 据模型以及获取、存储方法研究 11 后，只需要再进行一些 算就能得到。通过他们，能够极大限度的模拟一个特例： 们俩是两个完全相同的站点，但是没有出现在前面列出的四个关系中。所幸的是这样的情况极少（所知的只有一个，新的有待发现），我们可以人为的维护一个关系 记录这种情况。 这样，抓取进程在进行 （完全）搜集时，就可以利用这些信息，最大限度的 避免重复搜集。 系统实现 在具体实现中为了存取速度较快，我们采用了由 散列结构管理表头的映射表来存储 一个等价关系， 我们用等价类 x中最小的元素 x)来标识 x 所处的等价类。 最终在我们的系统中使用了一对映射表： A: ;以主机为键值，存储主机所在等价类的最小元素。用义的类型是： : 等价类的最小元素为键值，存储该等价类的所有元素。 言定义的类型是： 储到 A、 B 中的算法如下： 取出 的一个元素 ，执行如下运算， 1. 计算 值 A(!= & A(!= ( A(; A(!= A( A(!= A( 2. 把 入 A 中 A(= A(= 3. 把 入到 B 中 北京大学硕士学位论文 据模型以及获取、存储方法研究 12 重复进行 13 步操作，直到 的元素为空。 在顺利的把 息存储到了 A、 B 中之后，抓取进程就可以通过它们来避免搜集同义站点了。每当遇到一 个站点 A 中查 在等价类的最小元素，然后再用这个最小元素从 B 表中查出等价类中的所有元素。 北京大学硕士学位论文 据模型以及获取、存储方法研究 13 第三章 网页消重 题的提出 前一章我们提出，在搜集 ，有办法找出哪些主机是同义的，从而可以避免重复搜集这些主机上的网页。但是我们发现，在不同义的主机上，也会出现一些内容差不多的网页。我们可以把内容上相似的网页称之为“镜像”。用过未经消除镜像的搜索引擎的用户会发现， 实在有太多的镜像。经常被镜像的网页有这几类（根据天网 2001 年 4 月的统计）： 1 政府部门的法令、通告。例如 公安部颁布的 计算机信息网络国际联网安全保护管理办法 在国内的网站上有 120个镜像。 2 重大新闻，热点新闻。例如中欧 判取得进展但未达成协议有75个镜像。 3 技术文档。例如： ) 有100 个镜像， 有 90 个镜像。 4 提供一定服务的网站。例如“ 黄金书屋”的镜像有 30个。 这些镜像有的是没有一点改动的拷贝，有的在内容上稍作修改，比如同一文章的不同版本，一个新一点，一个老一点，有的则仅仅是网页的格式不同（如 这些镜像网页的出现，给网民带来了好处。重要网页可以有更多的机会被人们看到，并且在一些网络速度慢的地区，人们可以从多个镜像中选择一个距离自己较