（计算机应用技术专业论文）垂直搜索引擎关键技术研究及应用.pdf

华北电力大学硕+ 学位论文摘要 摘要 本文主要研究了垂直搜索引擎实现的关键技术，从细节上对两个核心模块，即 主题爬虫技术和索引技术进行了深入地研究分析。在主题爬虫的设计中，通过结合 基于内容和链接分析的主题相关性的搜索策略，利用基于内容的评价提高搜索内容 与主题资源的相关度，利用链接结构的评价来提高主题资源的覆盖率，从而有效的 提高了爬虫的性能；从索引文件本身的结构出发，采用分级的倒排表索引组织结构， 改进了传统倒排表索引器的实现方案，提高了索引创建的效率；最后，结合开源项 目n u t c h 的索引，设计并实现了一个基于数码主题信息的垂直搜索引擎，通过相关的 试验，验证了系统可以为用户提供比较完整准确的主题信息查询服务。 关键词：主题爬虫，向量空间模型，p a g e r a n k 算法，倒排表 a b s t r a c t t h et h e s i ss t u d i e dm ek e y t e c l l l l o l o 百e st ot h er c a l i z a t i o no fv e n i c a ls e a r c h ，r e s e 砌锄l d a l l a l y s i st l l e 觚oc o r em o d u l e s ，t l l em e m es p i d e r s 锄dm d c x i n gt 池l o g y 缸忸d “l s i n d 印m h lm ed e s i 盟o fs p i d t l l 】r o u g l lm e m er e l e v 锄c es 蚴油s 仃a 钯g yc o n l b i n e do f c o n t e n t 觚dl i i l l ( 觚a l y s i s ，a n di l l f o v e l 锄e - r e l a t e dd e 孵s 廿l 】r o u 曲c o n t t - b 嬲e d e v a l u a t i o i l ，m l p r o v em em e m er e s o l l r c 韶c o v e r a g e 1 0 u g hm ee v m u a t i o no fl i i 】i l 【鼬n l c 嘶，s o 舔t 0i l n p r o v ep e f f o m a n c co fs p i d e re 虢c t i v e l k 舶ms 叽c t 哪汜o f 1 ei n d e x 丘l ei t s e l a d o p t i n gad 嬲s i f i c a t i o ni n v e n e dt a l ) l et 0i 1 1 d e xo f 圮。玛觚i z a t i o n a ls 协l c ：t u ：r e ，a n di m p r o v c t t l e 仃a d i t i o n a li n l p l e m e n t a t i o np r o g 阳mo fi n v e f t e di i l d e x i n gt a _ b l e ，i n l p r 0 v o di n d e x 删e d e 伍c i e i l c y ；f i n a l l y ，c o m b i n ei n d e x i n gt e c l l i l o l o 影o f0 p e i ls o u r c ep r o j e c tn l j t c h ，d e s i 印觚d i n l p l 锄e n to fad i 百t a li n f o r m a t i o nt l l 锄e - b 弱e dv e r t i c a ls e a r c he n 百n e ，t h r o u g hm er e l e v 觚t t e s t s ，v e r i 匆m es y s t e mc a np r 0 v i d eu s e r sw i n li i l o r cc o m p l e t ea n da c 砚玎a t et l l et l l e m e i n f o m l a t i o ni n q u i r i n gs e r v i c e s w a n gy u h u i ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db ya s s o c i a t ep r o fc h e n gx i a o r o n g k e yw o r d ：t h e m es p i d e r v e c t o rs p a c em o d e l ，p a g e r a n ka l g o r i t h m ，i n v e r t e dt a b l e 华北电力大学硕+ 学位论文摘要 摘要 本文主要研究了垂直搜索引擎实现的关键技术，从细节上对两个核心模块，即 主题爬虫技术和索引技术进行了深入地研究分析。在主题爬虫的设计中，通过结合 基于内容和链接分析的主题相关性的搜索策略，利用基于内容的评价提高搜索内容 与主题资源的相关度，利用链接结构的评价来提高主题资源的覆盖率，从而有效的 提高了爬虫的性能；从索引文件本身的结构出发，采用分级的倒排表索引组织结构， 改进了传统倒排表索引器的实现方案，提高了索引创建的效率；最后，结合开源项 目n u t c h 的索引，设计并实现了一个基于数码主题信息的垂直搜索引擎，通过相关的 试验，验证了系统可以为用户提供比较完整准确的主题信息查询服务。 关键词：主题爬虫，向量空间模型，p a g e r a n k 算法，倒排表 a b s t r a c t t h et h e s i ss t u d i e dm ek e yt e d m o l o 百e st ot h er c a l i z a t i o no fv e n i c a ls e a r c h ，r e s e 砌锄l d a l l a l y s i st l l e 觚oc o r em o d u l e s ，t l l em e m es p i d e r s 锄dm d c x i n gt 池l o g y 舶md “l s i n d 印m h lm ed e s i 盟o fs p i d t l l 】r o u g l lm e m er e l e v 锄c es 蚴油s 仃a 钯g yc o n l b i n e do f c o n t e n t 觚dl i i l l ( 觚a l y s i s ，a n di l l f o v e l 锄e - r e l a t e dd e 孵s 廿l 】r o u 曲c o n t t - b 嬲e d e v a l u a t i o i l ，m l p r o v em em e m er e s o l l r c 韶c o v e r a g et i l o u g hm ee v m u a t i o no fl i i l l 【鼬n l c 嘶，s o 舔t 0i l n p r o v ep e f f o m a n c co fs p i d e re 虢c t i v e l k 舶ms 叽c t 哪汜o f 1 ei n d e x 丘l ei t s e l a d o m i n gad 嬲s i f i c a t i o ni n v e r t e dt a ：b l et 0i n d e xo ft i 圮。玛a i l i z a t i o n a ls 仃u c 舡l r e ，a n di m p r o v c t ：h e 仃a d i t i o n a li n l p l e m e n t a t i o np r o g 阳mo fi n v e f t e di i l d e x i n gt a _ b l e ，i n 呻v o di n d e x 删e d e 伍c i e i l c y ；f i i l a l l y ，c o m b i n ei 1 1 d e x i n gt ec _ t l i l o l o 影o f0 p e i ls o u r c ep r o j c c t d e s i 印觚d i n l p l 锄e n to fad i 百t a li n f o m l a t i o nt l l 锄e - b 弱e dv e r t i c a ls e a r c he i l 百n e ，t h r o u g hm er e l e v 觚t t e s t s ，v e r i 匆m es y s t e mc a np r 0 v i d eu s e r sw i n lm o r cc o m p l e t ea n da c c i 玎a 1 e t l l et l l e m e i n f o m l a t i o ni n q u i r i n gs e r v i c e s w a n gy u h u i ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db ya s s o c i a t ep r o fc h e n gx i a o r o n g k e yw o r d ：t h e m es p i d e r v e c t o rs p a c em o d e l ，p a g e r a n ka l g o r i t h m ，i n v e r t e dt a b l e 声明户明 本人郑重声明：此处所提交的硕士学位论文垂直搜索引擎关键技术研究及应 用，是本人在华北电力大学攻读硕士学位期间，在导师指导下进行的研究工作和 取得的研究成果。据本人所知，除了文中特别加以标注和致谢之处外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得华北电力大学或其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明并表示了谢意。 学位论文作者签名：垦垂逐日期：2 旦旦2 垂! 目乡日 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校有权 保管、并向有关部门送交学位论文的原件与复印件；学校可以采用影印、缩印或 其它复制手段复制并保存学位论文；学校可允许学位论文被查阅或借阅；学校 可以学术交流为目的，复制赠送和交换学位论文；同意学校可以用不同方式在不同 媒体上发表、传播学位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 作者签名：至垂竖 日 期：五丘雄! 目! 硼 导师签名： 日期： 华北电力人学硕士学位论文 1 1 课题背景及意义 第一章引言 随着网络与通信技术的迅速发展，w 曲信息爆炸性的增长，互联网已经成为一 个巨大的海量信息空间。如何快速、准确、方便的从如此庞大的信息库中获取自己 需要的信息，是互联网用户面临的一个重要问题。搜索引擎的出现，整合了众多网 站的信息，极快的查询起到了信息导航的作用，信息的价值得到众多商家的普遍认 可，成为互联网中最有价值的领域。大家熟知的搜索引擎g 0 0 9 l e 、百度、雅虎等都 是搜索引擎的杰出代表，为互联网的发展做出了重要的贡献。但同时，随着互联网 信息量的飞速增长带来的则是搜索服务品质的下降，查询结果里存在大量的重复信 息和垃圾信息，用户感觉到很难在短时间内准确的筛选出需要的内容，尤其是专业 化程度比较高的行业信息。市场需求多元化的发展决定了搜索引擎的服务模式必将 出现细分，针对不同行业提供更加精确的行业服务模式。因此，如何对传统搜索引 擎技术进行改进，使查询的结果集合更加贴近用户的要求，成为搜索引擎行业的研 究热点。 垂直搜索引擎应运而生。所谓垂直搜索，。就是针对性的为某一特定领域、某一 特定人群或某一特定需求提供的有一定价值的信息和相关服务。可以简单的说成是 搜索引擎领域的行业化分工。它采用的基本技术同传统搜索引擎相似，本质的区别 是它的搜索器搜索的是特定的主题信息，按预先己经定义好的主题有选择地收集相 关的网页，这样大大降低了收集信息的难度。垂直搜索的主要优势即在于：针对性 强，对特定范围的网络信息的覆盖率相对较高，具有可靠的技术和信息资源保障， 有明确的检索目标定位，有效地弥补了传统搜索引擎对专门领域及特定主题信息覆 盖率过低的问题。 1 2 搜索引擎概述 搜索引擎，就是因特网上一种基于w w w 的信息检索工具，用来检索w 曲网站、 w 曲网页、新闻组、图片、声音等w e b 文件。它实际上是一个专用的w w w 服务器， 也可以说是互联网上提供信息检索服务的网站。这类网站与一般网站不同的是，其 主要功能是采用人工或自动的方式去搜寻w w w 上的信息，并将网络信息进行分类、 建立索引，再把索引的内容存放到索引数据库中，通过查询语法为用户返回匹配的 资源，以帮助用户在i n t e m e t 中搜寻所需要的信息。面对浩瀚的网络资源，搜索引擎 为所有网上冲浪的用户提供了一个入口，毫不夸张的说，所有的用户都可以从搜索 华北电力大学硕+ 学位论文 引擎出发到达自己想去的网上任何一个地方。 纵观搜索引擎技术的发展过程，我们认为搜索引擎大体经历以下四代： ( 1 ) 经典信息检索理论为基础的第一代搜索引擎 第一代搜索引擎出现在1 9 9 4 年。它的实现基于较为成熟的信息检索技术 ( i n f o 彻a t i o nr 矧e v a l ，i r ) ，相当于利用己有的信息检索技术实现的一个w e b 上的应 用。但是，它所索引的网页数量少、检索时间长，用户访问数量也很少，这一代存 在的时间比较短，很快就出现了第二代搜索引擎。 ( 2 ) 以分布式为特征的第二代搜索引擎 为提高数据存储规模和响应速度，大约在1 9 9 6 年出现了采用分布式方案( 多个微 型计算机协同工作) 的搜索引擎系统，分布式网络爬虫和分布式数据库的应用是这一 代搜索引擎的主要特点。 ( 3 ) 以人工智能为特点的第三代搜索引擎 自1 9 9 8 年到现在，进入搜索引擎空前繁荣的时期，我们统称这一时期出现的搜 索引擎为第三代搜索引擎。它主要有三个特点：除了一般意义上的搜索以外，出 现了主题搜索和地域搜索等服务。积极采用w 曲数据挖掘技术，研究内容除了w 曲 内容挖掘以外，还包括超链分析和用户使用记录的挖掘。积极采用自动分类技术 来提高网络爬虫、信息处理和信息组织的能力。 ( 4 ) 垂直搜索引擎( v ；c 舭i c a ls e a r c he n g i n e ) _ 第四代搜索引擎 垂直搜索引擎，就是为查询某一学科或主题的信息而产生的查询工具，专门收 录某一方面、某一行业或某一主题的信息，所以有的文献也称之为“主题搜索引擎 或“专业搜索引擎。垂直搜索引擎是与通用搜索引擎对应的一个概念，垂直搜索 引擎提供的资源都是与某个领域或主题相关的，与通用搜索引擎相比，垂直搜索引 擎在服务上更有专业特色，有一定程度的个性化。由于垂直搜索运用了诸如人工分 类、专业领域知识等智能化的策略，因此它比上面提到的前三代搜索引擎将更加有 效和准确，我们将这类完善的垂直搜索引擎称为第四代搜索引擎。 它与前三代搜索引擎( 可以统称通用搜索引擎) 相比，存在很大的差别：第一， 垂直搜索引擎面向专业用户，向他们提供对特定专业的信息检索。第二，通用搜索 引擎对网络进行逐页的爬行，试图遍历整个w e b ，而垂直搜索引擎则采用一定的策 略预测相关网页的位置，动态的调整网页的爬行方向，使系统尽可能的在与主题相 关的网页集中的地方爬行，这可以节约大量的网络资源。第三，对硬件和网络的要 求不同，垂直搜索引擎由于不必遍历整个、b ，不需要有自己的大型的索引库，对 2 华北电力大学硕+ 学位论文 硬件要求就不是很高。 1 3 垂直搜索引擎国内外研究现状 1 3 1 垂直搜索引擎的产生 通用搜索引擎的出现在很大程度上解决了人们在互联网上查找信息的困难，但 是目前通用搜索引擎在使用中也面临着许多问题。 ( 1 ) 大规模的分布式数据源，基于w 曲的自身特点，大量的数据都分布在以数 以亿计的计算机为基础的互联网上，检索起来困难重重，单个搜索引擎的索引数据 库的覆盖率一般都低于3 0 ，很难索引所有w 曲资源。 ( 2 ) 网络信息的质量问题，互联网上信息无论从数量和类型都呈指数增长，但 大量信息的存活期却在大幅缩短，这导致搜索引擎的索引的及时性难以保持，大量 返回结果为无效或过时的d ( 3 ) 大量的动态页面导致无法检索，目前越来越多的w e b 网站使用了数据库和 动态页面生成技术，而通用搜索引擎无法检索到这些页面。 ( 4 ) 大量的多媒体信息和网上存在的多语种问题均需要被处理，因为即便是文 本信息也存在大量不同的文本格式。 ( 5 ) 忠实表达的问题，经典的信息检索理论认为用户很难简单地用关键字来忠 实表达他所真正需要检索的内容，也不知道如何更准确地寻找所需信息，表达的困 难将导致检索结果的不理想，而且如何将结果表达成用户容易理解和使用的方式也 是一个难题。 ( 6 ) 一次搜索的结果可能有成千上万条，而在这过于庞大的信息群中，有用信 息只是其中的小部分，并且常常发生收到和下载的信息难以消化的情况，即所谓的 “认知过载”【1 1 。 通用搜索引擎的种种弊端在网络信息的急剧膨胀下突显起来，搜索越来越难以 控制，用户需求和市场服务间的巨大反差产生了强大的“搜索噪音 ，人们呼唤更 有针对性的搜索引擎，垂直搜索引擎的出现成为搜索引擎发展史上的一块里程碑。 垂直搜索引擎由于所收集的学科领域小，信息量相对较少，可以采用有针对性的方 法对收集到的信息进行组织整理，进一步提高信息的质量，建立一个高质量的、专 业信息收集全的数据库。 1 3 2 垂直搜索研究现状 华北电力大学硕+ 学位论文 垂直搜索正在成为国内外相关领域的一个热点。垂直搜索引擎概念的提出，基 于自身突出的特点专、精、深，也就是说针对性的为某特定领域、某一特定人群 或某一特定需求提供的有一定价值的信息和相关服务，可以简单的说成是搜索引擎 领域的行业化分工。通用搜索引擎的性质，决定了其不能满足特殊领域、特殊人群 的精准化信息需求服务，市场需求多元化决定了搜索引擎的服务模式必将出现细 分，针对不同行业提供更加精确的行业服务模式。 从垂直搜索的数据来源看，可以是源于所处行业的各个相关站点提取而来，也 可以是来源于自身超大的数据集合，它的应用方向也很多，比如供求信息搜索、论 坛搜索、生活搜索、m p 3 搜索、人才搜索、地图搜索和图片搜索等等，几乎各行各 业各类信息都可以进一步细化成各类的垂直搜索引擎，市场非常丰富，发展潜力巨 大。 比较具代表性的垂直搜索系统主要有： ( 1 ) e l s e v i e r 的s c i m s 系统 s c i m s 科学搜索引擎是一种专为搜索高度相关的科学信息而设计的搜索引擎， 获得2 0 0 l 搜索引擎观察授予的“最佳专业搜索引擎奖”。s c r i u s 是目前互联网 上最全面、综合性最强的科技文献门户网站之一，它只面向包含有科学内容的网站， 如大学和作者个人主页以及e l s e v i e r 自己的数据库。 ( 2 ) b e r k e l e y 的f o c u s e dp r o i j e c t 这个系统由一个印度裔的科学家s c h 破r a b a r t i 带头研究开发，他是最早从事这 方面研究的人之一。该系统通过两个程序来指导爬虫：一个是分类器( c i a s s i f i e r ) ， 用来计算下载文档与预定主题的相关度。另一个程序是净化器( d i s t i l l 哪，用来确定 那些指向很多相关资源的页面。 ( 3 ) n e c 研究院的c i t e s e e r c i t e s e e r 是一个非常有名的针对计算机科学领域论文的检索系统。c i t e s e e r 的核 心是a c i ( a u t o m a t i c a l l yc i t a t i o nl n d e x ) 【6 l ，它可以自动地对网上的电子文件 ( p o s t s c r i p t 和p d f 等格式) 进行索引并分类。 ( 4 ) 美国国家科学数字图书馆的c o l l e c t i o nb u i l d i n gp r o g r a m ( c b p ) 这个项目旨在为科学、数学、工程和技术创建大规模的在线数字图书馆，试图 研究在某一主题上资源自动建设的可能性。c b p 有自己的特点：第一，因为c b p 是面向教育教学的，主题精确度比覆盖度更为重要。第二，c b p 不存储资源原文， 4 华北电力人学硕士学位论文 而只是提供u r l ：第三，c b p 只需要用户最少量的输入，如关键词，系统就可以全 自动的将有关该主题的最相关的u r l 返回给用户。 综上所述，随着相关技术的完善与发展，垂直搜索引擎的发展方向可以概括如 下： ( 1 ) 智能化：面对互联网的海量信息，很难保证信息的实时性和有效性，对智 能化的结构化信息提取技术的需求非常迫切。 ( 2 ) 深度挖掘型搜索：深度挖掘型垂直搜索引擎通过对元数据信息进行深度加 工，为用户提供网页搜索引擎无法做到的专业性、功能性和关联性，能很好地满足 用户对专业性、准确性、功能性和个性化的需求。 ( 3 ) 向搜索交易平台发展：垂直搜索引擎由于自身对行业的专注，使得它可以 提供行业信息深度和广度的整合以及更加细致周到的服务，对消费领域可以推出针 对某一行业的搜索交易平台，类似e b a y ，t a o b a o 那样的购物平台。 可以这样说，通用搜索引擎的发展为垂直搜索引擎的出现提供了良好的市场空 间，垂直搜索引擎势必将在互联网中占据一席之地，这也是搜索引擎行业细分化的 必然趋势，但前提是相应的垂直搜索理论技术需要得到更进一步的研究与发展。 1 3 3 垂直搜索领域发展面临的问题 垂直搜索的技术门槛不是很高，但要想做好它却是很有挑战的工作。一方面， 能否整合并驾驭好行业资源，是非领域内的专业人士难以胜任的。另一方面，衡量 一个垂直搜索引擎的标准需要考虑以下几方面： ( 1 ) 全面性 全面性对于一个垂直搜索引擎而言，要求其关注领域的方方面面都应该涉及， 自然要求关注该领域的站点也愈多，并且信息量也与之成正比。例如一个生活搜索 引擎，便要求能包罗衣食住行在内的各种信息，拥有与之相关的站点信息必定也越 多。 ( 2 ) 更新性 与通用搜索引擎相比，垂直搜索关注的面越小，对信息的价值要求愈高，更新 频率须迅速。以“酷讯的火车票搜索为例，其更新频率常在数秒钟之内，因为火 车一旦发出，信息便和过期车票一样，没有丝毫用处了。 ( 3 ) 准确性 5 华北电力人学硕十学位论文 作为专注于某一行业的搜索引擎，其对信息准确性的要求远远高于通用搜索引 擎。 ( 4 ) 功能性 在专业化领域需要与之搭配的完善的搜索服务，例如供求信息搜索应当支持信 息收藏、信用评价、甚至比价等全方位功能服务。 基于以上情况分析，不难发现，要做好垂直搜索的关键在于解决：如何快速、 准确地从主题相关的领域内获取结构化程度比较高的数据信息。相对于通用搜索引 擎，垂直搜索不仅要在信息检索环节上下足工夫( 如增加对结构化数据字段的排序 等) ，更须在信息采集环节上做好与业务相关的结构化数据和元数据的提取和挖掘 工作。因此，当前面临的问题与挑战主要包括信息抽取和网络深层次挖掘等。 1 4 本文的主要研究内容 论文的主要内容安排如下： 第1 章为绪论，针对课题的研究背景，搜索引擎技术的发展，重点分析了垂直 搜索引擎的相关概念，国内外发展现状，以及发展过程中面临的问题和挑战。 第2 章主要研究了垂直搜索的基本理论及其实现所需要的关键技术，包括主题 爬虫技术，全文检索技术等，重点分析了爬虫的几种常用搜索策略以及页面相关度 计算的经典算法向量空间模型( v s m ) 算法。 第3 章对垂直搜索引擎最核心的模块，主题搜索爬虫进行了研究和设计，从细 节算法上对该模块进行了实现。 第4 章研究了中文全文检索索引设计的主要技术问题，对基于单字和改进倒排 表索引的全文检索索引器的设计方案进行了实现。 第5 章对系统进行了相关实验，并且对实验结果做了详细的分析。 第6 章总结了系统的研究和开发经验，找出了一些不足之处，并指出今后需要 进一步改进的问题和研究的方向。 6 华北电力大学硕十学位论文 第二章垂直搜索引擎相关理论和关键技术 2 1 主题爬虫技术研究 2 1 1 主题爬虫工作流程 垂直搜索引擎和通用搜索引擎相比，在网页采集技术上有很大的不同。通用搜 索引擎的网络爬虫从一个或若干初始网页的u r l 开始，获得初始网页上的u r l ， 在抓取网页的过程中，它不断从当前页面上抽取新的u r l 放入队列，直到满足系统 的特定停止条件：而垂直搜索引擎因为和某一领域或某一主题密切相关，所以其爬 虫( 在本文中统称为“主题爬虫”) 的算法及工作流程较为复杂，需要根据一定的网页 分析算法过滤与主题无关的链接，保留有用的链接并将其放入等待抓取的u r l 队 列，然后，它将根据一定的搜索策略从队列中选择下一步要抓取的网页的u r l ，并 重复上述过程，直到达到系统的某一特定条件时停止，如图2 1 为普通爬虫和主题 爬虫的工作流程对比。 否| 厂j l ；厂 ；l 堡竺翌竺! ! ! 竺仝! 竺坠型i ， i 适多 足： 图2 1 通用爬虫和主题爬虫工作流程对比图 另外，被爬虫抓取的网页将会被系统存储，进行一定的分析、过滤，并建立索 7 宣 _ 华北电力大学硕士学何论文 引，以便以后的查询和检索；对于主题爬虫来说，这一过程所得到的分析结果还可 能对以后的抓取过程给出反馈和指导。 2 1 2 主题爬虫结构模型 主题爬虫的设计是以普通爬虫为基础，对其进行功能上的扩充，主题爬虫包括 以下三个关键组成部分，图2 2 为系统结构模型图。 匪匦 图2 2 主题爬虫结构模型图 ( 1 ) 采集模块：该模块是任何爬虫都不可或缺的通用模块，该模块负责协调超 链接分析模块和页面相关度分析模块的工作。首先，爬虫采集模块从待爬行u r l 队列中取出链接相关度较高的u r l ，将该u r l 相应的网页采集到本地，然后，将 该页面交由页面相关度分析模块处理。在整个爬行过程中，爬行的次序和爬行策略 都有链接分析模块提供。 ( 2 ) 链接分析模块：该模块是主题爬虫的核心模块，计算从主题相关页面解析 出来的u r l 与主题的相关度，并提供相关的爬行策略用以指导爬虫的爬行过程。 u r l 的链接评价分析得分越高，爬行的优先级就越高。反之，若通过一定的分析评 价策略，发现某链接与主题无关，则将该u r l 及其所有隐含的子链接一并去除，这 个过程我们称之为“剪枝”。不过“剪枝”的行为可能将潜在的与主题相关的页面也 剪掉。因此，链接分析模块所用的策略的好坏直接影响着爬虫的爬行效率以及爬行 质量。 ( 3 ) 相关度分析模块：该模块主要特点是引入了文本分类的思想。在爬虫爬行 之初，页面相关度分析模块根据用户输入的关键字和初始文本信息进行比较( 也可以 说是训练一个页面相关度分析模型) 。当一个被认为是主题相关的页面爬行下来之 8 华北电力人学硕士学位论文 后，该页面就被送入页面相关度分析模块，计算其主题相关度值，若该值大于或等 于给定的某阈值，则该页面就被存入页面库，否则丢弃。 由于不同的主题爬虫所采取的具体技术不同，以上所述三个模块的组成结构就 相应的也会不同，但是这三个模块的功能在主题爬虫中一般都会体现出来。 2 2 主题爬虫搜索策略 在主题爬虫系统中，最核心的问题就是选择利用何种策略来判定从页面分析中 得到的u r l 与主题的相关度，以及抓取下来的页面与主题的相关度。目前，判别主 题相关度的计算方法有两大类【2 】：( 1 ) 基于链接结构分析的判别。( 2 ) 基于内容评价的 判别。 2 2 1 基于链接结构分析的搜索策略 基于链接结构评价的搜索策略，是通过对w 曲页面之间相互作用关系的分析来 确定链接的重要性，进而决定链接访问顺序的方法。通常认为有较多入链或者出链 的页面具有较高的价值。p a g e r a n k 和h i t s 是其中具有代表性的算法。 应用p a g e r a l l k 算法( 基于链接结构评价) 的搜索引擎的优秀代表是g o o g l e ，其基 于这样一种认识：一个网页的重要性取决于它被其它网页链接的数量，特别是一些 已经被认定是“重要”的网页的链接数量。p a g e r a i l k 算法最初用于g o o g l e 搜索引 擎信息检索中对查询结果的排序过程【6 1 ，近年来被应用于网络爬虫对链接重要性的 评价。 h i t s 算法定义了两个重要概念：a u t h o r i t y 和h u b 。a u t h o r i t y 表示一个权威页 面被其它页面引用的数量，即该权威页面的入度值。网页被引用的数量越大，则该 网页的a u t h o r i t y 值越大。h u b 表示一个w 曲页面指向其它页面的数量，即该页面 的出度值。网页的出度值越大，其h u b 值越高。由于h u b 值高的页面通常都提供了 指向权威页面的链接，因而起到了隐含说明某主题页面权威性的作用。 2 2 1 基于内容评价的搜索策略 基于内容评价的搜索算法，主要是根据主题( 如关键词、主题相关文档) 与链接 文本的相似度来评价链接价值的高低，并以此决定其搜索策略。链接文本是指链接 周围的说明文字和链接u r l 上的文字信息。 基于内容评价的搜索算法根据语义相似度的高低决定链接的访问顺序。这类方 法起源于文本检索中对文本相似度的评价，它的显著优点是计算量比较小。但是， 因为w e b 页面不同于传统的文本，它是一种半结构化的文档，其中包含许多结构信 9 华北电力火! 学硕十学位论文 息，w e b 页面不是单独存在的，页面中的超链接在一定程度上表示了页面之间存在 着某些关系。由于基于内容评价的网络爬虫忽略了这些信息，因而在预测超链接的 价值方面存在一些缺陷，容易造成网页的误选。此外，评价的准确性也依赖于对主 题关键词集合的选择和构建。 2 3 主题相关性经典算法- 向量空间模型( v s m ) 搜索引擎的根源是传统的全文检索技术，搜索引擎沿用了传统的信息检索模 型。在传统的计算文档相似度的算法中，以s a l t o n 教授提出的向量空间模型( v e c t o r s p a c em o d e l ) 应用最为广泛【7 1 。向量空间模型基于这样一个关键假设，即组成文章的 词条所出现的顺序是无关紧要的，它们对于文章的主题所起的作用是相互独立的， 因此可以把文档看作一系列无序词条的集合。 v s m 模型以特征项作为文档表示的坐标，以向量的形式把文档表示成多维空间 中的一个点，特征项可以选择字、词和词组等( 根据实验结果，普遍认为选取词作为 特征项要优于字和词组) ，表示向量中的各个分量。 它的基本思想是：把文档d i 看成是由一组词条( t lt 2 t n ) 构成的，对于每一个 词条t i ，都可以根据它在文档中的重要程度赋予一定的权值w i 。可以将t lt 2 t n 看成一个n 维坐标系，w l ，w 2 ，w n 为对应的坐标值，因此每一篇文档都可看作向 量空间中由一组词条矢量构成的一个点，如图2 3 所示。 t j ， 由 ， j d i ；- j ， j ， 一， 。 弋i，一 t k ， 图2 3v s m 模型不恿图 向量空间模型中文档的特征表示方法如下所描述： 在向量空间模型中，设d 是一个包含m 篇文档的文档集合 d = d i ，d 2 ，d 。) ，f = l ，2 ，研 集合中的每篇文档d i 都被表示成如下形式的向量： d f = ( w i 岷) ，扛l ，2 朋，_ ，= l ，2 甩 l o ( 2 一1 ) ( 2 2 ) 华北电力人学硕士学位论文 其中表示第j 个特征项t j 在文档盔中的权值。 权值的计算有以下三种方法： i l ， 匆个特征项属于文档吐 ( 1 ) 嘞= lo ，第，个特征项不属于文档盔 l k ，射个特征项在文档d ，中出现的次数 ( 2 ) 嘞= l o ， 莉个特征项不属于文档吐 l ( 3 ) t f i d f 词频统计方法【2 引。 该方法基于这样的一个假设：在真实语料中，出现频率较高的词条( 特征) 带 有较少的信息，而出现频率较少的词条带有较多的信息。 t f i d f 的值表示权重，词条t i 在文档d i 中的t f i d f 值由下式定义： 嘞= 砭1 0 9 ( ，) ( 2 3 ) 其中，t f i 是词条t j 在文档d i 中出现的次数，d f j 表示整个文档集d 中包含词 条t j 的文档数，称为文档频率，i d f i 为d f j 的倒数，成为反转文档频率；n 表示统 计语料中的文档总数。因此，文档d i 可以表示成一个特征向量： 吐= ( w f l ，)( 2 4 ) 本论文所用的就是这种方法。因为特征词可能出现的位置不同，所以它对网页 的相关性提供的价值也不同。例如，出现在标题中的关键词是网页建设者提供的， 而锚文本中的关键词是别人对该网页的客观评价。基于此，本论文中对词频t f i 的 计算作了如下改进： 设关键词在网页内容中出现的次数为fp ，在标题中出现的次数为ft ，在锚文 本中出现的次数为fa ，则： z l = s 木( 厂一f + 厂一口) + 厂一p ( 2 5 ) 其中，e 是关键词出现在网页标题与锚文本中的权重。待分析的网页文本经过分 词程序分词后，首先去除停用词，将数字和人名等一些词汇合并，然后统计词频， 最终表示为公式2 4 描述的向量形式。 2 4 全文检索技术 全文检索技术是种重要的关键词检索方法。所谓全文检索，就是给定一个字 华北电力大学硕十学位论文 符串或字符串逻辑表达式，对文档库进行相应的检索，查找出与指定表达式相匹配 的文档，并将包含这些文字信息的文档作为检索结果返回给用户。 全文检索技术分为两种：一种是根据检索表达式直接在原文档中匹配查找，这 种方式适合于对小型文档库的检索；另一种是对文档预先建立索引，检索时对索引 进行检索，这种方式适合于对大容量的文档库的检索，如i l l t e m e t 网络上的文档检 索。全文检索技术包含两方面的核心问题：一个是如何建立和维护索引库；另一个是 如何提供快速有效的检索机制。面向网络的全文检索系统所处理的对象是大规模的 海量数据，要实现对它们快速有效的全文检索，主要需要从以下三方面进行考虑：( 1 ) 检索的快速响应。( 2 ) 索引库的建立与维护。( 3 ) 索引数据的压缩。 全文检索的方法主要分为按字检索和按词检索2 种。按字检索是指对于文档中 的每一个字都建立索引；而按词检索归根结底也是按字检索，只是在检索时将词分 解为字的组合。 全文检索系统是按照全文检索理论建立起来的用于提供全文检索服务的软件 系统。一般来说，全文检索需要具备建立索引和提供查询的基本功能，此外现代的 全文检索系统还需要具有用户接口、面向w w w 的开发接口、二次应用开发接口等 等【l5 1 。图2 4 是一个全文检索系统的整体构造模型。 查询引擎卜- 叫文本预处理引擎 应 用 v，1 ， 程 、 。4序 索引引擎索引器 开 ，o 全文检索引擎发 ， 。 图2 - 4 全文索引构造模型 从上图中可以看出，全文检索系统中最为关键的部分是全文检索引擎，各种应 用程序都需要建立在这个检索引擎之上。在检索引擎中可以看出索引引擎占据了核 心的位置，它是整个检索效率的重要决定因素，一个全文检索应用的优异程度，根 本上由全文检索引擎来决定。 华北电力大学硕士学位论文 2 5 多线程技术 采集效率是爬虫的一个很重要的性能指标，因为爬虫处理网页的数量至少是上 千的，所以如何提高程序的性能和效率是非常重要的【1 7 l 。在本文设计的主题爬虫中， 应用了多线程技术来提高采集效率。 多线程是指程序运行时同时执行一个以上的线程。我们采用多线程技术是有原 因的，首先，支持多线程的系统并发性较高，所有线程之间的执行都可以在同一时 刻发生，一个线程的执行不需要等待另一个线程执行完再执行。另外，由于多线程 发生在程序内部，它们使用同一块内存空间，所以线程可以很容易地共享资源。基 于以上两点，可以说多线程能够加快程序的响应时间，提高计算机资源的使用效率， 从而提高整个系统的性能。 在爬虫系统中，例如一个爬虫需要抓取十个网页，要实现这个目标，爬虫程序 必须向服务器发出请求然后接收这些网页，这时它必须等待它所发出的请求经过 i n t e n l e t 向w 曲服务器传输，如果让爬虫程序仅等待一个网页的请求结果，效率将 是很低的。在这种情况下实现多线程可以在很大程度上提高系统效率。在多线程的 条件下，多个线程允许这十个网页的等待时间同时发生，而不是让它们一个接一个 的执行。与单线程相比，每个线程负责一个网页的抓取，可以加速系统效率并且有 效地利用网络带宽。多线程使得爬虫程序同时等待大量的网页。在同一时刻运行超 过一个任务的多线程能力对提高程序的效率是非常重要的。多线程允许程序的多个 部分并行执行，这对执行多个i n t e m e t 访问的应用程序相当重要，它可以大大节省 访问时间。 在多线程的情况下，必须要考虑的一个重要问题就是线程同步问题。在本系统 中，待访问的队列就是多线程操作的，某个线程在访问该队列时，要保证其线程不 能同时对其进行插入、提取及修改等操作，图2 5 表示了待爬行u r l 队列中线程同 步的具体做法。 豳匦 恒! 受兰l 恒蚓 图2 5 线程同步示意图 每个线程从待爬行u r l 队列中提取链接时，首先锁定该队列，然后选择队列头 华北电力人学硕士学位论文 的u r l 爬行，选择好后，它将队列解锁，以便其它线程访问该队列。在解析页面的 过程中，当需要添加新的u r l 到待爬行队列时，因为有多个线程共享队列，也要将 队列锁定。当某个线程发现待爬行的队列为空时，并不表明整个爬行过程的结束， 因为可能这时正有其它线程在访问网页，从而可能会有新的u r l 被添加到待爬行队 列中，所以发现队列为空的线程要被置为s l e 印状态，经过一定的时间，当该线程 被唤醒时，要再次检查待爬行队列中是否有新的链接被添加进来，以便对其进行访 问。这个过程就需要一个全局跟踪器，跟踪处于s l e 印状态的线程个数，当所有的 线程都处于s 1 e 印状态时，整个爬行过程结束。 2 6 小结 本章主要研究了垂直搜索引擎的核心技术，包括主题爬虫的基本原理和结构， 深入分析了主题爬虫在w 曲上爬取网页时的两类搜索策略，即基于链接结构的搜索 和页面内容的搜索，对页面相关度计算的相关算法进行了研究，简要介绍了信息检 索技术和多线程技术，为下面章节的开展提供了理论基础和技术指导。 1 4 华北电力大学硕士学位论文 第三章主题搜索爬虫研究与设计 3 1 主题爬虫设计思想 爬虫的设计初衷就是在给定爬行周期内，尽可能多的下载w 曲网页。但当面临 着w e b 发展规模和数量成几何增长的客观现实时，传统的爬虫要想在爬行网页时既 保证网页的质量和数量，又要保证网页的时效性显然己经是力不从心了。于是，爬虫 的设计策略就调整为在给定的爬行周期内尽可能多地爬行高质量的网页，并且保持 网页的时效性。 一个好的爬虫需要达到以下两个要求：( 1 ) 它必须要有一个好的爬行策略，即决 定下一步要爬行哪些网页的策略；( 2 ) 它必须要有一个高度优化的系统结构，且健壮 性和可控性良好。对于主题爬虫而言，它还必须对下载的网页和搜索主题进行相关 度分析，以决定其是否符合垂直搜索的要求，因此要有一个好的分析方法。 主题爬虫的设计思想是考虑对页面过滤，不像普通爬虫对所有页面的链接进行 处理，它先对页面与受限领域的主题相关度进行分析，只有当其主题相关度符合要 求时才处理该页面中的链接，因为如果该页面和本领域比较相关，它所包含的链接 和本领域相关的几率也较大，这样提高了爬行精度，虽然会遗漏少数页面但综合效 果令人满意。因此主题相关度的分析是主题爬虫设计的关键，最简单的可以基于关 键词进行分析，更深入的可以上升到语义和概念层次。 相对于一般的通用网络爬虫，主题网络爬虫需要解决三个基本问题： ( 1 ) 主题目标描述。 ( 2 ) 主题相关度判定算法。 ( 3 ) 对u r l 的搜索策略。 抓取目标的描述和定义是决定主题相关度判定算法与u r l 搜索策略如何制定 的基础。而主题相关度判定算法是决定搜索引擎所提供的服务形式和爬虫网页抓取 行为的关键所在。 总而言之，主题爬虫设计主要从以下几个方面来考虑【1 7 】： ( 1 ) 下载高质量的网页。随着w e b 网页数量的急剧增长，爬虫不可能下载所有 的网页，要最大程度的满足用户的需求，就必须提高所下载网页的质量，以保证下 载的网页可用价值尽量高。 ( 2 ) 判断己经下载的网页与主题的相关性。对于己经下载的网页，我们可以通 1 5 华北电力大学硕十学位论文 过提取网页中的文字信息，包括围绕在链接周围的文字和网页内容，从而充分利用 信息，按照一定方法来计算网页与文本的相关性。 ( 3 ) 决定待爬行u r l 的访问次序。通用搜索引擎以搜集海量数据为目标，爬虫 在爬行的时候只需按照深度优先遍历或者广度优先遍历的方法下载页面，尽量提高 爬虫的爬行范围，而主题爬虫因其自身的特点，在爬行的过程中就要考虑优先访问 与主题相关页面，即要考虑如何管理待爬行的u r l 队列，从而使每次爬行都从相关 度最高的页面开始。 ( 4 ) 尽量降低被爬行网站的负担。因为爬虫在爬行的过程中，需要访问别人的 服务器，这样就要占用对方的计算机资源，如c p u 和磁盘空间等，同时也占用了网 络带宽，增加了网络的