主题网络爬虫的研究和实现---优秀毕业论文 参考文献 可复制黏贴.pdf

分类号 u d c 题目 英文 一 密 级 学校代码 堇q 垒窆2 武多凄程歹大浮 学位论文 主题网络爬虫的研究和实现 研究生姓名鉴撬 指导教师 姓名 乱l 职称j 塾 整学位 丛 单位名称计算机科学与技术学院邮编 4 3 0 0 7 0 申请学位级别亟 论文提交日期2 q 里曼生 旦论文答辩日期2 q q 生三旦 学位授予单位武汉理工大学学位授予日期 答辩委员会主席鲑盘评阅人 孳盘 至缉熊 2 0 1 1 年5 月 独创性声明 本人声明 所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果 尽我所知 除了文中特别加以标注和致谢的地方外 论文中不包含其他人已经发表或撰写过的研究成果 也不包含为获得 武汉理工大学或其他教育机构的学位或证书而使用过的材料 与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意 签名 二孝畦日期 一二边止矗斗 学位论文使用授权书 本人完全了解武汉理工大学有关保留 使用学位论文的规定 即 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版 允许论文被查阅和借阅 本人授权武汉理工大学可以将本学位论文的 全部内容编入有关数据库进行检索 可以采用影印 缩印或其他复制 手段保存或汇编本学位论文 同时授权经武汉理工大学认可的国家有 关机构或论文数据库使用或收录本学位论文 并向社会公众提供信息 服务 保密的论文在解密后应遵守此规定 研究生 签名 琳透导师 签名 也警粝日期 垆l i 岁 胡 一 摘要 随着网络信息时代的不断发展 广泛分布于因特网上的各类信息深刻地影响 着人类生活的各个方面 如今 人们能够通过浏览网页的方式来查询其所需的各 类目标信息 与此同时 由于因特网上的信息成千上万 信息量处于高速膨胀的 状态 使得如何通过网页便捷地查询到目标信息这一问题更为凸现 在信息多元化发展的趋势之下 通用搜索引擎在很大程度上为人们在因特网 上查找信息提供方便 但也暴露出种种不足 例如 查准率偏低 信息内容相对 陈旧 信息分布范围不均衡等 因此 主题搜索引擎技术成为新的研究方向 它 专门为特定领域 特定人群或特定需求提供具有一定价值的信息资源和检索服 务 主题爬虫作为主题搜索引擎的信息抓取部分 负责对与用户感兴趣的某一主 题相关的网页进行抓取 本文主要通过六个章节来分析主题爬虫的设计和实现 第一章主要阐述了搜 索引擎的发展过程 网络爬虫在搜索引擎中的作用 简述了国内外的研究现状以 及课题的研究意义 第二章是本文的理论基础 首先阐述了搜索引擎的基本原理 随后基于对比通用爬虫和主题爬虫找出其差异之处及其各自的特点之上 重点讨 论了两种爬虫的体系结构和基本工作原理 第三章主要讨论了主题爬虫领域关键 技术的研究和改进 包括文本特征项的提取方法 搜索策略以及网页消重技术的 研究 并提出基于主题相关度的p a g e r a n k 算法的改进 第四章主要探讨主题爬 虫的系统设计与实现 主要包括网页抓取模块 网页分析模块 中文分词以及 u r l 管理等模块 第五章描述了主题爬虫系统的界面与操作细节 以及利用该 系统进行的实验过程 通过对实验数据的分析 证明了前述章节中各个理论的合 理性与有效性 第六章对前面章节内容进行小结与归纳 并提出本文的创新点与 局限性 实验结果证明 该主题爬虫在稳定运行的同时有着更好的收获率 极大地减 少了时间和存储空间 在时间上的优势保证了网页的及时更新 此外用户查找时 得到的冗余和无用信息也较少 具有更高的查准率 关键词 主题爬虫 搜索策略 相关度模型 查准率 查全率 a b s t r a c t w i t ht h ei n f o r m a t i o na g e sd e v e l o p i n gg r a d u a l l y v a r i o u st y p e so fi n f o r m a t i o n w h i c hw i d e l yd i s t r i b u t e do nt h ei n t e r a c th a v ea f f e c t i n ga l la s p e c t so fh u m a nl i f e t o d a y p e o p l ec a nc h e c ka l lt y p e so ft a r g e ti n f o r m a t i o nw i mb r o w s i n gw e b sb y t h e m s e l v e s a tt h es a m et i m e t h o u s a n d so fi n f o r m a t i o ne x i s t i n go nt h ei n t e m e ti si na s t a t eo fh i g h s p e e de x p a n s i o n w h i c hp r o t r u d e st h ep r o b l e mo fh o wt og e tt h et a r g e t i n f o r m a t i o nc o n v e n i e n t l yb yb r o w s i n gw e b s w i t ht h ed e v e l o p m e n tt r e n do fi n f o r m a t i o nd i v e r s i t y g e n e r a ls e a r c he n g i n e w h i c hf a c i l i t a t e sp e o p l et oc h e c ki n f o r m a t i o no ni n t e r n e t a l s oh a ss o m es h o r t c o m i n g s s u c ha sl o wp r e c i s i o n s t a l ec o n t e n t sa n du n e v e nd i s t r i b u t i o no fi n f o r m a t i o n t o p i c s s e a r c he n g i n ei san e wr e s e a r c hm e t h o dw h i c hp r o v i d e sv a l u a b l ei n f o r m a t i o n r e s o u r c e sa n dr e l a t e ds e r v i c e st ot h es p e c i f i ca r e a s g r o u p so fp e o p l eo rn e e d s a st h e p a r to f i n f o r m a t i o nc o l l e c t i o no ft o p i c ss e a r c he n g i n e t h et o p i cc r a w lg r a b st h er e l a t e d w e b so f u s e r s i n t e r e s t t h i st h e s i si sd i v i d e di n t os i xc h a p t e r st oa n a l y z et h ed e s i g na n di m p l e m e n t a t i o n o ft h et o p i cc r a w l t h ef i r s tc h a p t e rd e s c r i b e st h ed e v e l o p m e n tp r o c e s so ft h es e a r c h e n g i n ea n dt h er o l eo fc r a w li nt h es e a r c he n g i n e i ta l s oa n a l y z e st h es t a t u sa n dt h e s i g n i f i e a n c e s o ft h er e s e a r c h t h es e c o n d c h a p t e ri s t h et h e o r e t i c a lb a s i so f r e s e a r c h i n go nt h et o p i cc r a w l w ef i r s ti n t r o d u c et h er e l e v a n tt h e o r i e so ft h er e s e a r c h e n g i n e a n dt h e n b a s e do nf i n d i n gt h ed i f f e r e n c e sa n dt h ef e a t u r e sb e t w e e nt h e s et w o c r a w l s w ec a nf o c u so nt h ea r c h i t e c t u r ea n dt h eb a s i cw o r k i n gp r i n c i p l e sa b o u tt h e g e n e r a l c r a w la n dt h et o p i cc r a w l n en l i r dc h a p t e re x p l o r e st h er e s e a r c ha n d i m p r o v e m e n to ft h ek e yt e c h n o l o g i e sa b o u tt h ea r e ao f t h et o p i cc r a w lw h i c hi n c l u d e s t h ee x t r a c t i o no ft e x tf e a t u r e s s e a r c hs t r a t e g i e sa n dt h es k i l lo ff i l t e r i n gw e bp a g e s i t a l s op r o p o s e st h ei m p r o v e m e n tm e t h o do ft h ep a g e r a n kb a s e do nt h es u b j e c t r e l e v a n c e t h ef o r t hc h a p t e rh a sag e n e r a la n a l y s i sa b o u tt h es y s t e md e s i g na n d i m p l e m e n t a t i o no f t h et o p i cc r a w lw h i c hc o n s i s to fs o m em o d u l e sa b o u tt h eg r a bp a g e t h ew e ba n a l y t i c s c h i n e s ew o r ds e g m e n t a t i o na n dt h eu r lm a n a g e m e n t i nt h ef i f t h c h a p t e r w ew i l lr e v e a lt h ei n t e r f a c ea n dt h eo p e r a t i o nd e t a i l so ft h et o p i cc r a w l s y s t e ma n dw ec a ns h o wt h ee x p e r i m e n tp r o g r e s sb a s e do nt h i ss y s t e m t h e nf r o m a b o v ee x p e r i m e n tr e s u l t sa n dd a t a w ec a nd e m o n s t r a t et h er a t i o n a l i t ya n dt h e h 毋 e 舵c t i v e n e s so ft h er e s e a r c h t h el a s tc h a p t e rh a sas u m m a r ya b o u tt h ep r e w o u s s e c t i o n sa n dp r o p o s e st h el i m i t a t i o n sa n dt h ei n n o v a t i o n so f t h i st h e s i s e x p e r i m e n t a lr e s u l t ss h o wt h a tt h et o p i cc r a w lh a sb e t t e rh a r v e s t i n gr a t ew i t h s t a b l eo p e r a t i o n i ta l s oc a nr e d u c et h et i m ea n dt h es t o r a g es p a c ea n da l s ou p d a t et h e w e b si nt i m e i na d d i t i o n i tp r o v i d e st h eh i g h e rs e a r c hp r e c i s i o na n dl e s sr e d u n d a n t i n f o r m a t i o nt ou s e l 8 k e yw o r d s t o p i cc r a w l s e a r c hs t r a t e g y r e l e v a n c ym o d e l p r e c i s i o n r e c a l l h i 目录 摘j 要 i a b s t r a c t i 第1 章绪论 l 1 1概j 苤 1 1 2国内外研究现状 l 1 3本文的主要研究内容及组织结构 3 第2 章网络爬虫的体系结构 4 2 1搜索引擎概述 4 2 1 1 搜索引擎的工作原理 4 2 1 2 搜索引擎的分类 5 2 2 通用爬虫的体系结构 6 2 3主题爬虫的体系结构 8 2 4本章小结 1 0 第3 章主题爬虫关键技术的研究 1 l 3 1 文本特征项提取方法的研究 1 l 3 2主题爬虫搜索策略的研究 1 3 3 2 1 广度和深度优先搜索策略 1 4 3 2 2 基于内容的搜索策略 1 5 3 2 3 基于链接的搜索策略 一1 6 3 3页面消重技术分析 1 9 3 3 1u r l 消重 2 0 3 3 2 内容消重 2 l 3 4本章小结 一2 l 第4 章数码相机主题爬虫系统设计与分析 2 2 4 1开发工具简介 2 2 4 1 1h e r i t r i 2 2 4 1 2s p r i n g 2 3 4 2系统总体设计 2 4 4 2 1 系统模块设计 2 4 4 2 2 系统流程设计 2 5 一 4 3数码相机初始种子集选择 2 7 4 4页面抓取模块 2 7 4 4 1 页面抓取模块流程 2 7 4 4 2 页面抓取模块分析与设计 2 9 4 5页面分析模块 3 2 4 5 1 页面主题信息提取 3 2 4 5 2 页面u r l 解析实现 3 3 4 6主题p r 值算法计算模块 3 5 4 6 1 主题相关度模型 3 5 4 6 2 基于主题相关度p a g e r a n k 算法的改进 3 5 4 7 中文分词模块 3 6 4 7 1 中文分词算法 3 6 4 7 2 中文分词模块实现 3 7 4 8u r l 管理模块 3 9 4 9数据库设计 4 0 4 1 0本章小结 4 l 第5 章系统界面和实验数据分析 4 2 5 1系统界面 4 2 5 1 1 系统平台 4 2 5 1 2 系统界面以及操作流程 4 2 5 2 实验数据分析 4 5 5 3本章小结 4 6 第6 章结束语 4 7 6 1 全文总结 4 7 6 2 问题与展望 4 7 致 射 4 9 参考文献 5 0 武汉理工大学硕士学位论文 1 1 概述 第1 章绪论 目前 因特网上的信息量正处于一种高速膨胀的状态 如何在无比巨大的 信息空间里快速查找并获取人们所需要的信息已成为信息检索方面至关重要的 问题之一 网络搜索引擎 1 在网络信息资源查找中起到了十分重要的作用 它可 以帮助人们检索网络信息并从中找到人们想要的信息 但是许多主流的搜索引擎 比如g o o g l e 百度等 都不是专门为检索特定领域资料而设计的 往往不能满 足有一些特殊的用户需求 针对这个问题 专家们提出了针对特定领域的主题搜 索引擎或称垂直搜索引擎 该搜索引擎的设计用意主要是为了满足特定领域 人 群的特定需求 可以为这些用户提供具备较高专业价值的信息服务与检索服务 主题网络爬虫作为主题搜索引擎的重要组成部分 负责抓取数据并且为主 题搜索引擎提供索引 主题网络爬虫是根据主题判断算法过滤掉与主题不相关的 网页链接 将抓取到的主题相关的页面链接放入等待爬行队列之中 并且根据特 定的主题搜索策略从等待爬行队列中选取要继续抓取的网页链接 不断循环上述 的过程 直到满足结束抓取条件 在抓取过程中 主题网络爬虫必须解决选取网 页u r l 的策略和计算网页和主题的相关度这两个方面的问题 本文通过结合基 于内容和链接两种搜索策略对经典的搜索策略进行改进并将其应用于网页链接 的选取策略 实现了一个数码相机主题网络爬虫系统 1 2 国内外研究现状 9 0 年代初 初代搜索引擎出现并且产生了最早的网络爬虫 该网络爬虫工 作方式主要基于网络拓扑图算法 即将整个网络作为一个巨大的有向连通图 采 用深度或广度优先的遍历方式 爬行整个网络 爬虫程序首先选择一个初始u r l 的集合作为爬虫的种子节点 然后检索与种子节点对应的网页 并提取网页中的 链接加入待爬行队列 不断循环以上步骤从而达到检索整个网络的目的 现如今 因特网上的网页数十分巨大 导致任何一个网络爬虫在有限的时间 内都无法对因特网上的所有网页完全遍历 所以如果一个网络爬虫要提高爬行效 率必须优先访问那些相对比较重要的网页 如何针对一个网页的重要性i 列来调整 爬行策略成为所有爬虫都需要解决的关键问题 基于主题相关度的爬行算法 通常情况下 相同或相似的网页会通过各种链 武汉理工大学硕士学位论文 接聚集在一起 形成一个主题网页团 因此 采用网页内科4 来进行网页重要性 评价的主题爬虫系统通过计算出每个网页与主题相关的程度 来评价该网页重要 性 并优先选择其中重要性评价高的网页 提取该网页上的u r l 链接进行下一 步爬行 基于链接权重f 5 的爬行算法 最具代表性的有p a g e r a n k 算法1 6 和h i t s 算法 7 1 等 p a g e r a n k 算法是美国斯坦福大学l a r r yp a g e 等人提出 该算法对于网页 除了基于内容的评价以外 还附加一个p r e s t i g e 值 简单来说 p a g e r a n k 算法把 爬行到的这个网络抽象为一个有向拓扑图 每个网页看成有向拓扑图中的节点 父网页到子网页之间存在一条有向边 网页的p r e s t i g e 值等于指向该网页所有父 链接p r e s t i g e 之和 简单来说 该算法假定被多个网页所指向的网页将具有较高 的权重 爬虫系统应该优先访问这些网页 h i t s 算法是p a g c r a n k 的一种改进算 法 h i t s 算法为每个网页都附加了h u b s 值和a u t h o i r t y 值 引 其中 a u t h o i r t y 值代表了网页被许多网页所指向的程度 h u b s 值则代表了网页指向其他有价值 网页的能力 这两个值在h i t s 计算过程中相互影响 并且都通过爬行网络有向 拓扑图计算进行迭代并稳定下来 以上阐述的这两种算法都是比较经典的利用网 页链接来评价网页权重的算法 其中p a g e r a n k 算法已经被很多大型搜索引擎所 采用 基于网页权重评价的爬行算法 例如b e s t f i s h 算法 9 1 等 这种算法虽然在很 大程度上可以提升主题爬虫系统搜索主题网页的能力 不过都存在一个比较大的 缺点即在对于优先选择的网页的处理上 它们选择遍历该网页上的所有链接 但 是大多数的与主题有关网页上很大一部分的链接都无法链接到相关的主题网页 因此 这种以网页为单位来拓展的爬行算法 1 0 1 严重制约了爬虫系统的性能 这 种算法假定网络是强连通的 但是事实上网络链接具有很大的随机性 这种强连 通性的假定比较牵强 并且还存在许多其他的因素干扰 例如 有些站点通过作 弊的手段提高网站权威值 人们浏览网页的时候可以通过多种元素来判断选择哪个链接继续浏览 其中 比较重要的元素就是锚文本 a n c h o rt e x t 锚文本实际上就是链接文本 比如 在某个综合网站上把h t t p l l w w w s i n a e o m 作为新浪的链接 用户可以通过点击网 站上的 新浪 进入h t t p w w w s i n a c o m 网页 那么 新浪 就是该链接的锚文 本 锚文本可以作为锚文本所指网页内容的评价 通常情况 网页中的链接都会 和网页内容相关 因此 分析锚文本信息对于主题爬虫系统十分重要 爬虫系统 可以通过锚文本对链接所指向的网页是否与主题相关进行预测 除以上阐述的爬行算法之外 主题爬行领域中还有一些通过进化模型建立起 来的爬行算法 这种进化模型的算法基于 适者生存一 自然进化 的思想 2 武汉理工大学硕士学位论文 将爬虫系统划分为多个子系统各自爬行 每个子系统具有一定的活跃度或生命 值 并随着各自收获主题相关网页的数量 子系统活跃度不断发生变化 收获主 题相关网页多的子系统能够持续较长的时间 并且有可能复制出新的子系统 而 收获主题相关网页比较少的子系统活跃度慢慢降低 最后销毁 以上阐述了几种主要的主题爬行相关技术 本文将通过一些相关信息 深入 讨论主题爬虫技术 1 3 本文的主要研究内容及组织结构 本文拟在介绍搜索引擎快速发展的基础上 设计出一个数码相机主题网络爬 虫系统并对其加以实现 深入的探讨了设计与实现过程中所包含的关键技术与分 析方法 例如网页抓取 中文分词技术 主题相似度的辨别 页面内容分析 搜 索策略的研究方法与改进措施等 全文共分为六个章节 具体内容如下 第一章主要对搜索引擎的发展历程作了简要回顾 介绍了网络爬虫在搜索引 擎中的地位 并简要阐述了与本文主题相关的国内外研究现状及研究意义 第二章对搜索引擎技术的工作原理进行剖析 对比爬虫与主题爬虫之间的相 似之处与不同点 着重分析了两种爬虫的基本工作原理及体系结构 第三章对主题爬虫领域的关键技术展开细致 深入的讨论 主要包括初始种 子选择方法 文本特征项的提取方法 搜索策略 中文分词技术以及网页消重技 术的研究 第四章主要讨论了主题爬虫的系统设计 对系统设计中的网页抓取 网页分 析 中文分词技术以及u r l 管理等模块技术问题进行重点研究和探讨 第五章描述了数码相机主题爬虫系统的界面以及操作细节 通过分析实验数 据 体现该系统在搜索策略上的优势 第六章作为全文的总结性章节 对本文的研究工作作系统性总结 并提出了 有待改进的地方以及今后研究工作的具体方向 3 武汉理工大学硕士学位论文 第2 章网络爬虫的体系结构 2 1 搜索引擎概述 2 1 1 搜索引擎的工作原理 通常情况下 搜索引擎系统的工作流程相对来说比较复杂 首先需要对因特 网上的网页进行尽可能全面地抓取 建立原始的网页数据库 然后将抓取的目标 网页进行预处理 形成倒排文件 用户输入查询请求 通过查询倒排文件定位相 关网页并呈现给用户 搜索引擎的工作流程大体上可以归纳成三个阶段 即爬行 和抓取 网页预处理和查询排名 如图2 1 图2 1 搜索引擎工作流程 搜索引擎的工作过程大体上可以分成三个阶段 1 2 1 爬行和抓取是完成搜索引擎工作的第一个流程 搜索引擎爬虫通过跟踪链接 发出访问网页的请求 并将获得的网页h t m l 代码存入原始网页数据库 为了 抓取尽可能多的网页 将整个因特网上相互交织成网状的网站及网页看成是一个 有向图集合 搜索引擎爬虫通过一定的爬行遍历策略跟踪网页上的链接并建立一 个地址库 爬虫抓取网页后 从h t m l 中提取出新的链接u r l 判定是否存入 地址库中以避免重复爬行和抓取网址 可以通过用户自主提交 定期抓取或增量 抓取等方式进行爬行和抓取 定期维护以便及时发现网页的新特征 抓取新网页 去除过期网页或己不存在的网页 网页预处理阶段为后续的查询排名提供良好的数据结构支持准备工作 这一 阶段最主要的步骤是对数万亿级别以上的网页数进行系统的索引 索引程序对抓 取来的网页h t m l 代码进行网页文字提取 中文分词 停止此过滤等 并去除 诸如h t m l 格式标签 j a v a s e r i p t 程序等无法用于排名的内容 查询排名阶段直接面向用户 将搜索引擎爬虫抓取的网页通过倒排索引处理 后直接提供给用户进行检索 用户输入关键词 排名程序调用索引库数据 计算 4 武汉理工大学硕士学位论文 关键词相关性 将查询和文本进行匹配 然后按一定格式生成检索结果网页排序 目前搜索引擎给出查询结果排序的主要方法包括g o o g l e 的p a g e r a n k 算法 k l e i n b e r g 的h i t s 算法等 2 1 2 搜索引擎的分类 搜索引擎的分类主要有以下几种 l 全文索引式搜索引擎 全文索引式搜索引擎是现今主流的搜索引擎 国内代表有b a i d u 国外代表 有g o o g l e 全文索引式搜索引擎主要是将从因特网上提取到的与每个网页相关 的基本信息集中起来建立一个镜像数据库 借助检索数据库得到与查询条件相匹 配的全部记录 并按照一定的排列顺序呈现给用户 全文搜索引擎按检索结果的来源角度来分 具体可以分为以下两大类 一类 搜索引擎其自身具备相对独立的网页提取 页面索引及检索系统 i n d e x e r 也 具备独立的爬虫 c r a w l e r 机器人 r o b o t 程序或者 蜘蛛 s p i d e r 程序 同时还具备独立的网页数据库 通过该网页数据库可以直接从中提取检索 信息 在国内外的大型全文搜索引擎中 b a i d u 和g o o g l e 正是此类搜索引擎的典 型代表 另一类引擎其自身并不具备完整独立的数据库 必须借助于其他搜索引 擎的页面数据库 通过对该页面数据库进行检索并提取出相关的检索信息 此类 搜索引擎的代表如l y c o s 2 垂直搜索引擎 2 0 0 6 年互联网上逐渐出现了一类新的搜索引擎 即垂直搜索引擎 1 4 l 垂直 搜索与通用的网页搜索引擎相比 它主要是设计为了服务特定的检索领域和检索 需求 如影视检索 票务检索 图书检索等 其专业化服务使其在这些特定的搜 索领域 1 5 具有更为出色的表现 此外 垂直搜索较通用的网页搜索引擎要求相 对较低的硬件成本 面向的用户需求相对特定化 查询的方式也可以是多种多样 3 元搜索引擎 用户通过向元搜索引擎 1 3 1 输入检索请求 该搜索引擎系统可以同时通过检 索多个其他搜索引擎系统的网页数据库提取相关搜索结果 并将其按特定顺序排 列呈现给用户 国内外的元搜索引擎的代表有d o g p i l e h t t p w w w d o g p i l e c o r n i n f o s p a c e h t t p w w w i n f o s p a c e c o r n v i v i s i m o h t t p v i v i s i m o t o m 等 搜星是比较具有 代表性的中文元搜索 元搜索引擎的检索结果按一定的排序呈现 这种排列过程 有的是基于来源排列检索结果 此类代表有d o g p i l e 有的依据特定规则排列 如v i v i s i m o 5 武汉理工大学硕士学位论文 4 目录索引式搜索引擎 目录索引式搜索引擎虽然具备一定的检索功能 但并不是严格意义上的搜索 引擎 它所实现的功能主要是借助一些搜索目录或者是分类目录来划分网站链接 列表 用户可以选择借助于对这些分类目录进行检索来获取所需要的相关信息和 资料 而不需要通过关键词 k e y w o r d s 的检索来获取目标信息 如今 新浪 雅虎等都是目录索引式搜索引擎的的典型代表 5 其他非主流搜索引擎形式 m s ns e a r c h a o ls a e r c h 等门户搜索引擎在提供检索服务时 由于其自身 不具备独立的网页数据库也没有独立的分类目录 因而这类引擎的检索结果只能 借助于其他搜索引擎来完成 集合式搜索引擎与元搜索引擎有着一定相似之处 也存在很大的差异 诸如 它并不能同时对多个大型的全文搜索引擎系统进行同步检索 而需要由用户在其 提供的常用搜索引擎列表中手动确定一个搜索引擎 然后对该搜索引擎中的数据 库进行检索 h o t b o t 就是此类搜索引擎的代表 免费链接列表 f r e ef o r a l ll i n k s f f a 通常只提供滚动链接条目 少部分 存在着比较简单的分类目录 2 2 通用爬虫的体系结构 因特网上的所有网页连接起来交织成网状 它们之间通过链接相互联系起 来 如果把网页作为网状物的节点 链接作为路径 网络爬虫将依据特定的遍历 策略 顺着路径对不同的节点进行遍历 网络爬虫作为搜索引擎系统的抓取模块 通过抓取网络页面 为之后的网页解析模块提供分析数据 由于在各种搜索引擎 系统之间存在不同的功能需求 其下的各种网络爬虫的工作方式也具有很大差 异 通用搜索引擎系统提供所有网页的全文检索 因此对服务于通用搜索引擎系 统的网络爬虫也提出了相对强大的功能要求 网络爬虫的爬行路径必须尽可能全 面的覆盖网络 其抓取范围也必须尽可能的扩大 这样才能抓取尽可能多的网页 从而丰富数据来源 可以说通用爬虫的最终目标是完全遍历因特网上的全部网 页 但实际上这无法实现 仅仅只是一种理想的假设 一方面当通用爬虫在爬行 网络页面的路径中网页的数量也在不断增长 新的网页不断的出现 许多旧的网 页也不断过期 另一方面由于网络拓扑结构十分复杂 节点数量过于巨大 目前 的搜索策略无法全部遍历 即便可以实现也由于爬行时间太长 抓取的网页很可 能已经更新或过期 因此通用爬虫需要在提高效率以获得更多的抓取量同时 在 资源有限的情况下对重要的网页资源优先访问 通用爬虫系统体系结构如图2 2 6 武汉理工大学硕士学位论文 所示 图2 2 通用爬虫系统体系结构 由此看出 通用爬虫的工作流程为 首先将初始u r l 作为入口 对u r l 进行 解析 根据解析出的w e b 服务器地址建立连接 发送请求和接收网页数据 将 抓取到的网页数据存储于原始网页库 利用链接提取器从其中取出链接信息放入 u r l 库 并从u r l 库中选取待抓取的u r l 放入u r l 队列中 不断循环以上过 程 直到满足条件 系统停止 例如 u r l 库为空 到达最大爬行时间或达到 最大抓取上限等 通用爬虫的实现过程相对比较简单 运行起来比较机械 快速抓取网页成为 其唯一需要解决的问题 众所周知 互联网上的网页数量庞大 每天都会有相当 多的网页内容出现或更新 这便要求通用爬虫对网页库进行周期性地迭代更新 通用爬虫对互联网进行周期性的爬行是为了更有效的保持网页的新鲜度 这给通 用爬虫提出了两个现实性的考验 一方面需要提高通用爬虫爬行的效率 使其尽 可能多的抓取网页 另一方面需要在合理安排资源的前提下 优先抓取那些重要 性程度较高的网页 为解决第一个现实性考验 目前大型通用搜索引擎系统一般都借助于分布式 方式将抓取任务分布到多个子服务器上 多个爬虫进程通过多个子服务器同时产 生 这些爬虫同时进行各自的爬行工作 尽管如此 网络爬虫在其爬行抓取的过 程中由于网络延迟的缘故浪费了相当多的时间 统计数据显示 从请求发送到收 到服务器响应之间的时延为4 0 0 1 0 0 0 m s 时延的长短受到网路带宽的影响 大 型通用搜索引擎系统采用分布式的方式 使扩大了网络的带宽 从而降低了网络 7 武汉理工大学硕士学位论文 时延产生的影响 加快了抓取过程 但是 分布式的实现同时也带来了新问题 各个爬虫并行爬行的同时 必须相互合作 其主要目的是为了避免网页重复访问 的同时又必须减少网页的遗漏 此外 分布式爬行还需要处理在一个系统中究竟 需要有多少台服务器同时工作以及每台服务器有多少线程数等问题 可以说特高 爬行效率并非服务器数量的简单增加就可以实现 网络爬虫相互之间的协作也会 带来额外的开销 爬虫数量太多 就会耗费额外的资源 反而降低了系统整体运 行效率 因此系统开发者需要在额外爬行开销和爬行效率提升之间寻求一个平衡 点 为解决第二个现实性考验 关键是对搜索策略进行优化并且找出评价网页重 要性的方法 如果我们把互联网抽象为一个巨大的有向拓扑图 最通用的遍历方 式有两种 分别是深度优先和广度优先 首先 深度优先作为一种搜索策略方式 主要是通过网络爬虫从初始节点沿某路径或称为边对网络结构中的子节点进行 逐一遍历访问 直至该节点不再具有未被访问的子节点为止 然后返回上一个节 点 选择另一兄弟节点继续爬行 依此方式不断重复循环 另外 广度优先是另 一种搜索策略方式 它主要是按层次划分互联网上的各个节点 先遍历所有起始 节点的下一层次的子节点 再遍历子节点往下层次的子节点 依此类推 一般情 况下 从网页重要性的角度来说 广度优先要好于深度优先 因为当某个页面的 深度很大 那么被用户浏览到的机会很小 因此该页面重要性很低 一般认为 一个重要性高的页面具有如下判定 1 页面深度小 页面的访问率比较高 2 页面镜像度高 页面内容比较热门 在因特网中存在较多副本 3 父页面重要性高 子页面一定程度继承父页面的重要性 4 页面入度大 从而表明被其他页面引用的次数比较多 以上判定 实际上描述了页面之间的链接关系 p a g e r a n k 算法正是从页面 的链接结构角度来评价页面重要性 并被许多大型系统采用 2 3 主题爬虫的体系结构 由于因特网上的页面数不断膨胀 2 0 0 8 年5 月 g o o g l e 宣称其搜索引擎抓 取到因特网上的网页数量超过了1 0 0 0 0 亿 面对不断膨胀的数据量 通用搜索引 擎的工作压力越来越大 研究者开始专注于开发基于领域的主题搜素引擎i i o j 这类搜索引擎系统不仅面向某领域有很深了解的专业用户 同时也面向寻求特殊 信息 爱好特定领域的一般用户 他们希望搜索引擎系统能够过滤掉无关信息 提供某一领域的专业化信息 但是通用搜索引擎系统检索的结果过于宽泛 往往 缺乏系统性 并且包含大量与用户需求相关性较小的网页 在这种情况下 主题 8 武汉理工大学硕士学位论文 搜索引擎系统就更能满足这种系统系搜索的要求 主题搜索引擎系统一般针对特定的领域进行网页检索 并且会选择性地忽视 与搜索主题相关性较小的网页 在主题搜索引擎系统中要求主题爬虫 1 7 1 8 1 在尽可 能多的抓取网页的同时 针对特定的搜索主题对因特网上与搜索主题相关的链接 进行有选择性地提取 准确定位所需要的页面 这个过程需要对网页的实际内容 进行深入分析才能准确辨别 倘若页面与指定的主题相关性极小 则系统自动放 弃保存 反之保留该页面以供索引 这个过程实质上是在网络爬虫抓取模块中 实现一部分原本需要通过预处理模块处理的功能 网页内容分析的目的 主要是 从页面的标题 正文文本以及u r l 链接等部分提取出信息文本 对这些信息文 本进行分词处理 然后计算页面与抓取主题的相关程度 给页面赋予相关度权重 判断是否抓取该页面 主题爬虫的任务是最大化的发现和抓取与主题相关的页面 过滤掉与主题无 关的页面 最大程度的利用有限的系统资源 获得较优秀的检索结果 综上所述 对于特定领域的主题搜索主题爬虫更具目的性和针对性 其抓取过程目的明确 不仅充分利用了信息资源 也提高了抓取效率 研究主题爬虫需要明确其工作原理的假设前提 1 9 1 主题相关页面中所涵盖 的链接指向的网页一般与该特定搜索主题相关 这些链接就可以供爬虫系统继续 访问 基于这个假设 爬虫系统经过相关度计算舍弃一部分与主题无关的链接 提取与主题相关的链接 对页面进行抓取 主题爬虫系统结构如图2 3 所示 图2 3 主题爬虫体系结构 9 武汉理工大学硕士学位论文 页面获取的过程1 2 0 2 2 如下 首先手工选定一个爬行任务的初始u r l 集合 爬虫将以这个初始u r l 集作为入口开始爬行网络 不断从待爬行u r l 队列中取 出重要度最高的页面链接进行访问 下载页面后提取出网页文本信息 对其进行 分词后 再执行主题相关度计算 如果主题相关度大于系统设定的阈值 则认定 该页面是主题相关的 并对爬行的页面进行主题相关性计算 如果主题相关度较 高 则保存入原始页面库 如果主题相关度偏低 则认定该链接指向的页面是与 主题无关的 放弃该页面 接着提取主题相关页面中的u r l 加入待爬行u r l 队 列 循环上面的步骤 直到抓取结束 2 4 本章小结 本章作为全文研究的背景章节 首先对搜索引擎系统的工作流程进行简要介 绍 定位了爬虫程序在搜索引擎系统中所占据的重要地位 通过对比分析通用爬 虫系统与主题爬虫系统的体系结构之间的异同点以及各自的特点 介绍了爬虫系 统的运行原理 工作方式以及爬行过程中存在问题等 为本文以下的研究工作提 供了理论基础 1 0 武汉理工大学硕士学位论文 第3 章主题爬虫关键技术的研究 本章主要讨论关系主题爬虫的关键技术 包括初始种子集的选择方法 文本 提取方法和搜索策略的改进 其中搜索策略的改进主要结合了两种不同的搜索策 略的优点 基于主题相关度对p a g e r a n k 算法进行改迸 提高的原算法的运行效 率 另外 还重点讨论了中文分词技术和页面消重技术 3 1 文本特征项提取方法的研究 首先 通常构成文本词条的数目非常大 因而表示文本向量空间的维数也相 应地非常高 有时候甚至可以高达几万维 过高的文本向量空间维数必然会对分 类算法的效率产生影响 其次 有些信息量较小的特征项对辨别文档所属类别几 乎没有任何意义 有时甚至会干扰分类器的准确判断 因而必须过滤掉这些特征 项 基于这些因素 笔者在对文本进行挖掘之前 首先需要对文本进行降维处理 以便提高挖掘效率以及降低计算的复杂度 文本特征项提取的任务正是为了去除 信息量小 不重要的特征项 从而达到降维的效果 降低维数的方法主要可以分为特征选择和特征重构两种 特征选择的基本方 法表现在对无用词的过滤删除 即筛选出对文档区分度意义不大的词 特征重构 一般则通过潜在语义索引来构造文本词频矩阵 利用奇异值分解技术来降低矩阵 的频数 将最重要的行加以保存 以达到过滤掉原文本词频矩阵中的无用信息并 保留有效特征词条的效果 一般来讲 特征词条集都具有完全性 区分性和精练 性三个特性 通常情况下 在计算加权值之后也可以再进行减维处理 主要做法是过滤掉 权值较小的词条 保存权值较大的词条 在减少维数的基础上达到更为快速地提 取文本特征项的目的 文本特征项的提取过程 如图3 1 所示 的基本表述如下 首先为了得到文 档中的所有词条需要对文本进行分词处理 同时去除掉部分停用词 计算每个词 的权值大小 选择性地排除掉那些权值较小的词 随后通过向量正规化处理 即 可得出基本的文档特征向量 武汉理工大学硕士学位论文 图3 1 文本特征项的提取过程 此外 对文本特征提取的分类处理需要先对同类别的文档进行各词条的比较 与分析 以便定位能代表该类文档的核心词条 并赋予权重指标 将其作为未知 文档的分类依据 目前学术界和理论界较多采用分词算法和词频统计法从文档中 筛选出尽可能多的词 词组和短语作为文本特征词 以此构成文档矢量 但用这 种方法表示的文档存在一定的弊端 主要是因为文档矢量的维数将出现数量级的 增长 不利于有效的处理文档并带来较为低下的处理效率 基于此 需要选取其 他方式对文档矢量进行降维处理 形成更为合理的方法 因而可以采用只保留文 本特征中最能揭示文档信息特征的子集的方法 这种方法能有效降低文档矢量的 维数 关于文本特征选择方法的研究 可以借鉴国内外相关研究学者的研究方法 主要包括以下两种 一种方法是通过采用某种评价函数计算文档中的每一个特征 词 预先设定一个取值区间a 将计算出的结果进行高低排序 其数值大于a 区间的特征词为有效特征词 另一种方法是通过借助潜在语义索弓i l s i 以构造 文本词频矩阵 其间运用单值分解技术以便减少频数矩阵 降低词频矩阵中的非 重要信息并保留有效的特征词 需要指出的是 国内外学者一般采用文档频数 d f 信息增益 i g 文本 证据权 互信息 m d 期望交叉算熵和x 2 统计法等评价函数来研究文本处理过 程 由于本文的研究中也需要借助于上述中的评价函数 在此对文档频数和信息 增益这两种文本特征抽取技术进行简要概述 文档频率 d o c u m e n tf r e q u e n c y d f 方法主要是指在语料训练和测试的过程 中出现该词条的文档数 在此研究方法中 特征词与某类别的相关度一般用该特 征词在某特定类别中出现的文档数来表示 文档频率方法作为一种实现最简单 算法复杂度最低的特征抽取技术 与其他几种方法的计算相比 分类性能也相差 甚微 因而常被用于大规模语料统计中 在实际的信息抽取研究运用中 应当适 当保留部分含有较多信息量的d f 值低的词条信息 信息增益 i n f o r m a t i o no a i n i g 方法被广泛的运用于服务器学习领域 在i g 中将特征为分类系统提供的信息量作为其重要度的衡量标准 它所衡量的是在获 知某一特征文本中出现与否时 所统计的信息的比特数 设定 c 待l 2 七为 k 个类别的集合 词条特征为t 文档类别为c 当c 中出现和不出现t 特征词 1 2 武汉理工大学硕士学位论文 条的文档频数就可以用来衡量词条t 对于c 的信息增益大小 我们可以将词条t 的信息增益定义如下 i g t 一 p c i l o g p c o p t 圭p c i i t l o g p c i t p i 圭p c i i 1 0 9 p c l i 1 i i li i 其中 尸 o 为类别c 的概率 只gi f 为包含t 词条时 类别g 的概率 尸 f 的意义表示包含词条t 在文档的概率 p t 表示不包含词条t 的文档的概率 p gi 则表示不包含t 词条