（农业机械化工程专业论文）invisible+web信息检索方法研究.pdf

西南人学硕卜学位论殳=摘璎 i n v i s i b l ew e b 信息检索方法研究 农业机械化工程专业硕士研究生刘婧 指导老师袁可副教授 摘要 随着互联网上的信息量迅猛增加，搜索引擎在人们使用网络的过程中扮演着越来越重要 的角色，儿乎所有上网的人都会用剑搜索引擎来查找信息。同时各搜索引擎在不断地发展， 收录的网页也越米越多。但这些搜索引擎并1 f 可以搜剑互联网所有的网页，网上仍有一大部 分页面普通搜索引擎搜索不到，这些网页就是“i n v i s i b l ew 曲”，即看不见的网页。据调奄研 究的结果可知，i n v i s i b l ew e b 中蕴含着大量有价值的信息，可是它们却不能被当前土流搜索引 擎搜索到。因此，研究能够对i n v i s i b l ew e b 进行搜索的技术和方法就显得很有必要且很有价值。 传统的面向i n v i s i b l ew e b 信息的检索方式主要有两人类：目录检索和自动检索。在国外 目录检索工具发展已经比较成熟，但这种检索方式奄全率低，检索速度慢，不能满足用户的 查询需要。而自动检索是真止地对i n v i s i b l ew e b 进行检索，它可以将用户的检索请求同时推 送到多个相关网络数据库中进行检索，而后把结果返刚给j j 户。所以自动检索逐渐成为该领 域研究的热点。 本文首先深入分析了i n v i s i b l ew e b 产生的原因及存在的主要类型，并论述了这种信息资 源的特点；然后分析了传统的检索方式检索i n v i s i b l ew e b 存在的问题，提出将分布式技术应 用丁i n v i s i b l ew e b 检索中，可以增强自动检索工具的检索能力。深入分析了分布式信息检索 的基本原理和体系结构，提出了采用分布式检索方式检索i n v i s i b l ew e b 信息的关键步骤，即： 数据集合划分、数据集合选择、结果合并。厦点研究了这三个关键步骤中的算法：提出一种 基于自动聚类的数据集合划分算法1 b c p a 算法，实验表明该算法具有很好的效果；分析 了四种典型的数据集合选择方法，并对各种算法进行了综合评价，最后提出了一种改进的数 据集合选择方法，即将d t f 与查洵驱动的选择方法相结合的方法；对经典的c o r i 算法雨i 新 提出的结果合了f ：算法一同门分析与选择下载相结合的h y b r i d 算法的基本原理进行了讨论， 并通过实验证明h v b r i d 算法的性能要优于c o r i 算法。 关键词：i n v i s i b i ew e b 分布式检索数据集合划分数据集合选择 结果合并 l 两南人学顺l j 学位论爻a b s t r a c t a bs t r a c t w i t ht h ed r a s t i c a l l yi n c r e a s i n go ft h ei n f o r m a t i o ni nt h ei n t e m e t ，s e a r c he n g i n e s h a v ep l a y e dam o r ea n dm o r ei m p o r t a n tr o l ei nt h ec o u r s eo fu s i n gt h ei n t e r n e t m e a n w h i l e ，s e a r c he n g i n e sa r ed e v e l o p i n gc o n s t a n t l y a n dw e bp a g e st h a tt h e yi n c l u d e a r eb e c o m i n gm o r ea n dm o r e h o w e v e r , t h e s es e a r c he n g i n e sc a n n o ts e a r c ha l lp a g e so f t h ei n t e r n e t ，a n dt h e r ea r es t i l lag r e a tm a n yo fp a g e st h a tc a n tb es e a r c h e db yg e n e r a l s e a r c he n g i n e s w h i c ha r ec a l l e d “i n v i s i b l ew e b ”i ti ss t u d i e dt h a tt h e r ea r eg r e a t a m o u n t so fv a l u a b l ei n f o r m a t i o ni nt h ei n v i s i b l ew e b ，w h i c hc a n n o tb es e a r c h e db y p r e s e n ts e a r c he n g i n e s t h e r e f o r e ，r e s e a r c ho nt e c h n o l o g i e sa n dm e t h o d st h a tc a l l s e a r c hi n v i s i b l ew e bb e c o m e si n d i s p e n s a b l ea n dv a l u a b l e t h et r a d i t i o n a lr e t r i e v a lm e t h o d so fi n v i s i b l ew e bm a i n l yf a l li n t ot w ok i n d s ： c a t e g o r yr e t r i e v a la n da u t o m a t i cr e t r i e v a l i nt h ef o r e i g nc o u n t r i e sc a t e g o r yr e t r i e v a l t o o l sh a v ed e v e l o p e dr e l a t i v e l ym a t u r e b u tt h i sr e t r i e v a lm e t h o dh a sd i s a d v a n t a g e s ， s u c ha sl o wr e c a l lr a t i oa n ds l o wr e t r i e v a ls p e e d ，a n di tc a n tm e e tu s e r s r e t r i e v i n g r e q u i r e m e n t s a u t o m a t i cr e t r i e v a lm e t h o di st r u l yr e t r i e v i n gi n v i s i b l ew e b ，a n di ts e n d s u s e r s r e t r i e v i n gr e q u i r e m e n t st om a n yr e l a t i v ew e bd a t a b a s e sa tt h es a m et i m e ，t h e n r e t u r n st h eu l t i m a t er e s u l t st ou s e r s c o n s e q u e n t l y , a u t o m a t i cr e t r i e v a lm e t h o dh a s g r a d u a l l yb e c o m et h er e s e a r c hi s s u ei nt h i sf i e l d t h i sp a p e rf i r s ta n a l y z e st h ee m e r g e n c ea n dm a j o rt y p e so fi n v i s i b l ew e b ，a n d e x p o u n d sc h a r a c t e r i s t i c so ft h i si n f o r m a t i o nr e s o u r c e t h e ni td i s c u s s e sm a i np r o b l e m s t h a te x i s ti nt h et r a d i t i o n a lr e t r i e v a lm e t h o d s ，a n dp r o p o s e st h a ta p p l y i n gt h ed i s t r i b u t e d t e c h n o l o g yt oi n v i s i b l ew e br e t r i e v a lc a ne n h a n c et h er e t r i e v a la b il i t yo fa u t o m a t i c r e t r i e v a lt o o l s t h e ni ta n a ly z e st h eb a s i cp r i n c i p l ea n da r c h i t e c t u r eo fd i s t r i b u t e d i n f o r m a t i o nr e t r i e v a l ，a n dp o i n t so u t3k e yp r o c e d u r e si nd i s t r i b u t e dr e t r i e v i n gi n v i s i b l e w e b ：d a t ac o l l e c t i o np a r t i t i o n ，d a t ac o l l e c t i o ns e l e c t i o n ，a n dr e s u l t sm e r g i n g i t e s p e c i a l l ye m p h a s i z e s o n a l g o r i t h m s i nt h e s e3 k e yp r o c e d u r e s ：p r e s e n t a c l u s t e r i n g - b a s e dd a t ac o l l e c t i o np a r t i t i o na l g o r i t h m 一一c b c p aa l g o r i t h m ，a n d e x p e r i m e n t ss h o wt h a tt h i sa l g o r i t h mi se f f e c t i v e t h e ni ti n t r o d u c e sf o u rt y p i c a ld a t a c o l l e c t i o ns e l e c t i o nm e t h o d s ，a n de v a l u a t e sa l lt h em e t h o d sc o m p r e h e n s i v e l y , f i n a l l y p r o p o s e sa ni m p r o v i n gm e t h o d - - - - c o m b i n i n gd t fa n dq u e r y d r i v e ns e l e c t i o n i t d i s c u s s e st h em a i np r i n c i p l eo ft w or e s u l t sm e r g i n gm e t h o d s 1 h ew e l l k n o wm e t h o d c o r ia n dt h en e wp r o p o s e dh y b r i da l g o r i t h mt h a tc o m b i n e sr e g r e s s i o na n a l y s i sa n d n 两南人学顾l 学f t 泠艾a b s t r a c t s e l e c t i v ed o w n l o a d ，a n de x p e r i m e n t ss h o wt h a tt h en e wh y b r i da l g o r i t h mg a i n sb e t t e r p e r f o r m a n c et h a nc o r i k e y w o r d s ：i n v i s i b l ew e b ，d i s t r i b u t e dr e t r i e v a l ，d a t ac o l l e c t i o np a r t i t i o n ，d a t a c o l l e c t i o ns e l e c t i o n ，r e s u l t sm e r g i n g 独创性声明 学位论文题目：五速i 壶丝 逝6 篮星遂杰左叁鸳鱼 本人提交的学位论文是在导师指导下进行的研究工作及取得的 研究成果。论文中引用他人已经发表或出版过的研究成果，文中已加 了特别标注。对本研究及学位论文撰写曾做出贡献的老师、朋友、同 仁在文中作了明确说明并表示衷心感i 身j 。 学位论文作者： 到墙 签字日期：2 口。夕年口月2 2 日 学位论文版权使用授权书 本学位论文作者完全了解两南大学有关保留、使用学位沧文的规 定，有权保留并 - - j 国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅。本人授权话南大学研究生院( 筹) 可以将学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书，本论文：口不保密， 口保密期限至年月止) 。 学位论文作者签名： 划葫 签字日期：卯夕年o 司2 日 锄签名：琉可 签字日期：叩年户月眵日 两市人学硕卜学伊论文绪论 第1 章绪论 1 1 研究背景 随着互联网上的信息餐迅猛增加，搜索引擎在人们使刖网络的过程中扮演着越来越重要 的角色，几乎所有上网的人都会片j 到搜索引擎来查找信息，因此对网民们来说，g o o g l e ，y a h o o ， a l t a v i s t a ，白度等搜索引擎已成为人家网上冲浪不可或缺的得力助手。同时各搜索引擎在不断 地发展，收录的网页也越来越多，女l l g o o g l e ，截t k 碧j 2 0 0 6 年底，已经收录了8 0 亿多个网页。但 这些搜索引擎并1 卜可以搜剑且联网上的所有网页，网上仍存在一大部分页丽普通搜索引擎搜 索不剑，比如保存住w e b 数据库中的信息、动态网页等。这些网页就是需要我f l 、j 了解的“i n v i s i b l e w e b ”，即“看不见的网页”。而我们通常所见的能被搜索引擎搜索剑的则是“s u r f a c ew e b ”， 看得见的网页。据调奄研究的结果【l 2 】，可失u l n v i s i b l ew e b 中蕴含着大鼙有价值的信息，可是它 们却不能被当前主流搜索引擎搜索剑。因此，寻找能够对i n v i s i b l ew e b 进行搜索的技术和r 具 就显得很有必要且很有价值。 从目前的研究成果看，面向i n v i s i b l ew e b 的检索方式主要有两大类：目录检索和自动检索 3 - 9 。目录检索是指将i n v i s i b l e w e b 中的信息资源按照学科或土题进行分类组织，用户按照目录 的层次结构奄找需要的信息。而自动检索是类似于搜索引擎的检索方式，用户使用此类- t 具 时，键人关键词后得到的结果不是站点列表，而是直接的相关资料。由于目录检索是基丁人 j ：搜集的资源，查询结果数量太少，且按目录查找速度太慢，不能满足查询的需要；而自动 检索则是真正地对i n v i s i b l ew e b 进行检索，它通过机器搜集了大量的i n v i s i b l ew e b 资源，并将 用户的检索请求同时推送到多个相关网络数据库中进行检索，而后把结果返回给用户，检索 的商全率和效率很高。而且在绝大多数情况下，用户希望i n v i s i b l ew e b 检索- 丁具可以直接给出 答案，而自动检索恰好能够满足j h 户的这一需求。所以自动检索工具比目录检索j ：具更有发 展潜力，而自动检索方式也逐渐成为该领域的研究重点。 分布式信息检索( d i s t r i b u t e di n f o r m a t i o nr e t r i e v a l ) 是信息检索的一种类型，它是针对网络 环境f 信息分布式存储而产生的一种检索形式，常见的自跨库、跨服务器检索。分布式信息 检索是建立在分布式处理系统之上的用户检索服务，是由检索代理程序将用户的检索任务同 时提交给网络上的多个主机，由位于这些主机上的检索程序分别独立检索并将检索结果返同 到检索代理程序，经过整理后显示给用户。可! ! i ，它的检索原理以及涉及的技术方法与自动 检索有相通之处，可以考虑将分布式信息检索应川于i n v i s i b l ew e b 检索中去，以增强自动检 索一l ：具的榆索能力。 两南尺学俩ii 。学位论迂绪论 1 2 研究现状 自1 9 9 9 年开始，国外针对i n v i s i b l e w e b 的研究相当热烈，成果众多。目录检索方面，国 外已经出现了不少比较成熟的目录检索 ：具。其中具有代表性的有：d i r e c ts e a r c h ，t h ei n v i s i b l e w e bd i r e c t o r y ，i n v i s i b l ew 曲c o m i o t q 。而自动检索方面的研究才刚刚开始，成熟的系统还很 少，代表性的只有b r i g h t p l a n e t 公司的c o m p l e t e p l a n e t l i n t e l l i s e e k 公司的b u l l se y e 。 c o m p l e t e p l a n e t - - 开始也是一个i n v i s i b l ew e b 资源目录，后来开发t 3 l e x i b o t 检索l ：具，能 根据刚户的查询请求选择6 0 0 个相关的i n v i s i b l ew e b 资源进行搜索并返同结果。l e x i b o t 后来又 升级至l l d e e p q u e r ym a n a g e r ( d q m ) 检索平台。d q m 不是一个搜索引擎，而是一个自动搜索 平台，它能够同时检索多个搜索引擎、网站目录希l l n v i s i b l ew e b 数据库。c o m p l e t e p l a n e t 在 i n v i s i b l ew e b 检索方面的研究是在前列的，不过由于是一个商业系统，没有公布相关研究成果， 而且其检索的效率和准确率都有待提高。 分布式信息检索的重点是将检索需求同时提交给网络上的多个土机，由位丁这些土机上 的检索程序分别独立检索并将检索结果整理后返同给用户。它的检索原理和涉及的技术方法 与自动检索有相通之处，冈此有必要了解其研究成果。针对分布式检索方法，近些年国外一 些学者已经进行了广泛的研究，取得了一定的进展。p a n a g i o t i sgi p e i r o t i s a 和l u i sg r a v a n o a 针对h i d d e nw e b 分布式检索中的数据库选择问题，提出了一种通过获取内容摘要和利刚数据 库的层次分类米进行选择的算法，实验结果表明这种基于内容摘要的选择算法能够更准确的 选择相关数据库【1 2 1 。f a b i oc r e s t a n i s h e n g l i 、u 针对分布式信息检索中存在的来自不同数据库 的检索结果的合并问题，对很多人提出的解决这个问题的聚类分析方法进行了研究验证，实 验结果表明在高度异构的分布式检索中采川聚类分析可以有效地向用户返同检索结果【1 3 i 。 相比之下，国内对i n v i s i b l ew e b 检索方面的理论研究起步较晚，相关论述也较少。但近 几年已引起了一些学者的关注。而在分布式信息检索方面已经有了一些研究成果。比如，文 献【1 4 】姚树宇，赵少东在分析传统搜索引擎技术存在不足的基础上，指出采用分布式搜索能够 提高检索效率和能力，并提出了一种基于分布式技术的搜索引擎的基本框架【l 引。文献【1 5 】手文 学，张博锋，周传飞，方爱国，郭晓燕等分析了传统分布式数据库访问方式的缺点，提出了 基于移动a g e n t 的分布式检索技术，实例证明能够提高分布式数据库检索效率f l 引。文献 1 6 】 李培，武丽辉研究了分布式检索中的信息库选择的几种方法，并对各种方法进行了评价，最 后指出采用合理的信息库选择方法可以促进分布式信息检索水平的进一步提高【1 6 】。 以上的这些研究成果都为i n v i s i b l ew 曲信息检索方法的研究提供了有益的启发。 1 3 研究目的和意义 i n v i s i b l ew e b 信息资源内容丰富、专业性较强，质精比一般网络资源( s u r f a c ew e b ) 好， 2 两南人学硐i 学f t 论史 绪论 而且随着互联网的发展，网上将会出现更多的不能被普通的搜索引擎奄找到的i n v i s i b l ew e b 资 源。所以如何检索剑这些有价值、权威的信息就成为一个值得研究的问题。 传统的检索i n v i s i b l ew e b 信息的方式主要是目录检索，这种检索方式的检索效率低、且查 询结果数量太少，不能满足用户查询的需要，而自动检索方式可以有效地解决这个问题。同 时，分布式信息检索的基本原理和涉及的技术方法与臼动检索有相通之处，冈而采用分布式 信息检索技术能够增强i n v i s i b l ew e b 自动检索： 具的检索能力。分布式检索i n v i s i b l ew e b , y , 息 土要涉及三个关键问题需要研究：数据集合划分、数据集合选择年结果合并。研究这三个关 键问题的改进算法，提高各算法的实现效率，对改善最终的检索质量和检索效率有着重要的 意义。 综上所述，我们希望通过本课题的研究，对i n v i s i b l ew e b 信息及如何利 h 分布式检索技术 对i n v i s i b l ew e b 进行有效检索有一个全面的认识和理解，以寻求能够提高i n v i s i b l ew e b 检索效 率的解决方法，最终实现对这种高质量信息的开发利用。 1 4 主要研究内容 本文的主要研究内容： ( 1 ) 分析了i n v i s i b l ew e b 形成的原因、定义及存在的类型，并论述了这种信息资源的特 点。 ( 2 ) 探讨了分布式信息检索的基本原理及其体系结构，并提出了针对i n v i s i b l ew e b 信息 检索的分布式检索过程。 ( 3 ) 深入研究了i n v i s i b l ew e b 分布式检索方法中的三个关键步骤：数据集合划分、数据 集合选择和结果合并，对各关键步骤中涉及的算法问题进行了分析研究。 ( 4 ) 对三个关键步骤设计的算法问题，在总结已有成果的基础上提出了实用高效的实现 方法。数据集合划分方面，提出了一种基于自动聚类的数据集合划分方法( c b c p a 算法) ，并 进行了实验验证，结果表明该算法能够取得很好的划分效果；数据集合选择方面，提出了一 种改进的数据集合选择方法，即将d t f 与查询驱动的选择方法相结合的方法；结果合并方面， 对经典的c o r l 算法与新近提出h y b d 算法的性能进行了实验验证，结果表明在不同的实验 环境下，h v b r i d 算法的性能都要优t - c o r i 算法。 1 5 论文组织结构 本文对i n v i s i b l ew e b 信息检索方法展开研究，重点研究了如何利川分布式信息检索方法 检索i n v i s i b l ew e b 信息。本文的主要结构如下： 第1 章为绪论，说明了本文的研究背景、研究目的和意义，着重分析了目前i n v i s i b l ew e b 3 两南人学硕l 学f t 论逻 绪论 信息检索方法在国内外的研究现状，并阐述了本文研究的主要内容。 第2 章对i n v i s i b l ew e b 进行概述，讨论了i n v i s i b l ew e b 形成的原因、定义及类璎，分析 了i n v i s i b l ew e b 的特点，说明研究高效检索i n v i s i b l ew e b 方法的必要性。 第3 章研究了分布式信息检索的基本原理，在分析分布式信息检索的体系结构的基础上， 提出了针对i n v i s i b l ew e b 信息的分布式检索的关键步骤：数据集合划分、数据集合选择和结 果合并。 第4 章首先介绍了数据集合划分的相关研究，然后提出了一种基于自动聚类的数据集合 划分的方法，从而把相关性高的网页数据聚集住少数子集中，捉高分布式检索的效率。最后 通过实验对所提出的算法进行了验证分析。 第5 章首先对数据集合选择的基本思想进行简要介绍，然后讨论了目前儿种典艰的数据 集合选择方法，对各种方法的效果进行了综合评价，最后提出一种改进的数据集合选择方法， 即将d t f 与查询驱动的选择方法相结合的方法。 第6 章对两种重要的奄询结果合，f 算法，即经典的c o r i 算法与新近提出的同门分析与选 择下载相结合的h y b d 算法的基本原理进行了讨论研究，然后通过实验对这两种算法的性能 进行了深入的比较分析。 第7 章对本文的j 二作做了回顾和总结，并对进一步工作进行了展望。 4 两南人，硕卜学位论文lnxisiblc w e b 镢述 第2 章i n v i s i b l ew e b 概述 本章主要讨论了i n v i s i b l ew e b 形成的原因，介绍了i n v i s i b l ew 曲的定义及其存在的主要 类犁，并分析了i n v i s i b l ew e b 的特点，说明研究高效检索i n v i s i b l ew e b 方法的必要性。 2 1i n v i s i b l ew e b 形成的原因 i n v i s i b l ew e b 的“不可见”是指这类资源未被一般搜索引擎的索引库所收录，用户通过一 股搜索引擎无法检索到这些信息。形成i n v i s i b l ew e b 的原冈主要有以下两个方面。 ( 1 ) 技术障碍 传统的搜索引擎爬虫主要是通过跟踪网页上的超级链接来提取新的u r l ，如此循环往复。 但爬虫无法自动进行“输入”动作，更没彳f 思考分析能力。这点就造成了如+ 卜两类资源不可 见： 网络数据库资源。互联网上存在许多数据库资源，其中很大一部分可以免费获取，例 如美国专利商标局的网上专利检索数据库是完全免费的。而网络数据库资源的组织方式正是 以数据库为后台、动态网页技术与数据库技术相结合的方式。用户在网络数据库检索页面上 输入检索词，获得的页面不是预先存在的静态网页，而是针对用户此次的检索词和其他一些 检索限制条件而动态生成的网页，即动态网页。爬虫无法进行“输入检索词”的动作，自然 就访问不了后台数据库。 需注册的站点。相当一部分站点需要用户注册，分为有偿注册和免费注册两种。用户 要进入站点，获取站点内容必须取得用户名和密码。对丁搜索引擎爬虫来说，不管是有偿的 还是免费的，它都无法进入。 ( 2 ) 搜索引擎对网络爬虫的访问限制 搜索引擎一般只收录h t m l 网页文件，而对丁 j j 户不经常检索的文件格式，如p d f 、e x e 、 f l a s h 文什等不加收录。h t m l 是且联网上最基本的通用语言，搜索引擎爬虫最擅长处理h t m l 语言写成的网页文件。在h t m l 中可以设置超级链接链接其他类型的文件，比如p d f 文档。 处理其他类型的文件在技术上没有很人的难题，但搜索引擎开发商出于种种考虑，一般将之 排除在外。维持一个一般搜索引擎的运营相当昂贵，这可能是最大的原因。不过近两年来已 有一些搜索引擎正在努力扩展和完善其检索服务，例如g o o g l e ，现在可以通过它检索图片、 p d f 、w o r d 、p o w e r p o i n t 等多种格式的文档。 对丁基丁脚本语言的网页，如果其u r l 中含有“? ”，爬虫通常放弃对该类网页的访问。 这是冈为爬虫住访问此类网页时，有可能陷入恶意的“陷阱”程序当中，导致爬虫陷入夕e 循 环，影响搜索引擎的l l ：常运转。冈此，搜索引擎一股限制爬虫访n d 此类网页。 5 两钶，、硕f 。 f ? ，沦艾l n x 。i s i b l ew e b 慨述 2 2i n v i s i b l ew e b 的定义和类型 i n v i s i b l e w e b ( 看不见的网络) ，义n l h i d d e n w e b ( 隐藏网络) 或d e e p w e b ( 深网) ， 它是一个与s u r f a c ew e b ( 表层网络) 相对应的概念。这一概念最初由d r j i l le i i s w o r t h 于1 9 9 4 年提i 【l - q ，是指那些由普通搜索引擎难以发现其信息内容的w c b 页面。2 0 0 1 年，c h r i s t s h e r m a n 、g a r yp r i c e 对i n v i s i b l ew e b 定义为：虽然通过互联网可以获取，但普通搜索引擎由 于受技术限制而不能或不作索引的那些文本页、文什或其它通常是高质量、权威的信息1 8 i 。 根据i n v i s i b l ew e b 形成的原闪，可以分为以b j t , 类1 1 9 1 ： ( 1 ) 来被链接的网页。没有被任何其他网页链接，即孤立网页。这是i n v i s i b l ew e b 的基 本组成部分。 ( 2 ) 动态生成的网页。由c g i 、a s p 、j a v a s c r i p t 等专j 制作动态网页的脚本语言所编写 的网页或者u r l 中含“? ”的动态网页。如b b s 上发布的动态网页。 ( 3 ) 网上可检索的数据库( s e a r c h a b l ed a t ab a s e 。s d b ) 。s d b 有两种类型：一是可自由 获取的公共数据库，如政府数据库、图书馆的公共目录查询系统等；二是订阅或者付费的数 据库，如e b s c o 、o v i d 和m e d l i n e 等。 ( 4 ) 实时信息。如最新新闻、股票价格、天气信息、航班信息等。冈其变化快，数据量 大，搜索引擎多不予收集。 ( 5 ) 部分1 eh t m l 格式文件。随着技术的发展，现在有些搜索引擎可以索引p d f 和 w o r d 文件以及f l a s h 文件。但对于执行科序、压缩文件、流媒体等类型的文件仍朱予索引。 ( 6 ) 其它难以搜索的内容。有些网站出于版权和隐私等方面的考虑，会使用“r o b o t s t x t ” 协议或者其它方式拒绝爬虫程序访问。搜索引擎搜索任何的信息都需要耗费资源。从成本角 度考虑，人多数搜索引擎对s p i d e r 程序的爬行深度和网页的人小都进行了限制，对丁过深或 过人的网页不予索引。 由上述分类可以看山，i n v i s i b l e w e b 类型多样，如果能对各种i n v i s i b l e w e b 都能自动搜索， 是最理想的情况。然而，一方面网上可检索的数据库包含的信息内容数量最多且价值极高； 另一方面，可检索的数据库由于有搜索页面作为入口，较容易被自动搜索。冈此，本文研究 的i n v i s i b l ew e b 主要是指那些隐藏在可检索的数据库中的信息资源。 2 3i n v i s i b l ew e b 的特点 2 0 0 1 年b r i g h tp l a n e t 公司曾针对i n v i s i b l ew e b 作过一个详细的调奄，并将其调查自皮书 发布分互联网站点上。该白皮 5 中所称的d e e pw 曲即i n v i s i b l ew 曲。以卜是文中提剑的儿点 调查发现1 2 0 j ： d e e pw e b 上资源的数鼍是w w w 上资源数量的4 0 0 5 0 0 倍； 6 两南人学砸i 学位论迂i n 、i s i b l ew e b 慨述 目前存在的d e e pw e b 站点超过2 0 0 0 0 0 个： 最- 人型d e e pw e b 站点的6 0 所包含的资源数量人约有7 5 0 g b ，已是s u r f a c ew e b 的 5 0 倍； d e e pw e b 站点的月访问量是一般站点的1 5 0 ，并且更经常地被链接，但是典型的 d e e pw e b 站点都不太有名； d e e pw 曲是互联网上最人、发展最快的新型信息资源； d e e pw r e b 站点与一般站点比较，所涉及范嗣较小，内容更为精深： d e e pw e b 资源的质量比一般网络资源要好得多： 大约一、i - - d e e p w e b 资源存在丁各种主体明确的网络数据库中； 9 5 的d e e pw e b 资源是免费信息。 这份研究报告的有关数据被广泛引辟i ，但也有人提出质疑。c h r i ss h e r m a n 就卢称b r i g h t p l a n e t 公司测量深网规模的技术存在缺陷，深网可能只有表面网的2 5 0 倍。尽管如此，我们 还是可以肯定：深网的规模远远大丁表面网。2 0 0 4 年7 月，美国伊利诺伊大学计算机科学系 b i nh e 等人发表的一份调研报告指出i 深网已有人约3 0 7 万个站点、4 5 万个数据库和1 2 5 8 万 个界面，并且一直在快速增k ，2 0 0 0 - - 2 0 0 4 年增长了3 7 倍。c h r i ss h e r m a n 和v a r yy r i c e 也 认为深网的增长速度可能已经超过通用检索工具功能的提高速度。 由上述数据我们可以总结出i n v i s i b l ew e b 的主要特点有： ( 1 ) i n v i s i b l ew e b 是一种快速增长的信息资源。 ( 2 ) i n v i s i b l ew e b 包含了大莲有价值的信息。 ( 3 ) i n v i s i b l ew e b 资源内容丰富，涵盖了广泛的学科领域，包括商业、娱乐和政府信息 等。 但目前i n v i s i b l ew e b 的检索土要还是基1 - i n v i s i b l ew e b 资源目录，这种检索方式不仅速 度慢，而且结果不全，效率很低。同时，自动检索_ t 具远远没有发展成熟。冈此，在这种情 况f ，研究i n v i s i b l ew e b 信息的检索方法以发展高效的自动检索上具就显得1 f 常有必要。 2 4 小结 本章概述了i n v i s i b l ew e b 的相关知识：i n v i s i b l ew r e b 的形成原因、i n v i s i b l ew e b 的定义及 其存在的主要类型。紧接着在重点分析i n v i s i b l ew e b 特点的基础上，说明了研究高效检索 i n v i s i b l ew e b 方法的必要性。为后续章。1 了讨论i n v i s i b l ew e b 信息检索的方法做准备。 7 刃i 市人， 顺i 学伊论艾分布，f 膏息伶索研究 第3 章分布式信息检索研究 本章主要研究了分布式信息检索的基本原理及其涉及的关键问题，在分析分布式信息检 索的体系结构的基础上，提出了采用分布式检索方式检索i n v i s i b l e w e b 信息的关键步骤。 3 1 分布式信息检索的基本原理 分布式信息检索( d i s t r i b u t e di n f o r m a t i o nr e t r i e v a l ) 是信息检索的一种类型，它是针对网 络环境下信息分布式存储而产生的种检索形式，常j ! l 的有跨库、跨服务器检索。在网络环 境下，信息资源往往存储在地理上分散的多个不同场地，即结点中。这些结点具有资源建设 的自主性和独立性，如果将其相互连接，形成一个彼此协调的系统，便成为分布式处理系统 ( d i s t r i b u t e d p r o c e s s i n g s y s t e m ) ，其j ：作由系统的后台软件完成。分布式处理是在一个高级操 作系统协调卜共同完成同一任务的处理方式。 分布式信息检索是建立住分布式处理系统之上的蚪j 户检索服务，是由检索代理程序将用 户的检索任务同时提交给网络上的多个主机，由位于这些主机上的检索程序分别独立检索并 将检索结果返回到检索代理程序，经过整理后显示给用户【2 儿。 它的主要特点有：( 1 ) 作业的交互式，这个特点使得分布式信息检索具有了良好的信息 反馈功能和快速的响应功能：( 2 ) 对用户的透明性，现实的信息分布在异构的、地理位置分 散的各个网络主机中，并且信息的储存方式、访问信息的协议等是不同的，这给信息的检索 带了一定的麻烦，然而分布式信息检索技术对用户屏蔽了这些差异，使得用户在利用分布式 信息检索系统进行信息检索时，体会不剑这些差异的存在；( 3 ) 用户界面的友好性，分布式 信息检索系统的用户界面一般都设计的非常友好，这也有利丁信息j j 户与检索系统的交流检 索的智能性，分布式信息检索系统的没计都考虑用户的喜好，提供个性化的服务。 要构建一个分布式信息检索系统，不仅要考虑分布式系统常见的：r ：程性问题，还要对信 息检索所特有的算法问题进行考虑 2 2 1 。关键的 ：程性问题包括：进行搜索协议的定义，以规 范化传输检索查询和结果：涉及一个服务器，这个服务器可以有效地接受查询、对子进科或 线程进行初始化以响应查询请求，并能使用高速缓存技术对任何局部内部数据进行处理；涉 及一个中介器，这个中介器可以向多个力：行搜索服务器提交检索商询，并能将中间结果合并 为最终的 h 户响应结果。算法问题包括：如何在分布式搜索服务器之问分发数据集；如何为 特定检索查询选择合适的服务器( 数据集) ；如何将来自不同服务器的中间结果进行合并。 在当今的网络环境- 卜，信息高度分布，i n t e m e t 上包含了成千上万个集合，从这些集合中 检索相关的信息与传统的信息检索有一些不同。检索分布信息最匝要的点是给定一个奄洵 式，如何找剑一个合适的集合来奁洵。在现实环境中同时处理各式各样的集合很麻烦，每个 集合又有不同的内容。一个即经济义有效的方法是把杏询限制在与奄询有关的集合范围中迸 8 两南人学硕i 学付沦艾 分布信息价索研究 行。最广泛使用的技术是创建选择集合的索引。它包含一组虚拟文本，由集合中单词及其权 值形成的列表组成。当有一个查询式提交时，系统先把它与虚拟文本比较，决定集合中与奄 询式相关的文本数，文本检索就在那些文本数较多的集合中进行。这种方法就是分布式检索， 它可以满足人们检索日益增多且分散存储的网络信息的需求。 3 2 分布式信息检索的体系结构 分布式信息检索的体系结构如图3 1 所示，一个具体的查询过程可以描述如下：用户从客 户端发山查询，经过分发服务器对厢户的夯询进行集合选择，选择最适合的数据集合进行检 索；用户的查询请求被发送到相应的检索服务器上进行并发查询：查询的结果再经过结果合 并过程，把最终的检索结果返同给用户，从而完成一次分布式检索的过程。 图3 1分布式信息检索的体系结构 3 3 分布式检索i n v i s i b l ew e b 的步骤及关键问题 前面章倒是剑，目前基于i n v i s i b l ew e b 的检索主要有目录检索和自动检索两种方式，相 比较而言，自动检索方式可以将检索结果直接返同给f j 户，且查全率和效率都很高，具有明 显的优势。可以看出，研究自动检索方法将为i n v i s i b l ew e b 提供有效的检索途径。而分布式 信息检索的重点是将检索需求同时提交给网络j ：的多个主机，由位于这些主机上的检索程序 分别独立检索并将检索结果整理后返回给用户。它的检索原理和涉及的技术方法与自动检索 有相通之处，因此，本文提出将分布式信息检索技术应用于i n v i s i b l ew e b 检索中玄，以达到 9 两南，：学硕f 孚： 之论逆分布- 府息伶累研_ ! 冗 有效检索i n v i s i b l ew e b 信息资源的目的。 根据分布式信息检索的基本原理，采用分布式检索技术检索i n v i s i b l ew e b 的过祥主要分 为以下儿个步骤【2 引，如图3 2 所示： ( 1 ) 数据集合划分：即将人型数据集合划分成若干数据子集分配给相应的信息检索服务 器； ( 2 ) 数据集合选择：即对于一个给定的奄询式，从集合划分结果的数据子集中选出与之 最相关的数据子集，其目的是在不影响检索效果的前提f ，尽可能的减少要检索的信息集的 数量； ( 3 ) 单数据集合检索； ( 4 ) 查询结果合并：即每个数据集返同的中间结果必须合并成一个单一的结果列表返同 给川户。 、，- ，一，一一一，- - ， 图3 2 分布式检索l n v i s i b i ew e b 的过程 在以上几个步骤中，除了单数据集合检索可以直接实现外，其它步骤都涉及若干算法问 题需要专门研究。这些关键的算法问题分别是：数据集合划分问题、数据集合的自动选择问 题、查询结果合并问题。