（计算机应用技术专业论文）互联网信息分布式深度搜索的研究.pdf

哈尔滨工程大学硕士学位论文 摘要 本文对互联网信息搜索技术进行研究，并在此基础之上建立一个基于 分布式的互联网信息深度搜索系统。 首先分析当前普遍采用的互联网信息搜索引擎的优缺点，鉴于互联网 信息搜索对网络信息所起的重要作用，对互联网信息搜索技术进行研究具 有重要意义。 本文介绍了互联网信息分布式深度搜索的概念及其技术方法，分析了 分布式搜索与深度搜索的优缺点，介绍了深度搜索的w e b 信息采集系 统、信息整理、信息存储、信息检索、分布式深度搜索的研究。设计并且 实现了基于分布式的互联网信息深度搜索。 关键词：搜索引擎；深度搜索；分布式；全文扫描；匹配技术 睦尔滨工疆大学硕圭攀使论文 a b s t r a c t 羊h i sp a p e rm 疲e sr e s e a r c h e so nc u r r e n ti n t e r n e ti n f o r m a t i o ns e a r c h i n g t e c h n o l o g i e s ，a n db u i l d sad i s t r i b u t i o nb a s e di n t e m e t i n f o r m a t i o nd e e p s e a r c hs y s t e mb a s e do nt h er e s e a r c h t h ep a p e ra n a l y z e st h ea d v a n t a g e sa n d d i s a d v a n t a g e so ft h ei n t e r n e ti n f o r m a t i o ns e a r c he n g i n e sw h i c h a r ew i d e l yu s e d t o d a y s i n c et h ei n t e r n e ti n f o r m a t i o ns e a r c h i n gh a v ep r o f o u n d l y i n f l u e n c e d i n t e r n e t ，t h er e s e a r c ho i li n t e r n e ti n f o r m a t i o ns e a r c h i n gt e c h n o l o g yi sv e r y v a l u a b l e 。 t h i sp a p e ri n t r o d u c e st h ec o n c e p t ，t h et e c h n o l o g ya n dt h em e t h o do f d i s t r i b u t e di n t e r a c ti n f o r m a t i o nd e e ps e a r c h i n g ，a n a l y z e sa d v a n t a g e sa n d d i s a d v a n t a g e so fb o t hd i s t r i b u t e ds e a r c h i n ga n dd e e ps e a r c h i n g ，t h e nm a k e s a i n t f o d u c t i o na b o u tt h er e s e a r c ho ft h ew e bi n f o r m a t i o nc o l l e c t i o ns y s t e m , t h e i n f o r m a t i o nc l e a n i n g ，t h ei n f o r m a t i o ns t o r i n g ，t h ei n f o r m a t i o ni n d e x i n ga n d q u e r y i n g ，a n dd i s t r i b u t e dd e e ps e a r c h i n gw h i c ha r ea l l i n c l u d e di nd e e p s e a r c h i n gr a n g e l a s t l y i t d e s i g n s a n di m p l e m e n t sad i s t r i b u t i o nb a s e d i n t e r n e ti n f o r m a t i o nd e e ps e a r c hs y s t e m 。 k e yw o r d s ：s e a r c he n g i n e ；d e e p s e a r c h ；d i s t r i b u t e d ；w h o l e _ l e n g t h s c a n n i n g ；m a t c h i n gt e c h n o l o g y 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的 指导下，由作者本人独立完成的。有关观点、方法、 数据和文献的引用己在文中指出，并与参考文献相对 应。除文中已注明引用的内容外，本论文不包含任何 其他个人或集体已经公开发表的作品成果。对本文的 研究做出重要贡献的个人和集体，均已在文中以明确 方式标明。本人完全意识到本声明的法律结果由本人 承担。 作者( 签字) ：杰赴 日期：伽6 年刁月影日 堕玺鎏三堡查兰堡主堂鱼堡茎 第1 章绪论 1 1 课题背景 二十世纪八十年代以来，i n t e r n e t 在国内和世界范围内都得到了突飞 猛进的发展，和人们的生活之间的关系变得越来越为亲密，它已经开始渗透 到人们工作生活中的每一个细节，它带来的好处是无法用语言描绘的，它本 身的巨大魅力越来越表现得淋漓尽致。在网上发展最为迅猛的w w w ( w o r l dw i d ew e b ) 技术，以其直观、方便的使用方式和丰富的表达能力， 已逐渐成为i n t e m e t 上最重要的信息发布和传输方式。 人们发展了以搜索引擎( s e a r c he n g i n e s ) 为主的检索服务，开发了各 种搜索引擎( 如g o o g l e 等) 。搜索引擎以一定的策略在互联网中搜集、发现 信息，对信息进行理解、提取、组织和处理，并为用户提供检索服务，从而 起到信息导航的目的。它包括信息搜集、信息整理和用户查询三部分：先是 用蜘蛛( s p i d e r ) 进行全网搜索，自动抓取网页；其次是将抓取的网页按照 关键词进行索引，同时也会记录与检索有关的属性，中文搜索引擎中还需要 首先对中文进行分词；最后通过检索生成的索引文件并按照各种参数进行复 杂的计算，产生结果并返回给用户【l 】。当用户检索时根据用户提交的检索条 件从索引库中迅速查找到所需的信息。 这些搜索引擎是一种广度搜索，研究的范围是互联网上的所有网页( 没 有区域限制，只有语言区分) ，关注点是某个词( 或词的组合) 在哪些网 页；最核心是的搜索结果的排序，如何把最合适的结果排到前面【2 】。对用户 关心的查询的词( 或词的组合) 在互联网中搜索显示其出现的网页，例如： 用户想用搜索引擎查询“新华字典”，搜索引擎显示出包含“新华字典”的网 页，同时显示的网页是按一定顺序进行排序。 1 2 课题研究的主要内容 本课题研究的分布式深度搜索，是基于互联网信息监管的需要。在信息 监管领域一个突出特点就是区域性管理：如国家、省级、市级、企业都有属 于自己的信息监管区域，绝大部分工作是要对自己的区域内的信息进行监 哈尔滨工程大学硕士学位论文 管。所以与传统搜索引擎相比较，本课题研究的分布式深度搜索是搜索范围 不同，既一个监管领域的一个网站或多个网站( 有限) 的所有w e b 页面，b 把整个互联网信息搜索缩小到一个相对比较小的范围，也就为深度搜索提供 了可能。 本课题研究以下内容： l 、深度扫描：对网站进行无限深度的搜索，及不断地深层扫描，搜索 到系统最深层的网页信息，最终达到遍历所有网页的目的。 2 、网页深度分析。分析网页中是否含有信息监管中所关注的敏感词， 以及网页是否有指向敏感u r l 的链接( 敏感词数量级别在1 1 0 千条，敏感 u r l 地址数量级别在1 0 0 万条) ；同时分析出敏感词和敏感u r l 链接是否 在网站的网页中出现，出现在哪些页面，及出现的频率、次数。因此高效匹 配算法和信息检索技术是网页深度分析的核心。 3 、解决w e b 信息采集系统延时，及时有效地采集最新的网页信息。 4 、分布式是通过多台机器同时运行并行处理，提高处理速度。处理速 度是两个方面的提高，一是搜索网页的速度的提高，另外一方面是网页分析 速度的提高。 5 、搜索结果的显示与查询； 1 3 本文安排 第二章回顾了搜索引擎的发展历史，对传统搜索引擎的技术进行了研 究，从而为开展进一步的理论研究和系统研发打下基础。在第三章里对深度 搜索引擎的信息采集和整理功能部分，作了较为详细的论述，并给出了我们 的设计方案和算法。在第四章里，我们讨论了深度搜索的信息整理系统，网 页深度分析功能，重点是页面的全文本扫描和高效匹配算法。第五章介绍了 深度搜索的信息存储和深度搜索的检索和分布式搜索的研究和应用模式。在 第六章里介绍基于深度搜索的系统的设计与实现，对系统的设置和实际操作 进行了简要的介绍，并给出了进一步需要研究的问题。 本文将在下面几章里探讨及深度搜索引擎、网页分析、分布式搜索等技 术以及系统的设计与实现。 2 哈尔滨工程大学硕士学位论文 第2 章搜索引擎研究 2 1 搜索引擎起源 所有搜索引擎的祖先，是1 9 9 0 年由m o n t r e m 的m c g i l lu n i v e r s i t y 三名 学生( a l a ne m t a g e 、p e t e rd e u t s c h 、b i l lw h e e l a n ) 发明的a r c h i e ( a r c h i e f a q ) 。a l a ne m t a g e 等想到了开发一个可以用文件名查找文件的系统，于是 便有了a r c l l i e 。a r c h i e ，这是第一个自动索引互联网上匿名f t p 网站文件的 程序，但它还不是真正的搜索引擎。a r c h i e 是一个可搜索的f t p 文件名列 表，用户必须输入精确的文件名搜索，然后a r c h i e 会告诉用户哪一个f t p 地址可以下载该文件 由于a r c h i e 深受欢迎，受其启发，n e v a d as y s t e mc o m p u t i n gs e r v i c e s 大学于1 9 9 3 年开发了一个g o p h e r ( g o p h e rf a q ) 搜索工具v e r o n i c a ( v e r o n i c af a q ) ，j u g h e a d 是后来另一个g o p h e r 搜索工具 2 2 搜索引擎发展和现状 世界上第一个s p i d e r 程序，是m i tm a t t h e wg r a y 的w o r l dw i d ew e b w a n d e r e r ，用于追踪互联网发展规模。刚开始它只用来统计互联网上的服务 器数量，后来则发展为也能够捕获网址( u r l ) 。 我们认为所有网页都可能有连向其他网站的链接，那么从一个网站开 始，跟踪所有网页上的所有链接，就有可能检索整个互联网。 1 9 9 3 年底，一些基于此原理的搜索引擎开始纷纷涌现。 1 、r b s e 是第一个索引h t m l 文件正文的搜索引擎，也是第一个在搜索 结果排列中引入关键字串匹配程度概念的引擎。 2 、e x c i t e 是分析字词关系，以对互联网上的大量信息作更有效的检 索。 3 、y a h o o ! - - - 几乎成为2 0 世纪9 0 年代的因特网的代名词。 ( 1 9 9 4 年 4 月，斯坦福大学的两名博士生，美籍华人杨致远和d a v i df i l o 共同创办 了y a h o o ) y a h o o 开始支持简单的数据库搜索。因为y a h o o ! 的数据是手工 输入的，所以不能真正被归为搜索引擎，事实上只是一个可搜索的目录。 3 哈尔滨工程大学硕士学位论文 y a h o o ! 中收录的网站，因为都附有简介信息，所以搜索效率明显提高。 4 、a l t a v i s t a ，这是是第一个支持自然语言搜索的搜索引擎，第一个实 现高级搜索语法的搜索引擎( 如a n d ，o r ，n o t 等) 。 5 、g o o g l e ，目前最优秀的支持多语种的搜索引擎之一，约搜索 3 ，0 8 3 ，3 2 4 ，6 5 2 张网页，提供网站、图像、新闻组等多种资源的查询。其中 包括中文简体、繁体、英语等3 5 个国家和地区的语言的资源。g o o g l e 在 p a g e r a n k 、动态摘要、网页快照、d a i j y r e f r e s h 、多文档格式支持、地图股 票词典寻人等集成搜索、多语言支持、用户界面等功能上的革新，象 a l t a v i s t a 一样，再一次永远改变了搜索引擎的定义。 2 3 搜索引擎原理 搜索引擎并不真正搜索互联网，它搜索的实际上是预先整理好的网页索 引数据库。 至少由三部分组成： 爬行器( 机器人、蜘蛛) 索引生成器 查询检索器 随着搜索引擎的发展，许多搜索引擎在此基础上增加特色功能。如百度 增加了监控程序。 1 、从互联网上抓取网页 利用能够从互联网上自动收集网页的s p i d e r 系统程序，自动访问互联 网，并沿着任何网页中的所有u r l 爬到其它网页，重复这过程，并把爬过的 所有网页收集回来。 2 、建立索引数据库 由分析索引系统程序对收集回来的网页进行分析，提取相关网页信息 ( 包括网页所在u r l 、编码类型、页面内容包含的关键词、关键词位置、生 成时间、大小、与其它网页的链接关系等) ，根据一定的相关度算法进行大 量复杂计算，得到每一个网页针对页面内容中及超链中每一个关键词的相关 度( 或重要性) ，然后用这些相关信息建立网页索引数据库。 3 、在索引数据库中搜索排序 4 哈尔滨工程大学硕士学位论文 当用户输入关键词搜索后，由搜索系统程序从网页索引数据库中找到符 合该关键词的所有相关网页【4 】。因为所有相关网页针对该关键词的相关度早 已算好，所以只需按照现成的相关度数值排序，相关度越高，排名越靠前。 最后，由页面生成系统将搜索结果的链接地址和页面内容摘要等内容组织起 来返回给用户。 搜索引擎的s p i d e r 一般要定期重新访问所有网页( 各搜索引擎的周期 不同，可能是几天、几周或几月，也可能对不同重要性的网页有不同的更新 频率) ，更新网页索引数据库，以反映出网页内容的更新情况，增加新的网 页信息，去除死链接，并根据网页内容和链接关系的变化重新排序。这样， 网页的具体内容和变化情况就会反映到用户查询的结果中。 2 4 搜索引擎分类 按照工作方式，搜索引擎可分为： 1 、全文搜索引擎( g o o g l e 、a l t a v i s t a 、f a s t a l l t h e w e b 等) 2 、目录索弓i ( y a h o o ! ) 3 、元搜索引擎( i n f o s p a c e 、d o g p i l e 等) 4 、垂直主题搜索引擎( 专业搜索引擎) ： 其中，垂直主题搜索引擎以其高度的目标化和专业化在各类搜索引擎中 占据了一系席之地。比如象股票、天气、新闻等类的搜索引擎，具有很高的 针对性，用户对查询结果的满意度较高。服务垂直( 专业) 化是互联网发展 的大势所趋，区别于大而全的水平网站，垂直网站更注重在单一领域提供更 专业、更精深的服务。 2 5 搜索引擎算法 1 、p a g e r a n k 算法( g o o g l e ) 基本思想：一个页面被多次引用，即很多页面有指向它的链接，则这个 页面很重要；一个页面虽未被多次引用，但被另一个重要页面引用，它可能 也很重要；一个页面的重要性被均匀地分布并传递到它引用的页面1 5 】。 p a g e & b r i n 根据此原理，与关键词检索以及其它基于文本的技术一起来 提高查询质量。 晗尔滨工程大学硕士学佼论文 2 、h i t s 算法( h y p e r t e x ti n d u c e dt o p i cs e a r c h ) 最早由k l e i n b e r g 程1 9 9 9 浑提出。它依赖于查询式，认斑页面的藏要 糕袄鞍子歪在裘谗蕊套键式；每燹蠢瓣令缀弱，繇a u t h o r i t i e s ( 权藏级 别) 和h u b s ( 中心级别) 3 、s a l s a 算法、p s a l s a 算淀、p h i t s 箕法等。 大体上与h i t s 算法相类似，或者说是h i t s 算法的改进和补充。 2 。鑫本章奎结 本肇简要介缓了搜索引擎的发展历程，它跫由第一个自动索引互联网上 匿名f t p 阏懿文件的稔序发展箍来，先螽经历了基予潮终释行鬟建立庞大 的索零 数摆库等发展玲段，介缨了当蘸程互联阚上应用比较广泛的几种搜索 孕l 擎。简明阐述了援索簪| 擎用畿够获互联网上舞动收檠阐页酶s p i d e r 系统 摆序收集信息、建立索弓l 数据瘩鄹在索孳l 数摄疼中搜索摊序这榉一个基举工 作原理，经典搜索弓l 擎的基本缭稳和分炎，其中，垂煮主题搜索弓l 擎戳箕离 度的目标化和专业化，为用户提供提供熨专业、更精深的服务，是我们研究 的主要方向。同时，本肇还介缡了比较流行的集中搜索弓 擎算法，讨论了关 于信息搜索的比较常用的几种方法。 6 哈尔滨工程大学硕士学位论文 第3 章深度搜索的w e b 信息采集系统 本课题研究的深度搜索引擎是建立对以某一u r l 地址为起点( 通常是 网站的起始页) 搜索其链接的网页( 通常只搜索与起点在同一网站的网 页) ，不断递归此过程，不断地深入网站挖掘网网页，从而达到遍历整个网 站的目的。因此深度搜索的信息采集系统与传统搜索引擎有着类似和区别。 下面介绍的深度搜索的w e b 信息采集系统的设计思路：包括w e b 信息 采集系统的基本原理、基本结构和d e l p l l i 实现。 3 1 基本原理 w e b 信息采集( w e bc r a w l i n g ) ，主要是指通过w e b 页面之间的链接关 系，从w e b 上自动的获取页面信息，并且随着链接不断向所需要的w e b 页面 扩展的过程1 6 】。实现这一过程主要是由w e b 信息采集器( w e bc r a w l e r ) 来 完成的。根据应用习惯的不同，w e b 信息采集器也常称作w e bs p i d e r 、w e b r o b o t 和w e bw o r m 。粗略的说，它主要是指这样一个程序，从一个初始的 u r l 集出发，将这些u r l 全部放入到一个有序的待采集队列里。而采集器 从这个队列里按顺序取出u r l ，通过w e b 上的协议，获取u r l 所指向的页 面，然后从这些已获取的页面中提取出新的u r l ，并对新提取的新的u r l 进行判断( 判断是否与起点u r l 在同一网站内部，或是否在同一子目录 下) ，符合则将他们继续放入到待采集队列里，然后重复上面的过程，直到 采集器根据自己的策略停止采集。 3 2 基本结构 如图3 1 所示，w e b 信息采集系统基本上可以划分为七个部分：u r l 处 理器、协议处理器、重复内容检测器、u r l 提取嚣、m e t a 信息获取器、语 义信息解析器和数据库，它们协调起来从w e b 上获取信息。图中的箭头表 示数据走向。 3 2 1u r l 处理器 这个部件主要给待采集的u r l 排序，并根据一定的策略向协议处理器 7 晗尔滨工程大学琰士学位论文 分瓣u r l 。按照采集系统鬟模熬不溺，i _ r i l l 可以是多孛采集获瑟，龟墨浚 怒一令u r ls e r v e r 。疆懿，天罗w e b 聚集系统采嗣了多个采集瓢确，琵 g o o g l e 采集系统则使用了u r ls e r v e r ，以这到更快的处理速度。u r l 处理 器主要有三个数据来源：1 ) 初始的种子u r l 集，如图中的粗箭头所示；2 1 从u r l 提取器传输过来的u r l 檠，它们是从已经采集到的页面中提取出来 的；3 ) 页面的m e t a 、主题以及摘要等信息，来自m e t a 信息获取器，它们主 骤用来显示从u r l 提取器中传输过来的u r l 的重要性，为在这里排序提供 依据。另外，u r l 处理器还有一个任务就是d n s 解析。 霞3 1w e b 僖惠聚集系统基本结梅 3 2 2 协议处理器 这个部件处于系统的底层，主骚通道各种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 为主。 8 哈尔滨工程大学硕士学位论文 3 2 3 重复内容检测器 w e b 上存在着大量的镜像页面和内容，最近的研究表明，将近3 0 的 页面是重复的【8 。这极大的浪费了网络的带宽和影响了系统的效率。所以， 重复内容检测变成了采集系统，特别是大型采集系统的重要组成部分。要采 用的检测方法，根据系统的需要，从简单的段落匹配到复杂的相似度比较中 选择。本课题研究的深度搜索针对一个网站，所以只需要使用相对简单的处 理。 3 2 4u r l 提取器 对于采集到的页面，经过重复内容检测后，需要分析其中的链接，并对 链接进行必要的转换，这些任务由u r l 提取器来完成。首先判别页面类 型，对类型为“t e x t 、h t m l 、s h t m l 和h t m ”等的页面进行分析链接。页面的 类型可由应答头分析得出，有些w w w 站点返回的应答信息格式不完整， 此时须通过分析页面u r l 中的文件扩展名来判别页面类型。需要分析的标 记包括 、 、 、 、 、 和 等。页面链接中给出的u r l 可以是多种格式的，可能是完整的包括协议、 站点和路径的，也可能是省略了部分内容的，或者是一个相对路径。为处理 方便，一般先将其规格化成统一的格式。 3 2 5m e t a 信息获取器 这里所要获取的内容包括已采集页面的m e t a 信息、a n c h o r 信息、页面 的标题、页面的摘要等。获取它们的主要目的是力图在没有对页面内容语义 信息进行理解的前提下，尽可能多的挖掘m e t a 、结构等的语义信息，来为 从这些页面中提取出来的u r l 的好坏，给出一个度量。度量的结果传输到 u r l 处理器用于排序。 3 2 6 语义信息解析器 根据采集策略的不同，有些采集器还有语义信息解析器。这里所说的语 义信息解析就是指对文本内容建立简单的索引。因为它在一定程度上挖掘了 页面内容的语义，所以叫做语义信息解析器【9 】。对于一些大型的信息采集 9 哈尔滨工程大学硕士学位论文 器，比如a l t av i s t a ，由于采集的信息量很大，对语义挖掘的深度要求较 高，所以般将页面语义挖掘与信息采集独立开来，而用专门的i n d e x e r 等 部件进行处理。对于一些轻量级的采集系统，比如基于用户个性化的采集， 因为采集的信息量不大( 这样语义信息解析就不太影响采集效率) 和采集过 程中更需要语义信息制导，所以它们也常用到语义信息解析器。 3 2 7 数据库 经过重复内容检测后的页面数据、提取出来的m e t a 信息、主题和摘要 等都要存入数据库，以备其他应用使用。比如，对于g o o g l e 这样的搜索引 擎，这个数据库中的内容将用于建立索引。如果系统有语义信息解析器，则 解析出来的内容也存入数据库。由于数据较多，所以在存入数据库之前，数 据一般要进行压缩。 3 。3w e b 信息采集面临的主要困难和相应的技术手段 粗看起来，采集的过程似乎比较简单，但实际上，它却存在着许多技术 上和工程上的挑战。在分析这些挑战之前，先看下w e b 的特点。 3 3 1w e b 的特点 互联网w e b 页面存在以下几个特点：1 ) 信息容量的巨大性，在1 9 9 8 年 7 月，w e b 上的静态文本大约有3 亿5 千万个，并且以每月6 0 0 g b 的速度 增长 k a h l e1 9 9 7 1 ；2 ) w e b 的动态性，每天w e b 中的内容和w e b 的结构都在 变化着；3 ) w e b 的异构性，w e b 中包含的文件类型各式各样，包括图像、图 片、声音、文本以及s c r i p t 等；4 ) w e b 页面的重复性，最近的研究表明，将 近3 0 的页面是重复的；5 ) 高链接性，平均每个页面有超过8 个链接指向别 的页面；6 1 多语种性，现在w e b 上的页面语种超过了1 0 0 个【l 。这为w e b 的有效采集，特别是为搜索引擎的采集提出了巨大的难题。 3 3 2w e b 采集面临的技术困难和相应手段 从技术角度看，挑战主要有以下几点： 1 、网站的页面数：一些网站的页面数可能很小，如简单的静态网站， 一般只有几十到几百个w e b 页面，这些网站进行深度搜索比较容易；一些 哈尔滨工程大学硕士学位论文 动态网站的页面数可能很大，如b b s 论坛有几万、几十万、几百万的w e b 页面。 2 、网站的网页变化：网站的网页数和网页内容可能随时发生变化，如 静态网站的页面的增加减少、网页内容的修改；动态网站的页面数大量增加 ( 如b b s 发表新的文章) ，可能一天增加几千个页面，同时一些已经存在的 页面内容也会发生比较大的修改( 如b b s 的用户对已经发表的文章的评 价，即跟贴，页面地址没有变化，而页面内容发生了很大的变化) 。 3 、网页面的大小：可能是很小，如几千字节，也可能是很大几百个千 字节。 这些对本课题研究的分布式深度搜索，特别是信息采集增加了很大的难 度和复杂度 3 4w e b 采集系统的基本结构和工作过程 如图3 2 所示，w e b 信息采集系统从功能上看可分为两个部分：采集 器部分和控制部分，中间的竖立虚线将他们分开。采集器部分主要负责实际 采集，它分为三个部分。1 ) 站点采集。把整个w e b 以站点为单位划分成若 干个连通子图是合乎人们的浏览习惯的，并且也是利于存储的。w e b 信息采 集系统的设计就是根据这一点，对w e b 上的页面以站点为单位进行采集。2 ) 页面采集。尽管系统从粗粒度上看，采集是以站点为单位的，但是从细粒度 上讲，每次只采集一页。这个部分考虑的重点就是对采集每页相关的协议的 处理和实时网上异常的处理。3 ) 存储库，主要存储采集到的数据、站点结构 信息以及相关的有用信息。 图3 2 信息采集系统结构 l l 哈尔滨工程大学硕士学位论文 控制部分主要负责采集以外的协调、策略以及与应用的接口，它分为五 个部分：1 ) 采集系统设置，主要用于系统管理员对采集系统的控制，包括 设置采集起点和采集策略。2 ) 采集系统控制，这是采集系统最具有全局观 念的一个子系统，它主要负责总体控制和其他各子系统之间的协调和连接， 另外它还集中式的控制多个采集器并行。3 1 存储库，主要负责存储一致化 处理后的各项数据以及在此基础上进行索引等处理的数据。4 ) 采集策略处 理，负责处理采集系统在理论上最难的一个部分一如何有效的采集和动态 的刷新。5 ) 安全开关，在实际应用系统中，采集器往往直接和w e b 相连， 而同时又与内部的应用服务器相连，如果不加安全处理，w e b 对于应用服务 器是非常危险的】。为此，本采集系统设计了低成本高效率的安全开关。 当与应用系统交换数据时，采集系统与w e b 断开；当在w e b 上采集数据 时，采集系统与应用系统断开。这也是本采集系统的特色之一。图中的箭头 描述了数据流向。 为了提高采集的效率，w e b 采集系统采用服务器( 采集系统控制) 采集器 的结构使采集系统具有很好的可扩展性。管理员可根据系统采集规模的变化 动态地调整采集器的数量，在保证系统性能的前提下尽量减少系统开销，达 到最佳的性能价格比，而且在规模动态变化的过程中，系统能维持一致的 管理和数据输出接口。 3 5w e b 信息采集系统模型 深度搜索引擎的信息采集在应用需求的推动下，已经成为一个热门的 研究课题【1 2 】。为了更好的研究这个课题，我们设计了一个深度搜索引擎的 信息采集系统模型，如图3 3 所示。为实现对基于主题的信息自动采集，我 们将整个处理过程分成五大模块：主题选择和初始u r l 选择、s p i d e r 采 集、页面分析、u r l 与相关性判定( 链接过滤链接预测) 、页面与主题的相 关性判定( 页面过滤) 。下边简要地说明整个系统模型中的关键问题，在后续 几章里，我们将详细讨论各个模块的算法及实现。 哈尔滨工程大学硕士学位论文 3 6 模型中的关键问题 3 6 1s p i d e r 采集 这个部分处于系统的底层，也叫“网络蜘蛛”，是系统专门与具体的 w e b 打交道的部分。主要通过各种w e b 协议来自动采集i n t e m e t 上w w w 站点内有效的信息( 包括文本、超链接文本、图象、声音、影像、压缩包等 各类文档) 。这些w e b 协议包括h t t p 、f t p 以及b b s ，还根据用户的需要 采集了w 曲c h a t 、i c q 等特殊信斛】。这个部分主要对应于在第二章中介 绍的w e b 信息采集系统的基本结构中的“协议处理器”部分。 图3 3 深度搜索引擎的信息采集系统模型 哈尔滨工程大学硕士学位论文 3 6 2 页面分析 在页面采集到以后，我们要从中提取出链接来，然后根据链接相关性 判定来过滤。为了其它操作的处理，我们也要进行对页面内容标题、摘要等 的提取。所有的这些就是页面分析的内容：链接的提取、元数据的提取、正 文的提取、关键词的提取、标题的提取、摘要的提取。同时进行判定分析， 决定是否需要对此页面进行信息整理。 3 6 3u r l 的相关性判定链接过滤链接预测 为了有效的提高基于主题的w e b 信息采集的准确率和效率，系统需要 对“待采集u r l ”进行u r l 与主题的相关性判定，也可以叫做链接过滤或 链接预测。按照高预测值优先采集、低预测值( 小于设定闽值) 被抛弃的原则 进行剪枝处理，这样可以大大减少采集页面的数量，有效的提高主题信息搜 索的速度和效率。 3 6 4 页面的相关性判定页面过滤 为了进一步提高采集页面的准确率，需要对已采集的页面进行主题相关 性评价，也就是页面过滤。通过对评价结果较低的页面( 小于设定的阈值) 剔 除，来提高所采集主题页面的准确率 1 4 】。这个问题是检索领域内的一个经 典问题，已经有许多成熟的基于关键词的相关性判定算法。 3 6 5 数据存储 主要有三种数据库需要存储，它们是主题页面库、全局u r l 队列和中 间信息记录库。主题页面库主要存放采集器采集过的并经过页面过滤处理后 的主题页面。全局u r l 队列则是存放从采集到的页面中提取出来的u r l 的 地方，这些u r l 在进入u r l 队列前必须经过u r l 预测处理，只有被预测 为指向主题相关页面的链接才能进入全局u r l 队列。在插入队列时，也要 根据u r l 与主题的预测相关性的大小排序，相关性越高，排序越前。为了 有效的进行u r l 与主题的相关性判定和页面与主题的相关性判定流程，显 然需要许多中间处理结果，比如使用p a g e r a n k 算法时每个页面所拥有的 p a g e r a n k 值，所有的这些中间数据，保存在中间信息记录库中。 1 4 堕签堡三堡查堂堡主堂垡丝塞 3 。6 6 刷新问题 对于搜索引擎的技术困难之一就是刷新问题 ”l 。本课题采取对每个页 面进行双重判断标记的方式，第一重是时间戳( 建立时间，修改时间) 和文 件大小；第二重是每次的页面分析前生成数字签名( m d 5 ) ，既对于网页会 进行m d 5 运算，并将m d 5 值作为签名存储到数据库中，下次搜索前进行 签名比对，对于未改变的信息不进行搜索。 当完成第一次完整扫描后，这些信息都存在于数据库中。当第二次扫描 ( 搜索引擎的s p i d e r 一般要定期重新访问所有网页) 或者以分布式扫描方 式进行时候，在分析到u r l 连接时，进行第一重判断，这时仅获得页面信 息，并未抓取页面。既判断时间戳和文件大小标志，如发生变化则标记为需 要重新抓取，若这些标记没有变化，则根据系统设定或p a g e r a n k 值决定是 不进行刷新还是重新抓取，这样即可过滤掉一些没有发生变化的页面，降低 这个深度搜索对网络的占有度。 当某页面重新抓取后，进行第二重判断先生成数字签名( m d 5 ) ，和第 一次生成的数字签名进行比对，如一致，则可以确定页面没有发生变化，不 需要对此页面进行整理、分析、存储等工作，从而降低了对c p u 运算、数 据库服务器的负荷。 3 7s pid e r 采集 信息采集系统的最前沿技术就是与i n t e m e t 相连的s p i d e r 采集，也叫 “网络蜘蛛”，是系统专门与具体的w e b 协议打交道的部分。主要通过各种 w e b 协议来自动采集w w w 站点内有效的信息( 包括文本、超链接文本、 图象、声音、影像、压缩包等各类文档) 。这些w e b 协议包括h t t p 、f t p 以及b b s ，我们还根据用户的需要，采集了w e bc h a t 、i c q 等特殊信息。 本章先就s p i d e r 结构作了一个简要说明，然后详细论述了我们的相关算 法。 雩廷毒一霉i 彦7一一，一、一，7 莺t 墨一一。 图3 4s p d e r 的系统模型 如图3 4 所示，为了能够高效地采集页面数据，我们在s p i d e r 系统中采 用了c l i e n t s e r v e r 结构。“网络蜘蛛”由一台或多台s p i d e r 构成，它们通过 内部通信，由信息服务器统一管理并协同工作。由于s p i d e r 的效率受采集 平台、网络性能等诸多限制，为了达到比较理想的采集速度，我们采用了用 多个s p i d e r 同时并行采集的策略，具体并行的s p i d e r 个数需要根据实际的 采集速度要求和网络环境而定。 我们这里所说的信息服务器主要负责对全局u r l 队列中的u r l 进行分 发、对采集到的页面信息和文件信息进行缓存和压缩以及在采集过程中的一 些协调和控制。这一部分所要处理的一个中心问题就是u r l 的分配策略， 以便能够快速的有效的利用多个s p i d e r 共同高效采集。为了实现的简单 性，我们采用了轮转法进行分配。并且当某个s p i d e r 没有待采集的u r l 时，它也会主动向u r l 分发器发送u r l 请求。 每个s p i d e r 的任务就是将信息服务器分配给它的u r l 按照到来的先后 顺序插入到自己的u r l 队列中，然后不停的从队首取出u r l 进行采集，直 到自己的u r l 队列为空。另一种u r l 入队的方法是根据u r l 的主题相关 性评分高低插入自己的u r l 队列( 评分最高的放在队首) ，但插入队列的时 间代价和入队时的互斥操作都会影响采集的效率，而此方法换来的好处“更 加优先的采集评分更高的页面”也并不太影响最终采集页面的质量。因此， 我们选择了前者这种简单的方法。为了提高进一步的采集效率，在每个 哈尔滨工程大学硕士学位论文 s p i d e r 上我们采用了多线程方式。 3 7 2 采集算法及实现 3 7 2 1u r l 的调度策略 为了提高分布式采集的效率，一般常用两种调度策略：静态调度和动态 调度。 静态调度相对比较简单，它并不看采集器当时的负载情况，而是按事先 的决策进行页面的分配。目前，主要有三种方法。1 ) 轮转法，即将待采集 的页面依次分配给1 3 个采集器，直观上看，每个采集器被分配了相同的采集 页面数，但是由于每个页面的连接时间不同，页面的大小也不同，尤其在复 杂多变的网络环境下，分配不均衡几乎是不可避免的。2 ) 加权轮转法，针 对刚才提到的轮转法的缺点，将导致分配不均的主要因素网络连接时间长短 作为权值，来引导轮转。一般来说，初始采集很难知道页面连接的时间长 短，所以此时不能用加权轮转法，但由于网络中大部分网站在一段时间内的 平均连接时间变化不大，因此在刷新的时候可以用加权轮转法，试验说明此 时加权轮转法好于轮转法。3 ) 随机选择法，假设每个页面的采集时间满足 指数分布，每个采集器的处理能力为c 1 ，c 2 ，c 。，则以概率最= c k y c ik = l ，2 ，n 为采集器k 分配待采集页面。当每个采集器的处理能 莒 力相同时，则对每个采集器按概率为1 n 分配页面。 实际的w e b 是异构的、无序的和复杂的，文件格式各式各样，网络状 况也随时间变化莫测。采用静态调度策略，并不考虑w e b 当前的负载情况 这一重要信息，结果常常难以令人满意。相应的，根据当前的负载情况进行 调度的策略称为动态调度，这是一种更加智能化的方法，但算法往往比较复 杂，维持此方法的系统开销也较大。动态调度主要有以下几种方法：1 ) 最 低负载法，即将页面总是分配给当前负载最低的采集器。这个算法的问题在 于：收集各个采集器的当前负载会导致额外的开销，并且过时的信息可能导 致误判坫 。2 ) p i c k 2 方法，在这种复杂的环境中，与其增加大量的开销以跟 踪负载，倒不如简单的增加选择的随机性以模拟环境的随机性。事实上，这 样反而会改善整个系统的性能。p i c k - 2 方法就是这样一个例子，它是指随机 1 7 哈尔滨工程大学硕士学位论文 的选择两个采集器，并选择负载较低的一个采集器分配页面。同理，p i c k - k 就是随机的选择k 个采集器进行比较，当k = n 时，p i c k k 方法就退化成最低 负载法了，当k - - 1 时，p i c k - k 方法就变成了我们前边说的随机分配法。 m i t z e n m a c h e r 对p i c k - k 进行了实验分析，他认为在大多数情况下，k = 2 是较 好的选择【1 7 j 。 对于我们的系统来说，首先这是一个试验系统，试验的重点并不是分布 式，而主要是测试页面和u r l 的过滤算法和系统的整体工作运转情况；其 次，我们系统中所并行的各个s p i d e r 的环境较相似( 网络环境和机器性能) ， 所以我们选择了较简单的轮转法。 3 7 2 2 每个s p i d e r 的抓取流程 图3 5s p i d e r 的抓取流程 抓取工作流程如图7 2 所示，大致步骤如下： 1 1 如果采集数据达到3 0 0 k ( 上传数据n n ) ，则上传数据到信息服务 器。 2 1 从u r l 队列中取出一个u r l 放入协议判断器中。如果此时u r l 哈尔滨工程大学硕士学位论文 队列为空，则转入7 ) ，否则转入3 ) 。 3 ) 根据u r l 头部的协议信息，协议判断器对u r l 所采用的协议进行 判断，如果是h t t p 协议，转入4 1 ，如果是f t p 协议，转入5 ) ， 如果是b b s 协议，转入6 1 。 4 ) 启动采集i - i t t p 协议的线程h t t p p a g e c o n t r o l ，对本页通过 h t t p c o r m e c t i o n 进行采集。采集完后保存此页，转入1 ) 5 1 启动采集f t p 协议的线程f t p p a g e c o n t r o l ，对本页通过 f t p c o r m e c t i o n 进行采集。采集完后保存此页，转入1 ) 6 ) 启动采集b b s 协议的线程b b s p a g e c o n t r o l ，对本页通过 b b s c o n n e c t i o n 进行采集。采集完后保存此页，转入1 ) 7 ) 向信息服务器发送请求u r l 指令，采集完毕。 3 7 2 3 抓取页面时的处理 因为所抓取的主要页面都是符合h t t p 协议的，所以我们以h r r p 协议 为例，说明具体的页面抓取时的处理。在页面抓取过程中用s o c k e t 实现了 基本的h t t p 协议，采集器可以经由指定的代理服务器( p r o x y ) 采集目标 u r l ，并且在目标u r l 要求身份认证时能自动用事先设置好的用户标识和 口令应答。抓取页面的主要实现算法如下： 1 1 分析页面u r l ，抽出目标站点地址和端e l 号，若无端e l 号设为 h r r r p 默认端口8 0 。判断该站点的连接方式设置，若设为直接连接 则与该地址和端口建立网络连接；若设为穿越p r o x y 连接则与指定 的p r o x y 地址和端1 3 建立网络连接。 2 】若建立网络连接失败，说明该站点不可达，中止抓取该页面并将其 抛弃；否则继续下一步骤获取指定页面。 3 1 由页面u r l 组装h t t p 请求头，若该站点需要用户标识和口令则 将其填入请求头中，发送请求到目标站点。若超过一定时间未收到 应答消息则中止抓取该页面并将其抛弃；否则继续下一步骤分析应 答消息。 4 1 分析应答头，判断返回的状态码： 若状态码为2 x x ，返回正确页面，进入步骤5 ) ； 1 9 哈尔滨工程大学硕士学位论文 若状态码为3 0 1 或3 0 2 ，表示页面被重定向，从应答头中提取出新 的目标u r l ，转入步骤3 ) ； 若状态码为其它，说明页面连接失败，中止抓取该页面并将其抛 弃。 5 ) 从应答头中提取出日期、长度、页面类型等页面信息。若设置了页 面抓取限制，进行必要的判断和过滤，抛弃不符合要求的页面。 6 ) 读取页面