（计算机软件与理论专业论文）垂直搜索引擎数据采集技术的研究与实现.pdf

华北电力大学硕士学位论文 摘要 垂直搜索引擎是针对通用搜索引擎的信息量大、查询不准确、深度不够等问题 提出来的新的搜索引擎服务模式。本文在查阅了大量的国内外文献的基础上，对垂 直搜索引擎的系统结构、工作原理、搜索策略、链接去重和网页更新等关键技术 和主要算法进行了深入的学习和研究。重点讨论了垂直搜索引擎数据采集系统的搜 索策略和主题相关性算法，并对链接去重和网页更新等算法进行了改进，在此基础 上对垂直搜索引擎进行了总体设计，设计实现了一个电子商务垂直搜索引擎的信息 采集系统。实验结果表明，该系统具有较高的采集效率，采集的页面具有较好的主 题相关度，达到了预期的设计目标。该系统具有较好的实用价值和应用前景。 关键词：垂直搜索引擎，主题爬虫，网络蜘蛛，p a g e r a n k a b s t r a c t t h ev e r t i c a ls e a r c he n g i n ei san e ws e a r c hs e r v i c e ，a i m e dt os o l v et h ep r o b l e m so f t o o - m a s s i v ed a t a ，l o ws e a r c ha c c u r a c ya n dp r o f u n d i t yi nc o m m o ns e a r c he n g i n e t h i s p a p e ri n v e s t i g a t e dag r e a td e a lo fd o m e s t i ca n di n t e r n a t i o n a ld o c u m e n t s ，a n dd e e p l y r e s e a r c h e da sw e l la st h ep r i n c i p l ea n dc r i t i c a lt e c h n i q u eo fv e r t i c a ls e a r c he n g i n eo n s y s t e ms t r u c t u r e ，w o r k i n gp r i n c i p l e ，s e a r c hs t r a t e g y , d u p l i c a t e dl i n k sd e l e t i o na n dp a g e u p d a t i n ga l g o r i t h m s t h ep a p e rf o c u s e so nt h es e a r c hs t r a t e g ya n dt o p i ca lg o r i t h m o n t h eb a s e so fi m p r o v i n gt h ed u p l i c a t e dl i n k sd e l e t i o na l g o r i t h m sa n dp a g eu p d a t i n g s t r a t e g y , t h i sp a p e ro v e r a l ld e s i g na ne l e c t r o n i cc o m m e r c e v e r t i c a ls e a r c he n g i n e ，d e s i g n a 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 e ro ft h es e a r c he n g i n e e x p e r i m e n t a lr e s u l t ss h o w t h a tt h es y s t e mi se f f i c i e n c y , h a sb e t t e rc o l l e c t i o no ft h ep a g e sr e l a t e dt ot h et o p i c ，h a s a c h i e v e dt h ea n t i c i p a t e dt a r g e t t h es y s t e mh a sg o o dp r a c t i c a lv a l u ea n da p p l i c a t i o n p r o s p e c t h a i t a o ( c o m p u t e rs c i e n c e ) d i r e c t e db yv i c ep r o f z h e n gl i n g k e yw o r d s ：v e r t i c a ls e a r c he n g i n e ，f o c u s e dc r a w l e r ，w e bs p i d e r ，p a g e r a n k 华北电力大学硕士学位论文 摘要 垂直搜索引擎是针对通用搜索引擎的信息量大、查询不准确、深度不够等问题 提出来的新的搜索引擎服务模式。本文在查阅了大量的国内外文献的基础上，对垂 直搜索引擎的系统结构、工作原理、搜索策略、链接去重和网页更新等关键技术 和主要算法进行了深入的学习和研究。重点讨论了垂直搜索引擎数据采集系统的搜 索策略和主题相关性算法，并对链接去重和网页更新等算法进行了改进，在此基础 上对垂直搜索引擎进行了总体设计，设计实现了一个电子商务垂直搜索引擎的信息 采集系统。实验结果表明，该系统具有较高的采集效率，采集的页面具有较好的主 题相关度，达到了预期的设计目标。该系统具有较好的实用价值和应用前景。 关键词：垂直搜索引擎，主题爬虫，网络蜘蛛，p a g e r a n k a b s t r a c t t h ev e r t i c a ls e a r c he n g i n ei san e ws e a r c hs e r v i c e ，a i m e dt os o l v et h ep r o b l e m so f t o o - m a s s i v ed a t a ，l o ws e a r c ha c c u r a c ya n dp r o f u n d i t yi nc o m m o ns e a r c he n g i n e t h i s p a p e ri n v e s t i g a t e dag r e a td e a lo fd o m e s t i ca n di n t e r n a t i o n a ld o c u m e n t s ，a n dd e e p l y r e s e a r c h e da sw e l la st h ep r i n c i p l ea n dc r i t i c a lt e c h n i q u eo fv e r t i c a ls e a r c he n g i n eo n s y s t e ms t r u c t u r e ，w o r k i n gp r i n c i p l e ，s e a r c hs t r a t e g y , d u p l i c a t e dl i n k sd e l e t i o na n dp a g e u p d a t i n ga l g o r i t h m s t h ep a p e rf o c u s e so nt h es e a r c hs t r a t e g ya n dt o p i ca lg o r i t h m o n t h eb a s e so fi m p r o v i n gt h ed u p l i c a t e dl i n k sd e l e t i o na l g o r i t h m sa n dp a g eu p d a t i n g s t r a t e g y , t h i sp a p e ro v e r a l ld e s i g na ne l e c t r o n i cc o m m e r c e v e r t i c a ls e a r c he n g i n e ，d e s i g n a 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 e ro ft h es e a r c he n g i n e e x p e r i m e n t a lr e s u l t ss h o w t h a tt h es y s t e mi se f f i c i e n c y , h a sb e t t e rc o l l e c t i o no ft h ep a g e sr e l a t e dt ot h et o p i c ，h a s a c h i e v e dt h ea n t i c i p a t e dt a r g e t t h es y s t e mh a sg o o dp r a c t i c a lv a l u ea n da p p l i c a t i o n p r o s p e c t h a i t a o ( c o m p u t e rs c i e n c e ) d i r e c t e db yv i c ep r o f z h e n gl i n g k e yw o r d s ：v e r t i c a ls e a r c he n g i n e ，f o c u s e dc r a w l e r ，w e bs p i d e r ，p a g e r a n k 士= 1明明 本人郑重声明：此处所提交的硕士学位论文垂直搜索引擎数据采集技术的研 究与实现，是本人在华北电力大学攻读硕士学位期间，在导师指导下进行的研究 工作和取得的研究成果。据本人所知，除了文中特别加以标注和致谢之处外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得华北电力大学或其 他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 学位论文作者签名： 逸2 鸯 日期：竺堕：三：1 2 ， 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校有权 保管、并向有关部门送交学位论文与复印件：学校可以采用影印、缩印或其它复 制手段复制并保存学位论文；学校可允许学位论文被查阅或借阅；学校可以学 术交流为目的，复制赠送和交换学位论文；同意学校可以用不同方式在不同媒体上 发表、传播学位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定 作者签名：姚导师签名： 华北电力人学硕十学位论文 1 1 选题背景及意义 第一章引言 随着i n t e m e t 的迅速发展，网络对我们的影响已经越来越大。而在网上发展最 为迅猛的w w w 技术，以其直观、方便的使用方式和丰富的表达能力，已逐渐成为 i n t e m e t 上最重要的信息发布和传输方式。随着网络信息资源的急剧增长，越来越多 的信息涌现到人们面前。然而w e b 信息的急速膨胀，一方面网上的信息多种多样、 丰富多彩，而另一方面用户却找不到他们所需要的信息。因而基于w w w 的网上信 息的采集、发布和相关的信息处理日益成为人们关注的焦点。搜索引擎就是在这样 的背景下出现的，并且已经发挥出不可替代的作用，成为帮助人们从浩瀚的信息海 洋中获取自己想要的信息的有效工具和一种举足轻重的网络应用手段。 搜索引擎以一定的策略在互联网中搜集、发现信息，对信息进行理解、提取、 组织和处理，并为用户提供检索服务，从而起到信息导航的目的。搜索引擎提供的 导航服务己经成为互联网上非常重要的网络服务，搜索引擎已经成为人们在网络中 的“导游一。搜索引擎技术因而成为计算机工业界和学术界争相研究、开发的对象。 作为搜索引擎的基础和组成部分，w e b 信息采集正发挥着举足轻重的作用，并 且随着应用的深化和技术的发展，它也越来越多的应用于站点结构分析、页面有效 性分析、w e b 图进化、内容安全检测、用户兴趣挖掘以及个性化信息获取等多种服 务和研究中。 传统的搜索引擎信息采集的目标就是尽可能多地采集信息、页面，甚至是整个 w e b 上的资源。随着w w w 信息的爆炸性增长，信息采集的速度越来越不能满足实 际应用的需要。最近的试验表明，即使大型的搜索引擎，它对w 曲的覆盖率也只有 3 0 4 0 l l 】。解决这一问题的直接办法是升级信息采集器的硬件，采用处理能力更强 的计算机系统，然而这种方法的扩展性有限，性价比也不高1 2 j 。一个更好的解决方 法是采用分布式方法来提高并行能力，但是并行不但增加了系统的开销和设计的复 杂性，并且并行换来的效益也随着并行采集器数目的增加而显著地减小。目前，一 般的大型搜索引擎都采用了并行机制，但并行带来的改善效果仍远不能满足人们的 需要，人们需要从其它角度改善目前的困境。 针对上述情况，另一种形式的搜索引擎悄然出现，它可以在较小的范围内取得 比通用搜索引擎更令人满意的结果，以满足某些特定用户的需要，这就是垂直搜索 引擎。垂直搜索引擎是相对通用搜索引擎的信息量大、查询不准确、深度不够等问 题提出来的新的搜索引擎服务模式，其特点就是“专、精、深一，且具有行业色彩， 华北电力大学硕士学位论文 显得更加专注、具体和深入。由于它面向某一特定的专业领域，具备有效的信息采 集策略，使得索引更新周期大大缩短，保证了对该领域信息的及时更新，能够从根 源上避免搜索时产生的“噪音”，提高了查询效率。 网络蜘蛛或者叫网络爬虫是搜索引擎采集数据的主要工具1 3 】。由于垂直搜索引 擎索引的信息内容仅限于特定主题或专门领域，故其网络蜘蛛在采集数据的过程中 无需对整个w e b 进行遍历，只需访问与主题相关的页面。这就需要采集时对站点的 主题相关性做出预测和筛选，并对网页的主题相关性做出判断。高效准确的采集数 据策略，对垂直搜索引擎的使用效果起着至关重要的作用。 随着网络的发展和普及，电子商务作为一种新的商业模式出现在人们面前，并 被越来越多的人所接受。它可以突破地域和时问限制，使处于不同地区的人们自由 地传递信息，互通有无，开展贸易。而搜索引擎能够通过其简便快捷的方式，解决 人们在互联网海量信息中获取数据困难的问题。如何将电子商务和搜索引擎相结 合，解决用户寻找和选择商品困难的问题，必将为用户带来巨大的便利和广阔的商 机。垂直搜索是一个较好的切入点，具有巨大的商业价值和广阔的应用前景。因此 对垂直搜索引擎的研究具有重大的实用价值和重要意义。 1 2 国内外研究现状 目前搜索引擎领域的商业开发非常活跃，各大搜索引擎公司都在投巨资研制搜 索引擎系统，同时也不断地涌现出新的具有鲜明特色的搜索引擎产品，搜索引擎已 经成为信息领域的产业之一。在这种情况下，对搜索引擎技术相关领域的学术研究 得到了大学和科研机构的重视。 y a h o o 是最早提供分类目录向导的搜索引擎。根据用户输入的检索式，y a h o o 将返回相关的y a h o o 分类目录、w e b 网站、w e b 网页和新闻。目前a l t a v i s t a 是i n t e m e t 上最大的搜索引擎之一1 4 1 ，它提供常规搜索、高级搜索和主题搜索，包括图像、视 频和音频等。a l t a v i s t a 所拥有的庞大的数据库使得用户找到所需信息的可能性大大 增加。g o o g l e 有四十亿个可搜索网页，每天处理的搜索请求已达2 亿次，在操作界 面中提供多达3 0 多种语言选择，包括英语、主要欧洲国家语言、日语、中文简繁 体、朝语等，g o o g l e 在w e b 信息的高效搜索、文档的相关度评价、大规模索引等方 面作了深入的研究，取得了很好的成果p j 。 由美国i n f o m o t i e s 公司主办的搜索引擎国际会议从1 9 9 6 年开始，每年举行一次， 对搜索引擎技术进行总结、讨论和展望，参加者有著名的搜索引擎公司、大学和研 究机构的学者，对搜索引擎技术起到了很好的推动作用。另外像i e e e 主办的国际 万维网会议、人机交互会议已有越来越多关于搜索引擎技术研究的文章发表。 国内开始研究搜索引擎是在上世纪末本世纪初，虽然国内起步较晚，但是己经 2 华匕电力火学硕士学位论文 涌现出了一些很优秀的产品。目前国内技术水平最高的搜索引擎是百度，它的功能 齐全，包括新闻搜索、网站搜索、m p 3 搜索、图片搜索等，特别是在中文搜索支持 方面，百度具有一定的技术优势。随着搜索市场价值的不断增加，越来越多的公司 开发出了自己的搜索引擎，中国搜索、搜狐的搜狗、阿里巴巴的商机搜索等也陆续 面世。另外北京大学、清华大学、国家智能研究中心等高校和研究单位对搜索引擎 技术开展研究，并开发出了几个较好的系统。如由北京大学计算机系网络研究室开 发的“天网”中英文搜索引擎，在系统规模及系统性能方面达到了国外中型搜索引 擎系统的技术水平。在垂直搜索领域则出现了以酷讯( w w w k o o x o o c o r n ) 火车票信息 搜索、和去哪) l ( w w w q u n a r , c o m ) 旅游搜索为代表的搜索产品。 值得一提的是，在开源社区出现了许多优秀的项目，以l u c e n e 、n u t c h 、h e r i t r i x 、 l a r b i n 等为代表。l u c e n e 是a p a c h e 软件基金会j a k a r t a 项目组的一个子项目，是一 个开放源代码的全文检索引擎工具包，提供了完整的查询引擎和索引引擎。n u t c h 基于l u c e n e ，同时添加了数据采集的功能。h e r i t r i x 是一个用j a v a 实现的基于文本， 可扩展，开源的w e b 信息采集项目。h e r i t r i x 的优点在于能够根据不同的需要添加 所需的组件和模块，以满足项目所需，扩展性非常好。l a r b i n 是使用c + + 设计实现 的w e b 爬虫，与n u t c h 不同的是它并不包含索引的模块。l a r b i n 是一个非常高效的 爬虫项目，能够多线程同时从不同的站点采集页面，一台家用机可以通过l a r b i n 每 天采集5 , 0 0 0 ，0 0 0 多页面信息。但是就目前来说，适合于垂直搜索引擎特点的网络 爬虫项目并不是很多也不是很成熟。 1 3 本文的工作与创新 本文所作的主要工作有以下几点： 1 在查阅了国内外大量文献资料的基础上，对当前搜索引擎的工作原理进行 了深入的学习和研究。并对垂直搜索引擎的特点做了深入的研究和分析。 2 深入研究学习了垂直搜索引擎中数据采集系统的主要搜索策略和算法。 3 在系统实现的过程中，使用了一种基于散列结构的u r l 快速去重算法。能 够有效的去除页面采集过程中提取的重复链接。 4 根据网页内容的特征提出了一种基于“链接比 概念的网页信息更新策略。 能够有效的对更新率较高的网页做出及时响应。 5 在学习了当前流行的软件开发技术的基础上，选择了j a v a 程序语言，使用 了些当前流行的开源项目做辅助，开发出了一个可视化的、配置灵活、可跨平台 使用的主题w 曲信息采集系统。 3 华北电力大学硕士学位论文 2 1 搜索引擎的分类 2 1 1 通用搜索引擎 第二章搜索引擎概述 由网络蜘蛛程序以某种策略自动地在互联网中搜集和发现信息，由索引器为搜 集到的信息建立索引，由检索器根据用户的查询输入检索索引库，并将查询结果返 回给用户。服务方式是面向网页的全文检索服务。该类搜索引擎的优点是信息量大、 更新及时、无需人工干预，缺点是返回信息过多，有很多无关信息，用户必须从结 果中进行筛选。这类搜索引擎的代表有g o o g l e 、a l t a v i s t a 、e x c i t e 、l y c o s 等，国内 的代表有百度，天网、搜狗等。 2 1 2 目录搜索引擎 以人工方式或半自动方式搜集信息，由编辑员查看信息之后，人工形成信息摘 要，并将信息置于事先确定的分类框架中。信息大多面向网站，提供目录浏览服务 和直接检索服务。该类搜索引擎因为加入了人的智能，所以信息准确、导航质量高， 缺点是需要人工介入、维护量大、信息量少、信息更新不及时。这类搜索引擎的代 表有y a h o o 、l o o k s m a r t 、o p e nd i r e c t o r y 、g og u i d e 等。 2 1 3 元搜索引擎 元搜索引擎没有自己的数据，而是将用户的查询请求同时向多个搜索引擎递 交，将返回的结果进行重复排除、重新排序等处理后，作为自己的结果返回给用户。 服务方式为面向网页的全文检索。这类搜索引擎的优点是返回结果的信息量更大、 更全，缺点是不能够充分使用所使用搜索引擎的功能，用户需要做更多的筛选。这 类搜索引擎的代表有w e b c r a w l e r 、i n f o m a r k e t 等。 2 2 垂直搜索引擎 2 2 1 垂直搜索引擎的出现 通用搜索引擎地出现很大程度上解决了人们在互联网上查找信息的困难。但随 着w e b 上信息的快速增长，通用搜索引擎面临着越来越多的问题，这类搜索引擎无 选择地采集索引w e b 上的所有内容，使得通用搜索引擎采集数据时占用了较大的网 4 华北电力人学硕士学位论文 络资源，存储空间，更新也不够及时，已经不能满足人们对个性化信息检索服务r 益增长的需要。特别是通用搜索引擎的查询结果往往不能很好的反映用户的偏好， 不能提供给用户一目了然的信息，给用户的信息检索带来了许多不便，降低了用户 使用搜索引擎检索信息的效率。在这种情况下垂直搜索引擎出现了。 垂直搜索引擎面向不同的主题和行业，有图书垂直搜索引擎，汽车垂直搜索引 擎，房地产搜索引擎，车票搜索引擎等等。每一个垂直搜索引擎都只解决一类问题。 它有效的解决了通用搜索引擎的信息量大、查询不准确、深度不够等问题。在查询 结果中提供与主题紧密相关的信息，极大的提高了用户查询的满意度，使用户从查 找问题向解决问题的目标迈进了一大步。 图2 1 展示了图书垂直搜索引擎的查询结果，查询关键字为j a v a ，在搜索结果 中显示了与j a v a 相关的书籍信息，包括书名，作者，简介，价格甚至是图书的封面 图片。显然对于一个寻找书籍信息的用户来说，这些信息正是他们所希望获得的， 而不是在通用搜索引擎返回的大量查询结果中寻找自己需要的信息了。 口窭墨露e 墨墨翟霞譬燮曩澄落耀粼黼戮貔魏囊缀滋戮雾蠹万_ _ 万_ 一 立件勤编辑喧查看! 啦藏哒i工星呸j帮助但 ，后退。!搜索收藏嘉撵体j ， v 癌 ， | 慧。，。，。，堡耋 鍪歉8 静秘犷繇；： 佑全部广按书名r 按作者f 投出版社 一“ 三籀卜丑殳鱼璺e 喧：塑：i i 虫塞匿! 两耋害鞲黉鬻寥啦f - o n e n l e d 一膨* 黼计 哮詈案案叫e f f e c t 啪，：盘文置 “癣巨参霎婺荔囊毒搿嚣嚣答卷警验删馒数姗则髓了艚撕从鹪新砷髓的 ：竖垡i 丝：丝丕鲞l ! 墨型翅退! 厦立蔓! 匮if 蓝竺猩匠爱蔓兰塑垫置董笾垫盟至曼登连耋要塞 的十太r r 图书之一2 再再：一善一j1 。k ，一 h _ m “ 本书是；技术经典参考书，多年畅镝不衰，盯舨在保留以前版本风格的基础上。涵差j a v a 2 开发平台标准版j 2 s e 5 0 的基础知识，主要内容乜括面向对象程厍设 重嚣鬻篆篇曩曩蝴书婪 2 2 2 垂直搜索引擎的特点 垂直搜索引擎是相对通用搜索引擎的信息量大、查询不准确、深度不够等问题 提出来的新的搜索引擎服务模式，其特点就是“专、精、深”，且具有行业色彩， 5 华j 匕电力人学硕士学位论文 显得更加专注、具体和深入。由于它面向某一特定的专业领域，具备有效的信息采 集策略，使得索引更新周期大大缩短，保证了对该领域信息的及时更新，能够从根 源上避免搜索时产生的“噪音一，提高了查询效率。 相比通用搜索引擎来说，垂直搜索引擎有以下几个主要特点。1 搜索结果所包 含的信息量更大，用户体验度更好，解决用户困难的能力也更强。2 由于垂直搜索 引擎只针对特定主题或是专业的网站检索，在对新信息的及时响应上也要比通用搜 索引擎快的多。3 对硬件的要求更低，不需要海量的存储，信息采集时占用较低的 带宽。 2 2 3 面向主题的数据采集 网络蜘蛛是搜索引擎采集数据的主要工具。由于垂直搜索引擎索引的信息内容 仅限于特定主题或专门领域，故其网络蜘蛛在采集数据的过程中无需对整个w e b 进 行遍历，只需访问与主题相关的页面。这就需要采集时对站点的主题相关性做出预 测和筛选，并对网页的主题相关性做出判断，保留主题相关的页面，放弃不相关的 页面从而得到目标数据源。另外一种方法是通过数据挖掘的方法将采集的页面根据 不同的主题进行聚类分类，从而得到垂直搜索引擎的数据源。垂直搜索引擎的数据 采集是面向主题的信息采集，较通用搜索引擎的数据采集来说有以下几个优点。 第一，在很大程度上缓解w e b 信息采集中的棘手难题即刷新问题所带来的弊 端。w e b 页面的动态变化使得数据在提取到的那- n 起就面临着数据过时的风险， 为了降低这种风险，w e b 信息采集器需要不停地对己采集的w e b 信息重新采集以保 持对数据的更新。随着w e b 规模上的急剧增长，面向整体w e b 信息采集中的刷新 问题变得异常的尖锐。尽管可以通过不断地提高单机性能，使用分布式计算技术增 加采集系统的并行能力，设计新型算法以优化刷新策略，但是w e b 信息的刷新问题 还远不能令人满意，许多大型搜索引擎刷新一次w e b 数据需要几周甚至几个月的时 间。对于面向主题的w e b 信息采集而言，这个问题相对容易处理。随着采集页面数 量的大幅度降低，就可以缩短页面的刷新周期，从而使得数据过时的风险也随之降 低。 第二，提高了资源的有效利用率，极大地节省了资源的消耗。整个w e b 上的信 息十分庞大，试图对w e b 进行整体信息采集或完全镜像地采集系统，且不说这种做 法的可行性，就其在采集过程中所使用的硬件资源和网络资源而言，代价将是十分 巨大的。而事实上，许多页面的使用几率很少，这就存在着一个极大的信息资源的 浪费问题。面向主题的w e b 信息采集就是在采集过程中对u r l 根据主题信息的需 要有所剪枝。通过u r l 的主题相关性剪枝，不仅使被剪枝掉的u r l 数目远大于被 采集的u r l 数目，它们之间的差别甚至可以是几个量级，这样做的同时使得采集到 6 华北电力大学硕士学位论文 的页面有着较高的利用率。 ， 第三，以一种更加专注、更加灵活的方式为用户提供服务。w e b 信息采集的目 的就是为了服务于用户，对于用户而言，他们不需要关心整个w e b 上的页面数据， 而只是其中一个很小的部分，而这部分数据往往就集中在一个或者几个近似的主题 领域内。面向主题的w e b 信息采集恰恰可以满足这些用户的需求，而且，由于采集 的页面数量较少，页面内容也更有针对性，能够更好地针对需要为用户提供服务。 也正是由于采集页面数量少，系统可以更加灵活。 第四，通过众多方向的面向主题w e b 信息采集器的协同工作，可以提高对整个 w e b 的页面采集覆盖率。面向主题的信息采集，由于关注的页面数量少，并且对于 该主题内的页面挖掘能力更强，所以和传统的面向整个w e b 的信息采集系统相比， 它在相关主题内能够采集到数量更多质量更好的页面。当多个主题w e b 信息采集系 统按照各自的主题领域分类对相关主题页面进行分类采集后，它们所采集页面的综 合页面集相对于w e b 的覆盖率也就更高了。 2 3 搜索引擎的工作原理 搜索引擎通常通过r o b o t 或s p i d e r 下载i n t e m e t 上的w e b 文档，进行过滤、分词、 转换等处理工作。然后对文档信息进行预处理和形式化描述，抽取特征并进行索引。 文档的收集是w e b 信息检索的基础。文档的预处理为后续检索工作提供了保证。一 个典型搜索引擎的基本工作流程如图2 2 所示。 建 骨 检 川 卫 一1 户 索 索 引 器 接 口 图2 2 搜索引擎基本t 作流程图 它主要包括如下四个过程：1 在互联网中发现、搜集网页信息；2 对信息进行提 取和组织建立索引数据库；3 由检索器根据用户输入的查询关键字，在索引库中快 速检索出文档。4 进行文档与查询的相关度评价，对将要输出的结果进行排序，并 将查询结果返回给用户。 1 发现、搜集网页信息。发现、搜集网页信息主要采取以下两种做法：一种 方法是由用户主动向搜索引擎报告或提交自己的资源。大多数搜索引擎的数据获取 工作采用的是另一种方式，由高性能的s p i d e r 自动完成。s p i d e r 是一个能够沿着超 链接漫游w e b 页面集合的程序，并且能够通过h t t p 等协议下载所漫游到的页面， 7 华北电力大学硕士学位论文 它会定期根据预先设定的地址去查看对应的网页，如网页发生变化则重新获取该网 页，否则根据该网页中的链接继续去访问。s p i d e r 访问页面的过程是对互联网上信 息遍历的过程，它可以采用深度优先和广度优先两种算法进行网页遍历，为了保证 s p i d e r 遍历信息的广度，一般事先设定一些重要的链接，然后对这些链接进行遍历。 在遍历过程中不断记录网页中的链接，不断遍历下去，直到访问完所有的链接。网 络蜘蛛为实现其快速地浏览整个互联网，通常在技术上采用抢先式多线程技术实现 在网上聚集信息。通过抢先式多线程的使用，能索引一个基于u r l 链接的w e b 页 面，同时启动一个新的线程跟随每个新的u r l 链接，索引一个新的u r l 起点。当 然在服务器上所开的线程也不能无限膨胀，需要在服务器的正常运转和快速收集网 页之间找一个平衡点。在算法上各个搜索引擎技术公司可能不尽相同，但目的都是 快速浏览w 曲页和后续过程相配合。 2 索引数据库的建立。索引数据库的建立关系到用户能否最迅速地找到最准 确、最广泛的信息，索引一般按照倒排文件的格式存放。如果索引不能及时更新， s p i d e r 带回的新信息就不能被使用搜索引擎的用户查到。对网页采用基于网页内容 分析和基于超链分析相结合的方法进行相关度评价，能够客观地对网页进行排序， 从而极大限度地保证搜索出的结果与用户的查询串相一致。在设计一个索引数据库 时，要针对实际需要确定索引数据库的数据结构和存储方式。由于搜索引擎系统通 常处理的都是海量的信息，因此还要设计一定的压缩策略，对索引库进行有效的压 缩，以提高检索的速度。 3 用户检索的过程。当用户输入关键词搜索后，分解搜索请求，由搜索系统 程序从网页索引数据库中找到符合该关键词的所有相关网页。 4 对搜索结果进行处理排序。所有相关网页针对该关键词的相关信息在索引 库中都有记录，只需综合相关信息和网页级别形成相关度数值，然后进行排序，相 关度越高，排名越靠前。最后由页面生成系统将搜索结果的链接地址和页面内容摘 要等内容组织起来返回给用户。 8 华北电力人学硕+ 学位论文 第三章系统的总体设计 前面对搜索引擎的工作原理和垂直搜索引擎的特点进行了介绍，本章以图书信 息主题为例，进行了图书垂直搜索引擎系统的总体设计。在介绍了图书垂直搜索引 擎的基本系统结构之后，重点对该搜索引擎的数据采集系统的结构进行了研究和设 计，分析了面临的主要问题和对策，并提出了设计目标。 3 1 搜索引擎的系统结构 搜索引擎由数据采集系统、索引系统和检索系统三个部分组成。系统首先由数 据采集系统采集w e b 上的网页信息；然后由索引系统分析内容，建立索引；再由检 索系统响应用户的检索请示，用户输入关键词后，搜索器要用这个检索词与建立的 索引器匹配，匹配后作相关性排序；最后将将排序结果返回给用户。图3 1 展示了 搜索引擎的总体结构。 数据采集 建立索引 数据检索 图3 1 搜索引擎的系统结构图 1 数据采集系统在互联网中漫游、发现和搜集信息。它要尽可能多、尽可能 快地搜集系统需要的主题信息，同时由于互联网信息更新很快，还要定期更新已搜 9 华北电力人学硕士学位论文 集过的旧信息，以避免死链接和无效链接。搜索器常用分布式并行计算技术，以提 高信息发现的机会和页面更新的速度。 2 建立索引所搜集的信息中抽取出索引项，用于表示文档以及生成文档库的 索引表。索引器读入搜索器生成的全文网页文件，首先进行分词处理生成索引项， 并作归并排序，生成索引文件。索引文件存储分词与倒排表的对应关系，内容为分 词在倒排表中相应的文档块起始地址，含有该词的文档数量等信息。索引器使用集 中式索引算法或分布式索引算法。当数据量很大时必须实现即时索引，否则跟不上 信息量急剧增加的速度。一个搜索引擎的有效性在很大程度上取决于索引的质量。 一般索引法有倒排文档、矢量空间模型、概率模型等。 3 数据检索系统根据用户的查询在索引库中快速检索出文档，进行文档与查 询的相关度评价，对要输出的结果进行排序，并实现某种用户相关性反馈机制。检 索器通常支持多种语法规则，如逻辑操作符a n d 、o r 、n o t 、“+ 一、“一连接 号和通配符、逗号、括号或引号等。对于每个索引项，匹配索引文件，查询倒排表 中包含该索引项的文档，并对所有找出的文档进行集合运算，将结果集按照基于内 容和基于链接分析的方法进行相关度评价并排序，最大限度地保证检索结果与用户 查询串的高相关性，将最终形成的有序文档结果集合返回给用户。 另外还应该提供给用户一个良好的接口。方便用户使用搜索引擎，高效率、多 方式地从搜索引擎中得到有效、及时的信息。用户接口的设计和实现使用人机交互 的理论和方法，以充分适应人们的思维习惯。 3 2 数据采集系统的系统结构 数据采集是搜索引擎中的重要组成部分。它为搜索引擎提供了基本的数据。数 据采集系统主要是指依赖w e b 页面之间的链接关系，从w e b 上自动地获取页面信 息，并且随着链接不断向所需要的w e b 页面进行扩展的过程。图3 2 展示的数据采 集系统的主要结构和各部分之间的关系。 图3 - 2 信息采集系统的结构图 1 0 华北电力人学硕士学位论文 3 2 1 信息获取器 信息获取器的功能主要是通过各种w e b 协议来完成数据的采集。一般来说协议 包括h t t p 、f t p 、g o p h e r 以及b b s ，也有些采集系统根据应用的需要采集w e bc h a t 、 i c q 等特殊信息。在本文中仍以h t t p 协议为主。 3 2 2 网页去重器 w e b 上存在着大量的镜像页面和内容，最近的研究表明，将近3 0 的页面是重 复的。这极大的浪费了网络的带宽和影响了系统的效率。所以，重复内容检测变成 了采集系统，特别是大型采集系统的重要组成部分。要采用的检测方法，根据系统 的需要，从简单的段落匹配到复杂的相似度比较中选择。 3 2 3u r l 抽取器 对于采集到的页面，通过网页去重检测后，需要分析其中的链接，并对链接进 行必要的转换以获取真实的u r l ，这些任务就是由u r l 抽取器来完成的。页面链 接中给出的u r l 的格式可能是不一样的，既可能是完整的绝对路径u r l ，也可能 是一个相对路径。为方便处理，需要先将其规格化为统一的绝对路径u r l 格式。 3 2 4 数据存储模块 通过去重检测后的页面数据、需提取出图书的标题、作者信息、摘要、出版社、 价格等均需的信息后并存入数据库中，以备使用。例如，进行分析建立索引等。由 于w e b 页面规模的庞大，提取的相关数据在存入数据库之前，一般要进行压缩处理。 3 3 面临的主要问题及对策 1 初始u r l 集合的选择和确定。一般的采集系统是从一个种子u r l 集出发， 通过w e b 协议向w e b 上所需的页面扩展的。基于主题的w e b 信息采集也不例外， 也有一个起始采集的种子u r l 集。但是，基于主题的w e b 信息采集的采集起点选 择却必须十分慎重，因为这将影响着采集的效率，尤其是刚开始采集的准确率。本 文在确定初始u r l 集合的过程中，主要采用了人工筛选的方式，以保证初始u r l 的主题相关性。另外参考了g o o g l e 搜索引擎的中以“图书厅为关键词的搜索结果， 因为g o o g l e 的搜索结果具有较好的权威度和主题相关度。 2 搜索策略。为了有效的提高基于主题的w e b 信息采集的准确率和效率，需 要一个有效的策略访问w e b 中的页面。系统需要对进行u r l 与主题的相关性判定， 优先访问质量较高的页面。本文按照高相关度优先采集，低相关度放弃的原则进行 1 l 华北电力大学硕士学位论文 处理。这样可以大大减少采集页面的数量，有效的提高主题信息搜索的速度和效率。 具体的算法将在系统实现部分中详细介绍。 3 页面的主题相关性评价。为了进一步提高采集页面的准确率，需要对已采 集的页面进行主题相关性评价，剔除评价结果较低的页面，提高所采集主题页面的 准确率。这个问题是检索领域内的一个经典问题，已经有许多成熟的基于关键词的 相关性判定算法。本文选择了基于关键词的向量空间模型算法对页面进行主题相关 性评价。 4 采集效率。如何提高采集效率是最终评价系统的一个重要指标。影响系统 采集效率的因素有很多。比如搜索策略，网络环境，计算机处理能力以等。本文在 程序设计上使用了多线程的技术，以提高系统对网络带宽和系统资源的使用率，从 而获得较高的采集效率。 3 4 系统设计目标 主题信息采集的基本工作流程是按照事先给出的主题，分析w e b 中的超链接和 己经下载的网页内容，来预测下一个要爬行的u r l ，保证尽可能多地下载与主题相 关的网页、尽可能少地下载无关网页，以此来提高主题爬虫的效率与准确率。主题 爬行器的设计主要从以下几个方面来考虑： 1 下载高质量的网页。爬虫不可能下载所有的网页，要最大程度的满足用户 的需求，就必须提高所下载网页的质量，以保证下载的网页可用价值尽量高。 2 良好的参数配置。需要充分考虑爬虫运行的不同环境和具体需求，能够对 一些参数进行修改，如初始地址、搜索的时间、网络代理、连接重试次数、超时时 间以及开启的线程数量等。 3 多线程。采用多线程处理技术可以提高主题爬虫的效率，能够并行执行和 处理多任务。在爬行过程中，由于网络响应时问等原因，不同网页的下载时间都有 差别，多线程的应用使u r l 得到并行处理，从而可以加快处理速度，有效利用网络 带宽，并节约时间。 。 4 灵活合理的程序结构。尽可能使得程序模块化，模块之间实现低耦合，设 计灵活合理的程序结构，以便在将来对程序能够方便进行维护和升级。 5 一定的智能化。为了提高整个系统的查全率、查准率及搜索速度，搜索算 法的设计应具备一定的智能化，可以对主题相关性进行预测。 1 2 华北电力大学硕士学位论文 第四章系统搜索策略的研究 数据采集系统的性能好坏直接影响着搜索引擎的整体性能和处理速度。传统的 通用搜索引擎的主要目的是获得较高的w e b 覆盖率，尽可能多的下载网页，它的网 络爬虫通常采用图的遍历算法( 如广度优先策略或深度优先策略) 来搜索w e b 。主题 搜索引擎的特点是搜索的内容只限于特定的主题或专门的领域，因而在搜索过程中 没有必要对整个w e b 进行遍历，只需要选择与主题页面相关的页面进行访问即可。 垂直搜索引擎更注重所下载页面的准确性。对于垂直搜索引擎来说主题信息的搜索 策略是整个系统的关键和核心。目前的垂直搜索引擎主要采用基于领域知识分析的 “启发式”搜索策略，即先通过在线获得的领域知识评价待访问链接的价值，借以 推断信息资源的分布情况，然后按最好优先原则选择价值最大的链接进行下一步的 搜索。当前，主题信息采集的策略主要包括下面两大类：基于内容评价的搜索策略 和基于链结构特征的搜索策略。 4 1 基于内容评价的搜索策略 基于内容评价的搜索策略的主要特点是利用页面中的文本信息作为领域知识 指导搜索，并根据页面或链接文本与主题( 如关键词、主题相关文档等) 之自j 相似度 的高低来评价链接价值的高低。这类搜索策略的代表有f i s h s e a r c h 算法、 s h a r k s e a r c h 算法。 4 1 1f i s hs e a r c h 算法 f i s hs e a r c h 算法于1 9 9 3 年由荷兰t u e 大学的d e b r a 教授提出，并整合到了当 时流行的m o s a i c 浏览器上，是实时搜索中比较有名的算法f 6 l 。该算法的关键是根据 用户的种子站点和查询的关键词或短语，将包含查询串的页面看作与主题相关，计 算该页面与主题的相关度，动态地维护待爬行u r l 的优先级队列u r lq u e u e 。这 个队列分为前端，中部和尾部三部分，另外还需要几个参数d e p t h 、w i d t h 和 p o t e n t i a ls c o r e ，分别用于记录被搜索网页的层深、每页最多分析的链接数目( 孩子 数) 和u r l 的相关度。 这个算法的基本思想是：它以一个u r l 为起始搜索网页，在搜索这个u r l 的 基础上动态的建立一个列表，这个列表中包含有待搜索的u r l 。这个列表中的 u r l ( 虽p 孩子链接) 具有优先级的区分，优先级高的u r l 将排在列表中的前端，将会 比排在列表后面的u r l 提前被搜索。在每一步开始时，取出列表中的第一个u r l 1 3 华北电力人学硕士学位论文 进行分析。如果该网页可以访问，则经过分析对它的p o t e n t i a ls c o r e 赋值，并改变 其相应的d e p t h 和w i d t h 值，然后再重新进行下一个u r l 的检索。 f i s hs e a r c h 算法的具体描述如下： 1 从最初的u r l 列表中选择一个u r l ，并取得与之对应的网页文件，将这个 文件与用户的查询内容对比，检查二者的相关性。 “ 2 给每个u r l 赋相应的d e p t h 值。