（计算机软件与理论专业论文）主题爬行器相关技术的研究与实现.pdf

摘要 1 i i 摘要 如何在浩如烟海的w e b 信息中更好地找到用户关心的信息，是搜索引擎面 临的一个极大的挑战。主题爬行器通过将下载页面限定在特定的主题领域，来 提高搜索引擎的效率和提供信息的质量。其思想是在爬行过程中按预先定义好 的主题有选择地收集相关网页，避免下载主题不相关的网页，其且标是找到对 用户更准确、有用的信息。 本文以一个下载招聘网页的主题爬行器系统的设计和实现为背景，对有关 技术进行研究。为了实现主题相关性的判别，系统使用隐m a r k o v 模型对招聘 网页进行建模，并利用这一模型和v i t e r b i 算法判断一篇网页是否主题相关，即 是否为招聘网页。之后，本文还将这一方法与基于文本分类的方法进行了比较。 结果表明，这一方法要好于基于文本分类的方法。在爬行器爬行过程中，系统 使用朴素贝叶斯文本分类算法学习指向招聘网页的链接的文本特征，并根据学 习的结果对待下载的链接所指向的网页是否为招聘网页进行预测，优先选择下 载那些主题相关的网页。实验表明，这一爬行算法在下载主题相关网页的效率 上要好于广度优先算法和b e s t f i r s t 算法。 由于系统中文本分类的算法起着非常重要的作用，本文对支持向量机，k 最近邻、朴素贝叶斯等常用文本分类算法进行了比较和分析。另外，本文还讨 论了系统所使用的基于j a v a c c 的文本分析、h t m l 分析、基于文档向量模型 的网页表示、基于多线程的下载调度等技术。 关键词主题爬行器；隐m a r k o v 模型；文本分类 a b s t r a c t f i n d i n gi n f o r m a t i o nw h i c ht h ei 娼e r sw a n ti nt r e m e n d o u sa m o u n to fw e b i n f o r m a t i o ni sag r e a tc h a l l e n g et ow e bs e a r c he n g i n e f o c u s i n gw e bp a g e s 加a g i v e nd o m a i n ， f o c u s e dc r a w l e r sc a l ls a v eag r e a td e a lo fw o r k sa n di m p r o v et h e q u a l i t yo f t h ei n f o r m a t i o nt h e yp r o v i d e t h em a i ni d e ai st os e l e c t i v e l yc o l l e c tw e b p a g e so nap r e d e f i n e dt o p i ca n da v o i dd o w n l o a d i n gi r r e l a t i v ew e bp a g e si no r d e rt o f i n dm o r ea c c u r a t ea n du s e f u li n f o r m a t i o nf o rt h eu s e r b a s e do nt h ed e s i g na n di m p l e m e n t a t i o no faf o c u s e dc r a w l i n gs y s t e mo nj o b a d v e r t i s e m e n tt o p i c ，w ed i s c u s st h er e l a t e dt e c h n i q u e s i no r d e rt oj u d g et h et o p i c r e l e v a n c eo f aw e bp a g e ，t h es y s t e mu s e sh i d d e nm a r k o vm o d e li nm o d e l i n gw e b p a g e s t h i sm o d e la n dv i t e r b ia l g o r i t h ma r ee m p l o y e d t oj u d g e sw h e t h e raw e b p a g e c o n t a i n sj o ba d v e r t i s e m e n ti n f o r m a t i o n c o m p a r e dw i t ht h em e t h o db a s e do n d o c u m e n tc l a s s i f i c a t i o n ，t h ee x p e r i m e n ts h o w st h a tt h i sm e t h o di sm o r ea c c u r a t e t h a nt h et e x tc l a s s i f i c a t i o nb a s e dm e t h o d s i nt h ep r o c e s so fc r a w l i n g ，t h es y s t e m l e a r n st h ef e a t u r eo ft h ew e bl i n k sw h i c hp o i n t st oj o ba d v e r t i s e m e n tw e bp a g e s 1 l s i i l gn a i v eb a y e sa l g o r i t h m u s i n gt h e s ef e a t u r e si tp r e d i c t sw h e t h e raw e b l i n k p o i n t st oaj o ba d v e r t i s e m e n tw e bp a g ea n dd o w n l o a d st h i sp a g ew i t hh i g h e rp r i o r i t y e x p e r i m e n t ss h o wt h a tt h i sa l g o r i t h mi sb e t t e rt h a nt h eb r e a d t hf t r s ta l g o r i t h ma n d b e s t f i r s ta l g o r i t h mi nt h ee f f i c i e n c y b e c a u s et e x tc l a s s i f i c a t i o np l a ya ni m p o r t a n tr o l ei nt h es y s t e m ，t h i sp a p e r c o m p a r ea n da n a l y z es u p p o r tv e c t o rm a c h i n e ，k - n e a r e s tn e i g h b o r ，n a i v eb a y e s a n do t h e rc o m m o n l yu s e dt e x tc l a s s i f i c a t i o na l g o r i t h m s i na d d i t i o n ，s o m er e l a t e d t o p l e sa r ed i s c u s s e d ，s u c ha s t e x ta n a l y z i n gw i t hj a v a c c ，h t m lp a r s i n g ， d o c u m e n te x p r e s s i o nb a s e do nv e c t o rm o d e la n dd o w n l o a ds c h e d u l i n gt e c h n o l o g y u s i n gm u l t i - t h r e a d k e y w o r d sf o c u s e dc r a w l e r ；h m m ；d o c u m e n tc l a s s i f i c a t i o n i i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 豹学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：；墨l 三】猢日期：兰1 21 ：箩 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：二地导师签名期：翌丑：罗 第1 章绪论 1 1主题爬行器概述 第1 章绪论 随着因特网的迅猛发展，7w e b 信息的增加，用户要在信息海洋里查找信息， 就像大海捞针一样。搜索引擎正是为了解决这一问题而出现的技术。它以一定的 策略在互联网中搜集、发现信息，对信息进行理解、提取、组织和处理，并为用 户提供检索服务，从而达到信息导航的目的。搜索引擎中的一个关键部分就是爬 行器，通俗地讲，爬行器就是一个网页下载程序。传统的搜索引擎通过爬行器尽 可能多地下载网络中存在的网页，并通过对其进行索引来向用户提供搜索服务。 然而，随着网络信息的高速增长，这种爬行策略越来越显出不足。据统计，从2 0 世纪9 0 年代到现在网络的规模几乎是每年翻一番。g o o g l e 搜索引擎的首席执行官 埃利克曾指出世界上大约存在5 0 0 万t b 的信息，被索引的只有约1 7 0 t b 。要对世 界上所有的信息进行索引，并使它们可供搜索，需要3 0 0 年的时间。可见想要穷 尽的下载所有的互联网信息并建立索引是不现实的。另外，在大量的网络信息面 前，人们的关注点已经不再是仅仅找到信息，而是要找到有用的信息。这要求搜 索引擎提供搜索结果更准确、搜索范围更广的服务。传统搜索引擎的搜索结果中 经常包含大量不相关内容，对用户有帮助的信息更是非常少。在这一背景下，近 年来研究学者提出了新一代搜索引擎的发展方向，定题检索是其中尤为突出的一 种。 所谓定题搜索，就是将信息检索限定在特定主题领域，就主题相关的信息提 供检索服务。不同于通用搜索引擎，定题搜索引擎的检索范围相对小，查准率和 查全率易于保证。主题爬行器就是为了满足这一要求而产生的。其基本思想是在 爬行过程中按预先定义好的主题有选择地收集相关网页，即先分析它的搜索范 围，再找到最相关的链接，避免不相关的w e b 页，目标是找到对用户更准确、有 用的信息。由于主题爬行器涉及的信息范围要小得多，所以可以大量节省硬件设 备，提高信息提供的质量，并有能力跟踪每个相关网页，迅速发现和收集网上新 加入的信息和被删除的信息，使得信息保持实时更新。 1 2国内外研究现状 f i s h 算法是最早的主题爬行方面的成果，其思想是维护一个按优先权排序的 待下载u r l 队列，对于主题相关的网页所包含的链接u r l 被赋予较高的优先权。 北京工业大学工学硕士学位论文 下载过程中，首先下载优先权高的u r l ，从而保持下载到的页面尽可能是主题相 关的【l j 。 h e r s o v i c i 等人在这一算法的基础上提出了s h a r k 算法【2 】，其特点是在计算优先 权时参考网页链按提供的信息( 如链接文本、地址等) 。另外，a g g a r w a l l 3 1 提出 使用概率统计的方法对链接信息、页面信息进行分析以确定u r l 的权值。 在主题爬行器的设计中，页面的重要性评估是很重要的一个方面，l a r r y p a g e l 4 1 等人提出t p a g e r a n k 算法。其基本思想是利用网页之间链接关系计算网页 的重要性。该算法被认为是对搜索引擎技术的一次重大贡献。o o o # e 采用这一技 术成功地提升了搜索结果的质量。文献【5 1 提出了一些改进措施，使其更适合于 主题爬行器的页面评估。 k l e i n b e r g 在此基础上提出t h i t s 算法 6 1 ，并将这一算法应用于a r c 系统【”， 其特点是区分t h u b 和a u t h o r i t i v e 类型的网页。a m h o r i t i v e 类型的网页是主题相关 的网页，丽h u b 型的网页本身可能不是主题相关的，但它包含了很多指向主题相 关网页的链接。该算法可以计算出每个页面的h u b 值和a u t h o n t i v e 值，并根据这 两个值综合评价网页重要性。 在主题爬行算法的研究中，机器学习理论得到了广泛的应用。m e c a l l u m a , g 提出使用增强学习的方法训练爬行器，使它根据链接提供的信息学习找到主题相 关页面的路径。使用这种方法，m c c a l l u m 等人建立t c o r a 论文搜索引擎并取得 了很好的效果。m d i l i g e n t t l 0 ) 提出建立c o m c x t g r a p h 的方法并应用贝叶斯分类器 对网页进行分类，由此推断爬行器所下载的网页与主题相关的网页在链接路径上 的距离，并进一步决定是否继续下载其包含的链接。h l “1 1 】提出使用隐式马尔 科夫模型对爬行路径进行建模，这一方法将下载到的网页的所有链接网页进行聚 类，并将聚类后的结果作为模型的输出符号，而将网页与主题相关网页在爬行路 径上的距离作为网页的状态，通过对一些人工标注了状态的网页进行训练从而估 计这一模型的参数，进而在下载了新网页后使用这一模型估计网页的所有链接网 页所处的状态，并根据状态的值( 即与主题相关网页的距离) 为这些链接网页包 含的子链接赋予下载优先级。 c a r b o n e l l 1 2 1 提出了一种基于智能代理( a g e n t ) 和遗传算法的爬行算法，并建 t i n f o s p i d e r 智能门户搜索引擎。i n f o s p i d e r 中每个代理相互独立，并且自行决 定其爬行策略。另外，每个代理有一个基于遗传算法的进化的关键词表，根据这 些关键词训练并使用神经网络对新的链接进行评估。另外每个代理被赋予一定的 能量，其值由它下载到的页面的主题相关度决定。i n f o s p i d e r 还使用遗传算法来 繁殖能量高的代理，而终止能量低的代理。 国内搜索引擎的发展较国外相对滞后。搜狐等早期的搜索引擎属于人工索引 类型，没有机器爬行的过程。近年来，随着天网，百度等新一代搜索引擎的兴起， 有关爬行器的研究逐渐丰富了起来。文献1 3 1 提出t i n h e r i t f e e d b a c k 方法进行主题 挖掘。其思想类似于h i t s ，通过网页链接关系评估网页重要性，但这一方法同 时还考虑了页面的主题相关性。文献【1 4 1 提出一种基于遗传算法的主题爬行算法， 其思想是通过遗传算法的交叉和变异操作进行下载页面的选择。 1 3本文的研究内容和技术路线 要建立一个主题爬行系统需要解决两个问题，一是如何判别一篇网页是否为 主题相关的网页，二是研究一种爬行策略，让爬行器从待下载u r l 队列中选择一 些u r l 进行下载，从而使得爬行器在下载尽量多的主题相关的页面的同时，遍历 尽可能小的页面集合。本文对这两个问题进行了研究，并通过建立一个专门下载 和搜索招聘网页的主题爬行系统实现这一研究，这一系统使用如下的技术解决这 两个问题： 主题相关性的判别 对于主题相关性的判别，通常使用文本分类的方法，即先收集大量网页，并 对主题相关的网页进行人工标注，使用这些网页训练一个文本分类器。对于一篇 网页，如果文本分类器将其分类到主题相关的类别，这篇网页就是主题相关的。 这种方法需要收集大量的网页，其判别精度也不能满足要求。本文针对招聘网页 的特征提出一种主题相关性判别方法，这一方法使用隐m a r k o v 模型对网页进行 建模，将网页中的文字和h t m l 标签作为该模型的输出符号，将招聘信息的不同 部分( 如职位、招聘要求等) 作为该模型的隐状态。之后使用这一模型和v i t e r b i 算法抽取网页中的职位、招聘要求等招聘信息，并根据抽取到的信息使用文本分 类算法判断其是否为招聘页面。由于这种方法同时考虑了网页中关键词以及关键 词的状态( 如关键词在职位信息中和在招聘要求信息中所起的作用是不同的) ， 另外还考虑了h t m l 标签的作用，其效果要好于只考虑关键词的文本分类算法。 爬行算法 通用搜索引擎通常使用广度优先的爬行算法，即先下载种子网页( 初始的网 页集合) ，再下载种子网页链接到的网页。当这些网页都下载完毕后，再下载这 些网页链接到的网页，如此不断。其目标是穷尽的下载w e b 中网页。主题爬行算 法则不同，它的目标是让爬行器在下载尽量多的主题相关页面的同时，遍历尽可 能小的页面集合。其思路是为每一个待下载的u r l 指定一个优先级，对于可能导 向主题相关网页的u r l 赋予较高的优先级并优先下载。为此爬行器必须预测待下 载u r l 地址指向页面的主题相关性。本文使用朴素贝叶斯文本分类算法在爬行器 北京工业大学工学硕士学位论文 爬行的过程中学习指向主题相关网页的链接的文本特征，即建立两个分类：一个 是能导向主题相关网页的链接，另一个是不能导向主题相关网页的链接。每当爬 行器下载到一个主题相关的网页，就将导向这个网页的链接作为第一个分类输入 分类器进行训练，反之下载到一个主题不相关的网页就将相应链接作为第二个分 类输入分类器进行训练。当训练分类器的链接达到一定数量并完成训练后，就可 以使用这个分类器对爬行器遇到的新链接进行分类，并根据分类结果决定链接的 下载优先级。 本文的组织结构如下，第二章为所建立的主题爬行系统的总体结构，以及系 统各个模块的简要介绍；第三章介绍网页的分析和处理方法；第四章研究了各种 不同的文本分类算法，并对它们进行了分析；第五章讨论了本文使用隐m a r k o v 模型对招聘网页进行判别的方法；第六章讨论了系统使用的爬行算法以及爬行器 设计的若干问题；第七章是结论。 2 1总体结构 第2 章总体设计 一个主题爬行器的基本结构如图2 1 所示： 链接信息 及相应 图2 1 主题爬行器结构 f i g u r e2 - 1f o c u s e dc r a w l e ra r c h i t e c h u r e 如图2 1 ，爬行器从优先级队列中取出优先级最高的u r l 进行页面下载，页面 处理和分析模块将下载后的w e b 页表示成适合系统处理的形式，并提取出页面中 的链接。页面及链接评估模块根据这些信息判断页面的主题相关度，并预测链接 指向页面的主题相关性，据此赋予链接u r l 相应的权值并提交到优先队列。 为了验证本文的研究，使用j a v a 语言实现了一个主题爬行系统。这个系统在 结构上的设计目标是在尽可能保证系统运行效率的前提下，提供较大的灵活性， 这种灵活性体现在： 1 ) 运用已有的代码，可以方便地实现一个新的主题爬行策略，系统使用新 的爬行策略不会影响已有代码。 2 ) 可以方便地替换系统对页面的评估方法，以实验不同的主题相关度判别 方法。 3 ) 图2 1 中页面的处理和分析、爬行器、页面和链接评估等模块相互间依赖 关系尽可能小，使个模块的改变不会对其他模块造成太大的影响。 北京工业大学工学硕士学位论文 图2 2 展示了系统包含的模块以及它们的依赖关系。 自目一；图自 - - - i l 一z 一- i 宙鼬崮一目 图2 - 2 系统包含的模块以及它们的依赖关系 f i g u r e2 - 2s y s t e mm o d u l es t r u c t u r ea n dt h e i rd e p e n d e n c yr e l a t i o n s h i p 从图2 2 可以看出，系统分为4 层，上层模块仅依赖于下一层的模块，并且设 计保证这一依赖关系尽可能的小。如第一层爬行效果监视与统计模块统计系统的 运行情况。如，系统已下载页面数，已下载页面中主题相关的页面数，并以图表 等形式实时地显示这些信息，这一模块使用第二层的爬行器模块提供的接口。爬 行器模块使用第三层的页面和链接评估模块运行爬行算法，并将信息反馈给第一 层模块。为了使爬行器模块不依赖于监视与统计模块，使用了观察者n 5 l ( o b s e r v e r ) 模式，爬行器维护一个对它的爬行情况感兴趣的对象列表( 称为它的听众) 。这 些对象都实现了以下接口： p u b f i ci n t e r f a c ec r a w l l i s t e n e r ( p u b l i cv o i dd o w n o a d e d ( d o w r d o a d e d t a s k r t f oi n f o ) ； p u b l i cv o i df i n i s h e d o ； ) 每当下载了新的页面，爬行器生成这一页面的统计信息d o w n l o a d e d t a s k l n f o ， 并通过调用听众的d o w n l o a d e d 方法通知它的所有听众。当下载结束后，再调用 第2 章总体设计 f i n i s h e d 方法通知它的所有听众下载结束。这样监视与统计模块通过注册为爬行 器的听众即可对其进行统计和观察，并且不需要了解爬行器内部的实现细节，面 爬行器也并不显式的依赖于监视与统计模块，而是依赖于c r a w l l i s t e n e r 接口。在 3 1 节介绍的h t m l 分析模块中也可以看到这一模式的应用。 2 2各个功能模块分析 2 2 1 爬行器模块 图2 - 3 爬行器模块u m l 类图 f i g u r e2 - 3c r a w l e rm o d u l e su m ld i a g r a m 爬行器模块的类设计如图2 3 所示，a b s t r a c t c r a w l e r 是所有爬行器的基类，它 提供了以下四个模板方法，派生类通过实现这四个方法实现相关功能： p r e p a r e c r a w l i n g ：派生类在这个方法中通过调用a d d d o w n l o a d t a s k 添加初始的 种子u r l 。 a f t e r c r a w l i n g ：派生类在这个方法中添加爬行结束处理代码，以实现资源的 释放、爬行过程中的统计信息的保存等功能。 c o m p l e t e ：每当一个下载任务完成后，a b s t r a c t c r a w l e r 会调用c o m p l e t e 方法， 北京工业大学工学硕士学位论文 派生类实现这一方法以便对下载文件进行分析，并可能进一步添加新的下载 任务( 如从下载的h t m l 文件中抽取到了链接u r l ) ，派生类还要在c o m p l e t e 方法中生成下载统计信息( d o w n l o a d e d t a s k l n f o ) ，并调用n o t i f y d o w n l o a d e d 以便通知爬行器的听众下载了新文件的消息。 a b a n d o n ：对失败的下载任务，a b s t r a e t c r a w l e r 会调用a b a n d o n 通知派生类下 载失败的消息。 另夕b a b s t r a c t c r a w l e r 使用d o w n l o a d s c h e d u l e 类，它是页面下载和调度模块 的外观( f a c a d e ) ，封装了系统使用页面下载和调度功能的接口。 f o c u s e d c r a w l e r 是所有主题爬行器的基类，每当实现一个新的爬行算法时都 需要继承它。f o c u s e d c r a w l e r 通过主题关键词( 如“招聘”) 在g o o g l e 或百度等 通用搜索引擎中搜索1 0 0 篇网页，并以它们为下载种子u r l 开始爬行。它在 c o m p l e t e 方法中使用h t m l 分析模块中的h t m l p a r s e r 对下载的h t m l 文件进行 分析，h t m l p a r s e r 使用了前文所述的观察者模式，通过注册为它的听众 h t m l p a r s e r l i s t e n e r 就可以得到h 州l 分析的结果，而不需要关心具体的分析过 程。f o c u s e d c r a w l e r 可以注册h t m l p a r s e r 的以下听众： l i n k e x t r a c t o r ：实现了网页链接的抽取，e x t r a c t l i n k h a n d l e r 进一步将抽取到 的链接填入d o w n l o a d e d t a s k l n f o 对象以便派生类进一步处理。 l u c e n e d o c u m e n t b u i l d e r ：将网页内容转换为l u c e n e 文档对象，负责建立索引 的b u i l d l n d e x h a n d l e r 会使用l u c e n e i 具包对网页建立索引，以便对网页进行 检索。 w o r d s e q u e n c e e x t r a c t o r ：抽取网页中的关键词和特定的标签，并按其顺序组 成一个序列。页面评估模块中的h m m p a g e e v a l u a t o r h a n d l e r 对象将使用第五 章介绍的招聘信息的抽取和判别技术对其进行处理，从而完成页面评估。 e x t r a e t h t m l t e x t l i s t e n e r ：抽取网页中的关键词并生成关键词到词频信息的 映射w o r d m a p 对象，页面评估模块中的m u l t i c l s e v a l u a t e h a n d l e r 使用第四章 介绍的多层分类技术对其进行处理，从而完成页面评估。 e x t r a c t l i n k h a n d l e r 、b u i l d l n d e x h a n d l e r 、h m m p a g e e v a l u a t o r h a n d l e r 、 m u l t i c l s e v a l u a t e h a n d l e r 都实现了h t m l c o n t e n t h a n d l e r 接口。f o c u s e d c r a w l e r 将它 们存放在一个数组中，并使用它们实现a b s t r a c t c r a w l e r l 拘c o m p l e t e 方法来完成下 载文件的分析和处理，并且在使用它们时，仅依赖于h t m l c o n t e n t h a n d l e r 接e l ， 而不依赖于其具体实现。另p b f o c u s e d c r a w l e r 通过调用这一接口上的工厂方法 c r e a t e p a r s e l i s t e n e r j 建前面所述的h t m l p a r s e r 听众，从而也不再依赖于 h t m l p a r s e r l i s t e n e r 的具体实现： p u b l i ca b s t r a c tc l a s sf o c u s e d c r a w l e r e x t e n d sa b s t r a c t c r a w l e r ， 这一设计使得替换系统对页面的评估方法变得十分容易，即2 1 节所述的第二 个设计目标。h m m p a g e e v a l u a t o r h a n d l e r 、m u l t i c l s e v a l u a t e h a n d l e r 使用了不同的 页面判别算法对页面进行评估，系统只需要将其中之一加入h a n d l e r s 数组就可以 使用相应的算法。另外也可以根据需要增减处理模块和对系统进行扩展，例如需 要建立索引时就将b u i l d l n d e x h a n d l e r 添加到h a n d l e r s 数组。 f o e u s e d c r a w l e r 定义了唯一的一个模版方法d o w n l o a d e d 。要实现一个主题爬 行器只要继承f o c u s e d c r a w l e r 并实现d o w n l o a d e d 方法即可。以下是一种主题爬行 算法b e s t f i r s t 的实到“，这种算法对于主题相关度高的页面中的链接给予较 高的下载优先级： p u b l i cc l a s sb e s t f i r s t c r a w l e re x t e n d sf o e u s e d c r a w l e r p r o t e c t e dv o i dd o w n l o a d e d ( d o w r d o a d e d t a s k l n f oi n f o ) i n tp r i o r = ( i n t ) ( i n f o m a r k + 1 0 0 ) ； f o r ( l i n k a g el i n k ：i n f o 1 i n k s ) a d d d o w n l o a d t a s k ( 1 i n k g e t u r l o ，i n f o u r l ，p r i o r ，0 ) ； 一 二= 北京工业大学工学硕士学位论文 ) ) ) 其中i n f o 。l i n k s 是从h t m l 页面抽取到的链接，由e x t r a c t l i n k l - l a n d l e r 生成， i n f o ，m a r k 是页面的主题相关度评估，m h m m p a g e e v a l u a t e h a n d l e r 或 m u l t i c l s e v a l u a t e h a n d l e r 生成。可以看出，定义新的爬行算法只需要简单地继承 f o c u s e d c r a w l e r ，就可以复用后者的链接抽取、主题相关性判别、索引建立等功 能，而派生类只须关注爬行算法本身即可。 2 2 2 文档向量和文本分类模块 1 3 节指出，为了实现爬行算法和网页主题相关性的判别，需要使用文本分类 算法。这些算法被封装到文本分类模块中。另外某些算法需要使用文档向量模型 对网页进行表示，这一部分功能被封装到文档向量模块中。这些模块的类设计如 图2 4 所示： 图2 - 4 文档向量和文本分类模块u m l 类图 f i g u r e2 - 4d o c u m e n tv e c t o ra n dt e x tc l a s s i f i c a t i o nm o d u l e su m ld i a g r a m 为了对文档进行处理，首先要将文档表示为计算机中的数据结构。由于本文 使用的文本分类算法都将文档看作一组关键词的集合，而不考虑词与词之间的关 第2 章总体设计 系，因此本文在进行文本分类时w o r d m a p 接口抽象表示一篇文档，它是文档中 出现的关键词到这些关键词的统计信息的映射。这些统计信息被抽象为w o r d l n f o 接口。它的不同实现可以记录词的不同信息。如图中的b a s i c w o r d i n f o 表示关键 词的词频信息、w o r d l n v e r s e l n d e x 记录了词的反向索引信息等。 图2 4 中标示出- j w o r d m a p 的两个实现：h a s h w o r d m a p 和b t r e e w o r d m a p ，前 者使用哈希表记录前面所述的信息，后者使用b e r k e l e y d b 软件包提供的b + 树存 储这些信息，它适用于信息量较大，无法在内存中存储全部信息的情况。注意到 系统中的类都仅仅依赖于w o r d m a p 接口而不是它们的具体实现，这使得这些类的 客户端可以自由地使用它们需要的存储方式。另外，缺省情况下这两种实现都存 储b a s i e w o r d l n f o 对象，可以通过重载它们的c r e a t e w o r d l n f o 方法以存储不同的对 象。w o r d m a p 与w o r d i n f o 的不同实现的组合可以满足不同的需要，在3 3 3 节介绍 的文档向量模型的实现正是利用了这种灵活性。 文本分类算法分为两类，一类是单类文本分类算法，该类算法判断篇文档 是否属于某一类别。系统中这类算法都继承自o n e c l a s s t e x t c l a s s i f i e r 接口。它有 四个方法：a d d t r a i n n s t a n c e 、a n a l y s e 、c l a s s i f y 和c o m p r e s s ，分别表示添加训练文 档、分析训练文档集合、对新文档进行分类以及对词表进行压缩。a d d t r a i n l n s t a n e e 和c l a s s i f y 接受一个w o r d m a p 参数，表示待训练和分类的文档，其中存储了文档 中每个关键词的词频信息，即b a s i e w o r d l n f o 。o n e c l a s s t e x t c l a s s i f i e r 有两个实现， 基于文档向量模型的o n e c l a s s d o e t e x t c l a s s i f i e r 年d 基于支持向量机的 o n e c l a s s s v m t e x t c l a s s i f i e r 。这两个实现都要使用文档向量模型对文档进行表 示，d o e v e c t o r b u i l d e r 封装了这部分功能的代码，它需要使用i n v e r s e l n d e x b u i l d e r 对训练文档集合建立反向索引即训练文档集合中每个关键词到包含它们的 文档i d 号集合以及它们在相应文档中出现频率的映射，这些信息包含在存储 w o r d l n v e r s e l n d e x 对象的w o r d m 印中。 第二类分类算法是多类文本分类算法，该算法判断一篇文档属于众多类别中 的哪一类别。系统中这类算法都继承i ! i t e x t c l a s s i f i e r 接口。图2 _ 4 中列出了这一接 口的三个实现：基于朴素贝叶斯算法的n a i v e b a y e s c l a s s i f i e r ，基于支持向量机的 s v m t e x t c l a s s i f i e r ，基于k 阶最近邻的k n n t e x t c l a s s i f i e r 。后两者的共同特征是 使用了文档向量模型，这使得它们有相同的基类d o c v e c t o r b a s e d t e x t c l a s s i f i e r ， 它使用d o c v e c t o r b u i l d e r 把训练和分类文档转化为向量，派生类只需要在向量上 进行训练和分类即可。第四章会对这三种分类器进行介绍和比较，由于它们都实 现t t e x t c l a s s i f i e r 接口，使得对它们分类性能的测试程序的编写更加简捷，因为 测试程序不需要了解这些算法的实现细节，只需要统计并比较它们在 t e x t c l a s s i f i e r 接口上的输出结果即可。注意至f j t e x t c l a s s i f i e r 的方法略微不同于 北京工业大学工学硕士学位论文 o n e c l a s s t e x t c l a s s i f i e r ，添加训练文档时需要指定文档的类别号、分类文档也将 返回一个类别号。 2 2 3 其它模块 图2 2 中的词法分析模块用来对文本进行分析，以便提取其中的关键词，这一 部分将在3 2 节介绍。页面评估模块使用词法分析模块对h t m l 中的文本进行分 析，提取出其中的关键词转换w o r d m a p 对象或h m m 模块的输入序列，从而供 页面判别算法使用。h m m 模块实现了隐m a r k o v 模型以及v i t e r b i 算法，这模块 结合文本分类模块被用来实现招聘页面的主题相关性判别，将在第五章介绍。链 接分析模块同样使用词法分析模块对链接文本进行分析，用提取出的关键词生成 w o r d m a p 对象，并用朴素贝叶斯分类器对其进行分类，从而生成链接地址的下载 优先级。这些模块共同作用，构成本文所述的主题爬行系统。 2 3网页的索引和查询 对网页的索引和查询是下载网页的最终目的。为了实验爬行器的爬行效果， 本文使用l u e e n e 实现网页的索引和查询。l u e e n e 是一个用j a v a 写的全文索引引擎 工具包，它可以方便的嵌入到各种应用中实现针对应用的全文索引检索功能。 图2 5 、2 - 6 显示了仅对爬行器下载的主题相关的网页建立索引后的查询结果，这 里的网页主题是招聘网页。 l u c e n e 为网页中出现的每个关键词建立了反向索引，以便用户查询。虽然系 统中的i n v e r s e l n d e x b u i l d e r 也可以完成网页的索引，但目前它只能记录关键词出 现在哪些文档中，而没有记录出现的位置。l u c e n e 可以记录每个关键词在文档中 的位置，这样可以在查询界面中商亮显示搜索关键词，如图2 - 5 、2 - 6 右侧的网页 内容栏，另夕 l u c e n e 还可以记录每篇文档的标题，以方便显示查询结果，如图2 5 、 2 - 6 左侧的搜索结果栏。进一步的工作可以考虑扩展i n v e r s e l n d e x b u i l d e r 使其实现 类似的功能。另外，本文使用词法分析模块扩展t l u c e n e 的词法分析系统使其可 以对中文进行分词，并使用h t m l 分析模块从网页中抽取文本供l u c e n e 建立索 引。 从图2 - 5 、2 - 6 的查询结果可以看出，返回的网页都是招聘类的网页，这正是 主题爬行器的优势所在：将搜索范围限制在一个特定的领域，从而使用户可以查 询他们真正想要的内容。 第2 章总体设计 图2 - 5j a v a 的搜索结果 f i g u r e2 - 5j a v a ss e a r c hr e s u l t 圈2 - 6l i n u x 的搜索结果 f i g u r e2 - 6l i n u x ss e a r c hr e s u l t 1 3 北京工业大学工学硕士学位论文 2 4参数配置 系统中存在大量参数，使用时需要赋予不同的值以满足不同的需要。本文将 这些参数定义在x m l 文件中，系统读取这一文件加载其所需要的参数，其内容 如下： 5 1 0 4 0 1 0 0 0 g a d o w n l o a d e d p a g e s m o z i l l a 4 0 ( c o m p a t i b l e ；m s i e6 o ；w i n d o w sn t5 2 ) 3 2 5 1 9 t e x t h t m l h t m l t e x t p l a i n t x t c o m g u o x i a n g c r a w l e r l i n k c l a s s i f i e r c r a w l e r c o r n g u o x i a n g c r a w l e r e v a l u a t e h m m p a g e e v a l u a t e h a n d l e r 5 0 0 0 g o o g l e 招聘 g ：i n d e x e s 值得指出的是a p p l i c a t i o n c r a w l e r c l a s s 标签中的内容，它定义了爬行器类， 并且必须是2 2 1 节介绍的f o c u s e d c r a w l e r 的子类，系统初始化时，会利用j a v a 反 射机制创建这个类的一个实例，并使用它进行爬行。因此，如果实现了一个新的 爬行算法或想使用另一种爬行算法，只要将其类名填入配置文件即可使用，而不 需要更改源文件。类似的标签还有a p p l i c a t i o n c r a w l e r e v a l u a t o r ，它定义了页面 评估类，并且必须是2 2 1 节所述的h t m l c o n t e n t h a n d l e r 的子类。表2 1 是配置文 件中各参数的意义( 略去t a p p l i c a t i o n 标签) 。 表2 - 1 系统参数及其描述 t a b l e2 - 1s y s t e mp a r a m e t e r sa n dt h e i rd e s c r i p t i o n 参数名称意义 d o w n l o a d c o n n e c t t i m e o u t h 1 v r