【毕业学位论文】（Word原稿）Blog搜集技术和百万Blog数据分析-计算机网络技术

北京大学 网络实验室硕士学位论文 硕士研究生学位论文 题目： 集技术和百万 据分析 姓 名： 包勇军 学 号： 10448178 院 系：信息科学技术学院 专 业：计算机系统结构 研究方向：计算机网络与分布式系统 导 师：李晓明 教授 2007 年 5 月 北京大学 网络实验室硕士学位论文 版权声明 任何收存和保管本论文各种版本的单位和个人，未经本论文作者同意，不得将本论文转借他人，亦不得随意复制、抄录、拍照或以任何方式传播。否则，引起有碍作者著作权之问题，将可能承担法律责任。 北京大学 网络实验室硕士学位论文 摘要 随着 全世界的流行， 面向 务系统也越来越多。其中最常见的是 索服务，也就是面向 垂直搜索引擎。尽管对研究方兴未艾， 但是很少有文献完整全面的讨论 搜集系统的设计，特别是在垂直搜索引擎的大框架 下。 本文的 工作就是分析和设计 直搜索引擎的搜集系统。 主要贡献包括下面几点 。 1. 设计了 直搜索引擎的系统架构。本文针对垂直搜索引擎和通用搜索引擎的区别，对 直搜索引擎的搜集、 索引和服务子系统作了分析 ，并给出了系统架构图 。 2. 分析了 直搜索引擎搜集系统设计要点。 本文给出 典型 搜集系统的架构，讨论 搜集系统普遍遇到的问题。 然后 具体 针对 直搜索引擎，分析它的搜集系统需要考虑的 一些 特殊 问题 ，包括搜集策略的问题， 问题，虚拟主机的问题 等等 。 3. 详细讨论了 索引 擎搜集系统的设计和工作流程。我们设计了搜集系统的系统架构；提出用 集策略搜集 点；利用站点的 式来识别 对 点的特点 ， 设计高效的 析系统； 分析 集中的 友好性设计 面临的问题，并给出详细的块的设计；分析 集 的两种方案，并给出 集 的 系统架构。 4. 对 搜集到的百万 据作了简单的分析。我们 讨论了 点 中存在的 链接局部性、 布不均衡等 4 点特性 ，并 评估 它们对搜集系统的影响， 尤其 针对 来的影响，给出了 集 的 一些 具体的改进方案 。 关键词 ： 索引擎，垂直搜索引擎，搜集系统 ，爬虫 北京大学 网络实验室硕士学位论文 of a a I in is of is in is no of of is to s 1. of on of we of at we 2. of of to by on to so 3. of We a to to RL to NS by of to 4. a on of of We of as on In 北京大学 网络实验室硕士学位论文 we to 京大学 网络实验室硕士学位论文 目录 第 1 章 绪言 . 1 于 . 1 么是 . 1 展史 . 1 国 展现状 . 2 关术语简介 . 3 直搜索引擎需求分析 . 4 什么需要垂直搜索引擎 . 4 传统 区别 . 5 直搜索的特色服务 . 6 文主要工作 . 7 关 工作 . 8 文组织 . 8 第 2 章 直搜索引擎搜集系统分析 . 10 索引擎基本架构 . 10 个典型的搜索引擎的架构 . 10 直搜索搜索引擎的系统架构 . 11 集系统设计分析 . 12 个典型的搜集爬虫的设计分析 . 12 直搜索引擎搜集系统设计要点分析 . 14 第 3 章 集系统设计 . 17 定 搜集 目标 . 17 点搜集子系统 . 17 统架构 . 18 于我们的搜集策略 . 20 别模块设计 . 20 滤已经抓取过的 . 22 析模块设计 . 23 北京大学 网络实验室硕士学位论文 块设计 . 25 集子系统 . 27 取 . 27 何 获取 更新 . 28 务模块 . 29 集子系统架构 . 30 集数据存储设计 . 31 第 4 章 百万 据分析与搜集系统评估 . 33 集 过程和数据集说明 . 33 据分析和搜集系统评估 . 34 接局部性对及其对搜集的影响 . 34 布不均衡及其对搜集的影响 . 35 术 应用情况及其对搜集的影响 . 37 度与被发现深度的关系 及其对搜集的影响 . 39 第 5 章 总结和工作展望 . 40 参考资料 . 41 附录 A 关术语解释 . 44 . 44 . 44 . 45 致谢 . 47 北京大学 网络实验室硕士学位论文 图 表 目录 图 2型的搜索引擎架构图 . 11 图 2直搜索引擎系统架构 . 12 图 2型的爬虫架构 . 13 表 2内主流 持情况 . 15 表 2内主流 用虚拟主机技术的情况 . 16 图 3集系统的架构 . 18 图 3构图 . 18 图 3式发现算法 . 22 表 3地域名数据库示例 . 24 图 3析系统 . 24 图 3块架构图 . 26 表 3国内主流 支持情况 . 28 图 3新预测算法 . 29 图 3集系统架构 . 30 表 4取数据统计 . 33 图 4发现 量随抓取层数增长的变化曲线 . 34 表 4应 面的 提取出的所有 的比重 . 34 图 4的 链接指向分布 . 35 图 4各 发现的 总数比较 . 36 图 4 点上在不同抓取层次新发现的 量比较 . 36 表 4内主流 用 生链接的情况统计 . 38 图 4度和被发现深度关系图 . 39 北京大学 网络实验室硕士学位论文 1 第 1 章 绪言 于 什么是 语 缩写，中文翻译为日志，博客，这里我们采用英文单词 单来说 一个个人或小团体维护的网络日记 。 面的展现形式也是日记一样的按时间排序； 其内容大多讲述作者 的所见所闻，阐述作者对某事件的看法 。 一个典型的 展现内容通常是文本，这跟大部分面一样 ， 此外也有一些特殊 图片，视频，音乐等多媒体的形式来展现。 如果要对 一个标准的定义，还是很困难。不同的文献中对出了不同的定义。尽管如此 ， 在人们通常的认知中，一个 点会 具有下面的 一些特征 17： (1) 首页是日记形式的页面，文章按发表时间排序。 (2) 每篇文章都有唯一的 文章都标记有发表时间 。 (3) 提供有一些交互机制 ，比如 (4) 提供 可以方便的跟踪 更新。 (5) 个性化（ ， 应了一个“人”的兴趣爱好，性格特征 。 过去的个人主页有几分相似 。 与个人主页相比， 更新更频繁，与外部的交流的手段和机制更丰富 ，与外部的连接也更密切。 比如，为了方便 读者获取更新， 制；为了加强 间的相互文章引用和交流， 制。此外，与过去的手工维护相比，现在对 维护更方便，有许多 点提供专门的 间，此外还有很多 件帮助你架设 自己的 如 等。实际上， 像一个标准化的增强的个人主页。 展史 追溯 源头，无疑是一件难事。 人们所认同的 最正宗的源头还是 北京大学 网络实验室硕士学位论文 2 是现在 1的前身），这是一家小小的软件公司， 现在被购。 三个创始人为了开发一个复杂的 “群件 ”产品，编写了一个小 软件，以 保持 彼此的沟通与协同。后来 他们觉得这个简单的小工具对别人也很有用处，于是， 1999 年 8 月，就在网上免费发布了 件。 从那时起， 队伍开始迅速繁衍开来。到 2000 年， 点 开始成千上万涌现，并成为一个热门概念。 在 展史上， 911 事件是一个重要的时刻。正是这场恐怖的袭击，使人们对于生命的脆弱、人 与人沟通的重要、最即时最有效的信息传递方式，有了全新的认 识 ， 此繁荣起来，可以说对 911 事件最真实 最生动的描述不在纽约时报，而在那些幸存者的 志中；对事情最深刻的反思与讨论，也不是出自哪一个著名记者手中，而是在诸多的 中。 据不完全统计，到今天，全世界的 经达到 千万之众 。虽然与数 亿的网民相比，还显得微不足道。但是这些 影响力，却 早已 超出了他作为个人、甚至作为自己所在行业的原有范围 ， 开始引起主流 媒体的强烈关注，并明显感受到博客崛起对传统媒体的冲击。同时，各个专业领域的博 客如 “雨后春笋 ”，纷纷浮 出水面，越来越成为该专业关注的焦点。 国 展现状 紧随 全世界的流行 ，中国的 点 在 2002 年呈现爆发性的增长。 百度 2006 年发布的中国 查报告 22显示 “ 截止到 2006 年 11 月 3日，全球中文博客站点数量达到 5230 万，博客用户数达到 1987 万 ,平均每个博客用户拥有大约 博客，博客站点数和博客用户数均比去年有一定程度的增长，人均拥有博客数与去年相比也略 有上升。在近二千万的中国博客用户中，每个用户平均每 更新一次博客，活跃的博客用户数（一周内有更 新的博客）达到 302 万，约 用户每周更新博客，同时，只有大约 用户每天更新博客。 在综合每日访问量和独立用户数的基础上，百度对全国100 家博客服务商进行了统计排名，其中， 2006 年前 10 名中国博客服务商分别为： ， 新浪博客 (， 搜狐博客 ( 百度空间 ( 网易博客 (， ， 博 客 网 (，北京大学 网络实验室硕士学位论文 3 ,和讯博客 ( ” 从百度的调查报告 数据可以看出， 中国已经是很 流行的网络应用 。 关术语简介 为了方便读者阅读本文，本节对 在本文中涉及到的 关术语作简单说明，更详细的介绍可以参考本文的附 录 A 部分。 常 见 的 术 语 包 括 :等。 是对那些写 护 网民的称呼，中文译作“博客”。可以看到中文对“ “ 有区分，都翻译成“博客”，需要根据上下文语义来区分。 本文使用英文以作 区分 ，用 示一个 点， 示维护 点的人 ， 一对多的关系，一个 有多个 点是常见的现象 。 一个集合名词，是对所有 点集合的称呼 ，中文可以翻译成“博客世界” 。 中文译作“日志”，也就是 点上发表的文章，这些文章是 点的主体组成部分。 全称 作 务提供商，顾名思义就是提供 务的站点，比如说新浪 搜狐 在 点上 注册 以后，你就拥有了自己的 点 ，对于 章的 写作发表以及 维护， 供了简单方便的 作接口。 中文翻译作“引用通告”。 简单说来， 网站与网站之间互相通告的一种方法。例如，当你读了一篇日志，想对此写下自己的感想，您可以把新的日志内容写到自己的博客 上。然后向原来的那篇日志发 送一个引用通告。通过这种办法，在原始文章的下面就留下了你自己 的日志的链接，这样对于同一个话题的讨论，可以不局限在 一个博客中了 ,更 北京大学 网络实验室硕士学位论文 4 是一种 式的文件。 通过访问该文件，外界 可以获知 点的最近更新内容， 一个 点的 包括 该站点 最近 更新的 信息，更 详细的说明参见附录 直搜索引擎需求分析 什么需要 垂直搜索 引擎 发展给人们带来了巨大的方便，使得人们可以跨越时间和空间的界限来共享大量的信息。可以在家中直接链 接 到其它的科研机构的网站上阅读感兴趣的文献；可以足不出户购买到需要的东西；可以实时的了解国内外的新闻实事。但是，面对如此大量的信息，人们同时也开始感到无所适从。太多的信息使他们很难迅速定位到真正 需要的信息，而跟随超链 接 在 漫游则会浪费大量的时间，而且很可能徒劳无功。因此，人们迫切需要有效的信息发现工具来为他们在 进行导航。 搜索引擎面世后 迅速成为人们网上搜索的有效工具。根据统计，大约85%的用户使用搜索引擎去定位他们需要的信息。并且，几个著名的搜索引擎一直都稳定的处于全球访问量最大的 50 个网站之列。 随着网络信息资源呈几何级数增长，搜索引擎对网络信息的覆盖率在整体上呈下降趋势，尤其令以覆盖所有学科、所有类型信息为宗旨的综合性搜索引擎越来越难以应对，搜索引擎在网络信息搜索与加工软件的升级 开发上亦无法跟上网络信息的增长速度。目前，尽管搜索引擎的发展已较成熟，但要准确、快速地查找所需信息却越来越困难。其原因有二： (1)一次搜索的结果可能有成千上万条，而在这过于庞大的信息群中，有用信息只是其中的小部分，可谓“冰山一角”，并且常常发生收到或下载的信息难以消化的情况，即所谓的“认知过载”。 (2) 目前的搜索引擎都是服务器端软件，用户需要严格按照各搜索引擎所要求的格式输人查询词，但种种限制使用户不知道如何确切地表达自己的信息需求，也不知道如何更准确地寻找所需信息，即所谓“迷航”。网络信息的急剧膨胀，搜 索越来越难以控制，用户需求和市场服务间的巨大反差产生了强大的“搜索噪音”，人们呼唤更有针对性的搜索引擎。 垂直搜索引擎（ 是针对某一特定领域、某一 特北京大学 网络实验室硕士学位论文 5 定人群或某一特定需求提供的有一定价值的信息和相关服务。其特点 是 具有行业色彩。垂直搜索引擎专注具体、深入的纵向服务，致力于某一 特定领域内信息的全面和内容的深入 。 垂直搜索引擎的搜索器只搜索特定的主题信息，按预先已定义好的专题有选择地收集相关的网页。这样大大降低了收集信息的难度，提高了信息的质量。由于所收学科领域小，信息量 相对较少，可以利用领域内的知识进一步提高信息的质量，建立起一个高质量的、专业信息收集全、能实时更新的索引 数据库；由于垂直搜索引擎只涉及一个或几个领域，词汇和用语“一词 (一语 )多意”的可能性降低，而且可以利用专业词表进行规范和控制，大大提高查全率和查准率；由于垂直搜索引擎可以聘请相关专家对用户的检索要求进行网上咨询和网上讲解，明确查询语句，使查询结果的准确率大大提高。垂直搜索引擎这种高度目标化、专业化的搜索引擎的优势在于，针对性强，对特定范围的网络信息的覆盖率相对较高，具有可靠的技术和信息资源保障，有明确的检 索目标定位，有效地弥补了综合性搜索引擎对专门领域及特定主题信息覆盖率过低的问题。同时，能够把具有相同兴趣点的人们集中在一个“主题社区”内，不仅集中提供各种专业资源，而且给大家提供了一个相互交流、共享经验和教训、展望行业发展前景的机会和场合。 目前 垂直搜索引擎的应用方向很多，比如企业库搜索、供求信息搜索引擎、购物搜索、房产搜索、人才搜索、地图搜索、 索、图片搜索 几乎各行各业各类信息都可以进一步细化成各类的垂直搜索引擎。 传统 区别 传统的 面有很大的区别， 这些区别构成了 点独特的风貌 ，让我们能够从不同与通用搜索的角度来设计 很多有特色的服务。在讨论这些特色服务之前，我们先讨论一下 传统 区别。 一个流行的 点，它的更新频繁，它关注的内容 也 流行。 很多流行的 它的读者带来了许多有意思的信息，这些信息通常 是一些新出现的事物、现象、观点、 话题。 出现促进了这些新事物的进一步流行，扩大了他们的社会影响力。传统的新闻网站也是关注新事物，不过与新闻网站不同， 供了更多的交流机制，比如说允许它的读者在 相关文章页面上写评论阐述自己的观点，读者甚至可以在自己的 发表见北京大学 网络实验室硕士学位论文 6 解，通过 原文发生关联。这种双向的信息流动：从作者到读者，从读者到作者，是 别与传统页面的一个很重要的特征。 此外， 点之间的交流也很密切。 创建者会关注与其相关的关通常是 者讨论的话题相同、 观点相近或相左 ),并创建一些链接到达那些 点，这些相关的、交流密切的 成了 一个小社会 。 2一文中总结了 传统 点的 如下 几个区别。 1. 常是单页面站点。 2. 活跃的 传统的 面 （ 比如说个人主页） 更新 更 频繁 ， 有时甚至是一种爆发性的更新。 3. 点与外部的交互方式有自己的特点。 链接的数目，质量和其他一些特性与传统 面不同。对此， 2一文中说“因为的文章被很多人阅读的，其中的一些读者会向 者 反馈指出文章中的错误包括链接错误，这使得 文章随时间流逝而改进；有一些 文章主体就是链接； 其他一些特性，会使得 的链接会有一些特别的性质，比如 点的链接中相当一部分是链向其他的 此形成了一个紧密链接的小社会，而指向非 点的链接都是一些深度链接，指向站点内部的某个具体内容页面，这些页面与 者讨论的某个具体话题相关”。 4. 容通常是个人日记或局限于范围很窄的几个话题。 5. 章的内容一般都是一个人所写，而且就那么几个屈指可数的点和 件，因此，与传统的 面相比， 点的内容，风格，外观更一致。 直搜索的特色 服务 直搜索产生的必要性在于 直搜索 可以提供 一些 特色服务。 服务系统是 直搜 索引擎的核心，是体现垂直搜索与通用搜索区别的地方。最最简单的服务当然就是关键词查询服务，这是搜索引擎常见的服务。一些更 具 特色的服务需要对搜集到的 数据进行挖掘。 针对上节讨论的传统 区别， 结合文献 1中的讨论，我们总结归纳了一些 直搜索能够提供 的 特色 服务。 北京大学 网络实验室硕士学位论文 7 第一， 点关注的很多是当前最流行的，最热门的话题，事件。基于此， 索引擎可以提供热点发现，趋势分析的服务。 第二，相对于传统的 包含的内容更有趣，更关注娱乐大众主题。这意味着，如果我们能有效的从 提取内容，我们可以将 索引擎用作一个娱乐杂志。 第三，由于 点 多数是有一个人来维护，其反应了 个人特征，比如语言风格，兴趣爱好等等。 事实上 认为是一种连接相同兴趣爱好的人们的社会媒体。基于此， 索能提供一项服务，使得 能够更有效的找到相同爱好的其他 第四， 内容包含个人的产品使用和服务使用经验。 有意购买这些产品和服务的用户传递 了很多有价值的信息，而产品和服务的供应商则可以使用 索引擎收集顾客的反馈 。因此， 索引擎可以在产品评价、 导购和质量反馈上提供有价值的服务。 文主要工作 目前对于 研究很多，但是很少有文献完整全面的讨论 搜集系统的设计，特别是在垂直搜索引擎的大框架下。尽管有很多文献涉及了 多的还是为其他方面的研究服务，因此对于 搜集的研究都不够充分。 集系统作为 直搜索引擎系统重要的一部分， 并不只是能搜集数据即可 ， 从 设计一个 完整 ，正确，有效 的系统 的 角度来说， 还有很多需要考虑的设计方面的问题， 因此 本文 就 直搜索引擎 的搜集系统 设计 作详细的分析 。 本文 的 工作 主要 包括以下几点： （ 1）简单讨论我们设计的千帆 4垂直搜索引擎工作流程和系统结构；（ 2）详细分析 索引擎的 搜集系统的设计要点 ；（ 3）实现 直搜索引擎的搜集系统 ；（ 4） 对搜集到的 100多万个 点及其链接关系进行分析，主要讨论影响 集系统性能和效率的一些性质。 北京大学 网络实验室硕士学位论文 8 关 工作 网页搜集系统俗称网页爬虫，是被广泛研究的领域。 网页搜集系统面对 是海量数据处理，在 系统的性能和 规模的 可扩展性 有较高的要求 。 8对 现作了细致的说明 ； 11设计了一个扩展 性较强 的搜集系统 ； 14讨论了高性能分布式搜索系统的实现。 这些搜集系统 面向的是整个 应用于 搜集时显得过于庞大臃肿 。 对 挖掘也是目前计算机科学中的热门研究领域， 3,4,6致力于社区发现； 7对 链接的结构和相关性质进行了分析； 24针对 了一些实验，给出了 一些 统计数据。这些文章针对 点 链接关系进行分析，挖掘 特殊性质，但是 对 这些性质对 索的影响没有什么分析。 在对 行 的研究中 ，也有很多文章 涉及到 搜集 或者直搜索 引擎 。 23提出了一个偏向主题抽取的