【毕业学位论文】（Word原稿）历史网页的持续收藏及其再访问的关键技术研究-计算机系统结构网络与分布式系统博士论文

博士研究生学位论文 题目： 历史网页的持续收藏及其再访问的关键技术研究 姓 名： 学 号： 10208821 院 系： 信息科学技术学院 专 业： 计算机系统结构 研究方向： 网络与分布式系统 导师姓名： 李晓明 二 00 八 年 五 月 On a in of ( i 2008 版权声明 任何收存和保管本论文各种版本的单位和个人，未经本论文作者同意，不得将本论文转借他人，亦不得随意复制、抄录、拍照或以任何方式传播。否则，引起有碍作者著作权之问题，将可能承担法律责任。 i 摘 要 网页是一种易逝的信息资源，在新网页不断涌现的同时旧网页也在逐步消失。如果没有专门的机构来对网页进行收集和保存，它们就会在不经意之间消失。而随着互联网成为一种不可忽视的新媒体，网页内容的重要性已经不言而喻。因此，持续收藏并永久保存出现过的网页具有重要的意义，可以为后人提供珍贵的历史资料。显然，人们还希望能 够以一种比较方便的方式来再访问这些保存下来的海量网页，从而才能体现出这种收藏的价值。这里所说的“再访问”可以有多方面的含义，包括根据 链接关系来浏览历史网页，像搜索引擎那样查询相关网页，等等。 不难想到，这项工作可以大致分成两个部分，一是有计划地进行网页的持续搜集，二是将搜集到的网页适当地组织起来，以便再访问。本文的工作属于后者。即我们假定有一个搜集系统源源不断地将网页搜集下来，我们需要对它们进行有效地组织和存储，并提供对它们有意义的访问方式。 针对这种需求，本文确定了四个关键技术问题，对它们分别进行了深入的研究，并基于研究的成果设计并实现了两个系统。本文的主要贡献包括： 1）提出了一种带有时间标签的链接图的存储及压缩方法。链接图是表达网页之间关系的一种重要数据结构，它是链接分析技术的基础，广泛应用于 据的分析、挖掘、检索领域。通常，链接图上是没有时间信息的。而由于本文工作所针对的是长时间持续搜集的历史网页，对应同一个 网页的不同版本会在不同时间被搜集下来，于是网页的链接 关系会随着时间发生改变，因而就形成了带有时间标签的链接图。本文 研究 了带有时间标签的链接图新型表示模型，详细设计了存储格式和 压缩方法。 这方面的研究成果的有效性在我们所收藏的 24 亿历史网页集 合 上得到验证， 从该集 合 我们构 造 了一个包含有1546 亿条带有时间标签链接 的链接图 系统 ，并得到一些初步应用 。 2）提出了一种从杂乱无章的网页集合中筛选出文章型网页的方法。我们称新闻报道、分析评论、论坛帖子、博客日记等由人创作完成的作品，具有标题以及一段逻辑上连续的正文，为网络文章。文章型网页指的是包含网络文章的网页。直觉上，它们具有较高的挖掘和检索价值。本文提出的方法基于对文章一般性规律的认识，具有通用性和较好的效果。简要地说，首先从网页内容中提取 出标题，然后从标题位置后面的文字内容中提取出正文来。 实验表明精度和召回率都很高。 根据这一方法 （但 在大规模数据条件下 因个别技术 难点 没有完整实现） ，本文从 24 亿网页中提取出了约 篇网络文章。 3）提出了一种新型的相似网页检测算法，同时具备高准确率与高覆盖率的优点。该算法采用基于 相 似性度量方法，设计了一个包含了三个步骤的检测过程框架，保证了算法 的效率。综合实验表明本文的算法同时获得了高准确率与高覆盖率。该算法成功应用于上述网络文章的消重，将 文章型网页分割为 个相似网页子集（即得到 篇不同的网络文章），整个过程使用 6 台 务器仅花费了 5 天的时间。 4）提出了一种网络文章发表时间的估计方法。发表时间是文章的一个重要属性。比较容易想到的方法是通过从网页文字内容中提取出来的时间、网页的 网页搜集时间这三种信息来推断文章发表时间。然而其效果并不足够理想。因而在此之上本文进一步提出了利用链接分析和检测相同 文章的方法来提高计算精度。综合实验表明，前者可以提高约 35%的计算精度，而后者的作用更加 显著， 如果能够检测到文章的多个其它拷贝，则有很大的概率计算出来的文章发表时间是准确的。 5）设计并实现了一个大规模历史网页仓储系统，并提供历史网页回放服务，称为 ）。它用于存储搜集系统持续不断搜集来的历史网页，用户可以在上面使用 获取和浏览历史网页。可扩展和增量存储是本系统的两个重要特性。对此，本文设计了相应的存储组织结构和索引结构，它们经历了海量网 页数据的考验并具备较好的性能。到目前为止，已经收藏了近六年来在中国互联网上出现过的近 30 亿网页，压缩以后的数据量超过 20外，本文还设计了一种适合网页长期保存的存储格式。 6）在上述研究成果的基础上，设计并初步实现了一种面向历史事件报道踪迹的搜索引擎系统，称为 ）。它用于检索在历史网页中所记录、描述的历史事件对象，并按时间的顺序将它们展现出来。当前系统建立在一个规模为 24 亿的历史网页集上，采用前面所描述的方法和技术，从中提取出 篇文章，在消重之后得到 篇不同的文章，并为每篇文章计算出它的最早发表时间。然后，为这些 文章的标题建立了索引，当用户输入历史事件的关键词时，系统返回与它关联的所有文章（网页），并按发表时间的顺序排列出来。 关键词 ：历史网页， 储， 信息检索， 相似性检测 v On a eb is a or If by in a be of of is of on a be up of to be in a to of is 1) ) by a It is to be is to in a is to In to we a up we to In to in we on At on we of 1) A of is is is an is of in no is on in so we is a of In we a of of is in A of on a .4 we a 54.6 on 2) A a of is We on eb as of at a of to a of is on of so it is we we s a s we s s of to of to we .4 3) A of is of is a 3is to A to a 30 8 of of to a 4) of is an of to a re by by by So we to 5% of of is if s we to 5) A ), is It is to by a by of we of As of a of 0 a of 6) on a of is ). It is to of in is in a is on a .4 of of a of a s it in a to 目 录 第 1 章 绪论 . 1 究工作的背景和意义 . 1 存现状 . 5 文研究内容概述 . 10 第 2 章 背景知识与相关研究 . 14 史网页的搜集 . 14 史网页的仓储 . 20 史网页的挖掘与检索 . 25 章小节 . 31 第 3 章 一种带有时间标签的链接图存储方法 . 33 言 . 33 关研究 . 34 有时间标签的链接图表示模型 . 34 关模型简介 . 35 型设计 . 36 计理念 . 38 缩存储格式设计 . 40 接图压缩技术综述 . 40 储格式设计 . 42 接表存储格式设计 . 43 术实现情况 . 46 章小结 . 48 第 4 章 一种从网页集合中筛选网络文章的方法 . 50 言 . 50 关研究 . 50 络文章的特点分析 . 53 选方法 . 55 x 验与评测 . 57 定标点符号分布特征的阈值参数 . 57 体效果评测 . 61 能及运行结果 . 62 章小结 . 62 第 5 章 一种基于 相似网页检测算法 . 64 言 . 64 关研究 . 64 于 相似性度量 . 66 景知识 . 66 量方法 . 67 似性度量的一般过程 . 67 度的比较 . 68 法与实现 . 69 统框架 . 69 能相似子集的计算 . 69 档过滤框架的计算 . 71 信 部分（ 计算 . 72 验评测 . 75 纹数量的影响 . 76 动窗口长度的影响 . 77 似度阈值的影响 . 79 行效率 . 80 法的比较 . 81 度的比较 . 82 章小结 . 83 第 6 章 网络文章发表时间的计算方法研究 . 84 言 . 84 关研究 . 84 章的时间属性分析 . 85 章发表时间的计算方法 . 86 究数据来源 . 86 础计算方法及其问题 . 86 高计算精度的方法 . 89 验与评测 . 91 章小结 . 94 第 7 章 种历史网页仓储系统的设计与实现 . 95 言 . 95 统设计 . 95 页的存储 . 99 据的组织 . 99 储结构 . 101 据管理与压缩 . 103 储性能 . 105 据访问 . 106 索引 . 106 索引 . 107 据服务 . 109 能与优化 . 110 页历史回放 . 111 页的长期保存 . 112 章小结 . 114 第 8 章 种面向事件报道历史的搜索引擎 设计与初步实现 . 116 言 . 116 往探索与经验 . 117 统设计 . 120 统概念框架 . 120 要环节分析 . 123 系结构设计 . 125 统实现情况 . 126 章小结 . 129 第 9 章 总结与展望 . 130 文的总结 . 130 一步的研究工作 . 134 参考文献 . 136 在读期间发表的文章 . 143 在读期间参加的科研项目 . 144 致谢 . 145 图示 图 2出的增量搜集体系结构 . 17 图 2同域名的网页变化周期 . 18 图 2基本模型 . 27 图 2个网页历史回放的例子 . 28 图 3接图的超级节点表示法 . 36 图 3分布图 . 41 图 3 存储 . 43 图 3接表存储格式 . 44 图 3个链接查询示例 . 48 图 4标签树实例 . 52 图 4个典型的记录型网页片段 . 54 图 4个典型的新闻类文章型网页片段 . 55 图 4人民日报语料库中文章的标点符号比例分布