（计算机软件与理论专业论文）基于主题的hidden+web信息获取研究.pdf

摘要 论文题目：基于主题的h i d d e nw e b 信息获取研究 学科：计算机软件与理论 研究生：杨增辉 指导教师：姚全珠教授 摘要 签名： 签名： 随着w o r l dw i d ew e b ( w w w ) 的爆炸式增长，h i d d e nw e b 中蕴含了海量的可供访问的 信息，并且还在迅速地增长。这些信息需要通过查询接口在线访问其后端的w 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 信息的方法，文中 给出了系统的框架结构，分析了h i d d e nw e b 爬虫抓取页面时的几个步骤，并讨论了实现 的关键技术。 通过引入的主题技术，能够节省网络资源，减少在不相关站点的停留，提高了抓取 的准确率；文中设计的启发式查询词选择算法，能够每次自动从候选查询词中选择“最 佳”查询词进行提交。与现有的网络爬虫采用的算法相比，该算法有效地减少了查询词 提交的次数，从而提高了抓取的效率。实验表明，该方法和早期的解决方案相比，取得 了较好的抓取效果。 关键词：主题技术；信息检索；h i d d e nw e b ；爬虫；启发式算法 埠簪 盔径 毒 a b s t r a c t t i t l e ：r e s e a r c ho nf o c u s e dh i d d e nw e bc r a w l e r m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：z e n g h u iy a n g s u p e r v i s o r ：p r o f q u a n z h uy a o a b s t r a c t s i g n a t u r e ： s i g n a t u r e ： a st h er a p i dd e v e l o p m e n to fw o r l dw i d ew e b ，t h e r ei stt r e m e n d o u si n f o r m a t i o n h i d d e n e d ”i nh i d d e nw e b ，a n di tsc a p a c i t yi si n c r e a s i n gr a p i d l y t h ei n f o r m a t i o n c a no n l yb ea c c e s s e db yth eq u e r yi n t e r f a c e sp r o v i d e db yw e bd a t a b a s e t h ed a t ai n h i d d e nw e ba g eo b t a i n e di nt h ef o r mo fd y n a m i cw e bp a g e sw h e nu s e r ss e n daq u e r y d u et ot h ep o o rs t r u c t u r eo fw e bp a g e sa n dt h ei n s t a b i l i t ya n dl a r g es c a l eo fh i d d e n w e b ，i ti sav e r yc h a l l e n g i n gt a s kt oi n t e g r a t et h ea b u n d a n ti n f o r m a t i o na u t o m a t i c a l l y a n du s ei te f f e c t i v e l y b e c a u s eo ft h i sh i d d e nf e a t u r e ，h i d d e nw e bi sh a r dt oc r a w l i tb e c o m e san e w d i r e c t i o ni nt h ef i e l do fi n f o r m a t i o nr e t r i e v a l i nt h i sp a p e rt h ec a u s eo ff o r m a t i o na n d t h ef e a t u r eo fh i d d e nw e bh a v eb e e ni n t r o d u c e d i ta l s os h o w e dt h es i m i l a r i t i e sa n d d i f f e r e n c e so fh i d d e nw e bc r a w l e ra n dt r a d i t i o n a lc r a w l e rb yc o n t r a s t t h r o u g ht h a t ， i ta n a l y z e dt h ek e yt e c h n i q u eo fd e s i g n i n gah i d d e nw e bc r a w l e r , a n dt h es t e pw h e na c r a w l e rc r a w l i n gt h ew e bp a g e i n t h i sp a p e ran e wm e t h o do ff o c u s e d h i d d e nw e bi n f o r m a t i o nr e t r i e v a li s p r o p o s e d i tp r e s e n t s ag e n e r i co p e r a t i o n a lm o d e lo ft h eh i d d e nw e bi n f o r m a t i o n r e t r i e v a la n dd e s c r i b e st h ek e yt e c h n i q u e s i ta l s oi n t r o d u c e saf o c u s e dc r a w l i n g t e c h n i q u ea n dan e wh e u r i s t i cq u e r ys e l e c t i o na l g o r i t h mw h i c hd e s i g n e db yt h i sp a p e r b a s e do nt h o s et e c h n i q u e s ，t h ec r a w l i n gi sm o r ee f f i c i e n ta n dm o r ea c c u r a t e t h e r e s u l to fe x p e r i m e n ti n d i c a t e st h a tt h en e ws o l u t i o ni sm u c hb e t t e rt h a nt h eo l do n e k e yw o r d s ：f o c u s e dc r a w l i n g ；i n f o r m a t i o nr e t r i e v a l ；h i d d e nw e b ；c r a w l e r ； h e u r i s t i ca l g o r i t h m 独创性声明 秉承祖国优良道德传统和学校的严谨学风郑重申明：j 本人所呈交的学位论文是我 一 个人在导师指导下进行的研究工作及取得的成果。尽我所知，除特别加以标注和致谢 的地方外；论文中不包含其他人的研究成果。与我_ 同工作的同志对本文所研究的工 作和成果的任何贡献均已在论文中作了明确的说明并已致谢- 本论文及其相关资料若有不实之处j ，由本人承担_ 切相关责任 论文作者签名：j 壶! 堡墨霉埘年；：7 ，胄立旧 学位论文使用授权声明 本人垒焦墨至茬导师的指导下创作完成毕业论文。，本人已通过论文的答辩， 并已经在西安理工大学申请博士硕士学位二本人作为学位论文著作权拥有者，同意 授权西安理工大学拥有学位论文的部分使用权，即：1 ) 已获学位的研究生按学校规定 提交印刷版和电子版学位论文，；学校可以采用影印、缩印或其他复制手段保存研究生 上交的学位论文，可以将学位论文的全部或部分内容编入有关数据库进行检索：2 ) 为 教学和科研目的，学校可以将公开的学位论文或解密后的学位论文作为资料在图书馆、 资料室等场所或在校园网上供校内师生阅读、浏览。 本人学位论文全部或部分内容的公布( 包括刊登 授权西安理工大学研究生部办 理。 ( 保密的学位论文在解密后，。适用本授权说明) 论文作者签名。磷筮 导师签名：上蚴 ：如。踔一；月jj 目 前言 1 前言 1 1 研究背景 伴随着w e b 搜索引擎的出现，为人们从w w w 获取信息发挥了重要的作用，要快速有 效地获取所需的相关信息却变得越来越困难，因而对信息获取技术的发展提出了更高的要 求。随着信息量的急剧增加和基于w w w 的新的应用模式的出现，现有的w e b 搜索引擎也面 临着新的挑战，其中影响搜索引擎最大的瓶颈是覆盖率和刷新率。最新的实验表明，即使 目前最大型的综合信息采集系统，对w e b 的覆盖率不超过1 6 1 1 j ，且都是直接可见页面 ( p u b l i c l yi n d e x a b l ew e b ) ，通常称为静态页面或s u r f a c ew e b 。另一方面，还存着大 量动态页面，又称为h i d d e nw e b 或d e e pw e b ，h i d d e nw e b 的权威定义为虽然通过互联网可 以获取，但普通搜索引擎由于受技术限制而不能或不作索引的那些文本页面、文件或其他 通常是高质量、权威的信息。这类页面只能通过提交表单的形式动态获得，且往往包含的 都是对用户重要的权威信息，而利用传统的搜索引擎无法获取这些信息，造成大量的信息 浪费。据b r i g h t p l a n t 的估计，h i d d e nw e b 的数量大概是静态页面的4 5 0 - - 5 5 0 倍，总数超 过5 5 0 0 亿文档。这样一来，如果加上h i d d e nw e b ，大型综合信息采集系统的覆盖率仅仅为 0 。0 3 2 1 。 h i d d e nw e b 资源内容更为丰富，专业性较强，质量比一般网络资源也好得多，其后台 数据库多是结构化的关系数据库，因此信息的质量要比非结构化的数据要高。传统爬虫仅 能爬行所谓的公共可索引的页面，它是通过分析页面中超链接来爬行的。然而h i d d e nw e b 页面是为响应来自客户端的表单查询请求由服务器端后台数据库动态产生的。因此要获取 这个页面集，就需要一种特殊的爬虫来搜集这些页面。 图1 - 1 显示了用户获取h i d d e nw e b 信息的过程：用户首先输入查询词到页面的表单， 浏览器和服务器通信，将查询词被发送到后台数据库。返回的数据又通过服务器发回到浏 览器上。由于要让爬虫自主完成这个过程是个具有挑战性的任务，目前的爬虫对h id d e n w e b f i i 动态页面，爬虫不做抓取。 综上所述，h i d d e nw e b 数据具有较高的权威性和实用性，但是目前还没有一个较好 的方法去获取，本文提出一种基于主题的h i d d e nw e b 信息获取系统。它可以对整个w e b 按主题自动下载h i d d e nw e b 页面，以便搜索引擎索引这些页面，最后将不同块整合，这 样就提高了页面的覆盖率；由于每块都是按相关主题进行，这样保证了结果只与某个特定 主题相关，从而提高了其查准率。 西安理工大学硕士学位论文 浏 一二1 览 裁峤 嚣 g 7 一 嘲澎口e 嘲 写裹 览结 图l - i 用户查询h i d d e nw e b 过程 f i g u r e1 一lt h ep r o c e s so fu s e ri n q u i r eh i d d e nw e b 1 2 国内外研究现状 目前国内很少有专门的文章对这方面的内容进行讨论，国外有一些大学在研究中进行 了很多有益的探索。 获取h i d d e nw e b 页面目前主要有两种方法，一种是集中式搜索引擎方式：自动从填写 表单并下载页面，索引以供用户查询。这种方式实时性好，但是刷新率低，前期准备任务 量大。典型代表是h i w e ： h i w e ( h i d d e nw e be x p o s e r ) 【1 1 是斯坦福大学的一个研究项目，设计了一种可以抽取 h i d d e nw e b 内容的爬虫。在此系统中爬虫管理器负责管理搜集过程。它对下载的w e b 页面 进行分析，包含表单的页面被送到表单处理器中专门处理。表单处理器先从页面中抽取出 表单，再从预先准备好的数据集中选择数据自动地完成表单的填写，然后将合成的u r l 提 交爬虫管理器去下载相应的结果页面。由于需要系统自动完成表单填写，所以要求用户事 先准备相应的表单数据集。h i w e 只能面向特定的领域使用，而且必须在人工帮助下完成。 此系统主要工作是让爬虫自己学习去填写查询接口，而不是怎样自主产生查询词，在抓取 前需要准备一个庞大的词库，然后依次提交词库里的查询词，效率低下，且此方法还很难 在没有限制的条件下使用。 另一种方法称为元搜索引擎方式：选择最相关的站点提供给用户。最终问题归结为数 据库选择和数据库发现。这种方法实时性差，且不稳定。典型代表为哥伦比亚大学的 p a n a g i o t i sg i p e i r o t i s 等人在文章 3 中讨论了自动地将w e b 网页所连接的后台数据库 进行分类的方法。它首先使用机器学习技术生成一套基于规则的分类器( c l a s s i f i e r ) 。 然后将分类器转变成查询u r l ，对后台数据库进行查询，计算查询结果。他们的算法最后 根据查询结果对数据库进行分类。但是它的研究只集中在怎样针对文本数据库的分类上 面。研究表明，大量的h i d d e nw e b 中的内容是非文本的。 文献 4 5 所研究的h i d d e nw e b 信，包、获取，抓取形式并d h i w e 类似，但是其注意力也只 2 前言 集中在文本型数据库，对于结构化数据库并不适用。 总体看来，目前还没有一种高效的能获取结构化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 爬虫，就可 以访问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 中的数据，则需要进行以 下3 个方面的工作： 1 找到与主题相关的h t m l 表单，即h i d d e nw e b 表单的入口。 2 提交有意义的查询词并自动填充h i d d e nw e b 入口表单。 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 信息获取的基本问题，提出了难点以及相关的解决方案， 特别对提出的解决结构化数据库启发式查询词提交选择算法做了详细的介绍，实验证明本 算法能较大幅度的提高检索效率。 论文的后续章节分别为： 第二章，相关技术介绍。本章主要介绍了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 西安理工大学硕士学位论文 之间的比较，总结了本方案的优越性。一 第六章，总结与展望。本章对本课题工作进行了总结，并对未来进一步的工作做了展 望。 后续内容分别是致谢、参考文献和在校学习期间发表论文情况。 4 相关知识及技术 2 相关知识及技术 1 9 9 4 年，美国学者d r j i l le l l s w o r t h 首次提出“i n v i s i b l ew e b 这一概念，用来 指那些通过普通搜索引擎搜索不到的网络信息，但直到2 0 0 0 年以后，才有相关的研究论 文和成果发表，并迅速得到重视。2 0 0 0 年，b r i g h t p l a n e t 公司首创了“d e e pw e b 术语， 也就是h i d d e nw e b ，用来表述那些存储于在线数据库中，且只能通过提交表单才能访问 的数据1 2 】o 可见，“h i d d e nw e b 和“i n v i s i b l ew e b ”指的是统一事物，但“h i d d e nw e b ” 在内涵上略胜一筹。 2 1h i d d e nw e b 介绍 c h r i s ts h e r m a n 和g a r yp r i c e 对h i d d e nw e b 的定义为：虽然通过互联网可以获取， 但普通搜索引擎由于受技术限制而不能或不作索引的那些文本页、文件或其它通常是高质 量、权威的信息。 专数量是静态页面的4 0 0 到5 5 0 倍 夸页面数接近5 5 0 0 亿张页面，对比静态页面的1 0 亿张 夸超过2 0 万的站点 每过半的站点是有关某一主题的 夸大约9 5 的内容是免费的 夸增长速度高于静态页面 未被传统搜索引擎索引 夸h i d d e nw e b 中的后台数据库大多是结构化的，其中结构化的是非结构化的3 4 倍 之多 夸在站点前3 层发现。 2 1 1hid d e nw e b 数据库模型 h i d d e nw e b 的后台数据库为可搜索数据库( s e a r c h a b l ed a t a b a s e ，s d b ) 且i 可进行搜索 的网络数据【加】。s d b 一般由客户端服务器端一数据库端三层结构组成：数据端保存 信息内容，返回满足查询的结果；客户端提供一个搜索页面，用户输入查询请求，并显示 最终搜索结果；服务器端用户的查询请递交给数据库，并将数据库返回记录生成动态网页 返回给用户【3 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 后台数据库类型，可以将h i d d e nw e b 数据库分为两类1 1 0 】： 文本数据库主要指包含有许多纯文本文档资料的数据库，例女i n e w s b a i d u t o m 。由于 纯文本文档通常没有很好的结构，大多数文本数据库提供一个简单的搜索接口，用户可以 在简单在此接口中键入关键词，然后得到检索页面。 新闻网亘l 占口巴知道m p 3 图片 b a i 留巍阉：l = 二二二厦丑 焦点i 跹l 雎 新闻敛0 新闻糯 图2 1 文本h i d d e nw e b 查询接口 f i g u r e2 - 1t h es e a r c hi n t e r f a c eo ft e x t u a lh i d d e nw e b 结构化数据库通常由有关联的多个属性的数据对象组成，它支持多属性的搜索界面， 后台的数据表也为结构化数据表。对于此类型数据的检索，需要在相关接口中键入相关的 关键词，以满足查询条件。 高级检索 舾名： 责任者： 丛书名： 主题词： r 一j r 一： 。，。，。二 一”_ 。”。1 “。“”。“- 。“+ 。一 压囹 出版社：! z 蛐l w l i s s 瞽号： 素书号： 起始年代l 囝囹 图2 2 结构化h i d d e nw e b 查询接口 f i g u r e2 - 2t h es e a r c hi n t e r f a c eo fs t r u c t u r e dh i d d e nw e b 2 1 2hid d o nw e b 不可见原因 a 技术障碍 传统搜索引擎爬虫在网络上沿着超链接漫游，主要通过点击网页上的超级链接提取 新的u r l ，如此循环往复。可以说爬虫的工作是通过点击动作完成的。爬虫无法进行输入 动作，更没有思考分析能力。这造成了如下两类资源不可见1 6 j ：网络数据库资源。互联 网上存在许多数据库资源，其中很大一部分可以免费获取，例如美国专利商标局的网上 专利检索数据库是完全免费的。网络数据库的资源组织方式正是前面已经提到过的以数据 库为后台、动态网页技术与数据库技术相结合的方式。用户在网络数据库检索页面上输入 相关知识及技术 检索词，获得的页面不是预先存在的静态网页，而是针对用户此次的检索词和其他一些 检索限制而动态生成的网页，谓之动态网页。爬虫无法进行“输入检索词 的动作，自然 爬不进数据库；需注册的站点。相当一部分站点需要用户注册，分为有偿注册和免费 注册两种。用户要进入站点，获取站点内容必须取得用户名和密码。对于搜索引擎的爬虫 来说，不管是有偿的还是免费的，它都无法进入。 b 搜索引擎对爬虫访问限制 搜索引擎一般只收录h t m l 网页文件，而对于用户不经常检索的文件格式，比如 p d f 文档等选择不加收录。h t m l 是互联网上最基本的通用语言，爬虫最擅长处理h t m l 语言 写成的网页文件。在h t m l 中可以设置超级链接链接其他类型的文件，比女i p d f 文档。处理 其他类型的文件在技术上没有很大的难题，但搜索引擎开发商出于种种考虑，一般将之排 除在外。维持一个一般搜索引擎的运营相当昂贵，这可能是最大的原因。不过近两年来已 有一些搜索引擎正在努力扩展和完善其检索服务，例女i g o o g l e ，现在可以通过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 中含有“? ，爬虫通常放弃对该类网页的访问。因为在访问此种网页时，爬虫有可 能陷入恶意的“s p i d e rt r ap ”程序当中，导致爬虫陷入死循环，影响搜索引擎的正常运 转。因此，搜索引擎一般限制爬虫访问该类网页。 2 1 3hid d e nw e b 分类 页面被设计为动态一般有三个原因：具有时效性的信息，用户定制和用户输入。这样， 导致了如下三种类型的动态： 时效性动态( t e m p o r a ld y n a m i s m ) ：一个包含有时效性( t i m e s e n s i t i v e ) 动态内容的 页面则说明了其具有时效性动态。例如一个显示股票行情或最新世界新闻标题的页面就属 于此类。根据定义，对一个具有时效性动态页面通过两个不同要点同时请求的内容可能完 全不同。 现在爬虫抓取时效性动态页面的数据，关键的问题是抓取的页面是更新过。例如怎 样去更新抓取来的集合的方法是和最新的站点内容作对比。由c h oe t a 1 提出的尽可能 去更新的( t om a x i m i z ef r e s h n e s s ) 分析和抓取的策略在这篇文章中很适用。 基于客户的动态( c l i e n t - b a s e dd y n a m i s m ：) ：一个包含特定客户( 或用户) 定制生成内 容页面是基于客户的动态。最常见的基于客户的动态是在个性化( p e r s o n a l i z a t i o n ) 应 用中。w e b 站点通过特定用户或社区用户定制设和它们自己的页面( 包括外观，行为以及 内容等) 。这通过应用来自客户端c o o k i e s 或登录的信息详细地给出了动态( o nt h ef l y ) 页面地产生，去鉴定是哪个用户。 因为基于客户的动态具有个人定制的内容，抓取这些页面对许多不同应用目的人可能 不具有价值。( 例如一个被特殊搜索引擎使用的爬虫) 。不过，对特定的应用，一个专门的 7 西安理工大学硕士学位论文 爬虫( r e s t r i c t e dc r a w l e r ) 可以加载有需要的c o o k i e s 和登录信息( 例如用户名和密码) ， 使其抓取站点的全部信息。 输入动态( i n p u td y n a m i s m ：) ：一个依靠用户输入来显示内容的页面称其具有输入动态。 这种典型的例子是w e b 服务器回应用户提交而生成的页面。例如，通过填写表单查询一个 在线可搜索的数据库产生一个或多个包含有查询结果的页面。所有这些包含结果的页面被 归类为输入动态。总体而言，所有动态页面都表现为输入动态。本课题着重关注此类页面 的抓取。 许多动态页面表现为以上三种类型动态的混合。例如，a m a z o n 网站的欢迎页面显示为 基于客户( 例如推荐的书为基于用户喜好和兴趣) 和时效性( 例如最新图书清单) 两种动 态。 此外，还有许多混杂的动态形式不属于以上三种中的任何一种。例如，一些建立和维 护网站的工具经常允许将数据存储在本地数据库和文件中。这些工具提供在运行时有原始 数据生成h t m l 格式页面的程序，使得数据和显示得到了清晰的分离。在此情况下，即使页 面是动态生成的，其数据从本质上说是静态的。 2 2 主题技术 普通搜索引擎可以满足用户一般的查询需要，但存在这样的需求：用户只对很具体的 一个主题感兴趣，希望获得针对该主题比较详尽信息，这就需要有一个工具能够快速、准 确、全面的检索到该主题相关的网页，并能够对网页进行分析，尽可能地对主题进行挖掘。 普通搜索引擎与用户的这一需求之间存在着很大的偏差： 普通搜索引擎的目标是回答用户的所有查询，对于只关心某一具体主题的用户，这一 目标显得过于浪费，覆盖一切的目标造成了技术上和资源上的极大压力，也降低了针 对具体主题查询的查准率和查全率。 使用普通搜索引擎用户往往用几个简单的词表达查询，而这样有时并不能准确地定义 主题。 用户的查询是在服务器的网页库和索引上进行的，从根本上说是静态的，由于w w w 信 息更新非常迅速，查询的结果很可能不准确，而且更新索引的代价非常大。 普通搜索引擎仅通过对网页的内容的分析判断与用户查询符合与否检索出用户需要 的网页，缺乏对检索得到的网页进行进一步挖掘和分析的能力，而检索结果网页之间的链 接结构、以及这些网页与其它主题无关网页之间的链接结构都蕴含着大量信息，普通搜索 引擎不能对其进行利用。对于关注具体主题的用户来说，他们更需要一个针对主题进行网 页收集、管理和分析的工具，这就导致了主题技术的出现。 基于主题的w e b 信息采集( f o c u s e dc r a w l i n g ) ，也称为t o p i c - s p e c i f i cc r a w l i n g ， 主要是指选择性地搜寻那些与预先定义好的主题集相关的页面进行采集的行为。主题爬虫 相关知识及技术 最初的设计思想是考虑对页面的过滤，不像普通爬虫对所有页面的链接进行处理，而是先 对页面与受限领域的主题相关度进行分析，只有当其主题相关度符合要求时才处理该页面 中的链接，因为如果该页面和本领域比较相关，它所包含的链接和领域相关的几率也较大， 这样提高了爬行精度，虽然会遗漏少数页面，但综合效果是令人满意的f 1 6 1 7 1 。 2 3 爬虫介绍 网络爬虫是一个自动提取网页的程序，它为搜索引擎从万维网上下载网页，是搜索引 擎的重要组成。传统爬虫从一个或若干初始网页的u r l 开始，获得初始网页上的u r l ， 在抓取网页的过程中，不断从当前页面上抽取新的u r l 放入队列，并重复上述过程，直到 达到系统的某一条件时停止【2 0 】。 2 3 1 传统爬虫和h i d d e nw e b 爬虫比较 传统爬虫只处理静态页面，当遇到含有表单的页面时，由于传统爬虫没有自动填写表 单的能力，只抓取表单页面本身，对隐藏在表单背后的大量有用数据不做处理。 h i d d e nw e b 爬虫遇到表单能自动填写相关项，从而得到一个包含有结果的响应页面， 然后对这个页面进行抓取。 图2 3 显示了传统爬虫和h i d d e nw e b 爬虫在遇到包含表单页面时的行为对比。 图2 。3 传统爬虫和h i d d e nw e b 爬虫的行为比较 f i g u r e2 - 3t h ed i f f e r e n c eb e t w e e nh i d d e nw e bc r a w l e ra n dc o n v e n t i o n a lc r a w l e r 2 3 2h i d d e nw e b 爬虫工作原理 静态页面整个内容完全存储于服务器中，如果客户端有请求发出，就将其内容发送给 客户端。利用这种机制，传统爬虫通常从种子页面集出发，通过h t t p 协议请求并下载w e b 页面，分析页面并提取链接，得到更多的u r l 以获取更多的网页，然后再以循环迭代的方 9 西安理工大学硕士学位论文 式访问w e b ，直到所有的链接全部被访问完毕。 。一 动态页面不像静态网页那样保存在服务器中，而是保存在类似s d b 的三层结构中， 由数据库返回内容，服务器生成动态网页。动态页面内容由服务器端或客户端程序在运行 时产生，所以h i d d e nw e b 在网络空间中实际并不存在，其数据通常来自于和站点相连的 数据库，只有用户在变量区域中输入若干参数以后才会根据这些参数返回一个响应页面， 显示出相关内容。这样，只依靠u r l 来查找并抓取页面的传统爬虫对h i d d e nw e b 显得无 能为力。 图2 - 4 是斯坦福大学设计的名为h i w e 爬虫的组织结构： 1 标签值集表( l a b e lv a l u es e tt a b l e ) 是一个包含许多表目的表，每个表目包含 一个l a b e l 及其对应的v a l u es e t ，在l v s 管理器的管理下可以实现表目的增加和删除以 及v a l u es e t 的更新，它的功能是帮助实现表单求值。 2 u r l 表用于存放网页的u r l ，可以有多种状态，最基本状态有已爬行状态和未爬行 状态。 标签值集(lvs)袭url表 匡垂墓雪r 匡蚕 ， 数据源 匝固 耍蔓 t ：j i ! i j ：i ! j l ! j ! j l i ! ，。! e ，一 一4页面处理器i - i 。 反馈 表单 提交 返回响 应页面 图2 - 4h i d d e nw e b 爬虫的系统结构 f i g u r e2 - 4t h ea r c h i t e c t u r eo fh i d d e nw e bc r a w l e r 3 爬虫管理器从u r l 表中读取一个将要爬行的新的网页地址，并从i n t e r n e t 中抓取 该网页，交给解析器进行解析。 4 解析器对网页进行解析，将网页中的u r l 添加到u r l 表中，如果有f o r m ，把它移 交给表单分析器进行处理。 5 表单分析器对表单进行分析，如果是h i d d e nw e b 的查询接口，将表单元素转换为 1 0 相关知识及技术 爬虫的内部统一表示，并将转换结果交给表单处理器。 6 表单处理器在l v s 管理器的帮助下对表单进行求值，自动填写表单，然后提交表 单到i n t e r n e t 中的相应w e b 服务器，w e b 服务器按表单提交的数据在数据库叶 进行查询， 将查询结果以响应页面的形式传给响应页面分析器。 7 响应页面分析器对响应页面进行信息提取，提取的结果反馈给表单处理器，以此 来决定下一次查询中的表单求值。表单填写和芨送过程，从而实现对h i d d e nw e b 的爬行。 8l v s 管理器可以对l v s 表进行访问实现l v s 表的内容的更新，还能从数据源中 抽取新的表目增加到l v s 表中，此外，它还有一个最主要的功能协助表单处理器，寻找晟 匹配的表目填写表单。 23 3h i d d a nw e b 爬虫的关键技术 首先h i d d e nw e b 查询接口表单的识别表单的种类很多如何识别h i d d e nw e b 查询接 1 ：3 表单，这是第二个关键问题。文献 1 0 提出丁基于查询接口的特征，利用决策树实现了 查询接口识别的解决办法。该方法对于w e b 中的随机数据集准确性有了较大的提升，但是 还有很大提升空间，此外还提出了判断页面中是否含有查询接口表单的个简单方法它 目2 - 5h i d d e nw e b 爬虫抓取过稗 f i g u r e2 - 5 t h ec r a w l i n gp r o c e s so fh i d d e nw e bc r a w l e r 包括三条规则：第，页面中要有f o r m 标签：第二，f o r m 标签中必须有t e x t 文本 输入控件；第三，至少出现某些关键词组( 如“s e a r c h ”、“g o ”、“确定”、“查询”、“搜索” 等) 中的一个。这种方法在实验中还存在一定的缺陷，如不能区分h l d d c nw c h 简单查询 西安理工大学硕士学位论文 接口和搜索引擎的查询接口。可以利用其他一些特征，比如a c t i o n 所指的u r l 是否与本 h i d d e nw e b 同一个i p 或同一个域名，还有查询接口在页面中的视觉布局信息，所在页面 的频繁词汇信息等作进一步的判断。 其次表单仿真( 就是表单分析，表单求值，表单填写和表单发送的整个过程) h i d d e n w e b 爬虫必须能够自动完成表单仿真，关键问题是如何进行表单求值。一般来说，对于提 供选择项的表单元素，如复选框，单选按钮，选择列表等，可以采用穷举的办法，但如何 填写文本输入框中的内容，相对来说困难一些，文献 1 2 提出了两种填写表单的方法：一 是随机算法；二是普通词频算法( g e n e r i c f r e q u e n c y ) ；通过对比实验发现后者优于前者。 但是两种方法都有其应用的环境，也存在一定的缺陷。在h i w e 系统中，将表单元素中的 标签与l v s 表中的标签进行匹配，用最佳匹配表目的v a l u es e t 来填写表单，l v s 可以在 l v sm a n a g e r 模块的管理下，可以更新或添加新的表目，只是需要用一些l a b e l 和关联的 v a l u es e t 人工初试化l v s 表。本文第四章提出了一种启发式查询词选择算法，该算法能 从候选查询词中高效的挑选出最佳查询词，以最小的交互次数得到最大的覆盖率，提高了 检索效率。 1 2 系统设计 3 系统设计 考虑到h i d d e nw e b 的唯一入口是搜索表单，让爬虫自动完成h i d d e nw e b 抓取需要 解决3 个问题【1 1 。在抓取时，爬虫要能够识别出页面中的表单部分，然后“理解表单各 项标签的含义，然后选择有意义的查询词进行提交，最后抓取响应页面。为了提高抓取的 准确性，系统首先还要进行相关性评价，因此f h w c ( f o c u s e dh i d d e nw e bc r a w l e r ) 主 要有三个模块( 图3 一1 ) ：相关性评价，表单分析，分析提交。 图3 1f h w c 体系结构 f i g u r e3 - 1f h w ca r c h i t e c t u r e 相关性评价模块用来过滤掉与主题无关的页面，提高采集的准确率。表单分析模块用 来抽取页面中包含的搜索表单，并剔除无关表单。分析提交模块模仿用户行为，通过向站 点提交查询，获得响应页面然后分析，进行相关处理。 与现有的h i d d e nw e b 信息获取系统相比，本文提出的f h w c 增加了相关性评价模块， 改进了提交分析模块。这两个模块均是为了提高检索的准确性和效率。 3 1 导航模式 由于产生动态页面的方法多种多样，基于此因素仅考虑两种通过用户在w e b 站点上的 导航行为归纳出来的通用的导航模式。其形式化的定义如下： 定义1 ：一个导航模式被表示为一个五元组= ( p ，仃，p 。，t ) ，p 代表页面集， 代表页面间的转换机制集，盯代表p 转到尸的函数集，此函数表示用户从一 1 3 西安理工大学硕士学位论文 个页面转到另一页面的行为集，p 。p 是起始页面，且r 是p 的子集，代表用户 访问的相关页面集。 用一个有向图来代表导航模式，其中图中每个元素是p 中的一个点，顶点p ；与p ，之 间的边表示通过转化机制得到的p ；与pi 页面的一条路径。在w e b 站点上用户操作的每一个 特定序列称为导航。每一个导航序列代表导航模式中的一个实例。在w e b 站点设计中有两 种导航模式非常流行。第一种如图3 - 2 所示，用户从站点主页开始，填写搜索表单，然后 提交表单获取结果页面集。第二种增加了含有用来搜索提炼链接结果集的中介页面，从此 页面用户可以获取最终结果页面，如图3 3 示。 图3 - 2 一般导航模式图 f i g u r e 3 2g e n e r i cn a v i g a t i o np a t t e r n 图3 3 含搜索和提炼链接模式图 f i g u r e3 - 3s e a r c ha n dr e f i n en a v i g a t i o np a t t e r n 对于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 2 爬行问题形式化定义 理论上，查询关键词选择问题可以被如下形式化的定义：假设爬虫从站点下载的页 面集为s ( 如图3 - 4 所示) 用一个点来代表s 中的每一个页面，对于每个潜在的查询口，返回 的结果页面集可以认为是s 的一个子集。对于每个查询q ；都有一定的代价，如资源消耗量 等。在这种定义下其目标是通过最小的代价来寻找能覆盖最多点的查询。这个问题等价于 图论【4 6 】中集覆盖问题。 在此形式化定义中主要涉及两个问题。首先是，实际上针对每次查询q ，爬虫并不知 道将有哪些和将有多少页面被返回。即日i 返回的子集是事先不知道的。不清楚这个子集， 1 4 系统设计 爬虫将不能决定什么样的查询关键词将有最大的结果覆盖率。再一个是，集覆盖最优解问 题被认为是一个n p 难问题，目前还没有找到一个在多项式时间内解决此问题的有效算法。 图3 - 4 集覆盖的最优解问题 f i g u r e3 - 4as e t - f o r m a l i z a t i o no ft h eo p t i m a lq u e r ys e l e c t i o np r o b l e m 本文提出一种在可计算代价内近似最优解的次优解算法。尽管不知道对于每次查询q ； 将有多少页面被返回，综合实验观察本文提出一种查询选择算法，它可以预测将有多少页 面被返回。基于此信息查询选择算法，每次可以选择“最好的或最有希望的”的查询关键