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

VIP免费
3.0 侯斌 2024-11-19 4 4 1.67MB 96 页 15积分
侵权投诉
I
摘 要
Web 信息的急速膨胀,在给人们提供丰富的资源的同时,又使人们在对如何
有效使用它们方面面临巨大的挑战。作为检索服务的基础和组成部分,Web 信息采
集正发挥着举足轻重的作用。
网络资源搜索系统是 Web 搜索引擎的前端,负责在网络上搜集所需的信息资
源。同时,为了保证搜索引擎及时、准确地更新信息资料,也要求系统在尽可能
短的时间内对网络资源进行更新。资源是否获得及时的更新将直接影响其检索的
准确性。
单主机资源搜索系统受到了单机硬件性能和操作系统的限制,难以进一步发
展,并行资源搜索系统已成为必然的选择。利用并行计算模型,计算结点并行工
作以提高处理能力的特点,将更新任务分配到适合的计算节点运行,可以较好的
处理批量网络资源更新问题。此外,对于计算结点的添加、减少,能自动进行任
务分配调整,也有助于提升系统的可扩展性。增量更新技术通过对网页更新度的
预估,减少了系统更新页面的工作量,提升页面的新鲜度。
本课题提出了一个采用机群架构的网络资源搜索系统,资源搜索系统使用增
量更新方法,控制整个机群,实现对网络资源的收集和更新维护。本文重点描述
了系统的工作原理,并在此基础之上给出了系统的设计和实现。系统通过基于向
量空散列实现务的衡,均衡 CPUMEMORY、I/ONET
(网络带宽)等因素,动态获取各计算节点的运行状况,实现动态监控和任务分
配调度策略的改变。并通过将夹角余弦向量法与增量更新思想相结合,提高了网
络资源搜索系统的效率。
关键词: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 DOMSAX 的选择 ................................................................................. 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 17日,美国政府由于国防需要,在五角大楼成立了国防前沿研究
(ARPA)1960 ARPA 研发了第一个计算机互联网络 ARPA 网,1974
ARPA 的鲍勃•凯恩和斯坦福的温登•泽夫提出 TCP/IP 协议[3],并在 1983 年将
采用机群架构的网络资源搜索系
2
ARPA 网的核心协议由 NCP[4]改变为 TCP/IP,即现在的互联网基础协议。在 1986
年,美国国家科学基金会〔National Science FoundationNSF) 建立了大学之间互
联的骨干网络 NSFnet这是因特网历史上重要的一步。由于 NSF 网对全社会开放,
得到了极大的发展,迅速取代 ARPA 网,成为国际互联网络的主干网。1994 年,
NSFNET 转为商业运营。
在互联网发展的同时,1991 86日,Tim Berners Lee CERN(欧洲原子
能研究组织,European Organization for Nuclear Research)经过两年的努力,终于在
新闻组上发布 world wide web 项目,即今天的万维网。万维网通过 HTML(Hyper
Text Marker Language)标记语言编写网页,通过超链接把网页组织在一起,而这些
网页也会链接到更多得其他网站,这样就将整个万维网链接起来,从而可以简单
方便的互相访问。
万维网一经推出就得到了极快的发展,如今已经成为互联网上最重要的应用。
各种传统的应用分分向 WWW 整合,比如传统的 EmailBBS 等网络系统。另一
方面,新的基于 WWW 的应用也层出不穷,比如 BlogWiki 等等。经历了十几年
的发展,WWW 正变得更加繁荣。
§1.2.2 搜索引擎分类
随着 WWW 内容越来越繁多,人们查找想要的内容也变得越来越困难,互联
网搜索引擎的出现很大程度上解决了这个问题。通常人们把目录检索系统也视为
搜索引擎,比如很著名的雅虎 Web 目录。但是它与本文所研究的搜索引擎存在着
很大的差别,很多学者也认为它并不是严格意义上的搜索引擎。搜索引擎的一个
重要特点是,根据要检索的内容构造索引倒排表。查询时从倒排表索引中找到相
关内容的文档,这是目录检索系统并不具备的。搜索引擎的分类方式很多,目前
也没有很统一的分类表。本文在参考了很多搜索引擎分类,并考察了目前广泛应
用的搜索引擎系统后,总结出如下分类:
1)按照搜索的范围,搜索引擎可以分为:
A桌面搜索引擎。桌面搜索引擎的目的为了方便个人电脑用户查找自己计算
机上的文件,通过对个人电脑上的文件建立索引,加快查找速度。目前 Google
及其他几家公司都已经推出,或者正在开发桌面搜索引擎产品。
B企业搜索引擎。企业搜索引擎主要是针对企业用户对企业局域网和其他共
享资源建立索引,方便企业用户查找内部资源。目前 GoogleIBM 等几家公司
经推出了相关产品。
C互联网搜索引擎。面向整个互联网资源的搜索引擎,通常由爬虫机器人自
第一章 绪论
3
动从互联网搜集资源,然后建立索引,供用户查询。目前己有一大批互联网搜索
引擎厂商推出了相应产品,如 GoogleMsn,百度等等。
2)按照搜索的文档类型,搜索引擎又可以分为:
A网页搜索。网页搜索是目前互联网搜索引擎最主要的搜索内容,搜索内容
集中于互联网页面。
B图片搜索,图片搜索是近几年出现的针对互联网图片的一种搜索,目前技
术能力的限制,图片搜索还不能根据图片画面内容来搜索,只能通过图片所出现
的上下文文字,以及图片所包含的元数据信息来搜索。
C音频搜索,与图片搜索类似,音频搜索主要检索互联网上出现的各种音频
文件,如 mp3 等。由于音频文件一般都有元数据信息,因此建立索引检索比较容
易。另外对于歌曲,往往还会有相应的歌词搜索。
D.视频搜索。视频搜索是最近几年才出现的,与图片搜索和音频搜索类似,
搜索内容集中于视频短片。视频搜索的推出一方面得益于搜索技术的日益成熟,
另一方面是由于宽带互联网的推广。
E文档搜索。文档搜索一般应用于桌面或企业搜索引擎中,搜索的内容主要
限于常用的文档类型,比如 WordExcelPPTPDF,以及电子邮件等文件。
3)按照搜索的互联网内容,可以分为:
A.一般网页搜索即针对普通网页的搜索引擎。
B新闻搜索,主要针对实时新闻内容,搜索引擎往往爬行大量新闻门户网站,
对爬行得到的大量新闻内容建立索引,供用户搜索。另外搜索引擎还往往对新闻
资讯进行聚合,推出新闻服务。
CBT 搜索,由于 P2P 技术的流行,BT 搜索也应运而生,专门针对 BT 种子
发布的一种搜索引擎,往往会汇集很多 BT 种子发布网站的种子供用户搜索。
DRSS 搜索,随着 RSS 技术的流行,也出现了很多相应的 RSS 搜索引擎。
EBlog 搜索,由于 Blog 的流行,很多搜索引擎厂商也推出了相应的 Blog
索引擎。Blog 往往都具有类似的信息结构,并且大部分可以都通过 RSS 发布,更
新速度快,因此搜索引擎厂商往往针对 Blog 推出专门的搜索引擎。
F学术搜索,很多科研工作者在研究某个课题时,往往需要查阅大量的论文,
学习其他工作者的研究成果。虽然很多杂志社和专门的学术数据中心都有专门的
学术论文搜索引擎,但是下载论文往往需要支付一定的费用,并且这些系统各不
相通,用户往往需要查阅很多个这种数据中心才能得到比较全面的资料。学术搜
索针对这一需求,利用爬虫技术自动从互联网上获取大量论文资料,建立索引。
由于很多论文作者会把自己的论文发布到自己的个人主页上,从这些地方就可以
采用机群架构的网络资源搜索系
4
免费下载论文了。
4)按照搜索内容所属的行业,可以分为:通用搜索引擎和行业搜索引擎。
通用搜索引擎即针对普通网页的搜索引擎,而行业搜索引擎则是指针对某一行业
信息的专门搜索引擎,比如工作就业,商品等。
5)按照其他标准分类:
当然,搜索引擎的分类方式不止以上几种。例如:有一种分类方法是按照搜
索结果来源,一般搜索引擎都是从互联网爬行网页,建立索引,然后查询索引数
据库得到搜索结果,返回给用户。这种元搜索引擎不同于其它搜索引擎,它本身
不爬行互联网网页,其搜索结果来源于其他搜索引擎。用户搜索时,它将搜索语
句发送给其他搜索引擎,其他搜索引擎返回结果后,元搜索引擎将这些结果整合
在一起返回给用户。元搜索引擎极大的提高了搜索的查全率,但是搜索效率方面
要低一些。
§1.3 课题的来源及意义
网络资源搜索系统,即网络爬虫系统,Web 搜索引擎的前端,负责搜集 Web
上所需的信息资源。搜索引擎中信息的搜集量和搜索的效率是搜索引擎的重要质
量指标。由于目前,WWW 上的资源成指数级的增长,同时已有的资源又在不断
地更新。为了保证搜索引擎及时、准确地更新信息资料,要求网络资源搜索系统
在尽可能短的时间内对已有的网络资源进行更新。系统是否收集了足够的资源,
以及资源是否获得及时的更新,这都将直接影响其检索的准确性。
单主机的网络资源搜索系统由于受到单机硬件性能和操作系统的限制,其搜
集,更新网络资源的速度是有限的,就目前互联网的规模来说,已无法在有效的
时间范围内完成一次更新任务。同时,单机系统的可扩展性差,也使得系统很难
随着互联网的不断增长而扩展。并行网络资源搜索系统[5, 6]采用多台计算机并行工
作,可以提高整个系统的工作效率,且具有良好的扩展性。因而,采用并行抓掘
的网络资源搜索系统已成为必然的选择,利用机群系统控制多台计算机并行抓掘
成为一种可行的方案。基于机群架构的网路资源搜索系统由多个网络爬虫组成,
每个网络爬虫都分别进行 Web 信息搜集。各个网络爬虫之间通过 URL 散列分配策
略相互协调,完成搜集任务。URL 散列分配策略在一定程度上决定了系统的性能。
国内外关于搜索引擎的研究以及正在使用的商业搜索引擎虽然很多,但都没
有专门针对 URL 分配方式进行讨论。国际上,在搜索引擎中采用分布式网络爬虫
比较典型的是 Harvest 系统,其设计时没有考虑搜索信息的速度等指标。Google
是目前较为成功的搜索引擎,其成功之处主要在于后端的 PageRank 设计与实现,
第一章 绪论
5
而对网络爬虫的并行性并未作专门的研究。并且,由于商业机密等因素的影响,
较详细的介绍并行信息采集系统的文章并不多。基于并行 Web 信息采集的理论
还不完善、有待研究。
结合机群模型,计算结点并行工作以提高处理能力的特点,将更新任务分配
到适合的计算节点运行,可以较好的处理批量网络资源更新问题。此外,对于计
算结点的添加、减少,能自动进行任务分配调整,也有助于提升系统的可扩展性。
在此基础上引入增量更新技术[7]使得系统可以通过对网页更新度的预估,减少了网
络资源搜索系统更新页面的工作量,提升页面的新鲜度。
§1.4 论文的主要工作和组织结构
本课题针对并行网络资源搜索系统,通过基于向量空间的散列方法实现机群
任务的负载均衡,通过均衡 CPUMEMORYNet Adapter网卡I/ONET
(网络带宽)等因素,动态获取各计算节点的运行状况,实现动态监控和任务分
配调度策略的改变。理论分析和实践表明,本文提出的基于余弦向量匹配算法的
抓掘任务分配模型具有良好的分配适应性和负载平衡性。使用增量更新方法的网
络资源搜索系统,通过将夹角余弦向量法与增量更新思想相结合,提高了系统的
运行效率。
本论文安排如下:
第一章主要介绍搜索引擎的相关技术发展现状,网络爬虫的意义,以及论文
的研究目标;
第二章主要对网络爬虫进行综述介绍;
第三章简述了系统实现过程中所涉及到的相关技术及相应的解决方案;
第四章论述了增量并行抓掘策略,详细介绍了使用余弦向量法实现抓掘任务
散列,使用增量更新方法提升网页库新鲜率,并给出了相关的算法描述;
第五章论述了系统的设计与实现细节;
第六章通过实验验证了余弦向量匹配算法的抓掘任务分配模型具有良好的
分配适应性和负载平衡性,以及采用机群架构的网络资源搜索系统在实际应用情
况下的可用性这一结论;
第七章总结与展望。
摘要:

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

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

共96页,预览10页

还剩页未读, 继续阅读

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

开通VIP享超值会员特权

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