（计算机应用技术专业论文）hidden+web搜索技术的研究.pdf

摘要 h i d d e nw e b 中包含了大量结构好、质量高的信息，而且随着信息化建设的加强，这 些信息的数量一直在快速增加。虽然h i d d e nw e b 的信息量变得越来越大，但是现有搜索 引擎对其的搜索能力却非常有限，导致了许多优质信息无法被广泛获取，造成了大量的 信息资源浪费。 分析了h i d d e nw e b 的成因和已有的一些搜索方法，发现这些方法多是从h i d d e nw e b 数据库的分类以及查询接口的集成方面进行研究，在h i d d e nw e b 普适性搜索上存在不 足。为了找到h i d d e nw e b 搜索的普适性方法，主要从解决搜索引擎对h i d d e nw e b 搜索的 局限性出发，对h i d d e nw e b 搜索技术进行了以下两方面的研究： ( 1 ) h i d d e nw e b 查询接口的自动识别。摒弃了传统的采用样本集训练的识别方法， 采用关键词模糊提交，并对返回结果分析处理的方法。识别精度不受训练集的 影响，识别效率大大提高。 ( 2 ) h i d d e nw e b 查询关键词的产生算法。采用样本估计的方法产生候选关键词，并 对样本词频进行了进一步的分析，得出了样本词频公式。使用样本词频公式选 择关键词，可以很好地符合词频走势，使得到的关键词最优。 经过实验证明，论文中提出的接口识别方法和关键词产生算法切实可行，能够准确 识别出h i d d e nw e b 的查询接口，并可以快速地对查询关键词进行优选，为h i d d e nw e b 的普适性搜索奠定了基础。 关键词：h i d d e nw e b ，搜索，接口识别，样本估计，关键词选择 r e s e a r c ho fh i d d e nw e bs e a r c ht e c h n o l o g y l iw e 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 y ：s e n i o re n g i n e e rz h a n g w e n d o n g a b s t r a c t h i d d e nw e bc o n t a i n sl o t so fw e l l s t r u c t u r e da n dh i g h - q u a l i t yi n f o r m a t i o n a l o n gw i t l l t h ee n h a n c e m e n to fi ta p p l i c a t i o n ，t h eq u a n t i t yo f s u c hi n f o r m a t i o nh a sb e e ni n c r e a s i n gf a s t e r a n df a s t e r a l t h o u g ht h eh i d d e nw e bi n f o r m a t i o ni si n c r e a s i n gr a p i d l y ，t h eq u a n t i t yi n d e x e d b yt h es e a r c he n g i n ei sv e r ys m a l l s oi tc a u s e sal o to fi n f o r m a t i o nw a s t e t h i sp a p e rf i r s ta n a l y s e st h eo r i g i no fh i d d e nw e ba n ds e a r c hm e t h o d sm a i n l yo n h i d d e nw e bd a t a b a s ec l a s s i f i c a t i o na n ds e a r c hi n t e r f a c ei n t e g r a t i o n a n dt h e ni no r d e rt of i n d ac o m m o ns e a r c hm e t h o df o rh i d d e nw e b ，t w om a j o rs e a r c h i n gt e c h n o l o g i e sa r es t u d i e d ： ( 1 ) a u t o m a t i ch i d d e nw e bs e a r c hi n t e r f a c er e c o g n i t i o n w i t h o u tu s i n gs a m p l es e t ，o n l y b ys u b m i t t i n gk e y w o r d sa n da n a l y z i n gt h er e s u l t s ，t h em e t h o dc o u l df i n dt h eh i d d e n w e bs e a r c hi n t e r f a c e r a p i d l ya n da c c u r a t e l y ( 2 ) h i d d e nw e bs e a r c hk e y w o r d ss e l e c t i o na l g o r i t h m f i r s tu s i n gs a m p l ee s t i m a t e m e t h o dt of i n dt h es e a r c hk e y w o r d s ，a n dt h e na n a l y z i n gt h ew o r d s f r e q u e n c yi nt h e s a m p l es e tt og e tt h ef o r m u l ao ft h es a m p l ef r e q u e n c y k e y w o r d ss e l e c t e dw i t ht h e f o r m u l ar e f l e c tt h et r e n do ft h e i rf r e q u e n c yi nt h eh i d d e nw e bd a t a b a s e ，s ot h e s e l e c t e d 、v o r d sc o u l db et h eb e s ts e l e c t i o n t h em e t h o do fi n t e r f a c er e c o g n i t i o na n dk e y w o r d ss e l e c t i o na l g o r i t h mi st e s t e db y c e r t a i ne x p e r i m e n t s t h ee x p e r i m e n t sw e l lv a l i d a t eo u rr e s e a r c h k e yw o r d s ：h i d d e nw e b ，s e a r c h i n g ，i n t e r f a c er e c o g n i t i o n ，s a m p l ee s t i m a t e ，k e y w o r d s s e l e c t i o n 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均已在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：主兰是日期：沙矛g 年r 月汀同 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印刷版 和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、借阅和 复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、缩印或其他 复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名：乏坌兰垄 指导教师签名： 驻爻鱼 日期：渺留年j - 月灯同 日期：幼形年厂月z 厂同 中国石油大学( 华东) 硕士学位论文 1 1 论文研究背景及意义 第一章前言 1 1 1研究背景 h i d d e nw e b 也被称为“i n v i s i b l ew e b ”、“d e e pw e b ”。美国互联网专家c h r i ss h e r m a n 和g a r yp r i c e 将h i d d e nw e b 定义为： “在互联网上可获得的但传统的搜索引擎由于技 术限制不能或者经过慎重考虑后不愿意作索引的那些文本网页、文件或其他高质量、权 威的信息【。 随着计算机的普及和计算机网络技术的发展，i n t e m e t 作为一种信息获取的有效渠 道，越来越体现出高效、快速、准确、实时的特点。越来越多的人将i n t e r n e t 作为获取信 息的首选。人们利用搜索引擎搜索网络，以达到快速定位信息的目的。普通的搜索引擎 只搜索公共索引网络p i w ( p u b l i c l yi n d e x a b l ew e b ) 【2 】，而对数量更多的h i d d e nw e b 却无 从下手。 h i d d e nw e b 的信息与p i w 相比质量更好、数量更多【1 1 。h i d d e nw e b 的信息大都存储 在后台数据库中，信息的存储规范统一，结构非常好，适合进行检索。对得到的数据只 需简单的处理就可以作为很好的数据源。大部分的h i d d e nw e b 所包含的信息都是公共信 息，不需要支付额外的费用。据保守计算【3 1 ，h i d d e nw e b 所包含的信息量是p i w 所包含 信息量的4 0 0 5 0 0 倍，全球h i d d e nw e b 总共包含信息7 5 0 0 t b ，而p i w 所包含的信息量仅 为1 9 t b 。如果可以得至l j h i d d e nw e b s 艮少一部分的信息，那也将是相当庞大的。对于我 们这个以信息作为驱动力的时代来说，这毫无疑问是十分具有诱惑力的。 由于h i d d e nw e b 具有很好的特性，许多学者都对其搜索方法进行了探索性研究，但 这些方法都存在着一些问题。 ( 1 ) 由于需要填写表单，所以需要用户事先准备表单数据，这给用户的使用带来 了麻烦。 ( 2 ) 搜索大多只能针对特定领域进行，需要人工帮助，限制条件多。 ( 3 ) 对表单元素的抽取采取全文扫描，逐字匹配，抽取效率不高。 ( 4 ) 由于对以j s p 、a s p 为基础的文件抽取难度很大，在表单元素抽取的过程中大 多只针对h t m l 格式的文件。 为了能有效克服这些问题，本文从研究传统搜索引擎的原理出发，深入分析了 第一章前言 h i d d e nw e b 的特点及产生原因，主要研究了h i d d e nw e b 查询接口的识别方法和表单关键 词选择算法，从理论和实验两方面对接口识别方法和关键词选择算法做了详细的论述。 1 1 2 研究意义 ( 1 ) 通过对基于结构和内容的w e b 分块方法的研究，可以从结构和内容两个方对 w e b 页面进行综合考虑，从而可以准确的提取出w e b 页面的主要内容，特别是对于主 要内容中夹杂着不相关信息的页面，提取效果同样很好。这种方法不但可以有效地识别 并提取出页面中的表单信息，简化h i d d e nw e b 接口识别的难度，而且可以对w e b 挖掘 的页面进行预处理，提高挖掘的效率。 ( 2 ) 通过研究h i d d e nw e b 查询接口识别方法和关键词选择算法，可以自动完成 h i d d e nw e b 查询接口识别，并使用较少样本估计的方法自动选择最优的关键词进行提 交。这样不但省去了用户逐个提交关键词的麻烦，而且对多数h i d d e nw e b 站点普遍适 用，不用对每类h i d d e nw e b 站点都建立特殊的样本词库。 ( 3 ) 如果按上述两种方法对现有搜索引擎做出改造，使其可以识别查询接口并且 可以自动选择关键词，则现有的搜索引擎就不但可以索引普通h t m l 页面，对于提供 查询接口的h i d d e nw e b 也可以进行索引，使搜索引擎对w e b 的覆盖率大大提高。 1 2 国内外研究现状 国外对h i d d e nw e b 的研究已经有1 0 年左右的时间，研究成果既有综述性的介绍，也 有搜索方法的探索性研究。与国外相比，国内的研究起步晚一些，综述性的研究较多。 但是随着对h i d d e nw e b 研究的深入，其价值也越来越受到国内研究者的重视。 1 2 1 国外研究现状 在2 0 0 0 年，b r i g h tp l a n e t 公司针对h i d d e nw e b 的规模和相关性进行了研究，b e r g m a n 【3 】 的报告指出，截止2 0 0 0 年大约有9 6 0 0 0 个提供w e b 查询的站点。但到了2 0 0 4 年4 月，文献 【4 】指出这样的查询站点已经增长到了大约4 5 0 0 0 0 个，增长速度十分迅速。b r i g h tp l a n e t 的研究报告被广泛引用，但是也有人提出了质疑。c h r i ss h e r m a n 就声称b r i g h tp l a n e t 公司 测量h i d d e nw e b 规模的技术存在缺陷【i 】h i d d e nw e b 的规模可能只有表面网络的2 5 0 倍。 h i d d e nw e be x p o s e r ( h i w e ) t 5 l 是s t a n f o r d 大学的一个研究项目。r a g h a v a n 和 g a r c i a m o l i n a 设计了一种可以抽取h i d d e nw e b 内容的c r a w l e r 。在此系统中c r a w l e r 管理 器负责管理搜集过程。它对下载的w e b 页面进行分析，包含表单的页面被送到表单处理 2 中国石油大学( 华东) 硕l 学位论文 器中专门处理。表单处理器先从页面中抽取出表单，再从预先准备好的数据集中选择数 据自动地完成表单的填写，然后将合成的u r l 提交c r a w l e r 管理器去下载相应的结果页 面。由于需要系统自动完成表单填写，所以要求用户事先准备相应的表单数据集。h i w e 只能面向特定的领域使用，而且必须在人工帮助下进行工作。此方法还很难在没有限制 条件的情况下使用。 哥伦比亚大学的p a n a g i o t i sg i p e i r o t i s t 等人在文献【6 】中讨论了自动地将h i d d e nw e b 网页所连接的后台数据库进行分类的方法。它首先使用自动学习技术生成一套基于规则 的分类器( c l a s s i f i e o 。然后将分类器转变成查询u r l ，对后台数据库进行查询，计算查 询结果。他们的算法最后根据查询结果对数据库进行分类。该方法在进行数据库分类前 需要大量的训练数据。 1 2 2 国内研究现状 在文献【7 】中，作者详细介绍了h i d d e nw e b 的成因、分类以及研究意义等内容。文章 从传统搜索引擎的产生和发展历史出发，对h i d d e nw e b 的成因作了很深入的分析，并得 出了h i d d e nw e b 不可见的两个重要原因：技术障碍和搜索引擎对s p i d e r 的访问限制。 在文献【8 】中，作者给出t h i d d e nw e b 表单抽取的t t o e ( t a g - t r e e b a s e do b j e c t e x t r a c t i o n ) 技术。要想自动地从一个网页中将表单及相关说明信息抽取出来，难度很大。 这主要有以下一些原因：在w e b 页面显示时，靠近表单项用来说明表单内容的文本信息， 可能在h t m l 文本结构中是和表单项本身分离的。有些表单项周围根本没有相关的文本 来说明表单内容，而是通过选项本身来说明的。特别是对于整个表单的功能，大多数都 没有文本直接说明。t t o e 技术给解决上述问题提供了一种解决思路：首先将w e b 页面 表示成树型结构，然后再以此树为基础进行表单对象的抽取。整个工作由四个步骤组成： 网页标准化，树结构生成，表单分析，表单对象索引。 文献 9 】提出了一种基于图模型的h i d d e nw e b 数据库采样方法，可以通过查询接口从 w e b 数据库中以增量的方式获取近似随机的样本，通过样本分析对后台数据库进行分 类。文献 1 0 】提出了一种基于词频统计的方法来估算h i d d e nw e b 数据库的规模，通过分 析w e b 数据库查询接口中各个属性之间的相关度，来获取某个属性上的一组随机样本， 并对该属性分别提交由前k 个高频词形成的试探查询，以估算w e b 数据库中记录的总数。 文献【1 1 】提出了一种对w e b 数据库查询结果进行语义标注的方法，可以实现机器对查询 结果的语义识别，提高了查询结果的处理效率。文献 1 2 】提出了一种基于分层模糊集思 3 第一章前占 想的h i d d e nw e b 数据库分类算法，可以对h i d d e nw e b 数据库资源进行更细粒度的划分。 以上四个文献都属于对h i d d e nw e b 后台数据库的研究，包括数据库的自动分类和大小估 计等内容。 文献 1 3 】提出了一种基于语义及统计分析的实体识别机制，能够有效解决h i d d e n w e b 数据集成中数据纠错、消重以及整合等问题。文献 1 4 】提出了一个三分类器的框架， 用于自动识别特定领域的h i d d e nw e b 入口，查询接口得到以后，可以将它们进行集成， 然后将一个统一的接口提供给用户以方便他们查询信息。文献 1 5 提出了一种基于知识 环境变化理论的处理方法，包括h i d d e nw e b 集成环境变化处理模型以及适应h i d d e nw e b 环境变化的动态体系结构和处理算法，可以对大规模h i d d e nw e b 集成的进一步探索和应 用提供参考。以上三个文献属于h i d d e nw e b 集成技术研究，主要是针对不同接口的 h i d d e nw e b 站点，采用接口集成技术，将异构的h i d d e nw e b 查询接口规范化、统一化， 将用户需要多个站点分别查询变为单一接口查询。 1 3 研究主要内容 论文主要研究了两项内容：h i d d e nw e b 查询接口识别和关键词选择算法。 ( 1 ) h i d d e nw e b 查询接口的识别。通过对h i d d e nw e b 查询接口表单从结构和表 现两方面的研究，提出一种h i d d e nw e b 查询接口的表示和识别方法，可以自动找到关 键词的查询接口，即关键词的提交表单，并提取有用信息。可以自动分析出表单的输入 项、提交u r l 等信息。 ( 2 ) 基于样本估计的h i d d e nw e b 查询关键词选择算法的研究。将已查询信息作 为样本，对h i d d e nw e b 后台数据库的关键词覆盖频率进行估计，自动找到覆盖率最优 的候选关键词，使得以该关键词查询的返回结果能最大的覆盖h i d d e nw e b 的数据库， 使用较少的查询，获得最多的返回结果。 1 4 论文的组织结构 第一章是前言，论述了课题的背景和现实意义，然后对国内外研究现状作了分析， 最后对课题的主要研究内容做了说明。 第二章是对传统搜索引擎的概述。包括搜索引擎的般结构和原理，分类等内容。 最后是传统搜索引擎用到的主要技术。 第三章是对h i d d e nw e b 搜索技术相关内容的分析。主要分析了h i d d e nw e b 的成因、 4 中周嵇油大学( 华东) 硕十学位论文 分类，最后对本论文的研究思路和方法做了说明。 第四章主要研究w e b 页面的分块和结构化表示，以及对分块的识别和块内主要信 息的提取。 第五章主要研究了h i d d e nw e b 查询接口的识别方法。包括站点识别，查询入口识 别，返回结果分析等内容。 第六章提出了一种基于样本估计的h i d d e nw e b 关键词选择算法。主要论述了算法 的思路、推导过程，并利用实验验证了算法的有效性。 最后对课题的研究做了全面总结，并提出了下一步的工作打算。 5 第- 二章搜索引擎概述 第二章搜索引擎概述 2 1搜索引擎的工作原理和系统架构 搜索引擎( s e a r c he n g i n e ) t 1 6 1 是指根据一定的策略、运用特定的计算机程序搜集互联 网上的信息，对信息进行组织和处理后，为用户提供检索服务的系统。从使用者的角度 看，搜索引擎提供一个包含搜索框的页面，在搜索框输入关键词，通过浏览器提交给搜 索引擎后，搜索引擎就会返回跟用户输入的内容相关的信息列表。 2 1 1 搜索引擎的工作原理 利用网络蜘蛛( s p i d e r ) 【1 7 】从因特网上自动收集网页信息，将收集到的网页内容交给 索引和检索系统，索引和检索系统通过扫描每一个网页中的每一个词，建立以词为单位 的倒排文档，再根据关键词在每一个网页中出现的频率对包含这些关键词的网页进行排 序，最后输出排序结果，页面生成系统再将结果组装成页面并返回给用户，用户就可以 通过浏览器看到搜索结果了。 2 1 2 搜索引擎的系统架构 图2 1 是一般搜索引擎的系统架构图，其中主要包括搜索器( s p i d e r ，也叫做c r a w l e r ) 、 索引器( i n d e x e r ) 、检索器( s e a r c h e r ) 和用户接口( u i ：u s e ri n t e r f a c e ) 等四个部分，下面对其 各自的功能实现进行分析。 ( 1 ) 搜索器 图2 - 1 搜索引擎架构图 f i 9 2 1 t h ea r c h i t e c t u r eo f s e a r c he n g i n e 6 中国石油人学( 华东) 硕上学位论文 搜索器即网络蜘蛛( s p i d e r ) ，其功能是在互联网中漫游、发现和搜集信息。它通常是 一个计算机程序，同夜不停地运行，尽可能多、尽可能快地搜集各种类型的新信息。搜 索器沿着网页中的超链接( h y p e r l i n k ) ，连续地抓取网页。由于互联网中超链接的应用很 普遍，理论上从一定范围的网页出发，就能搜集到绝大多数的网页。目前有两种搜集信 息的策略【1 8 】：1 ) 从一个起始u r l 集合开始，沿着这些u r l 中的超链接，以宽度优先、 深度优先或启发式方式循环地在互联网中发现信息。这些起始u r l 一般是一些非常流 行、包含很多链接的站点，j t l y a h o o ! 。2 ) 将w e b 空间按照域名、i p 地址或困家域名划分， 每个搜索器负责一个子空间的搜索。 对于h i d d e nw e b 搜索来说，其搜索策略使用第二种更为合适，即将h i d d e nw e b 站点 分门别类的划分，然后进行索引。因为h i d d e nw e b 站点大多是动态站点，其信息是以后 台数据库为基础，并不能通过简单的u r l 链接关系进行获取。本文主要研究h i d d e nw e b 识别和搜索算法，没有对其分类做过多论述。 ( 2 ) 分析器 分析器【1 9 】也是一个计算机程序，它负责分析搜索器收集回来的网页，提取网页对应 的u r l 、编码类型、页面中包含的关键词、关键词位置、生成时间、大小、与其它网页 的链接关系等信息。然后将这些信息整理形成原始页面信息数据库。分析器的技术主要 包括分词、过滤和转换等。 分词即从文档中抽取词条。英文分词直接以空格作为分隔符，分词十分方便。由于 中文句子中各词语间没有固定的分隔符，汉语语义及结构上的复杂性和多边性给中文分 词带来极大困难。汉语分词主要有两大类方法【2 0 】：基于词典与规则，或者基于统计。前 者应用词典匹配，汉语词法或其他汉语语言知识进行分词，如最大匹配法( m a x i m u m m a t c h i n g ) 、最小分词方法等，其性能依赖于词典的完备性、规则的一致性。后者基于字 和词的统计信息，如相邻字词的相关性，词频及相应的贡献信息等。 分词后通常要使用禁用词表( s t o pl i s t ) 来过滤出现频率很高的无意义词条，如a 1 1 、 t h e 、o f , 的等。另外需要对词条进行单、复数转换，词缀去除，同义词转换等工作，如 将j u m p s 、j u m p e d 、j u m p e r 都统一成j u m p 进行索引。 ( 3 ) 索引器 索引器从分析器提取的信息中抽取出索引项，用于表示文档以及生成文档库的索引 表。索引表一般使用倒排表【2 1 l ( i n v e r t e dl i s t ) ，即由索引项查找相应的文档。索引表也可 能要记录索引项在文档中出现的位置，以便检索器计算索引项之间的相邻或相近关系 7 第二章搜索引擎概述 ( p r o x i m i t y ) 。 索引项有客观索引项和内容索引项两种。客观索引项与文档的语意内容无关，如作 者名、u r l 、更新时间、编码、长度、链接流行度( l i n kp o p u l a r i t y ) 等。内容索引项是用 来反映文档内容的，如关键词及其权重、短语、单字等。内容索引项可以分为单索引项 和多索引项( 或称短语索引项) 两种。单索引项对于英文来讲是英语单词，比较容易提 取，因为单词之间有天然的分隔符( 空格) ；对于中文等连续书写的语言，必须进行词 语的切分。在搜索引擎中，一般要给单索引项赋予个权值，以表示该索引项对文档的 区分度，同时用来计算查询结果的相关度2 2 1 。使用的方法一般有统计法、信息论法和概 率法。短语索引项的提取方法有统计法、概率法和语言学法。 索引器可以使用集中式索引算法或分布式索引算法。当数据量很大时，必须实现即 时索i ( i n s t a n ti n d e x i n g ) ，否则跟不上信息量急剧增加的速度。索引算法对索引器的性能 ( 如大规模峰值查询时的响应速度) 有很大的影响，一个搜索引擎的有效性在很大程度 上取决于索引的质量。 ( 4 ) 检索器 检索器的功能是根据用户的查询在索引数据库中快速检索出文档，进行文档与查询 的相关度评价，对将要输出的结果进行排序，并实现某种用户相关性反馈机制。检索器 常用的信息检索模型有集合理论模型、代数模型、概率模型和混合模型等多种，可以查 询到文本信息中的任意字词。 检索器从索引中找出与用户查询请求相关的文档，采用与分析索引文档相似的方法 来处理用户查询请求。如在矢量空间索引模型【2 3 】中，用户查询q 首先被表示为一个范化 矢量v ( q ) = ( t 1 ，w l ( q ) ；t i ，埘( q ) ；t n ，啪( q ) ) ，然后按照某种方法来计算用户查询与 索引数据库中每个文档之1 1 自j 的相关度，而相关度可以表示为查询矢量v ( q ) 与文档矢量 v ( d ) 之问的夹角余弦，最后将相关度大于阀值的所有文档按照相关度递减的顺序排列并 返还给用户。 8 中国油大学( 华东) 硕上学位论文 一提交查 图2 - 2 检索器工作过程 f i 9 2 - 2t h ew o r kf l o wo fi n d e x e r ( 5 ) 用户接口 用户接口为用户提供可视化的查询输入和结果输出界面，提供用户相关性反馈机 制。主要目的是方便用户使用搜索引擎，高效率、多方式地从搜索引擎中得到有效、及 时的信息。用户接口的设计和实现使用了人机交互理论和方法，以充分适应人类的思维 习惯。用户输入接口可以分为简单接口和复杂接口两种。简单接口只提供用户输入查询 串的文本框；复杂接口可以让用户对查询进行限制，如逻辑运算( 与、或、非) 、相近 关系、出现位置( 如标题、内容) 、信息时间、长度等。在输出界面中，搜索引擎将检 索结果展现为一个线性的文档列表，其中包含了文档的标题、摘要、u r l 等信息，用户 需要逐个浏览以便找出所需的文档。 2 2 搜索引擎的分类 按照信息搜集方式和服务提供方式的不同，搜索引擎可以分为：目录式搜索引擎、 全文搜索引擎和元搜索引擎三类。 2 2 1 目录式搜索引擎 目录式搜索引擎【2 4 1 通过人工发现信息，并依靠标引人员进行甄别和分类。用户在分 类体系中直接进行浏览检索。它的优点是信息标引质量高，检准率高，适合于族性检索， 缺点是查询速度比较慢，而且没有标准的分类原则，用户有时很难确定要查找的内容存 放在哪一类。因此，这种目录式搜索引擎不适合大范围的互联网，只适合在某个特定的 网站中，比如大型的门户网站，采用这种方式为用户提供检索服务。早期的搜索引擎， 如y a h o o ，l o o k s m a r t ， o p e n d i r e c t o r y 等，目前这类搜索引擎也采用了网络蜘蛛爬取 9 第二章搜索r j f 擎概述 等先进技术，但还是保留了以前传统的目录结构。 2 2 2 全文搜索引擎 全文搜索引擎2 1 】由网络蜘蛛程序以某种策略自动地在互联网上搜集和发现信息，由 索引器为搜集到的信息建立索引，通过检索器，根据用户的输入检索索引数据库，并将 查询结果返回给用户。这类搜索引擎的优点在于，搜集的信息量大，更新及时，不需要 人工干预。具有高效性和智能化，但同时存在一个较大的隐患：返回的搜索结果太多， 很多是无关信息，用户需要根据自己的喜好筛选结果。这类搜索引擎的代表有：g o o g l e ， a l t a v i s t a ，i n k t o m ，i n f o s e e k ，f a s t f a s t s e a r c h ，l y c o s ，国内的天网，悠游，o p e n f i n d ， 百度也属于这类搜索引擎的范畴。 2 2 3 元搜索引擎 元搜索引擎【2 1 】【2 5 1 是建立在己有搜索引擎基础之上的一种搜索引擎，它把其它己存在 的搜索引擎作为自己的成员搜索引擎，并把他们的结果重新组合，返回给用户。对于每 一个用户的检索请求，元搜索引擎自己并不做任何处理。而是按照各个成员引擎的查询 格式做相应的转化之后，再分发到各个成员搜索引擎。各个成员搜索引擎把返回结果给 元搜索引擎之后，元搜索引擎进行结果组合，并按权重的顺序输出给用户。这类搜索引 擎的特点是：能够分散处理负载，增加检索的范围，使结果的信息量更加大，更加全面， 同时还具有良好的可扩展性，可以加入多个搜索引擎，而且各个成员引擎可以缩小规模， 提供更好的性能，检索响应时间更短，同时还可以保证检索的内容最新。缺点是不能够 充分使用搜索引擎的功能，用户要做更多的筛选。这类搜索引擎的代表有：i n f o s p a c e ， d o g p i l e ， v i v i s i m o ，m e t a c r a w l e r ，i n f o m a r k e t 等。 元搜索引擎与独立搜索引擎最大的区别在于后者拥有独立的网络资源采集、索引机 制和一定的数据库，能直接提供用户需求的网络信息、数据；元搜索引擎没有属于自己 独立的数据库，而是利用网络服务器及路由器之间的功能切换机理、以及各自物理层与 应用层之问的藕合联结系统的延伸方式来形成由分布于不同服务器与物理层上、具有独 立检索体系的多个独立搜索引擎构成的逻辑结合体。元搜索引擎是以各独立搜索引擎的 分布式数据库为基础，将进人自己检索界面的用户检索转交给其所链接的这些处于底层 的独立搜索引擎，去分析和处理。 1 0 中国石油大学( 华东) 硕上学位论文 2 3 搜索引擎的主要技术 2 3 1网络爬虫 网络爬虫即w e bc r a w l e r ，因其在网络上爬来爬去抓取网页而得名，网络爬虫是搜 索引擎的核心模块，它是通过网页的链接地址来寻找网页，从网站某一个页面( 通常是 首页) 开始，读取网页的内容，找到在网页中的其它链接地址，然后通过这些链接地址 寻找下一个网页，这样一直循环下去，直到把这个网站所有的网页都抓取完为止。如果 把整个互联网当成一个网站，那么网络爬虫就可以用这个原理把互联网上所有的网页都 抓取下来。网络爬虫技术并不是一项十分高深的技术，但要做一个强大的网络爬虫，却 非易事。它的体系结构与爬行算法都是值得研究的问题，在目前磁盘容量已经不是瓶颈 的时候，搜索引擎一直在扩大自己的网页数量。同时也在努力不断优化自己的网络爬虫。 图2 3 为典型网络爬虫的工作流程。 调度器 u r l | 下载进程 w w w 、弋 j i i u r l s i 1r u ij s i u r l 队列 j 数据库 图2 - 3 网络爬虫的工作机制 f i 9 2 - 3 t h ew o r kf l o wo fw e bc r a w l e r 为了尽可能多的下载网页和缩短下载所需的时间，网络爬虫多采用分布式的体系结 构，即图2 3 中下载进程分布在其他多台主机中并行工作或一台主机同时运行多个进程 进行下载，当爬虫下载完一个网页的时候，抽取里面的u r l 链接并将其送入u r l 队列 中，同时将网页内容进行存储。调度器是一个调度进程，一般来说单独运行于某台服务 器上，它依据某些搜索策略决定u r l 队列中待爬行的一个首先被爬行，被选中的u r l 将被送交到一个空闲的下载进程去进行爬行。因为w e b 上的网页都是相互链接的，所 以，理论上来讲网络爬虫是可以将网络上所有网页都抓取下来的。 2 3 2 信息获取模型 信息获取模型2 6 1 给出了文档的表示方式，查询的表示方式以及查询与文档的匹配过 第一二章搜索引擎概述 程。目前大多数获取模型依赖于布尔模型，而在实验室用的最多的是向量空间模型，其 他信息获取模型还有概率论模型、神经网络模型、聚类模型、基于规则的模型、模糊模 型和语义模型等。 布尔模型2 7 】：定义一个二值变量的集合，这些变量对应文档的某个特征。如果该变 量可以用来作为文档的表示，则此特征则为“真”，否则为“假。文档就表示为这些 特征变量的集合，查询表示为特征变量和“与 、“或”、“非的操作。 向量空间模型【2 7 】：定义一组特征值，用权来表示各个特征值的重要程度，文档表示 为特征值权的集合，查询也用同样的特征值来表示。通过计算向量间的某种距离度量来 反映文档对查询的满足程度。 2 3 3 排序技术 搜索引擎体系结构中每一部份的实现都较复杂，每个搜索引擎的具体实现也不尽相 同。这些复杂部分中最能体现搜索引擎设计思想的就是网页排序系统，因为面对常常是 数以万计的返回结果，用户一般只会去点击排在前一百位的搜索结果。因此搜索引擎最 关注的不是如何返回尽可能多的结果，而是尽可能的将最有可能与用户搜索请求相关的 链接放在前面。g o o g l e 是迄今为止最成功的搜索引擎，它成功的因素有许多，其中最重 要的是g o o g l e 对搜索结果的排序比其它搜索引擎都要好。g o o g l e 保证让绝大部分用户， 都能在搜索结果的第一页找到他想要的结果。g o o g l e 采用了p a g e r a n k ，即网页级别技 术。下面介绍两种常用的排序技术。 ( 1 ) p a p e r a n k p a g e r a n k 值代表了网络上某个页面的重要程度。一般搜索引擎将p a g e r a n k 值与网 页搜索结果相似度共同作为搜索结果的排序依据。该值仅仅依赖于网络的链接结构，而 与具体的检索内容无关。检索语句不会呈现在p a g e r a n k 本身的计算上。不管得到多少 检索语句，p a g e r a n k 值也是一定的、文件固有的评分量。 ( 2 ) h i l l t o p 与p a g e r a n k 结合，h i l l t o p 算法确定网页与搜索关键词匹配程度的基本排序过程， 取代了过份依靠p a g e r a n k 值去寻找那些权威页面的方法。这对于两个具有同样主题而 且p a g e r a n k 级别相近的网页排序过程中，h i l l t o p 算法就显得非常的重要了。h i l l t o p 同时也避免了许多想通过增加许多无效链接来提高网页p a g e r a n k 值的做弊方法。 1 2 中周石油人学( 华东) 硕七学位论文 2 4 当前搜索引擎遇到的问题 通用搜索引擎的出现很大程度上解决了人们在互联网上查找信息的困难，但由于其 覆盖一切、追求普遍的设计目标，己经不能满足人们对个性化信息检索服务日益增长的 需要。目前，通用搜索引擎在使用中面临着较多亟待解决的问题。 ( 1 ) 索引覆盖率不高。i n t e m e t 信息资源呈指数级增长，再加上基于w e b 的自身特 点，大量的数据分布在数以亿计的计算机互联网上，搜索起来非常困难。一般而言，搜 索引擎的索引数据库的覆盖率都低于3 0 ，很难索引更多的w e b 资源。 ( 2 ) 不能满足人们日益增长的对个性化服务的需求。它们遵循着以不变应力变的 设计理念，成千上万的查询结果往往没有足够的准确性。它们想迎合每一个可能的查询， 但结果是返回成千上万个没有相关性的结果。 ( 3 ) 对复杂数据源的支持还不成熟。目前，多数搜索引擎的搜索对象主要是文本 格式，主要原因是搜索引擎的自动排序软件，只能接受这种格式的网页。能够搜索多媒 体信息资源的搜索引擎较少。多媒体技术的发展，对搜索引擎提出了更高的要求，搜索 引擎应更好地支持动态网页，尽快解决动态网页查询的问题。 2 5 本章小结 本章深入分析了传统搜索引擎的结构、原理和在搜索中用到的主要技术。通过对这 些技术的分析，有利于找准h i d d e nw e b 无法被传统搜索引擎搜索的原因。在下一章中 将结合本章的知识，深入分析研究h i d d e nw e b 的相关知识，为后面的内容奠定基础。 1 3 第三章h i d d e nw e b 搜索媾础 第三章h i d d e nw e b 搜索基础 3 1h i d d e nw e b 的产生原因 普通站点和h i d d e nw e b 站点对于人来说没有区别，h i d d e nw e b 不可见只是对于搜索 引擎而言。搜索引擎最早出现于1 9 9 4 年，当时的互联网资源少、更新慢，主要以静态网 页的形式存在，搜索引擎能够轻易地索引整个网络。但自从1 9 9 6 年开始，有3 种现象对 互联网上的资源组织方式产生了巨大的影响：数据库技术的不断发展，电子商务概念的 出现和动态网页技术的发明。电子商务通过网络开展商务活动，这是一个互动的过程。 因此，电子商务网站必须以动态网页为主，静态网页根本无法实现互动。许多站点尤其 是大型站点抛弃静态网页方式，转向了以数据库为后台、动态网页技术和数据库技术相 结合的资源组织方式。然而搜索引擎的发展却相对滞后，虽然搜索技术得到一定的改进， 例如针对检索结果的相关度排序问题，就引入了“引文索引【7 j 的思想，形成了超链分 析技术，但是搜索引擎基本的工作模式没有大的改变，s p i d e r 收集的主要还是静态网页。 这就是h i d d e nw e b 形成的主要原因。如果作更细致的分析，则成因可以概括为以下两个 方面：技术障碍i l j 和搜索引擎对s p i d e r 的限制。 ( 1 ) 技术障碍 一般搜索引擎i 拘s p i d e r 在网络上沿着超链接搜索网页，通过网页上的超链接提取新 的u r l ，如此循环往复。s p i d e r 只能通过简单的链接进入新的页面，无法进行表单输入 操作。这点造成了如下两类资源不可见：1 ) 网络数据库资源。网络数据库的资源组织 方式j 下是前面已经提到过的以数据库为后台、动态网页技术与数据库技术相结合的方 式。用户在网络数据库检索页面上输入检索词，获得的页面不是预先存在的静态网页， 而是针对用户此次的检索词和其他一些检索限制而动态生成的网页，也就是动态网页。 s p i d e r 无法进行“选择和输入查询词”的操作，自然无法搜索这种资源：2 ) 需注册的站 点。用户要进入站点，获取站点内容必须取得用户名和密码。对于搜索引擎的s p i d e r 来 说，不管是有偿的还是免费的，它都无法进入。这种站点虽然也是需要输入，看起来与 第一种类似，不过这种站点更复杂，更难处理。 ( 2 ) 搜索引擎对s p i d e r 的访问限制 维持一个搜索引擎的运营相当昂贵，因此其s p i d e r 所使用的资源也就显得特别宝贵， 1 4 中国石油大学( 华东) 硕上学位论文 许多搜索引擎都对自己的s p i d e r 有所限制：1 ) 搜索引擎般只收录h t m l 网页文件，而 对于用户不经常检索的文件格式，l 匕0 1 1 p d f 文档等选择不加收录。以使有限的资源获得 更多的页面。文献【l 】指出，搜索一个p d f 文档所消耗的时间通常是搜索一个普通h t m l 页面时间的几倍甚至十几倍。不过近两年来已有一些搜索引擎正在努力扩展和完善其检 索服务，例0 n g o o g l e ，现在可以通过g o o g l e 检索图片、p d f 、w o r d 、p o w e rp o i n t 等多种 格式的文档。2 ) 对于基于脚本语言的网页，如果其u r l 中含有“? ”，s p i d e r 通常放弃 对该类网页的访问。因为在访问此种网页时，s p i d e r 有可能陷入恶意的“s p i d e rt r a p ”1 程