（计算机应用技术专业论文）垂直搜索引擎的抓取技术研究.pdf

浙江大学硕上学位论文摘要 摘要 垂直搜索引擎的概念，是针对某一特定行业领域提供有一定价值的信息和相 关服务，它是搜索引擎的细分和延伸，是为用户提供符合专业用户操作行为的全 新信息服务方式，本文是对垂直搜索引擎的抓取技术研究，主要关注垂直搜索引 擎的抓取中所遇到的隐蔽网抓耿、时效性以及性能和效率问题。 本文首先介绍了垂直搜索抓取系统的体系结构，提出了一种分布式和基于可 扩展插件的垂直搜索抓取系统框架，其分布式特性和插件模式都便于将来的扩 展。然后讨论了垂直搜索抓取系统中隐蔽网抓取的三个问题，并针对隐蔽网抓取 中结果消重的问题提出了一种自学习的中文地址判重方法；接下来针对垂直搜索 的时效性问题提出了一种基于查询驱动的实时抓取方式；讨论了并比较了影响垂 直搜索抓取系统的抓取模式、抓取策略和抓取频率，在本文的系统中采用了稳定 持续模式、及时替换式更新、实时抓取与固定频率相结合的方式。 本文最后进行了关于判重问题和时效性问题实验，通过实验，证明了本文提 出的方法在应用中能获得更好的效果和用户体验。 关键词垂直搜索，可扩展，隐蔽网，时效性 浙江大学硕，i ：学位论文 a b s t r a c t a b s t r a c t t h ec o n c e p to f v e r t i c a ls e a r c he n g i n ei sd i r e c t e dt o w a r d sas p e c i f i cd o m a i nt op r o v i d e s o m ev a l u a b l ei n f o r m a t i o na n ds o m ei n t e r r e l a t e ds e r v i c e i ti st h es u b d i v i s i o na n dt h e e x t e n s i o no fs e a r c he n g i n e i ti sab r a n dn e ww a yo fp r o v i d i n gi n f o r m a t i o ns e r v i c ei n a c c o r d a n c ew i t ht h eo p e r a t i o no fp r o f e s s i o n a lu s e r s t h i sp a p e ri sc o n c e r n i n ga b o u tt h e c r a w lt e c h n o l o g yo fs e a r c he n g i n e ，m a i n l yc o n c e r n i n ga b o u tt h ec r a w lp r o b l e mi n v e r t i c a ls e a r c he n g i n e ：h i d d e nw e b ，t i m e - e f f e c t i v e n e s s ，p e r f o r m a n c ea n de f f i c i e n c y w ef i r s ti n t r o d u c et h ea r c h i t e c t u r eo fo u rv e r t i c a ls e a r c hc r a w ls y s t e ma n dp r o p o s ea c r a w ls y s t e mf r a m e w o r kw h i c hi sd i s t r i b u t e da n db a s e do ne x t e n s i b l ep l u g - i n s t h e d i s t r i b u t e dp r o p e r t ya n dt h ep l u g i na r ea l lc o n v e n i e n tf o re x t e n s i b l ef o rt h ef u t u r e t h e nd i s c u s s3q u e s t i o n si nh i d d e nw e bc r a w l ，b r i n gas e l f - l e a r n i n gw a yo f e l i m i n a t i o no fd u p l i c a t e dc h i n e s ea d d r e s sf o rt h ec r a w lr e s u l to fh i d d e nw e b ；t h e n d e v e l o paq u e r yt r i g g e r e dc r a w l i n gf o r t h et i m e e f f e c t i v e n e s sp r o b l e m d i s c u s sa n d c o m p a r et h ec r a w lm o d e ，c r a w ls t r a t e g y , c r a w lf r e q u e n c y w h i c hc o u l da f f e c tt h e v e r t i c a ls e a r c hc r a w ls y s t e ma n di no u rs y s t e mw ea d o p tt h es t e a d ym o d e ，i n p l a c e s t r a t e g y , c o m b i n eo f r e a lt i m ec r a w la n df i x e df r e q u e n c y a c c o r d i n gt ot h ee x p e r i m e n t ，o u rm e t h o df o re l i m i n a t i n gd u p l i c a t er e s u l ta n dt h e t i m e e f f e c t i v e n e s sc o u l dg e tb e t t e re f f e c t i v e n e s sa n db e t t e ru s e re x p e r i e n c e 。 k e y w o r d s v e r t i c a ls e a r c h ，e x t e n s i b l e ，h i d d e nw e b ，t i m e e f f e c t i v e n e s s l l 浙江大学硕 ：学位论文第1 章绪论 图目录 图1 1 覆盖集的最优解问题7 图1 2 两种不同下载策略的表现，d b 优于l b 1 3 图1 3p a g e r a n k 方法计算下载概率和基本方法的比较1 3 图1 4w h a 、h a 和d b 在2 4 个周期内的比较1 4 图2 1 垂直搜索抓取系统体系结构1 6 图2 2 分布式结构扩展图2 3 图3 1 单一关键字查询接口2 8 图3 2 多属性查询接口2 8 图3 3 自学习地址判重算法流程3 3 图4 1 监视网页的组成3 6 图4 2 覆盖率结果3 6 图4 3 长时问覆盖率结果3 7 图4 4 覆盖率重复结果3 7 图4 5 抢占式抓取子系统结构4 0 图5 1 间隔批量模式4 6 图5 2 稳定持续模式4 6 图5 3 稳定持续模式下整体预存更新策略4 8 图5 4 间隔批量模式下整体预存更新策略4 9 图5 5 最佳抓取频率随网页变化频率趋势图5 1 图5 6 两种爬虫的结构及其优缺点5 4 图5 7 实时抓取与固定频率相结合5 5 图6 1 对不同的f 的地址判重率比较5 7 图6 2 时效性实验更新频率对比图5 8 图6 - 3 时效性实验效率对比图5 8 图6 4 时效性带宽对比图5 9 i i i 浙江大学硕 j 学位论文第1 章绪论 表目录 表3 1 中文地址切分后各子域内容3 0 表5 1 抓取方式和策略组合5 0 表6 1 地址规范度计算实验结果5 6 表6 2 时效性实验对比5 9 i v 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加潋标注和致谢的遗方外，论文中不包含其能人已经发 表或撰写过的研究成果，也不包含为获得逝姿基堂或其他教育机构的学位或 证书而使用过的材料。与我同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者签名：参。i 退 签字日期：d og 年6 月g日 学位论文版权使用授权书 本学位论文作者完全了解逝姿叁茎有权保留并离国家有关部门或枫构 送交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝鋈盘堂可 以将学位论文的全部或部分内容编入有关数据摩进行检索稆传播，可泼采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 签字日期：沙。毽年6 月8 日 导师签名： 签字吼。矿年g 月f 日 浙江人学硕 二学位论文 第1 章绪论 1 1 课题背景及意义 第1 章绪论 随着网络技术的爆炸式发展，互联网已经成为当前信息的主要载体，人们也 越来越习惯在互联网上获取信息，如何有效地提取并利用这些信息，这就是搜索 引擎需要做的事。传统的通用搜索引擎和g o o g l e 、y a h o o 以及国内的b a i d u 等等， 他们作为一个辅助人们检索信息的工具成为绝大多数互联网用户访问网络的入 口和指南。但是，这些通用性搜索引擎也存在着一定的局限性，如： 1 ) 不同领域、不同背景的用户往往具有不同的检索目的和需求，通用搜索引擎 所返回的结果包含大量用户不关心的网页。 2 ) 通用搜索引擎的目标是尽可能大的网络覆盖率，有限的搜索引擎服务器资源 与无限的网络数据资源之间的矛盾将进一步加深。 3 ) 互联网数据形式的丰富和网络技术的不断发展，图片、数据库、音频视频 多媒体等不同数据大量出现，通用搜索引擎往往对这些信息含量密集且具有 一定结构的数据无能为力，不能很好地发现和获取。 4 ) 通用搜索引擎大多提供基于关键字的检索，难以支持根据语义信息提出的查 询。 在这种情况下，为了解决这些问题，垂直搜索引擎应运而生，“垂直搜索引擎 的概念，是针对某一特定行业领域或组织，某一特定人群或满足某一特定需求、 或者组织某项业务需求提供有一定价值的信息和相关服务，它是搜索引擎的细分 和延伸，是对某类网页资源和结构化资源的深度整合，是为用户提供符合专业用 户操作行为的全新信息服务方式。垂直搜索的诞生起源于搜索引擎的细分化发展 格局，即细分服务模式针对不同行业领域提供更加精确的行业服务模式。 垂直搜索引擎地实现主要分为数据抓取和数据显示两个部分，而本文所研究 的内容正是针对垂直搜索引擎的抓取技术。考虑到目前垂直搜索引擎的一些问 l 浙江人学硕上学位论文 第l 章绪论 题：结果消重、时效性以及性能和效率问题。本文提出了一种分布式的可扩展垂 直搜索抓取系统，并以可扩展插件的方式提出了有关中文地址判重、时效性等问 题的解决方案。 1 2 垂直搜索抓取技术中目前的研究热点 垂直搜索抓取系统主要遇到的问题有隐蔽网抓取问题、时效性问题、性能与 效率问题、整个系统的架构问题等等。本节将主要介绍针对隐蔽网抓取和时效性 问题的一些研究现状。 1 2 1 垂直搜索隐蔽网研究现状 1 2 1 1 机器学习的隐蔽网入口发现 隐蔽网数据主要是网页表单获取，如何发现这些表单并将其自动分成是或者 不是查询接e 1 两类，是隐蔽网入口发现的主要问题。在文献 6 中对自动分类网页 表单提出了一种机器学习方法。主要分为特征提取和机器学习两大关键步骤。 1 网页表单特征的提取 特征提取是自动分类的前提，它可以从以下几个方面提高自动分类系统的性 能。首先是分类速度，通过特征的选择，可以大大减少特征集合中的特征数，从 而提高自动分类系统的运行速度，使之能够满足现实需求。二是通过适当的特征 选择，不但不会降低系统的准确性，反而会使系统的精度提高。 用h t m l 表示的网页表单包含了复杂的信息结构，可以从中获取大量的有 用信息集合。如何选择合适的特征对网页表单进行描述，以便有效地对网页表单 自动分类，是首先需要解决的问题。 网页表单即包含在h t m l 标签 之内的相关内容。其一 般格式为 网页表单内容 ，其中参数a c t i o n 用以指明要将网页表单数据提交给的服务器处理程序 ( 包括网络路径或相对路径) 。参数m e t h o d 用以指明表示用户输入的网页表单内 2 浙江大学硕1 ：学位论文第1 章绪论 容以何种方式传给服务器( 分为g e t 和p o s t 两种) 。 网页表单的内部控件可以分三大类：i n p u t 控件，s e le c t 控件和 t e x t a r e a 控件。i n p u t 控件定义了网页表单内可以输入编辑的区域，i n p u t 控件的t y p e 属性描述了控件的类型，有t e x t ，c h e c k b o x ，r a d i o ，s u b m i t ，r e s e t ， r a d i o ，i m a g e ，h i d d e n 八种，其中s u b m i t 类型控件用于将填好的网页表单内容提 交；i n p u t 控件的n a m e 属性指定每一个控件一个名称，这个名称与控件是一一 对应的。服务器就是通过调用某一控件的n a m e 属性来获得该区域的数据。i n p u t 控件的v a l u e 属性是另一个公共属性，它可用来指定控件的缺省值。s e l e c t 控 件用来创建一个下拉列表框或可以复选的列表框。t e x t a r e a 控件用来创建一 个可以输入多行的文本框。 网页表单拥有如此多的有用信息，因此可以通过提取网页表单中出现过的各 种控件信息对网页表单进行特征表示，如对控件类型的提取和对控件名称的提取 等。而一些用于体现控件外观表现方式的属性可以剔除，如s i z e ，l e n g t h 等，当 然还有所有的c s s 属性。另外对于s e l e c t 和t e x t a r e a 控件，由于需要考虑 的是如何通过网页表单的结构获取特征，进而得到网页表单是否为查询接口的问 题，因此对下拉列表框中出现的选项内容并不做提取。 此外，还可以通过对网页表单中控件出现的次数进行特征提取，例如一个网 页表单可能存在一个文本框，也可能存在多个文本框。注意到一些网站提供的高 级检索往往具有多个文本框，而一些站内检索往往仅仅只有一个文本框，由此可 见这对网页表单的特征提取也是有积极意义的。 综合上述观点，根据网页表单的结构，将提取以下网页表单特征： 1 ) 网页表单 标签中的n a m e 属性值。 2 ) 从网页表单 标签的a c t i o n 属性值中提取的词。 3 1 网页表单中出现的控件类型。 4 1i n p u t 控件的n a m e 属性值和v a l u e 属性值。 5 1s e l e c t 控件和t e x t a r e a 控件的n a m e 属性值。 6 1 存在于控件标签之间的词。 浙江大学硕十学位论文第1 章绪论 其中从网页表单 标记的a c t i o n 属性中提取的词是指将a c t i o n 属性 中出现的u r l 字符串根据斜线“划分出来的子串。另外由于存在于网页表单 控件标签之间，呈现在网页上以提示用户如何填写网页表单的词对分类也起到一 定的作用，因此也将这些词作为特征提取出来。 经过上述的特征提取过程，已经可以获取大量的网页表单特征，但是网页格 式灵活，可以多种格式并存，而且同一格式的网页也存在多个标准；同时网页设 计人员的写作风格、习惯不尽相同。这使得提取出来的网页表单特征显得过于杂 乱。因此在特征提取时，需要对特征进行标准化以提高分类的准确性。 可以根据以下几个规则对特征进行标准化： 1 ) 将特征中出现的英文字母统一转化为小写。 2 ) 去除出现在括号中的内容。 3 ) 如果特征中出现的内容由多个词组成，则要进行分词，去除停用词。 4 ) 转换缩写和简写并利用w o r d n e t 【7 】来得到统一的特征表示。 使用以上提取和转换步骤，就可以而得到网页表单对一些有用的特征，再对这些特征进 行机器学习，就可以判定其是否是隐蔽网的查询接口。 2 机器学习 目前有许多成熟的通过机器学习实现的文本自动分类方法，包括概率模型方 法、关系学习方法、支持向量机方法等。其一般过程都是通过对已经分好类的一 组训练文本的学习来自动创建分类器，通过有指导的学习对测试文本进行分类。 在对网页表单进行自动分类的过程中采取的是概率模型方法，并使用y s b 素贝叶 斯分类算法。 朴素贝叶斯分类算法是一种简单、有效而且在实际使用中很成功的分类算法， 其性能可以与判定树与神经网络分类算法相媲美，在某些场合还优于其他分类算 法。设有变量集u = a t ，a 。，c ，其中a l ，4 是实例的属性变量，c 是取m 个 值的类变量。假设所有的属性都条件独立于类变量e ，即每一个属性变量都以类 变量作为唯一的父结点，就得到朴素贝叶斯分类器。使用朴素贝叶斯分类器进行 分类的做法是：通过概率计算，从待分类实例的属性值q ，a 。求出最可能的分类 4 浙江人学硕+ 学位论文第1 章绪论 目标值。即计算各类勺c 对于这组属性的条件概率p ( q 旧，口。) ，其中= 1 ， 2 ，1 t i ，并输出条件概率最大的类标签作为目标值。应用贝叶斯定理可得： p ( q ta 埘。) = p ( 口，口。ic j ) p ( c ，) p ( a ”，口。) 朴素贝叶斯分类算法假设条件是 独立的。因此p ( 口，口。ic ) = 兀p ( a 。ic j ) ，同时由于尸( 口，n 。) 对于所有类为常 七= 1 数，因此，只要计算兀p ( a 。 c i ) p ( c i ) 就可以了。假设p ( c lm ) 为待分类网页表 k = l 单m 是查询接口的概率，p ( c ：im ) 为待分类网页表单m 非查询接口的概率。只 p ( c 。i m ) p ( c ：i m ) ，就可以判定网页表单m 为查询接口，反之则为非查询接 口。 1 2 1 2 隐蔽网查询构造 发现隐蔽网入口后，如何针对这些查询接口构造有意义的查询，文献 1 5 提 出了一种对于隐蔽网查询接口的理论框架，和几种策略。这里介绍一下该文所提 出的理论和算法。 1 爬虫爬行基本算法 为简化问题，假设爬虫仅处理单一属性关键词查询问题。爬虫首先决定下次 将使用那一个关键词，然后是发送查询获得结果索引页，最终基于这些超链接， 爬虫下载具体页面内容。反复执行这个过程，直到其耗尽所有的资源。此算法最 为关键的一步是爬虫针对查询接口选择下次将提出什么样的查询关键词用于表 单提交。如果爬虫能提供成功的查询，它将返回很多匹配页面同时它将使用最少 的资源提前完成爬行任务。相反，如果爬虫提出的是一个与查询任务完全无关的 关键词，它将不返回任何与任务相关的页面同时浪费很多资源。因此，爬虫对表 单下次提交关键词的选择问题将在很大程度上影响其效能。算法伪代码如下： 爬行d e e pw e b 站点算法 p r o c e d u r e ( 1 ) w h i l e ( t h e r ea r ea v a i l a b l er e s o u r c e s ) d o 浙江人学硕士学位论文第l 章绪论 ( 2 ) q i = s e l e c t t e r m ( ) 选一关键词发送到d e e p w e b 站点 ( 3 ) r ( q i ) = q u e r y w e b s i t e ( q i ) 发送查询，获取结果索引列表页面 ( 4 ) d o w n l o a d ( r ( q i ) ) 下载用户自己感兴趣的页面内容 ( 5 ) d o n e 2 查询问题形式化定义 理论上，查询关键词选择问题可以这样形式化的定义：假设爬虫从站点下载 的页面集为s ( 如图1 1 所示) 用一个点来代表s 中的每一个页面，对于每个潜 在的查询q i 返回的结果页面集可以认为是s 的一个子集。对于每个查询q ，都有一 定的代价，如资源消耗量等。在这种定义下其目标是通过最小的代价来寻找能覆 盖最多点的查询。这个问题等价于图论【8 】中集覆盖问题。 在这个形式化定义中主要涉及两个问题。一个是：实际上针对每次查询q ；爬 虫并不知道将有哪些和将有多少页面被返回。即g ，返回的子集是事先不知道的。 不清楚这个子集，爬虫将不能决定什么样的查询关键词将有最大的结果覆盖率。 再一个就是：集覆盖最优解问题被认为是一个n p 问题【8 】，目前还没有找到一个 在多项式时间内解决此问题的有效算法。这里采用一种在可计算代价内近似最优 解的次优解算法。尽管不知道对于每次查询g ，将有多少页面被返回，综合实验观 察本文提出一种查询选择算法，它可以预测将有多少页面被返回。基于此信息查 询选择算法可以选择“最好的或最有希望的 的查询关键词。下一节将详细说明 预测方法和查询选择算法。 6 浙江大学硕十学位论文第1 章绪论 图1 1 覆盖集的最优解问题 3 性能评价标准 给定查询q ，使用p ( q ，) 表示对于查询g ，站点返回的结果页面数占所有可能 结果页面数的比例。例如：如果一个站点总共有1 0 0 0 0 个页面。若使用查询 吼= ”n e w s ”返回了3 5 0 0 个结果页面，则e ( q ，) = 0 3 5 。使用p ( q 。a q ：) 来表示由查 询g 。和g ：均返回的页面数量占所有可能结果页面数的比例，即p ( q 。) a n e ( q ：) 的交 集；同样使用p ( q 。v q ：) 来表示由查询吼和g ：一共返回的页面数量占所有可能的 结果页面数的比例，即p ( q 。) a np ( q ：) 的并集。 用c o s t ( q ，) 来表示查询吼的各种代价总和。代价评定标准要么是时间，网络 带宽，要么是表单提交次数等，或者是由这些量组成的一个函数。下一节中提出 的算法实际上是没有考虑到代价函数的。通常情况下，查询代价包含多方面的因 素，包含提交查询到站点的查询代价，检索索引页面代价和下载实际页面的代价。 下载页面的代价是与返回的匹配文档数量成比例的。然而，设提交一次查询的代 价为e ，得到结果页面的代价为c r ，抓取每一篇文档的代价0 。查询q ，的总代 价可表示为：c o s t ( q ，) = q + c r p ( q ，) + o p ( q ，) ，其中qc r ，巳为常量。 一般情况下，由g ，查询所返回的页面中有一部分可能由前一次查询已经下 载。这样爬虫就可以跳过这些页面，直接下载新产生的页面，上面的代价函数可 修改为：c o s t ( q f ) = e + c p ( q f ) + g 只。( g ，) 。 7 浙江大学硕上学位论文第l 章绪论 接下来会研究怎样来估计p ( q ，) 和只。( g ，) 来评估查询q ，的总代价。由于算法 实际上没有考虑查询代价问题。假设一个一般的代价函数c o s t ( q ，) ，做了上面的 定义后，可以把爬虫爬行问题形式化定义为：在查询关键词g ，q 。中寻找一个关 键词使得p ( 吼v v q n ) 值最大，其约束条件是c o s t ( q ，) f ，其中t 是提供给爬 i = 1 虫的最大资源数。 4 查询关键字选择策略 查询关键字选择的目标是使用最少的代价下载最大数量的后台数据库内容， 有以下几种策略： 1 ) 随机选择：从词典中随机选择关键词用于提交表单查询。希望通过随机查询 返回一定数量的匹配文档资源。 2 ) 根据词频选择：通过分析普通的w e b 文档集来获得每一关键词的频率贡献。 基于词频贡献，首先使用词频最高的关键词用于隐蔽网后台数据库的查询提 交，然后检索返回的结果。下次使用词频次之的关键词，反复执行这个过程， 直到爬虫耗尽其所有资源。希望在w e b 文档集中的词在后台数据库中词频也 较高，从而返回更多的匹配文档资源。 3 ) 适应性策略：分析以前查询返回的结果文档，然后估计下次使用哪个关键词 可以返回最多的文档资资源。基于此分析，提出“最有希望”的查询，迭代 此过程，直到资源耗尽或者是满足用户要求。 5 估计页面匹配概率 为得到“最符合条件 的查询关键词，需要针对下次查询g ，估计将返回多少 新的匹配的文档。假设已经提出查询吼，g f _ 。】，需要对下次每种潜在查询吼估 计p ( q ，v v q 【f 】) 值，比较出其中的最大值。可以通过改写估计函数的形式来计算 这个值。 浙江大学硕十学位论文第l 章绪论 p ( ( g lv vq e i - 1 ) vg f ) = p ( q lv v 陆l 】) + p ( g f ) 一p ( ( g lv v 睢q ) aq f ) = p ( q lv vq i - i ) + 尸( g f ) 一p ( q lv vq f _ - q ) 尸( g fi ( q lv vq i - i ) ) 在上面的公式中，可以通过分析查询g ，之前已下载的页面来准确计算 p ( q lv vq e i - 1 ) 和p ( q 小吼v vq i - q ) ) 值。p ( q lv vq i - 1 ) 是查询q f 之前已下载 的所有页面总和，p ( q 小g 。v vq t i - 1 ) ) 是查询g ，出现在g l ，q 【j - 1 】下载页面中的条 件概率，也可从分析已下载页面中得到此值。因此要计算p ( ( g ，v vq t i - i ) vq i ) 仅 需计算p ( q ，) 的值。有两种方法来估计此值： 1 ) 独立估计量：假设下次查询每个潜在的关键词g f 是独立于q l , - - , q l 的，此时 有p ( q f ) = p ( q fi ( 吼v vq t i - t ) ) 。 2 ) z i p f 估计量：在文献 9 中，i p e i r o t i s 提出了一种方法来估计某一文档子集中 的特定术语在整个文档集中出现了多少次。此方法利用了这样一个事实：文 本集中的词频规律对此问题有很大贡献。也就是说，根据述语出现的频率排 列所有述语的等级，最高等级的标记为l ，次之标记为2 ，依此类推。这样在 文本集中的术语频率f 被定义为 f = 口( y + ) 。 式中：厂表示术语的排列等级，口，7 是由此文本集决定的常量。可以使用上 述公式来估计p ( q ，) 的值。 6 查询选择算法 隐蔽网爬虫设计的目标是使用有限资源从后台数据库中下载最大数量的目 的文档资源。为了达到此目标，爬虫设计主要考虑两方面的因素：一方面是选择 查询关键词吼，使其可以返回最大数量的新文档；另一方面是查询g ，所花费代价 问题。例如：对于两个不同的查询选择q ，和g ，若在相同代价的情况下，查询吼 l l , q ，返回更多数量的相关的新页面，则认为查询q ，l t , q ，更有“希望”。基于此发 现，这里给出了爬虫查询选择算法效能评价标准的一个形式化的定义： 9 浙江人学硕士学位论文 第l 章绪论 e f f i c i e n c y ( q f ) = 只。( g f ) c o s t ( q f ) 这里只。( g ，) 代表查询g ，返回新的页面数占站点可能总页面数的一个比例， c o s t ( q ，) 代表查询q ，所花费的总代价。直觉上效能评价标准反映的是对于查询q ， 单位代价下可以获取多少新的文档页面。隐蔽网爬虫可以以此来估计每个查询g ， 的效能，下一次将要选择的关键词就是效能值最大的那个关键词。下面出了查询 选择算法，原则上此算法是个“贪婪”算法，它可以获得潜在的最优解。 p a r a m e t e r s ：t ：潜在的查询关键词列表 p r o c e d u r e ( 1 ) f o re a c ht ki ntd o ( 2 ) e s t i m a t ee f f i c i e n c y ( t k ) = p 。w ( t k ) c o s t ( t k ) ( 3 ) d o n e ( 4 ) r e t u r nt kw i t hm a x i m u me f f i c i e n c y ( t k ) 可以使用上述算法计算每种潜在查询的效能值。查询q ，返回的新文档数占可能文 档总数的比例为 只。( 吼) = p ( q lv v q v q i ) 一p ( 吼v v q t l l 】) = p ( q f ) 一p ( q lv v q i i - h ) p ( g f | q iv v q t l - 1 1 ) 同样地也可类似的估计c o s t ( q ，) ，若采用公式c o s t ( q ，) = c 口+ c ，p ( q ，) + e 。( g f ) 。 可以通过估计p ( q ，) 和匕。( 吼) 来估计c o s t ( q ，) 。 1 2 2 垂直搜索时效性问题研究现状 垂直搜索抓取系统往往会对结果的时效性有要求，而互联网的网页是在不断 变化，为了解决抓取的时效性问题，在文献【1 l 】中介绍了基于检测目标网站更新 规律的方法，下面介绍该文中介绍的形式化定义以及算法。 爬虫程序在一个周期内只能下载固定数量的网页，把这个固定的数量定义为 下载资源数( d o w n l o a dr e s o u r c e s ) ，而这个周期称之为下载周期( d o w n l o a dc y c l e ) 。 这样，目标就是在给定的下载资源数条件下在每个下载周期内尽可能地下载最多 l o 浙江大学硕士学位论文第l 章绪论 的更新过的网页。 网页抽样的更新检测算法基于这样一个假设：相关的网页有相似的更新模 式。在每个下载周期中，爬虫随机地从本地已抓取的网页中选出一部分作为样品， 然后从目标网站获得这些网页的最新数据，比较本地数据和最新线上数据，再结 合下载概率巾，爬虫程序决定是否讲这些样品作为种子，然后下载和它们的距离 在一定范围内的相关网页，这个距离称为下载粒度d 。 1 下载策略 上文中提到的下载粒度d 决定了给定一个样品网页，需要下载哪些和其相关 的网页，d 的定义不同直接决定了下载策略的不同，有两种不同的下载策略： 1 ) 基于链接的下载策略( l i n k b a s e d l b ) 下载粒度d 定义为两个网页a 、b 之间a 最多需要通过几次链接到b 。 2 ) 基于目录结构的下载策略( d i r e c t o r y - b a s e d d b ) 下载粒度d 定义为两个网页的u r l 深度的差别，也就是两个网页的u r l 中 包含的，”数量之差加1 。 2 下载概率 比较抽样网页的本地数据和最新线上数据，根据几种不同的方法，可以得到 不同的下载概率巾，该参数即决定是否需要对更新和抽样网页相关( 即下载粒度 d 符合预设条件) 的网页。 1 ) 最基本的方法 根据网页的最近一次更新情况来决定巾，如公式卜1 ，f1 如果抽样网页更新 矽= 1o其他 ( 公式1 - 1 ) 2 ) 基于历史数据权重策略( h ah w a ) 将网页p 的变化率定义为入p ，当p 在一个周期内变化时，得到概率由为公 浙江大学硕十学位论文第1 章绪论 i - 2 所示： = p 尸 丁 = f 兄p p 一砟f = 1 一e 一乙 ( 公式1 2 ) 其中入p 由网页p 在n 个周期内的历史变化规律计算得到，见公式( 1 3 ) 允p = 栉i = 1w ，1 ( p ，)- z、z7 ( 公式1 - 3 ) 这里i l ( p i ) 是一个指示函数，当网页p 在第i 个周期变化，其值为1 ，否则为0 。 而w i 是在不同的周期中变化的权重。一般来说，越接近当前时间的周期其变 化越重要，也就是权重w i 越高。将权重、研设为= f 罗? ，其中n 表示到 现在为止一共经历的下载周期数。 3 ) 基于p a g e r a n k 的策略( p r a ) 将巾设置为在p a g e r a n k 算法中该网页p 的流行比例，计算公式如下： 矽咧= 百1 - d 蚓乃邑，筹 ， 其中p l ，p 2 ，p n 是网页，i l ( p i ) 是链接到p i 的网页集合，o l ( p j ) 是p j 3 算法评价 对照上述几种不同策略，将下载周期设为两个星期，下载资源数设为2 5 0 0 0 个网页，用变化率作为度量标准，变化率( c h a n g e r a t i o ) 定义为在一个下载周期内 已下载的更新网页数量除以总的网页数量。e 为每个下载周期内的变化率，c 为 所有周期内的平均变化率。 首先，根据下载粒度d 的两种不同定义，测试l b 和d b 的性能表现，下载 概率对变化的网页设为l ，没有变化的网页设为0 ，d 的取值范围为0 - 6 ，结果见 图1 2 1 2 浙江大学硕 学位论文第1 章绪论 秀 甏 2 霪 落 霪 爱 e 1 彳3 4 霸 隗嘞 图1 2 两种不同下载策略的表现，d b 优于l b 很明显d b 策略优于l b 策略，因此应当选用目录结构做为寻找相关网页的策略。 接下来，测试对于不同的下载概率计算方法对c 的影响，结果见图1 3 0123456 锄陟 图1 3p a g e r a n k 方法计算下载概率和基本方法的比较 从图中可以看出，p r a 算法的结果c 几乎是基本方法的两倍。 最后，图1 4 给出的是多个周期内，基于历史数据权重策略( h aw h a ) 和d b 的性能比较，可以看出，刚开始，两种基于历史数据的策略表现要低于d b ，然 而随着时间推移，两种策略的性能一直上升，知道超过d b ，这表明程序在长期 运行时，将过去的变化数据考虑进来会对预测将来的变化有很好的效果。而w h a 的性能优于h a 则说明在考虑历史变化数据时应该更多的考虑离当前时间更近的 下载周期。 弘 一 携 黼 弘 e e e f e 瑟秀嚣，移m鎏“露簿 浙江大学硕十学位论文第1 章绪论 3s 7罄 1 3 ，s1 7 饴2 1 筋 渤摊哟嘲e 弦溉 图1 4w h a 、h a 和d b 在2 4 个周期内的比较 1 3 本文的工作和组织 本文首先设计了一个垂直搜索抓取系统的框架，然后讨论抓取中遇到的一些 问题：隐蔽网抓取问题，时效性问题，以及性能与效率问题。 对于隐蔽网抓取问题，当前的研究热点如前文所说关于隐蔽网抓取大多是关 注于隐蔽网的切入点发现以及针对表单的查询构造，本文将主要针对隐蔽网的另 一个问题：结果消重，提出了一种自学习的中文地址判重方法。 针对时效性问题，传统的时效性解决方法：检测目标网站更新规律、基于用 户查询分布概率等在面对高时效性需求时其时效性和带宽消耗均不够理想，本文 提出了一种基于查询驱动的实时抓取解决这一问题。 垂直搜索抓取系统的总体目标是以更少的消耗抓取更多、更新的数据。本文 给出了不同抓取模式、抓取策略和抓取频率的对比，并采用了稳定持续模式、及 时替换式更新、实时抓取与固定频率相结合的方式。 本论文共分七章。 1 ) 第1 章绪论。本章介绍论文的选题背景和意义、国内外相关领域技术的现状 以及论文的组织结构。 2 ) 第2 章垂直搜索抓取系统框架。本章介绍了垂直搜索抓取系统的体系结构， 1 4 3 骞 2 s ， 6 o o 纰 戳 孙 巍 瓣 。嘿笺c雾 浙江人学硕士学位论文第l 章绪论 主要是分布式的构架以及基于可扩展插件方式解决垂直搜索抓取系统中遇到 的一些问题 3 ) 第3 章垂直搜索抓取系统的隐蔽网抓取。本章首先介绍隐蔽网抓取在垂直搜 索抓取系统中的重要性和隐蔽网抓取遇到的几个问题，并提出了一种自学习 的中文地址判重方法。 4 ) 第4 章垂直搜索抓取系统的时效性。本章提出垂直搜索抓取系统的时效性问 题和，并提出一种基于查询驱动的实时抓取解决高时效性要求问题。 5 ) 第5 章垂直搜索抓取系统的效率与性能。本章介绍并比较了垂直搜索抓取系 统的总体抓取模式、总体更新策略和抓取频率，介绍了我们的系统中所采取 的方式以及优缺点。 6 ) 第6 章测试和实验。给出了自学习的中文地址判重方法以及基于查询驱动的 实时抓取实验数据和对比。 7 ) 第7 章总结与展望。总结了论文创新点，展望了垂直搜索抓取系统中值得继 续优化和解决的问题。 浙江大学硕十学位论文 第2 章垂直搜索抓取系统框架 第2 章垂直搜索抓取系统框架 2 1 垂直搜索抓取系统的体系结构 本文的抓取系统体系结构如图2 1 所示，其中为解决垂直搜索的隐蔽网抓取 结果判重、时效性等问题我们采用了基于可扩展插件的模式，在系统中加上抓取 结果判重插件、时效性处理的插件等。而性能和可扩展性我们采取了分布式的结 构。将在本章的后两节中讲述。 前台w e b 服务器 图2 1 垂直搜索抓取系统体系结构 2 2 垂直搜索抓取策略可扩展插件 垂直搜索抓取中遇到的问题在本文的抓取系统中利用可扩展插件的设计模 式来解决这些问题。常见的插件模式有a o p 、f i l t e r 、h o o k 等等。 1 6 浙江人学硕七学位论文第2 章垂直搜索抓取系统框架 1 )a o p a o p 曾经主要用于学术和研发机构，如今开始进入主流开发领域。与o o p 在面向过程的编程方法基础上的改进一样，a o p 是在面向对象编程( o o p ) 方法 的基础上进行改进而来的一种创新的软件开发方法。o o p 引入了封装、继承和多 态性等概念来建立一种对象层次结构，用以模拟公共行为的一个集合。然而，o o p 在处理范围扩展到一些无关对象的公共行为方面达不到要求。也就是说，o o p 允 许你定义从上到下的关系，但并不适合定义从左到右的关系。例如，看一下日志 功能。日志代码往往水平地散布在所有对象层次中，而与它所散布到的对象的核 心功能毫无关系。对于其他类型的代码，如安全性、异常处理和透明的持续性也 是如此。这种散布在各处的无关的代码被称为横切( c r o s s c u t t i n g ) 代码，这也是 a o p 编码方法产生的原因。 a o p 提供一种提取横切代码的方法，这种横切代码横跨各个对象层次，但与 它所跨越的对象代码在功能上没有相关性。a o p 不是在类中嵌入横切代码，而是 允许你将横切代码提取到一个单独的模块中，然后在需要的时候动态地应用该代 码，这个单独的模块叫做一个“特征代码”( a s p e c t ”，也译作“标记”) 。通过在你 的对象模型中需要应用横切代码的地方定义特定的位置一切入点( p o i n t c u t ) 一来实 现动态的应用横切代码。在运行或编译时，根据你的a o p 框架，横切代码被插 入指定的切入点。本质上说，a o p 允许你在对象中引入新功能，而对象无需了解 所引入的功能。这是一个非常有用的概念。 2 ) f i l t e r f i l t e r 功能使用户可以改变一个r e q u e s t 和修改一个r e s p o n s e f i l t e r 不是一个 s e r v l e t ，它不能产生一个r e s p o n s e ，它能够在一个r e q u e s t 到达s e r v l e t 之前预处理 r e q u e s t ，也可以在离开s e r v l e t 时处理r e s p o n s e 。换种说法，f i l t e r 其实是一个”s e r v l e t c h a i n i n g ”( s e r v l e t 链) 。一个f i l t e r 包括： a ) 在s e r v l e t 被调用之前截获； b ) 在s e r v l e t 被调用之前检查s e r v l e tr e q u e s t ； c ) 根据需要修改r e q u e s t 头和r e q u e s t 数据； 浙江大学硕+ 学位论文第2 章垂直搜索抓取系统框架 d ) 根据需要修改r e s p o n s e 头和r e s p o n s e 数据； e ) 在s e r v l e t 被调用之后截获。 你能够配置一个f i l t e r 到一个或多个s e r v l e t ，单个s e r v l e t 或s e r v l e t 组能够被多个 f i l t e r 使用。几个实用的f i l t e r 包括：用户辨认f i l t e r 、日志f i l t e r 、审核f i l t e r 、加 密f i l t e r 、符号f i l t e r ，能改变x m l 内容的x s l