采用机群架构的网络资源搜索系统

VIP免费
3.0 侯斌 2024-11-19 4 4 1.67MB 96 页 15积分
侵权投诉
I
摘 要
Web 信息的急速膨胀，在给人们提供丰富的资源的同时，又使人们在对如何
有效使用它们方面面临巨大的挑战。作为检索服务的基础和组成部分，Web 信息采
集正发挥着举足轻重的作用。
网络资源搜索系统是 Web 搜索引擎的前端，负责在网络上搜集所需的信息资
源。同时，为了保证搜索引擎及时、准确地更新信息资料，也要求系统在尽可能
短的时间内对网络资源进行更新。资源是否获得及时的更新将直接影响其检索的
准确性。
单主机资源搜索系统受到了单机硬件性能和操作系统的限制，难以进一步发
展，并行资源搜索系统已成为必然的选择。利用并行计算模型，计算结点并行工
作以提高处理能力的特点，将更新任务分配到适合的计算节点运行，可以较好的
处理批量网络资源更新问题。此外，对于计算结点的添加、减少，能自动进行任
务分配调整，也有助于提升系统的可扩展性。增量更新技术通过对网页更新度的
预估，减少了系统更新页面的工作量，提升页面的新鲜度。
本课题提出了一个采用机群架构的网络资源搜索系统，资源搜索系统使用增
量更新方法，控制整个机群，实现对网络资源的收集和更新维护。本文重点描述
了系统的工作原理，并在此基础之上给出了系统的设计和实现。系统通过基于向
量空间的散列方法实现机群任务的负载均衡，通过均衡 CPU、MEMORY、I/O、NET
（网络带宽）等因素，动态获取各计算节点的运行状况，实现动态监控和任务分
配调度策略的改变。并通过将夹角余弦向量法与增量更新思想相结合，提高了网
络资源搜索系统的效率。
关键词：Web 数据抓掘； 并行抓取； 增量更新策略； 余弦向量法；
计算机机群
II
ABSTRACT
The rapid extension of web information offers us with abundant resource,
meanwhile it challenge us a lot in how to use it efficiently. As one of the necessary parts
of a searching system, the collection of web information works as a key rule.
Web resource searching system which mainly response to collect web resource
locates in the front of a search engine. To ensure the search engine work on time and
actually, it needs the crawler system to update the web resource and whether
information is freshness or not inference the search engine a lot.
With the restriction of the hardware and operation system, traditional crawler
system faced bottleneck in its development and parallel crawler system has become a
right choice. Taking the advantage of parallel system model which could make
computing nodes working parallel to enhance the handling ability and dispatch the
assignment to a suitable node, the dispatching model of computer cluster was
introduced to solve the batch updating properly. Further more, the function of increasing
and decreasing nodes and assignments dispatching adjustment automatically greatly
helped the crawler system on its expanding. Increment update strategy was used to
estimate flashing rate of the pages, and it decrease the updating pressure of the crawler
system and enhance freshness rate of the web repository.
The paper mainly proposed a computer cluster based web resource searching
system which used increment updating strategy and controlled clusters to collect and
maintain the web repository. The paper focused on describing the working principal of
the system and gave the designment and realization in detail. Cosine vector parallel
crawling model was used as the load balance strategy of the system. Considering the
elements of CPU, memory, I/O, net bandwidth etc., the system could monitor
information from working notes, and change its dispatching strategy. Combining the
cosine vector parallel crawling model with increment update strategy enhanced the
efficiency of the crawler system.
Key Words ：Web data mining; parallel crawler; increment update
strategy; cosine vector; computer cluster
III
目录
摘 要................................................................................................................................. I
ABSTRACT ..................................................................................................................... II
目录.................................................................................................................................III
第一章 绪论.....................................................................................................................1
§1.1 引言 ....................................................................................................................... 1
§ 1.2 互联网与搜索引擎 .............................................................................................. 1
§1.2.1 互联网的历史与发展.....................................................................................1
§1.2.2 搜索引擎分类.................................................................................................2
§1.3 课题的来源及意义 ............................................................................................... 4
§1.4 论文的主要工作和组织结构 ............................................................................... 5
第二章 网络爬虫综述.....................................................................................................6
§2.1 网络爬虫的产生和发展 ....................................................................................... 6
§2.2 通用网络爬虫模型 ............................................................................................... 7
§2.2.1 通用网络爬虫结构.........................................................................................7
§2.2.2 通用网络爬虫的主要技术问题.....................................................................8
§2.3 网络爬虫的热点技术 ........................................................................................... 9
§2.3.1 聚焦爬虫的工作原理和关键技术.................................................................9
§2.3.2 个性化智能爬虫...........................................................................................12
§2.3.3 分布式网络爬虫...........................................................................................15
§2.3.4 网络爬虫网页分析算法...............................................................................18
§2.4 本章小结 ............................................................................................................. 20
第三章 系统涉及的相关技术及其解决方案...............................................................21
§3.1 HTTP 协议 .......................................................................................................... 21
§3.2 网页处理背景知识 ............................................................................................. 22
§3.2.1 HTML 基本概念.......................................................................................... 22
§3.2.2 HTML 标签分类.......................................................................................... 23
§3.3 URL 简介及页面 URL 提取策略 ...................................................................... 25
§3.3.1 URL 简介 ......................................................................................................25
§3.3.2 URL 提取策略 ..............................................................................................27
§3.3.2.1 正则表达式匹配技术...............................................................................28
§3.3.2.2 词法分析器................................................................................................29
§3.4 XML 技术简介 ................................................................................................... 31
§3.4.1 XML 概述.....................................................................................................31
§3.4.2 XML 的优点.................................................................................................32
§3.4.3 XML 解析器简介及比较.............................................................................33
§3.4.3.1 XML 解析器简介......................................................................................33
§3.4.3.2 DOM、SAX 的选择 ................................................................................. 34
IV
§3.4.3.3 使用 DOM 和SAX 处理 XML 性能的比较 ........................................... 36
§3.5 多线程搜索器 .................................................................................................... 36
§3.5.1 多线程技术...................................................................................................36
§3.5.2 多线程爬虫工作方式简述...........................................................................38
§3.5.3 多线程网络爬虫的优化..............................................................................39
§3.5.4 线程管理的实现..........................................................................................39
§3.6 本章小结 ............................................................................................................ 41
第四章 增量并行抓掘策略...........................................................................................42
§4.1 负载均衡 ............................................................................................................. 42
§4.1.1 负载均衡基本问题......................................................................................42
§4.1.2 负载均衡基本算法.......................................................................................43
§4.1.2.1 轮叫调度(Round Robin Scheduling) ....................................................... 43
§4.1.2.2 加权轮叫调度(Weighted Round-Robin Scheduling) ...............................44
§4.1.2.3 最小连接调度(Least-Connection Scheduling) ........................................ 45
§4.1.2.4 加权最小连接调度(Weighted Least-Connection Scheduling) ................ 46
§4.1.2.5 其它负载均衡的基本算法简介...............................................................47
§4.2 爬虫负载信息描述与信息收集策略 ................................................................. 48
§4.2.1 爬虫负载信息描述.......................................................................................48
§4.2.2 爬虫负载信息收集方式...............................................................................49
§4.2.3 爬虫收集负载信息时间控制.......................................................................49
§4.2.4 爬虫信息描述包构建..................................................................................50
§4.3 网络资源增量更新策略 .................................................................................... 51
§4.3.1 基本模型.......................................................................................................51
§4.3.2 变化估测.......................................................................................................52
§4.3.3 估测效率......................................................................................................54
§4.4 系统定义及算法 ................................................................................................ 55
§4.4.1 搜索系统简介...............................................................................................55
§4.4.1.1 网络资源搜索系统结构............................................................................55
§4.4.1.2 系统要求与相关概念................................................................................57
§4.4.2 构建相关向量的定义..................................................................................57
§4.4.3 抓取任务和爬虫节点的能力匹配...............................................................58
§4.4.4 并行算法构建...............................................................................................59
§4.4.4.1 并行算法相关定义...................................................................................59
§4.4.4.2 余弦向量法实现爬虫节点间负载平衡....................................................60
§4.4.4.3 相关算法伪代码描述...............................................................................60
§4.4.5 网页更新频率计算方法..............................................................................62
§4.5 本章小结 ............................................................................................................. 64
第五章 系统设计与实现...............................................................................................65
§5.1 网络资源搜索系统工作原理 ............................................................................. 65
§5.1.1 起始地址选择...............................................................................................66
§5.1.2 漫游空间划分...............................................................................................67
V
§5.1.3 网络资源搜索系统控制原则......................................................................67
§5.2 系统的设计与实现 ............................................................................................. 69
§5.2.1 网络爬虫的结构..........................................................................................69
§5.2.2 系统的工作过程..........................................................................................70
§5.2.3 队列的选择和实现.......................................................................................70
§5.2.3.1 基于内存的队列管理和基于 SQL 的队列管理间的比较 ..................... 70
§5.2.3.2 队列管理实现............................................................................................71
§5.2.4 系统工作流程图..........................................................................................72
§5.2.5 系统信息搜集策略......................................................................................73
§5.2.6 Robot 协议 ....................................................................................................74
§5.2.6.1 Robot 简介 .................................................................................................74
§5.2.6.2 robots.txt 程序流程图 ............................................................................... 75
§5.2.7 搜索信息的种类..........................................................................................77
§5.2.8 网页内容提取..............................................................................................77
§5.2.8.1 HTML 语法分析....................................................................................... 77
§5.2.8.2 网页中信息资源提取...............................................................................78
§5.2.9 Hash 策略解决链接碰撞问题 ..................................................................... 79
§5.2.10 数据库存储策略和文件存储策略对比.....................................................80
§5.3 本章小结 ............................................................................................................. 81
第六章 实验及分析.......................................................................................................82
§ 6.1 实验环境配置 .................................................................................................... 82
§6.1.1 本地文件存储策略......................................................................................82
§6.1.2 软件环境......................................................................................................82
§6.2 实验结论及分析 ................................................................................................. 82
§6.2.1 通过余弦向量法实现爬虫间负载平衡的验证...........................................83
§6.2.2 余弦向量法、轮循法和最小队列法比较...................................................83
§6.2.3 单机抓取页面数和余弦向量法并行抓取页面数对比...............................85
§6.2.4 系统在连续时间段内更新页面状况...........................................................85
§6.3 本章小结 ............................................................................................................. 86
第七章 总结与展望.......................................................................................................87
§7.1 结论 ..................................................................................................................... 87
§7.2 展望 ..................................................................................................................... 87
§7.2.1 评价网页权威性实用性功能.......................................................................87
§7.2.2 模型抽取.......................................................................................................88
§7.2.3 加强网页对于 script 链接的抽取................................................................88
参考文献.........................................................................................................................89
在读期间公开发表的论文和承担科研项目及取得成果.............................................92
致 谢.........................................................................................................................93
第一章 绪论
1
第一章 绪论
§1.1 引言
人类文明的发展，生产力的进步都离不开知识的积累。从古埃及的亚历山大
图书馆，到现代的大英博物馆和美国国会图书馆，以及近代的第一检索电子期刊
馆藏联机(First Search Electronic Collections Online)，人们一直梦想将世界上所有
的知识汇总起来，做成一本反映人类全部文明的百科全书。然而当 Internet 的革
命以及数字图书馆技术的快速发展看来要将这个乌托邦式的梦想付诸实现的时
候，一个更严峻的问题摆在了人们面前，即我们如何利用和开发这个包罗万象的
知识宝库呢？我们如何来翻阅这本厚厚的百科全书呢？
近年来，互联网的规模不断扩大，网上的信息变得异常庞大复杂。搜索引擎
的出现可以帮助用户在网络上方便的查找到自己需要的信息。随着网络的普及，
网络在人们工作生活中的地位越来越重要，人们对搜索引擎也不再满足原来的简
单功能，而是提出了更高的要求，这对搜索引擎提出了更严峻的挑战。现有的搜
索引擎 google(www.google.com)、百度(www.baidu.com)、北大天网(e.pku.edu.cn)、
雅虎(www.yahoo.com)、搜狐(www.sohu.com)等正在网上信息检索发挥着巨大的
作用。这些搜索引擎在给人们提供功能强大的服务的同时，也还存在一些不足。
例如：搜索引擎不具有智能性，搜索引擎不分检索对象等等。
然而，其中最大的瓶颈还是要数搜索引擎抓取网页能力不足。目前，World
Wide Web 上的资源成指数级增长，同时已有的资源又在不断地更新[1]。仅以国内
的Web InfoMall 为例，其规模以平均每天 150 万个网页的速度扩大，5年已经达
到了 24 亿个网页(约1300GB)[2]。为了保证搜索引擎及时、准确地更新信息资料，
要求网络资源搜索系统在尽可能短的时间内对已有的网络信息资源进行抓取。为
了克服这一不足，更多地满足人们的需要，本文提出一种采用机群架构的网络资
源搜索系统，针对机群的特性，对网络资源搜索系统的设计和实现进行了探讨。
§1.2 互联网与搜索引擎
§1.2.1 互联网的历史与发展
1958 年1月7日，美国政府由于国防需要，在五角大楼成立了国防前沿研究
项目署(ARPA)。1960 年，ARPA 研发了第一个计算机互联网络 ARPA 网，1974
年ARPA 的鲍勃•凯恩和斯坦福的温登•泽夫提出 TCP/IP 协议[3]，并在 1983 年将
摘要：

I摘要Web信息的急速膨胀，在给人们提供丰富的资源的同时，又使人们在对如何有效使用它们方面面临巨大的挑战。作为检索服务的基础和组成部分，Web信息采集正发挥着举足轻重的作用。网络资源搜索系统是Web搜索引擎的前端，负责在网络上搜集所需的信息资源。同时，为了保证搜索引擎及时、准确地更新信息资料，也要求系统在尽可能短的时间内对网络资源进行更新。资源是否获得及时的更新将直接影响其检索的准确性。单主机资源搜索系统受到了单机硬件性能和操作系统的限制，难以进一步发展，并行资源搜索系统已成为必然的选择。利用并行计算模型，计算结点并行工作以提高处理能力的特点，将更新任务分配到适合的计算节点运行，可以较好的处理...

展开>> 收起<<
采用机群架构的网络资源搜索系统.pdf

共96页,预览10页

还剩页未读， 继续阅读

相关推荐

更多
立即下载
作者：侯斌 分类：高等教育资料 价格：15积分 属性：96 页 大小：1.67MB 格式：PDF 时间：2024-11-19

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

推荐作者

热门标签

/ 96
评分 收藏
分享
立即下载 VIP免费下载
客服
关注