（检测技术与自动化装置专业论文）基于java技术的智能化搜索引擎的研究与设计.pdf

c l a s s i f i e di n d e x ： i u d c ： l i i ii ii iii tl l l ii i iiii y 18 0 9 2 0 1 ad is s e r t a t i o nf o rt h ed e g r e eo fm e n g r e s e a r c ha n d d e s i g no fi n t e l l i g e n ts e a r c h e n g i n e ba s e do nj a v a t e c h n o l o g y c a n d i d a t e ：l e ib i n s u p e r v i s o r ：s e n i o re n g i n e e r w a n gj i n g g a n g a c a d e m i cd e g r e ea p p l l e df o r ：m a s t e ro fe n g i n e e r i n g s p e ci a l it y ：d e t e c t i o nt e c h n o l o g ya n da u t o m a t i ce q u i p m e n t d a t eo fs u b m i s s i o n ：d e c e m b e r ，2 0 0 9 d a t eo fo r a le x a m i n a t i o n ：m a r c h ，2 0 1 0 o n i v e r s i t y ：h a r b i ne n g i n e e r i n gu n i v e r s i t y 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导 作者本人独立完成的。有关观点、方法、数据和 文中指出，并与参考文献相对应。除文中已注明 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 答字) ：捌 日期：1 0id年片7f 日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 臼在授予学位后即可口在授予学位1 2 个月后口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：f 窍趴 导师( 签字) ：珈 日期：1 0 fd 年乙月if 日、2 夕f0 年；月日 哈尔滨丁程大学硕十学位论文 摘要 随着i n t e m e t 的快速发展，网络信息量迅速增加，人们越来越需要通过 搜索引擎来获取有用信息。通用搜索引擎的由于范围太广，造成搜索结果的 覆盖率、准确度太低，搜索的效率也就随之降低，这对于用户的体验是不友 好的，在这种情况下对于特定领域内的智能化搜索引擎的需求就越来越明显。 本文通过研究搜索引擎的技术和框架设计方案、对比其与特定领域主题搜索 引擎的区别特点，开发设计了一套具有在特定领域内进行爬取、索引和检索 功能的搜索引擎。 首先本文通过分析国内外搜索引擎的历史发展、分类特点，垂直搜索引 擎的特点和发展，研究搜索引擎开发的技术要点，并重点介绍了l u c e n e 开发 工具包的技术和应用特点。 随后通过对搜索引擎的框架和技术分析，设计了整个系统的流程图和设 计方案，并分析各模块的功能特点。 接下来又对搜索引擎中的一个重要模块主题网络爬虫模块进行分 析，并在设计爬行策略时对传统的f i s h s e a r c h 算法做了改进，提出了将待爬 行链表进行一分为二的策略，并通过实验证明，这样的改进提高了爬虫爬取 的准确率。 最后对搜索引擎中的索引和检索模块进行设计分析，并且在索引构造方 法中提出了一种关键词加摘要索引方法，通过实验证明了这种方法既能够减 小索引文件的大小，也能够提高检索结果的查准率，即提高了整个搜索引擎 的效率。 关键词：主题爬虫；搜索引擎；l u c e n e自动摘要 c “ 哈尔滨t 稃大学硕十学仲论文 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n t e m e t ，t h ei n c r e a s i n ga m o u n to fn e t w o r k i n f o r m a t i o n ，t h es e a r c he n g i n ei sb e c o m i n gm o r ea n dm o r ei m p o r t a n tf o rp e o p l e t og e tu s e f u li n f o r m a t i o n b e c a u s eo ft h el a r g es e a r c h i n gs c o p e ，g e n e r a ls e a r c h e n g i n eh a sal o wc o v e r a g ea n dl o wa c c u r a c y , s ot h es e a r c he f f i c i e n c ya l s o d e c r e a s e s ，w h i c hi su n f r i e n d l yt ot h eu s e r s i nt h i sc a s e ，t h ei n t e l l i g e n ts e a r c h e n g i n ew h i c hi sf o c u so ns o m ep a r t i c u l a ra r e a sh a sb e c o m em o r ei m p o r t a n tt h a n e v e rb e f o r e i nt h i sp a p e r , a ni n t e l l i g e n ts e a r c he n g i n es y s t e mh a sb e e nd e s i g n e d w h i c hc a nc r a w l i n gi ns p e c i f i ca r e a s ，i n d e x i n ga n ds e a r c h i n g ，b yc o m p a r i n g 晰t 1 1 t h ed i f f e r e n c eb e t w e e nc o m m o na n di n t e l l i g e n ts e a r c he n g i n e f i r s t ，t h eh i s t o r yo ft h ed e m e s t i ea n di n t e r n a t i o n a ls e a r c he n g i n ei sb e e n d i s c u s s e di nt h i sp a p e r , a l s ot h ec l a s s f l c a t i o nf e a t u r e s ，t h et e c h n i c a lf e a t u r e so f v e r t i c a ls e a r c he n g i n e ，a n dh i g h l i g h t st h et e c o n o l o g ya n da p p l i c a t i o nf e a t u r e so f t h el u e e n et o o l k i t t h e ni td e s i g n e dt h ef l o w c h a r ta n dm e t h o do ft h es y s t e mb ya n a l y s i n gt h e f r a m e w o r ka n dt e c h n i c a lo fs e a r c he n g i n e ，a l s oa n a l y z e dt h ef e a t u r e so fa l lt h e m o d u l e s f o l l o w i n g ，a ni m p o r t a n tm o d u l e - t h e m a t i cn e t w o r kc r a w l e r , i sb e e na n a l y z e d ， w h i c hh a sm a d e s o m ei m p r o v e m e n to nc r a w l i n g a l g o r i t h mb a s e do nt h e t r a d i t i o n a lf i s h - s e a r c ha l g o r i t h m ，p u tf o r w a r dt h es t r a t e g yt os e p a r a t et h es i n g l e w a i t i n g _ l i s ti n t ot w op a r t s ，a st h er e s u l t ss h o w , t h i si m p r o v e m e n ti n c r e a s et h e a c c u r a c yo fr e p t i l e sc r a w l i n g f i n a l l y , t h ei n d e x i n gm o d u l ea n dd e s i g nm o d u l ei sd e s i g n e da n dd i s c u s s e d ， w h i l ec r e a t i n gi n d e xf i l e s ，an e wm e t h o di sd e s i g n e d ，w h i c hd o i n gi n d e x i n go n s u m m a r yc o n t e n ta n dt h ek e y w o r d s ，t h er e s u l t ss h o wt h a tt h i sm e t h o dc a nr e d u c e t h es i z eo f i n d e xf l i e s ，a n da l s oc a ni n c r e a s et h ep r e c i s i o no fs e a r c hr e s u l t sa n dt h e e f f i c i e n c yo ft h ee n t i r es e a r c he n g i n e k e yw o r d s ：t h e m ec r a w l e r ；s e a r c he n g i n e ；l u c e n e ；a u t o m a t i cs u m m a r i z a t i o n 哈尔滨t 程大学硕十学何论文 目录 第1 章绪论1 1 1 搜索引擎概述1 1 2 搜索引擎发展1 1 3 搜索引擎的分类4 1 4 垂直搜索引擎的研究4 1 5 本文主要工作5 第2 章搜索引擎关键技术7 2 1 网页信息抓取7 2 1 1 网络蜘蛛原理7 2 1 2 网络蜘蛛工作过程”9 2 2 网页信息与处理1 0 2 2 1l u c e n e 简介”1 0 2 2 2l u c e n e 索引文件的建立l o 2 2 3l u c e n e 索引文件格式1 2 2 3 信息检索模型1 2 2 3 1 布尔模型1 3 2 3 2 向量模型1 3 2 3 3 概率模型1 5 2 3 4l u c e n e 检索机制1 7 2 4 自动摘要技术”1 9 2 4 1 基于统计的自动摘要1 9 2 4 2 基于理解的自动摘要2 0 2 4 3 基于信息抽取的自动摘要2 1 2 4 4 基于结构的自动摘要2 l 2 5 本章小结2 2 第3 章特定领域智能化搜索引擎的设计2 3 3 1 需求分析2 3 哈匀：滨t 程大学硕十学位论文 3 2 系统总体设计2 4 3 2 1 系统开发环境2 4 3 2 2 总体设计2 4 3 3 系统工作原理2 5 3 4 系统软件模块功能分析2 6 3 5 本章小结2 7 第4 章主题网络爬虫的设计与实现2 8 4 1 主题网络爬虫的设计分析“2 8 4 2 主题网络爬虫的技术要点“3 0 4 2 1 多线程3 0 4 2 2 线程同步31 4 2 3 数据库存储设计31 4 2 4 提取链接“3 3 4 2 5 停止协议3 4 4 2 6 字节输入输出流3 5 4 2 7 爬行策略3 6 4 3 实验测试4 3 4 4 本章小结4 5 第5 章索引和检索功能模块设计与实现4 6 5 1 功能模块设计分析4 6 5 2 网页去噪4 8 5 2 1h t m l 网页文件4 8 5 2 2 网页净化4 8 5 3 自动文本摘要”5 1 5 3 1 自动文摘方法选择5 l 5 3 2 基于统计方法的文本摘要实现5 2 5 3 3 自动摘要性能评测5 6 5 5 索引文件构造及扩展配置功能”5 9 5 6 检索功能及界面设计与实现6 0 5 7 实验测试“6 2 哈尔滨i t 挥大学硕十学何论文 5 8 本章小结6 7 结 仑6 8 参考文献6 9 攻读硕士学位期间发表的论文和取得的科研成果7 3 驾【谢7 4 哈尔滨t 程大学硕十学何论文 第1 章绪论 1 1 搜索引擎概述 搜索引擎( s e a r c he n g i n e ) 是【l 】指根据一定的策略、运用特定的计算机 程序搜集互联网上的信息，在对信息进行组织和处理后，并将处理后的 信息显示给用户，是为用户提供检索服务的系统。网络信息日益膨胀， 可以说，谁能把握网络资源，就能最新把握最新的科技技术。在这个网 络时代我们获取网络信息最重要的和最频繁的方式就是通过搜索引擎， 它已经称为人们日常生活中必不可少的工具，搜索引擎从产生开始到现 在发展就特别迅速，对搜索引擎的研究已称为信息检索领域研究的热点。 搜索引擎的功能也越来越强大，效率越来越高，如我们熟悉的百度地图搜 索、百度m p 3 搜索、g o o g l ee a r t h 等特色的搜索服务，无不极大的方便了人们 的生活，目前搜索引擎还在继续向着专业化、个性化、智能化的方向发展。 但它目前仍存在很多问题，如：由于网络信息量增加的速度实在太快致使网 页覆盖率很低；垃圾网站严重干扰搜索结果，造成搜索结果大量重复且经常 包含名不符实的欺骗性网页；搜索结果过于庞大，除了分页没有进一步分类 筛选的功能；专业化程度不够，对于专业性需求强的搜索，常常得不到需要 的结果。 1 2 搜索引擎发展 所有搜索引擎的祖先，是1 9 9 0 年由m o n t r e a l 的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 ef a q ) 。a l a ne m t a g e 等想到了开发一个可以用文件名查找文件 的系统，于是便有了a r c h 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 是后来另 哈尔滨t 稗大学硕十学何论文 一个g o p h e r 搜索工具。 很快，第一个互联网爬虫- m a 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 - 出现了，爬虫( s p i d e r ) 是用于抓取互联网信息的程序。其实，他最初 是想测量w e b 的增长速度而开发这个爬虫来计算w e b 上活动的站点的个数 的，但很快，他又升级了这个爬虫来抓取实际的u r l 。 e x c i t e 的历史可以上溯到1 9 9 3 年2 月，6 个s t a n f o r du n i v e r s i t y ( 斯 坦福大学) 大学生的想法是分析字词关系，以对互联网上的大量信息作 更有效的检索。到1 9 9 3 年中，这已是一个完全投资项目，他们还发布了 一个供w e b m a s t e r s 在自己网站上使用的搜索软件版本，后来被叫做 e x c i t ef o rw e bs e r v e r s 。 1 9 9 4 年4 月，斯坦福大学的两名博士生，美籍华人杨致远和d a v i d f i l o 共同创办了y a h o o ! 。随着访问量和收录链接数的增长，y a h o o 目录 开始支持简单的数据库搜索。因为y a h o o 的数据是手工输入的，所以不 能真正被归为搜索引擎，事实上只是一个可搜索的目录。y a h o o 中收录 的网站，因为都附有简介信息，所以搜索效率明显提高。 1 9 9 5 年，一种新的搜索引擎形式出现了元搜索引擎( m e t a s e a r c he n g i n e ) 。用户只需提交一次搜索请求，由元搜索引擎负责转换处 理后提交给多个预先选定的独立搜索引擎，并将从各独立搜索引擎返回 的所有查询结果，集中起来处理后再返回给用户。第一个元搜索引擎， 是w a s h i n g t o n 大学硕士生 e r i e s e l b e r g 和 o r e ne t z i o n i 的 m e t a c r a w l e r 。元搜索引擎概念上好听，但搜索效果始终不理想，所以没 有哪个元搜索引擎有过强势地位。 智能检索的产生：它利用分词词典、同义词典，同音词典改善检索 效果，进一步还可在知识层面或者说概念层面上辅助查询，通过主题词 典、上下位词典、相关同级词典检索处理形成一个知识体系或概念网络， 给予用户智能知识提示，最终帮助用户获得最佳的检索效果。如当用户 输入“微机”时，相应的“计算机 等相关的词汇也能在搜索结果中， 还有处理纠错能力，如当用户输入一个不合理的词汇时，或者由于失误 输入错误时，搜索引擎能给出合理的提示，并返回相应查询的结果，这 样有利于提高搜索的质量。 2 哈尔滨丁程大学硕十学位论文 个性化搜索引擎的发展：个性化趋势是搜索引擎的一个未来发展的 重要特征和必然趋势之一。一种方式通过搜索引擎的社区化产品( 即对 注册用户提供服务) 的方式来组织个人信息，然后在搜索引擎基础信息 库的检索中引入个人因素进行分析，获得针对个人不同的搜索结果。白 2 0 0 4 年1 0 月y a h o o 推出m y w e b 测试版，到1 1 月a 9 推出个性化功能， 到2 0 0 5 年g o o g l e s e a r c h h i s t o r y 基本上都沿着一条路子走，分析特定用户 的搜索需求限定的范围，然后按照用户需求范围扩展到互联网上其他的 同类网站给出最相关的结果。另外一种是针对大众化的，g o o g l e 个性化 搜索引擎，或者y a h o o m i n d s e t ，或者我们都知道的前台聚类的v i v i s i m o 。 但是无论其中的哪一种实现方式，即g o o g l e 的主动选择搜索范围，还是 y a h o o ( h t t p ：m y y a h o o t o m ) ，v i v i s i m o 的在结果中重新组织自己需要的 信息，都是一种实验或者创想，短期内无法成为主流的搜索引擎应用产 品。 搜索引擎的不足：现有搜索引擎的不足【2 】主要表现在，首先，信息 覆盖面不足：根据美国科学期刊n a t u r e s 的一篇报告中称，全球功能最 大的搜索引擎最多只能覆盖现有网页的1 6 ，也就是说现有的搜索引擎 漏掉了约8 4 的网页信息，而中文搜索引擎起步较慢，中文信息占互联 网全部信息的比例小等原因在这方面尤为突出；其次，查全率和查准率 不，查全率指检索出的相关信息量与存储在检索系统中的全部相关信息 量的百分比，查准率是指系统所检索到的真正与查询内容相关的文档占 检索的所有文档数的百分比，这些缺陷也与第一条所举出的缺陷有着直 接的联系；再次，检索功能方面存在缺陷：现在大型的搜索引擎一般都 能提供组合搜索的功能，而且还有能提供拼音相似查询的功能，但是许 多关于搜索引擎的使用技巧并不是每个普通用户都能很好的掌握，因此 在检索功能方面还有需要加强；最后，专业性的搜索引擎发展迟缓：专 业性搜索是为专门行业、某一主题信息而建立的，这也是本文将要研究 的技术，虽然近期涌现了很多像多媒体搜索、工作搜索等专业的搜索引 擎，但是这些专业搜索引擎的发展速度仍然远远跟不上现在网络用户对 于特定领域内的需求发展。 对于搜索引擎未来的发展，举个例子说明，在第二届广东大学生科 哈尔滨t n 大学硕十学位论文 技学术节上，谷歌全球副总裁大中华区联合总裁曾说过，随着搜索引擎 的智能化，所提供的服务也将不断提升。“在输入母亲节送花给母亲， - d , 时后，一束新鲜的康乃馨立即送到母亲的手上，而用户只需要在搜 索器上输入关键词以及在信用卡付款栏点击确定。”。未来最聪明的搜索 引擎并不是要提供多元化的信息，而是能够提供用户提出问题的答案， 甚至解决问题，用户的要求不同，搜索结果也应该不同。整合搜索、社 区搜索和移动搜索将称为今后发展的三大趋势。 1 3 搜索引擎的分类 搜索引擎按其工作方式主要可分为三种：全文搜索引擎、目录索引 类搜索引擎和元搜索引擎。 全文搜索引擎是目前流行的大型搜索引擎普遍采用的形式。它是指 用户可以去搜索一篇文章中的任何部分，不论是标题，还是正文，用户 得到了更大的自由度。如g o o g l e 、百度等就是优秀的全文搜索引擎。 目录式搜索引擎并不是严格意义上的搜索引擎，它只是将网站进行 人工归类，如果用户想要找到一个网站，那么就顺着分类一直找下去， y a h o o 便是目录式搜索引擎的鼻祖【，l 。 元搜索引擎是将用户发来的查询请求，转发给各大搜索引擎网站， 然后将它们的结果进行汇总，并返回给用户，比较有代表性的是 v i v i s i m o ，i n f o s p a c e 等。 1 4 垂直搜索引擎的研究 垂直搜索引擎的发展：垂直搜索引擎是相对通用搜索引擎的信息量 大、查询不准确、深度不够等【一】提出来的新的搜索引擎服务模式，通过 针对某一特定领域、某一特定人群或某一特定需求提供的有一定价值的 信息和相关服务。其特点就是“专、精、深 ，且具有行业色彩，相比 较通用搜索引擎的海量信息无序化，垂直搜索引擎则显得更加专注、具 体和深入。垂直搜索引擎为用户提供的并不是上百甚至上千万相关网页， 而是在范围很小、极具针对性的具体信息。因此，特定行业的用户更加 青睐垂直搜索引擎，是垂直搜索引擎的长期、稳定的群体。国内外垂直 4 哈尔滨1 j 稃大学硕十学位论文 搜索引擎发展都很迅速，以下就列举几种比较典型的垂直搜索引擎。 ( 1 ) s c i r u s ( h t t p ：w w w s c i r u s c o r n ) s c i r u s 是e l s e v i e r t s l 科学出版社开发的科技文献门户网站，是目前 互联网上最全面、综合性最强的科技文献门户网站之一，目前s c i r u s 已将9 0 0 0 0 0 0 0 个网页编入索引中。还包括1 2 8 0 0 0 0 0 条m e d l i n e 文摘； 1 6 0 0 0 0 0 篇s c i e n c e d i r e c t 全文；9 0 0 0 0 0 项u s p t o 专利等等信息。s c i r u s 只提供包含科学信息的网站。 ( 2 ) c h a c h a ( h t t p ：w w w c h a c h a c o r n ) 此网站成立于2 0 0 8 年1 月，专注于移动搜索( m o b i l es e a r c h ) ，通 过文本信息和即时信息向用户提供免费服务【6 】，该搜索引擎也曾被归到 国外最被看好的十大垂直搜索引擎之一。 ( 3 ) 房老大( h t t p ：w w w f o l o d a c o m h o u s e u s e d h o u s e a s p x ) 这是国内的一个垂直搜索引擎，用户可以通过此搜索引擎选择不同的地 点来查询二手房、租房、经纪人、社区等针对房屋的信息，其信息量更新很 快，信息划分详细，用户也能在网站上发布自己的关于房屋的信息，使用起 来非常方便，不愧是房屋当中的“老大 。 ( 4 ) 去叨i i j d 旅游搜索( h t t p ：w w w q u n a r c o m ) 自此搜索引擎开发出后就得到了广大用户的喜爱，人们可以不用打电话 咨询或找朋友问就可以及时的掌握最新的旅游信息。搜索引擎中的许多功能 都能给用户带来很大的方便，如机票搜索的功能，网站给出了最新的各地机 票票价和打折信息，并实时的给出机票价格动态变化曲线，出于经济方面考 虑的用户可以根据网站提供的信息来指定自己的出行计划，而且也能在最短 的时间联系购买到自己想要的机票。 1 5 本文主要工作 本文是在研究了搜索引擎关键技术基础上，参考了许多搜索引擎的实现 策略，开发设计了一套针对特定领域的智能化搜索引擎，使之能够在特定领 域内进行网页爬取、索引和检索，并且能达到良好的查准率，论文的主要工 作如下： 1 针对垂直搜索引擎的特点设计并实现了网络主题蜘蛛程序，蜘蛛程序 哈尔滨_ t 程大学硕+ 学位论文 实现了一套基于f i s h s e a r c h 算法改进的算法，提出将待爬行队列一分为二的 策略，采用网页标题与主题相似度的来判断将要爬取链接的权重，通过实验 得出这种方案能够得到很高的爬取准确率。 2 在参考许多关于自动文摘系统的文献后，比较了各个自动摘要算法的 实现的难易程度和摘要算法的效率，选取了一套适合本系统的摘要算法来实 现摘要的生成，并根据本系统采集到的网页的特点对摘要算法进行了调整改 进。另外为了验证摘要性能，也采取了比常规方法更有效的算法来验证。 3 设计实现了网页噪音去除功能，为系统的索引和检索模块打好了基 础。 4 基于l u c e n e 的接口开发设计了索引构造器，并且在构建索引文件时 采用了一种新的索引方案，即只对关键词和摘要内容进行索引，实验证明， 这种索引构建方案可以在很大程度上减小索引文件的大小和提高检索的效 率。 5 基于l u c e n e 的接口开发设计了检索器，与用户接口模块共同完成搜 索任务。 6 哈尔滨t 程大学硕+ 学何论文 第2 章搜索引擎关键技术 2 1 网页信息抓取 搜索引擎先要将网页信息文件抓取到，然后再对网页文件进行处理， 但网络信息是每天都在不断更新的，可以说搜索引擎网页爬取的速度跟 不上信息更新的速度，这也就是现在搜索引擎覆盖率不高的原因，因此 信息抓取模块也就自然而然成了搜索引擎中至关重要的一个部分，执行 这一功能的也就是人们平时常说的网络蜘蛛，即网络爬虫( c r a w l e r 、 s p i d e r 程序) 。 2 1 1 网络蜘蛛原理 网络蜘蛛可自动在互联网上进行搜索，对所有发现的网站和网页进 行标记。它从一个简单的w e b 页面上开始执行，然后通过其超链接再访 问其他页面，如此反复，理论上可以扫描互联网上的所有页面。网络蜘 蛛抓取网页主要有两种策略：深度优先搜索策略和广度优先搜索策略。 ( 1 ) 深度优先搜索策略 图2 1 深度优先搜索遍历过程 深度优先搜索是早期用的比较广泛的一种策略。它的目的是要达到 被搜索结构的叶结点( 即那些不包含任何超链的h t m l 文件) 。在一个 7 哈尔滨t 程大学硕十学位论文 h t m l 文件中，当一个超链接被选择后，被链接的h t m l 文件将执行深 度优先搜索，即在搜索其余的超链接结果之前必须先完整地搜索单独的 一条链。深度优先搜索沿着h t m l 文件上的超链接走到不能再深入为 止，然后返回到某一个h t m l 文件，再继续选择该h t m l 文件中的其 他超链接。当不再有其他超链接可选择时，说明搜索己经结束。深度优 先搜索的优点是能遍历一个节尼b 站点或深层嵌套的文档集合；缺点是 由于w e b 结构相当深，有可能造成一旦进去再也出不来的情况发生【7 】。 而且从我们亲身体验到的经历来看，当深度查询到一定程序后得到的信 息往往都是与我们想要的内容关系不大或者毫无关系，网页信息之间是 互相连接的，所以网页信息我们可以用一张有向图来表示，如图2 1 所 示就是深度优先过程。图中1 、2 等节点代表网页信息文件，节点被访问 的顺序是l 、2 、4 、5 、3 、6 。 ( 2 ) 广度搜索优先策略 还是把网页信息文件当作有向图来处理，广度优先搜索是假设从图中某 个定点a 出发，在访问了a 之后访问a 的各个未被访问过的邻接点，并使 图2 2 广度优先搜索遍历过程 “先被访问的定点的邻接点 先于“后被访问的定点的邻接点 被访问，直 至图中所有已被访问的定点的邻接点都被访问到。若此时还有未被访问的顶 8 哈尔滨1 二程大学硕士学位论文 点，则另选图中的一个未被访问的顶点作为起点，重复上述过程，直至图中 所有的顶点都被访问到为止。如图2 2 所示就是广度搜索遍历的过程，节点 被访问的顺序是l 、2 、3 、4 、5 、6 。 2 1 2 网络蜘蛛工作过程 s p i d e r 程序在编写是可以采用递归过程和非递归过程，递归过程要反复 的调用函数本身，在调用时就得要使用同一个堆栈。每次递归都要把内容压 入堆栈，所以当程序运行很多次以后堆栈会变得很大，可能会耗尽整个堆栈 内存和导致程序终止。而且递归还有多线程不兼容等问题，因此，在编写 s p i d e r 程序时一般都会采用非递归方式，这种方式下会采用四个队列。 ( 1 ) 等待队列，在这个队列中，在这个队列中，u r l 等待被s p i d e r 程序处理。新发现的u r l 被加入到这个队列中。 ( 2 ) 处理队列，当s p i d e r 程序开始处理u r l 时，它们被传送到这一队 列重要的是同一个u r l 不能被多次处理，因为这是浪费的，当一个u r l 被 处理后，它被移送到错误队列或者完成队列。 ( 3 ) 错误队列，如果在下载网页时发生错误，它的u r l 将被加入到这 一队列中去。不再移入其他队列，一旦被移入到错误队列后，s p i d e r 程序将 不会再对它做进一步处理。 ( 4 ) 完成队列，如果下载时网页文件没发生错误，该u r l 将加入到完 图2 3u r l 状态流程图 成队列，该u r l 到达这一队列后不再移入其他队列【3 l 。 在同一个时间同一个u r l 只能在一种队列中，如图2 3 所示给处理队列 9 哈 之间的关联关系。 2 2 网页信息处理 搜索引擎处理的是大量的数据，大型的搜索引擎都是在处理着上千亿个 网页的数据量，但却要保证在小于一秒的时间内返回用户查询的结果，为了 保证那么高的效率，这就关系到了搜索引擎的核心技术一索引文件。索引文件 是在数据区之外建立起来的能够指示逻辑记录和物理记录之间一一对应关系 的文件，而l u c e n e 采用的倒排索引方式能保证搜索引擎的高效。 2 2 1iu c e n e 简介 l u c e n e 是本文的核心开发工具包。l u c e n e 不是个完整的搜索引擎，它是 个高性能的、可扩展的信息检索工具，你可以把它融入到应用程序中以增加 索引和搜索功能。l u c e n e 是一个纯j a v a 实现的成熟的( 后来有了其他语言的 版本) 、自由开源的软件项目；它是备受程序员欢迎的开源组织a p a c h e j a k a r t a t g l t , o j 的成员项目，l u c e n e 提供了一套简单确十分强大的核心a p i ，在使 用它们时并不需要用户对全文索引和搜索的机制有很深的了解。因此现在很 多项目都是基于l u c e n e 基础上来研究的。l u c e n e 的原作者是d o u gc u t t i n g ， 他是一位资深全文检索专家，曾经是v - t w i n 搜索引擎的主要开发者，后在 e x c i t e 担任高级系统构架师，目前从事一些i n t e m e t 底层架构的研究。l u c e n e 的发展很快，一直在不断完善着它的功能，也更新了好几个版本，到本文研 究时已经发布了2 4 1 版本。也一直有越来越多的人在基于l u c e n e 的基础上 在做开发研究和改进，如李颖等设计实现了基于l u c e n e 的中文分词方法1 ； 索红光等针对中文检索的l u c e n e 作了改进策略 1 2 1 ；管建和等通过研究l u c e n e 全文检索技术设计与实现了校园网搜索引擎( 1 3 1 ，本文也将参考这些学者所做 出的成果来进行进一步的研究和改进。 2 2 2i u c e n e 索引文件的建立 l u c e n e 不能对网页文件直接索引 1 4 l ( i s l ，如h t m l 格式文件等，而只能处 理文本字符流，因此要先将其所有爬取到的文件转化为文本文件的格式。当 这一部处理完了后，先创建若干个域的d o c u m e n t 对象，然后调用l u c e n e 提 1 0 哈尔滨t 程大学硕士学何论文 供的i n d e x w r i t e r 的a d d d o c u m e n t 方法，将数据传送给l u c e n e 来进行索引操作， 在对数据进行索引处理时，l u c e n e 会首先分析( a n l a y z e r ) 数据使之更加适合被 索引。分析数据时，先将文本数据切分成一些大块或者语汇单元( t o k e n s ) ， 然后对它们执行一些可选的操作；例如在索引之前对其中的英文字母转化为 小写，使得搜索对大小写不敏感；或者根据所要建立的搜索引擎的特点过滤 掉一些无用的词汇，如：“的 、“吗 等。在完成分析后将数据写入索引，此 时保存数据时的方式就是前面本文提到的倒排索引。在进行关键字快速查询 时，这种数据结构能够有效地利用磁盘空间。它把从文档中抽取出来的语汇 单元看作是查找关键字，而不是把文档作为中心实体。例如，当我要查询“学 校”这个词时，查询时将根据关键字所在的文档返回“哪些文档中包含这个 单词的形式 将结果返回给用户。如下就是实现这一过程的关键代码。 i n d e x w r i t e rw r i t e r = n e wi n d e x w r i t e r ( i n d e x _ s t o r e _ p a t h ，a n a l y z e r , t r u e ) ； d o c u m e n td o c = n e wd o c u m e n t 0 ； f i e l df i e l d = n e w f i e l d ( ”c o n t e n t ”， c o n t e n t ，f i e l d s t o r e y e s ， f i e l d i n d e x t o k e n i z e d ) ； d o c a d d ( f i e l d ) ； 其中的f i e l d 就是代表一个域，可以根据需要生成若干个域，在添加到索 引文件后仍可继续对索引文件进行优化。如图2 4 所示为索引结构图。 图2 4 索引结构图 l l 哈尔滨t 程大学硕+ 学何论文 2 2 3iu c e n e 索引文件格式 2 2 3 1 多文件索引结构 l u c e n e 可选择索引的结构，当对其进行多文件索引时得到的是s e g m e n t s 、 f n m 、f d x 、f d t 、t i i 、t i s 、d e l e t a b l e 格式文件。s e g m e n t s 代表的是一个完整 的索引段，一个索引中通常会含有多个s e g m e n t s ；f n m 格式的文件包含了 d o c u m e n t 中所有域名称，如上节列出的代码中就包含一个名为“c o n t e n t 的 域；f d x 和f d t 格式文件，这两类文件是综合使用的文件，其中f d t 文件用于 存储具有s t o r e y e s 属性的f i e l d 的数据，上节列出的代码中“c o n t e n t ”域就 是以这种方式存储的，而f d x 文件则是一个索引，用于存储d o c u m e n t 在f d t 中的位置；t i i 和t i s 格式文件，t i s 文件用于存储分词后的词条( t e r m ) ，而t i i 就是它的索引文件，它标明了每个t i s 文件中的词条位置；d e l e t a b l e 的功能则 类似于w i n d o w s 的回收站一样，所有的文档在被删除后，会首先在d e l e t a b l e 文件中留下一个记录，要真正删除时，才将索引除去。 2 2 3 2 复合索引结构 多文件索引结构有个弊端，就是当要索引的文件数量很大时，索引目录 中也会产生大量的文件，所以并不适合存在大量索引且索引包含大量域的环 境下工作复合索引生成c f s 、s e g m e n t s 、d e l e t a b l e 三种文件，因此可以看出， 当进行复合索引后要查询关键字时只要从索引文件中打开两个文件，从而会 减少系统的资源消耗。要采用这种方式进行索引只要在初始化一个 i n d e x w r i t e r 对象后，使用s e t u s e c o m p o u n d f i l e ( b o o l e a n ) 方法，将u s e c o m p o u n d f i l e 属性设置为t r u e 就可以了( 1 u c e n e 默认的是此方式) 。 2 3 信息检索模型 在对数据文件进行索引构造后就涉及到检索问题了，