（计算机软件与理论专业论文）基于表单的深度搜索技术研究.pdf

摘要 皇曼曼曼曼曼量曼曼! 曼曼曼曼曼曼蔓曼曼曼曼! 曼! ! ! 曼曼! 曼曼曼曼曼曼曼曼曼! 曼曼i 一一i 一一 o ! 曼鼍曼! 曼曼! 曼鼍 摘要 目前大多数搜索引擎仅仅搜索超链接可以搜索到的静态网页，而许多的重要 数据存放在w e b 的后台数据库中，它们需要通过表单查询的方式获取，相应的 网页称为隐藏网页。为了帮助用户获取更多的信息，本文讨论隐藏页面的搜索方 法，给出了系统架构，并讨论其中的关键技术。 本文首先分析了当前普遍采用的互联网信息搜索引擎的优缺点，比较通用搜 索与深度搜索的不同，提出了适合深度搜索的爬行策略，即利用链接分类、文本 分类进行聚焦爬行。并通过设置同一站点内停止搜索标准条件，对规则网站设置 路径学习，尽量找到含有表单的网页。 本文通过模拟用户访问深度网页的过程，开展了如下工作：首先，通过调查 研究，提出适合能快速有效地下载含有表单的网页的爬行策略；然后处理网页， 抽取出表单信息，将网页表单信息转换成程序可以理解的形式，即对表单进行建 模。其次，利用启发式规则和表单分类方法提取有用的表单。再次，对表单标签 和语义词进行提取，自动填写提交，找到需要网页。 本文充分利用表单的结构和文本信息，其中的分类器使用标签分类和表单周 围有用文字分类比较的办法。用c e n t r o i d 、k n n 、s v m 算法进行训练。实验表 明，表单周围文本分类效果好，用s v m 算法效果最佳。最后，对表单自动填写 的n a m ev a l u et a b l e 进行了一些讨论。 通过实验验证了表单分类和表单信息抽取的有效性。 关键词网页文本分类：隐藏网页；信息抽取；表单；名值表 a b s t r a c t 曼曼曼曼曼i 曼i 曼皇曼皇曼曼曼皂鼍! 曼曼鼍曼皇曼量曼! 曼鼍曼! 曼曼毫曼曼鼍 a b s t r a c t m o s to ft h es e a r c he n g i n eo n l yr e t r i e v ep u b l i ci n d e x a b l ew e b ( e i w ) w h i c hi s o b t a i n e db yh y p e r l i n k b u tt h ef a c ti st h a tw i t ht h ed e v e l o p m e n to fw e b ，m o r ea n d m o r ei n f o r m a t i o na r es t o r e di nw e b sb a c k s t a g ed a t a b a s e t h e s ed a t ac a nb er e t r i e v e d o n l yt h r o u g hh t m lf o r m ；t h e ya r ec a l l e dh i d d e nw e bp a g e i no r d e rt oh e l pp e o p l et o o b t a i nt h ei m p o r t a n td a t ai nt h ew e bd a t a b a s e ，w eh a v ea s y s t e mw h i c hc a ns e a c ht h e h i d d e nw e bp a g e s i nt h i s p a p e r , t h ea r c h i t e c t u r ei sp r e s e n t e d ，a n dt h ek e y t e c h n o l o g i e sa r ed i s c u s s e d f i r s t ，t h ec o m m o ns e a r c he n g i n e sa d v a n t a g e sa n dd i s a d v a n t a g e sa l ea n a l y s i s e d ， a n dt h ed i f f e r e n c eb e t w e e nc o m m o ns e a r c he n g i n ea n dh i d d e nw e bs e a r c he n g i n ea r e c o m p a r e d t h ep r o p e rs t r a t e g yw h i c hs u i t st oh i d d e nw e bc r a w l l i n gb yu s i n gl i n k c l a s s i f i e ra n dt e x tc l a s s i f i e ri sg i v e n t h i sc a na c h i e v ef o c u sc r a w l i na d d i t i o n ，b a s e d o nt h es p e c i f i cc h a r a c t e r i s t i c so ff o r m s ，t h en e w s t o p p i n gc r i t e r i at h a ti sv e r ye f f e c t i v e i n g u i d i n gt h ec r a w l e rt o a v o i de x c e s s i v es p e c u l a t i v ew o r ki nas i n g l es i t ei s i n t r o d u c e d i nt h i sp a p e r , t h ep r o c e s so fu s e r sa c c e s s i n gh i d d e nw e bi ss i m u l a t e d f i r s t ，f o r m s a r ec o n v e n e dt oa l lu n d e r s t a n d a b l ef o r mf o rp r o g r a m i tm e a n s m o d e l i n gt ot h ef o r m s e c o n d l y , t h eu s e f u lf o r m sa r ee x t r a c t e db yu s i n gh e u r i s t i cr u l e sa n df o r mc l a s s i f i e r a tl a s t ，f o r ml a b e la n dt h ec o n t e x to ff o r ma r ee x t r a c t e d t h er e s u l t sa r ef i l l e d i nt h e f o r m sa u t o m a t i c a l l yt of i n dt h eh i d d e nw e b p a g e w em a k et h ef u l lu s eo ft h es t r u c t u r ea n dt e x ti n f o r m a t i o no ff o r m s t h ec l a s s i f i e r i n c l u d e st h ec o o p e r a t i n go fl a b e lc l a s s i f i n ga n dt h ef o r ma p p e n d i xc o n t e x tc l a s s i f i n g w eu s ec e n t r o i d ，k n na n ds v m a l g o r i t h m t h ee x p e r i m e n t ss h o wt h a ts v m a l g o r i t h mh a st h eb e s te f f e c t t h r o u g ht h ee x p e r i m e n tw ev e r i f yt h ee f f e c t i v e n e s so ff o r mc l a s s i f i n ga n df o r m e x t r a c t i n g ， k e yw o r d sp a g et e x tc l a s s i f y ，h i d d e nw e b ；w e bi n f o r m a t i o ne x t r a c t ；h t m l f o r m ；n a m ev a l u et a b l e i i i - 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 虢刍砬嗍嘲妒 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：新签名羞嗍趔3 第l 章绪论 第1 章绪论 传统的搜索引擎仅仅搜索互联网上称为p u b l i c l yi n d e x a b l ew 曲 2 0 l ( p i w ，可 索引) 的信息，也就是静态页面。但是，大量有用的信息都存储在后台数据库中， 没有显式的网址索引，要想获取他们，只能通过提交表单才能实现查询。我们称 之为隐藏网页。研究表明【7 j ，目前d e e pw 曲大约有3 0 7 0 0 0 个站点，4 5 0 0 0 0 个 后台数据库，1 2 5 8 0 0 0 个查询接口，其信息资源仍在迅速增长，当前主要的搜索 引擎已经覆盖d e e pw e b 大约l 3 的页面，然而，在d e e pw e b 信息覆盖率上当前 搜索引擎存在技术上的本质缺陷，可见，通过填写表单获得后台数据库的信息是 很有意义的。 1 1 通用搜索引擎 搜索引擎几乎贯穿着整个互联网发展的历史。这种让网络使用者在信息汪洋 中去芜存菁、尽快找到自己所需信息的工具，已经成了互联网上不可缺少的重要 部分。 搜索引擎是互联网上最先商业化的一个应用服务，据美国互联网调查机构 p i a l p 公布的统计数据，网民对互联网搜索引擎的依赖性越来越大，搜索引擎如 今已成为继电子邮件之后的第二大网络应用。 美国知名网络评级机构尼尔森评级( n i e s e n n e t r a t i n g s ) 的调查报告称，超过一 半的网民在访问某一网站时并不会直接键入其网址打开，绝大多数情况下通过点 击搜索引擎得到的搜索结果进入。另据n i e l s e n n e t r a t i n g s 的最新数据显示，2 0 0 5 年1 2 月份全球6 5 个搜索引擎的搜索总量达5 0 多亿次，其中8 0 以上的搜索量 来自三大搜索引擎g o o g l e 、y a h o o 和m s n 。g o o g l e 已经占据美国在线搜索市场 的一半份额1 2 j 。 2 0 0 5 年百度公司的成功上市创造了中文搜索引擎的神话，2 0 0 5 年1 1 月1 7 日g o o g l e 公司的股价一度超过4 0 0 美元，这一切都说明互联网搜索引擎的巨大 需求和市场潜力，搜索引擎已经被业界公认为继广告、网络游戏、无线增值之后 互联网的第四桶金。 1 1 1 搜索引擎的发展历程 世界上第一个s p i d e r 程序，是m i t m a t t h e w g r a y 的w o r l d w i d e w e bw a n d e r ， 用于追踪互联网发展规模。刚开始它只用来统计互联网上的服务器数量，后来则 发展为能够捕获网址u r l ，我们认为所有网页都可能有连向其他网站的链接， 那么从一个网站开始，跟踪所有网页上的所有链接，就有可能检索整个互联网。 1 9 9 3 年底，些基于此原理的搜索引擎开始纷纷涌现。 北京工业大学丁学硕一l - 学位论文 l 、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 v a d i f i l o 共同创办了y a h o o ) y a h o o 开始 支持简单的数据库搜索。因为v h a o o 的数据是手工输入的，所以不能真正被归 为搜索引擎，事实上只是一个可搜索的目录。y a h o o 中收录的网站，因为都附有 简介信息，所以搜索效率明显提高。 4 、a l t a v i s t a ，这是是第一个支持自然语言搜索的搜索引擎，第一个实现高级 搜索语法的搜索引擎( 如a n d ，r 0 ，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 l y r e f r e s h 、多文档格式支持、地图股票词典寻人等集成搜索、多语 言支持、用户界面等功能上的革新，象a l t v a i s t a 一样，再一次永远改变了搜索引 擎的定义。 6 、百度的搜索服务主要定位在中文搜索，目前已经成为中国搜索届的领军 企业。2 0 0 0 年1 月1 日，公司创始人李彦宏、徐勇携1 2 0 万美元风险投资，从 美国硅谷回国，创建了百度公司。2 0 0 0 年5 月，百度首次为门户网站提供搜索 技术服务，之后逐渐成为最主要的搜索技术提供商之一。2 0 0 1 年8 月，发布 b a i d u c o r n 搜索引擎b e t a 版，从后台服务转向独立提供搜索服务，2 0 0 1 年1 0 月2 2 日正式发布b a i d u 搜索引擎。1 1 2 搜索引擎分类 按照工作方式，搜索引擎可分为： 1 、全文搜索引擎( g o o g l e 、a l t a v i s t a 、f a s v a l l t h e w e b 等) 2 、目录索引( y a h o o ) 3 、元搜索引擎( i n f o s p a e e 、d o g p i l e 等) 4 、垂直主题搜索引擎( 专业搜索引擎) ： 其中，垂直主题搜索引擎以其高度的目标化和专业化在各类搜索引擎中占据 了一席之地。比如象股票、天气、新闻等类的搜索引擎，具有很高的针对性，用 户对查询结果的满意度较高。服务垂直( 专业) 化是互联网发展的大势所趋，区别 于大而全的水平网站，垂直网站更注重在单一领域提供更专业、更精深的服务。 1 1 2 搜索引擎的工作原理 第一代的目录式搜索引擎主要是采用人工发现和整理信息，这里主要介绍第 二代的索引搜索引擎和元搜索引擎的工作原理【刀。 第1 币绪论 曼! ! ! ! 曼曼曼! 曼皇! 曼! ! 曼! 曼! 曼曼曼! ! 鼍曼! ! ! 曼曼鼍i | - - i |i i 一! ! 曼曼皇曼曼曼! 曼! ! ! 曼曼! ! ! ! ! ! ! 皇曼! 曼曼曼曼曼曼皇! 现在使用的搜索引擎都综合了上面提到的两种检索方式。搜索引擎通常由 三个子系统：信息采集、信息处理、信息检索组成，如图1 1 所示： 1 ) 信息采集 信息采集主要由一个网络蜘蛛组成。网络蜘蛛s p i d e r ( 也称为r o b o t 或c r a w l e r ) 实际上是一个基于w e b 的程序，它从一个初始网页集出发，自动地遍历i n t e r n e t 采集网络信息。当s p i d e r 收集某个h t m l 页面时，它会分析h t m l 标记结构来 获取指向其它页面的超级链接，然后通过既定的搜索策略选择下一个要访问的链 接。从理论上讲，如果为s p i d e r 指定一个适当的初始文档集和一个适当的网络搜 索策略，它就可以遍历整个网络。 2 ) 信息处理 信息处理主要是对网络蜘蛛提取的网页进行处理，创建索引后入库，以备 用户检索使用。处理网页的过程主要包括这几部分：文档特征向量提取、网页 筛选、相关度分析、文档分类和入库操作等等。 3 ) 信息检索 信息检索是搜索引擎和用户之间的接口。它首先获取用户查询条件并加以分 析，然后访问索引数据库对关键词进行匹配获得检索结果，最后按照相关度进行 降序排序处理后返回给用户。 图1 - 1 搜索引擎的基本工作流程 f i g u r e1 - 1w o r k f l o wo f s e a r c he n g i n e 1 1 3 目前搜索引擎存在的主要问题 通用搜索引擎的出现很大程度上解决了人们在互联网上查找信息的困难，但 也面临覆盖率低的问题。 在最基础层面上，通用搜索引擎使用名为c r a w l e r 的程序来查找和检索存储 北京t _ , l k 大学工学硕十学位论文 在全世界服务器上的网页。然而c r a w l e r 必须依赖在网页上找到的链接来查找其 他网页，如果一个网页没有被其它网页链接，网页的主人又没有把网址提交给搜 索引擎，搜索引擎就无法收录这些网页。或者网页主人有意设置口令保护、禁止 索引的网站标记。这些无法被索引的网页资源就成为网络的空白地带，也构成了 隐蔽网络中最基本的组成部分。 事实上，搜索引擎所面临的最大技术难题在于检索存储在数据库中的信息。 一般来说，搜索引擎c r a w l e r 很难找到数据库的接口和网关的页面，并且无法像 人一样与数据库进行交互，完成诸如输入密码进行登陆这样的动作，因此往往无 法发掘出隐藏在数据库界面下的丰富资源，这些网络可检索的数据库组成了隐蔽 网络中的大部分内容。 此外，一些以非普通的h t m l 格式存在的网页、动态网页、还有实时信息， 搜索引擎收录都存在技术问题。还有些非技术方面的原因，如经济制约。出于商 业考虑，索引非h t m l 文档格式的文件花费过多或更新实时信息数据库会耗费 太多的搜索引擎资源，网络公司不愿意索引这类网络信息。 1 2 深度搜索引擎 1 2 1 隐藏网络概念 隐蔽网络【l 】是一个与可见网络相对应的概念，最初由d r j i l le l l s w o r t h 于1 9 9 4 年提出，意指那些普通搜索引擎难以发现的信息内容。2 0 0 1 年，c h r i s ts h e r m a n 、 g a r yp r i c e 合著隐蔽网络：揭开搜索引擎看不到的信息源，其中对隐蔽网络的 定义为：虽然通过互联网可以获取，但普通搜索引擎由于受技术限制而不能，或 者经审慎考虑后而不作索引的那些文本页、文件或其他通常是高质量、高权威的 信息。隐蔽网络亦被称为深网、隐形网络或看不见的网站。 1 2 2 隐藏网络分类 1 2 2 1 不透明网络( t h eo p a q u ew e b ) 或灰色网络( t h eg r e yw e b ) 不透明网络【l 】是指搜索引擎可以索引但没有索引的网页，主要由以下几个因 素造成：( 1 ) 搜索深度，受经济因素制约，早期的搜索引擎基本上都只索引网站 主页等表层网页。虽然随着s p i d e r 爬行成本的降低，其搜索深度也在不断增加， 但还是会受到深度限定而无法爬行任何站点的任何网页，这样一来，一部分超过 其搜索深度但有价值的网页就成为了不透明网络；( 2 ) 搜索的最大数，即使在搜 索深度之内s p i d e r 爬行的网页数也有可能超过其最大容量。这样s p i d e r 就不得 不舍弃其中的一部分，这一部分也成为不透明网络；( 3 ) 搜索频率，互联网上的 信息日新月异。而搜索引擎s p i d e r 的爬行速度有限，大概为1 2 千万页天，这 第1 审绪论 样，在s p i d e r 再次光顾之前，新出现的网站( 页) 也就成为不透明网络。此外，链 接中断或未被链接的网页等也可能形成此类网络。 1 2 2 2 私人网络( t h ep r i v a t e w e b ) 私人网络川就是指含有个人的非公开信息、限制访问的网页，其形成原因主 要有：( 1 ) 网站口令的设置，目前许多网站需要注册并使用用户名和密码登录后 才能访问，而s p i d e r 无法获取密码自动完成输入内容，因此，这一部分内容搜索 引擎难以索引； ( 2 ) 知识产权的负面影响，有些网站出于保护知识产权或个人隐 私的考虑，会使用”r o b o t s t x t ”协议来阻止s p i d e r 的爬行，正如g o o g l e 公司的技 术主管c r a i gs i l v e r s t e i n 说的 这是他们的知识产权，他们的保护意识很强，不 愿意让我们进行搜索”，因此这部分网页对s p i d e r 来说也是不可见的；( 3 ) 不索 引 标签，有些网站如企业内联网等使用禁止索引的网站标记 ( n o n i n d e x m e t a t a g ) ，s p i d e r 自然无法索引，这一部分也就成为私人网络。 1 2 2 3 专有网络( t h ep r o p r i e t a r yw e b ) 专有网络【lj 是指只对注册用户( 免费注册用户和收费注册用户) 开放的网页， 这部分网页都需要用户输入用户名和密码，其资源才可被利用。机械式的搜索引 擎无法填表注册，当然也就无法索引。另外收费的商业在线信息服务商如d i a l o g 、o c l c 、s i r s 、i n f o t r a c 等，或是在线百科全书，对于未付费的用户来说也 是不可见的。 1 2 2 4 真正的隐蔽网络( c o m p l e t e l yi n v i s i b l ew e b ) 真正的隐蔽网络【l 】主要包括非h t m l 格式的文档、动态网页、实时数据及网 络数据库，其形成原因主要包括：( 1 ) 目前大部分搜索引擎只能索引h t m l ( h y p e r t e x tm a r k u pl a n g u a g e ) l 网页文档。h t m i 文档都有 h e a d ”和 b o d y ”两部分， 搜索引擎根据”h e a d ”来判断其为h t m l 文档并加以索引，而对于其它如p d f p p t 、 d o c 等格式的网页，搜索引擎的开发商出于成本等多种考虑而不加以索引，这样， 非h t m l 格式的网页内容都被深藏在信息海洋的海底。不过随着检索服务的逐 步完善，一部分搜索引擎可以索引多种格式的文档，如g o o g l e 现在已经可以检 索i m a g e 以及p p t 、p d f 、d o e 、p s 等格式的文档：( 2 ) 搜索引擎无法索引动态网页 ( d y n a m i c a lp a g e ) 及网络数据库。现在i n t e r n e t 上存在着海量的数据库资源，其中 很大一部分资源可以免费获取，但都是以数据库为后台，动态网页技术和数据库 技术相结合的方式组织资源。数据库根据用户输入的检索式返回符合检索要求的 动态网页，而s p i d e r 都是沿着超链漫游，根据超链提取新的u r l ，无法完成” 输入检索式”的动作，因此也就无法对其加以索引；( 3 ) s p i d e rt r a p ”。s p i d e r 一旦 陷入恶意的”s p i d e rt r a p 程序中就有可能陷入死循环而影响搜索引擎的正常工 作，因此搜索引擎都会限制s p i d e r 爬行此类网页而使之成为”漏网之鱼”，基于 北京t q k 大学工学硕：卜学位论文 脚本语言且u r l 中含有”? ”的网页就是此类代表。 1 2 3 深度搜索引擎特点 深度搜索引擎【3 3 ”】与通用搜索引擎的工作原理和主要技术大致相同：都是由 信息采集、信息处理、信启、检索和用户界面构成。不同之处在于深度搜索是针 对为某一特定领域、某一特定人群或某一特定需求提供的有一定价值的信息和相 关服务的专业搜索引擎。它只搜索特定的主题信息，是搜索引擎的细分和延伸， 是对网页库中的某类专门的信息进行一次整合，抽取出需要的数据进行处理后再 返回给用户。使查询结果的准确率、精确率大大提高。 深度搜索引擎的信息采集比通用搜索引擎较为复杂，需要根据一定的网页分 析算法过滤与主题无关的链接，保留与主题相关的链接并将其放入等待爬行的 也队列。然后，主题爬虫将根据一定的搜索策略从队列中选择下一步要抓取 的u i 也。重复上述过程，直到达到系统的某一条件时停止。在对网页进行中文 分词时，本深度搜索系统按照机械专业词典对网页进行分词。只切分网页中属于 机械行业的词语，忽略分词词典以外的词语。然后依据切分的结果，计算网页与 主题的相似度，最后对网页进行索引，存入数据库。 1 2 4 深度搜索引擎的优势 对h i d d e nw 曲的信息抽取【4 0 1 ，有着很大的商业前景，有许多商业网站提供 了获取h i d d e nw 曲部分信息的方法。如i n v i s i b l e w e b t o m ( 建立了一个包括约1o ， 0 0 0 个数据库的目录，这些数据库通过标准搜索引擎是无法获取的。b r i g h t p l a n e t t o m 则索引了大约4 0 ，0 0 0 个包含d e e pw 曲信息的数据库。这些商业服务都声称 他们采用了半自动的技术来索引d e e pw e b ，但是由于商业秘密，这些技术都没 有在公开的资料中进行探讨。目前国内还没有专门的文章对这方面的内容进行讨 论，国外有一些大学在研究中进行了很多有益的探索。 1 2 5 研究现状 目前h i d d e nw e b 大约有3 0 7 0 0 0 个站点，4 5 0 0 0 0 个后台数据库和1 2 5 8 0 0 0 个 查询接口。其信息资源仍在迅速增长，从2 0 0 0 年到2 0 0 4 年，它增长了3 7 倍。 h i d d e nw 曲内容分布于多种不同的主题领域。 国外对h i d d e nw e b 进行了很多的研究，最著名有h i d d e nw e be x p o s e r ( h i w e ) 1 ，这是斯坦福大学研究的一个项目，设计了一种可以抽取h i d d e nw e b 内 容的c r a w l e r 。此系统的工作过程是，c r a w l e rm a n a g e r 管理整个爬行过程，然后 把爬下的网页交给p a r s e r ，它不仅要抽取链接，把他们加入链接队列，而且，把 有表单网页交给f o r ma n a l y z e r 处理，f o r mp r o c e s s o r 先从页面中抽取出表单，再 第l 章绪论 ! 曼! 曼曼! 寰曼! ! 曼! 曼! i 一一； 一 ：i i：i ! ! ! 从预先准备好的数据集中选择数据自动地完成表单的填写，然后将合成的u i u 提交c r a w l e rm a n a g e r 去下载相应的结果页面。由于需要系统自动完成表单填写， 所以要求用户事先准备相应的表单数据集。h i w e 在人工帮助下用l v s 表协助填 写表单，它是面向特定的领域使用的，l v s 表的设计是表单提取的关键。另外， 哥伦比亚大学的p a n a g i o t i sg i p e i r o t i s 等人在文章中1 ，r 讨论了自动地将w _ e b 网 页所连接的后台数据库进行分类的方法。它首先使用机器学习技术生成一套基于 规则的分类器( c l a s s i f i e r ) 。然后将分类器转变成查询u r l ，对后台数据库进行查 询，计算查询结果。他们的算法最后根据查询结果对数据库进行分类，但只针对 文本数据库的分类上面。而大量的h i d d e nw e b 内容是非文本的。 国内对h i d d e nw e b 方面的研究比较少，还处于学习、跟踪和探索阶段。国 内研究单位及相关文献非常少。上海交通大学宋晖等人提出基于标记树的对象抽 取( t a g t r e e b a s e do b j e c te x t r a c t i o n ) p 1 方法自动地从w 曲页面中抽取h i d d e nw e b 信息，然后以对象的形式表示出来抽取的信息，保存起来，给出基于表单对象的 查询算法，用户可以通过提供需要查找的对象各种属性来找到提供相应服务的 w e b 页面。另外苏州大学的郑冬冬等人也对d e e pw e b 的访问进行了相关的研究， 在 爬虫研究与设计”卜1 一文中提出使用启发式规则集和领域本体知识库来自动 发现相关表单，填写表单，同时识别和收集相关结果页面。 目前开发的商业i n v i s i b l ew e b 搜索引擎【4 l j k r u g l e 是为开发者设计的搜索引擎。它可以很方便的搜索到技术信息、源码 并回答代码相关的技术问题。它可以从开放源码库中存档邮件列表、b l o g 和网页 中获得代码样本提供搜索。并且支持标签，可共享代码和搜索结果集合等。从主 打优势来看，其在信息抽取上优势比较明显，这也是现在很多深度搜索试图发展 的基础，比如酷讯，他们面向的用户群相对比较小，k r u g l e 力图帮助程序员快速 的解决他们的问题或获得相关信息，k o d e r s 也是这样，专注一域也许能成就一 番天地。 l i v e p l a s m a 是个提供可视音乐和电影资源搜索的引擎，可检索的资源涵盖 了乐队、艺术家、电影、演员和导演等等，界面支持多语言选择。它以基于f l a s h 的可视化数据检索为特色，并运用了思维导图( m i n dm a p p i n ) 模式来提示信息 的关联，而且它还是一个推荐式的引擎，能够发现相似的音乐和电影给人们浏览。 t r u v e o ，p a n d o r a ，l a s t f m 也提供类似的服务。 q u b e 提供点击一次即可得到搜索结果的桌面应用，不需用浏览器切换程序， 甚至不需要输入关键字。它即时搜索已存在于屏幕上的( 或手动输入的) 任何文 本并快速返回结果，与此同时有实时拼写检查、历史日志、字典结果等等增强搜 索功能，所有这些都不会有任何操作性能损害，q u b e 是e b r a h i me z z y s 的公司。 北京丁业大学工学硕十学位论文 ! i i ；一i o i 曼曼曼曼曼! ! 曼! 曼! ! 曼! ! 曼! ! 曼! 曼! 曼曼! 苎曼! ! 曼曼! ! ! ! 曼曼皇曼曼曼! ! 曼! 曼曼皇曼曼! 皇! 曼皇 - z o o m i n f o o 为人们和他们的联系信息搜捕网页( 公司网址、新闻发布会、电 子新闻服务、证管会申报和其它在线公共信息) 。它编制有关个人公司的简明摘 要，并以组织好的形式发表出来。如果你选择成为他们的客户还可以享用社会网 络工具。随着w e b 普及和增长，专门的搜索引擎是一个有意义的需求，然而传 统搜索引擎，比如g o o g l e 已经包含巨大的相似信息，专门的搜索引擎能处理这 些数据并且提供一个能充分理解的格式。z o o m i n f o o 将信息采集发挥到难以想象 的境界。 c o l l a r i t y 称为个性化搜索引擎，是因为它会根据你的搜索习惯来给出相应的 搜索结果。在c o l l a r i t y 中输入关键词时，搜索框下面会出现实时提示，提示类别 分为个性化、社区和全球。也就是说，你可以查看符合你自己习惯的搜索结果， 也可以在线查看社区或大众化的搜索结果。 c h a c h a 提供图书馆实时参考咨询服务，由s c o t tj o n e s 创办，人称m r j o n e s ， 语音邮件以及现在流行的i p o d 和i t u n e s 音乐数据库中的某几项技术都和他有关。 他所创建的c h a c h a 也是个搜索引擎，能提供自动化的搜索结果，同时，通过内 嵌式的i m 工具，能实时地向问题指导者提问进行咨询，这些所谓的问题指导者 都是网站招募的”打工者”一一具有特定专长经验( d o m a i n - s p e c i f i ce x p e r i e n c e ) 的人，他们会通过解答问题得到网站付给的酬劳。 w o n d i r 也是类似的提供图书相关信息检索和咨询的平台，它的创始人 m a t t h e wk o l l 则在网络还少有人知的上个世纪9 0 年代初期，就开发了一套文本 搜索引擎p e r s o n a ll i b r a r ys o t t w a r e ( p l s ) ( 1 9 9 8 年卖给了著名的a o l ) ，9 0 年 代中期，他又第一次提出了i n v i s i b l ew e b 的概念。2 0 0 4 年8 月创建了w o n d i r ， 它的最初理念是将元搜索技术( m a t a s e a r c h ) 、深层搜索( d e e ps e a r c h ) 技术以及 成百上千的由图书馆员开设的a s k a 的数字参考服务结合起来，形成一个用 m a t a s e a r c h 搜索表层网( o p e nw e b ) 、用d e e ps e a r c h 搜索深层网( i n v i s i b l ew e b ) 、 用人( 图书馆员以及志愿者) 来进行实时交流，从而将表层网、深层网和人力三 个方面的资源结合成一个社区( c o m m u n i t y ) 的知识发现、共享、交流服务。 1 3 本文的组织结构 本文将按照以下结构进行组织： 第一章为绪论，主要介绍课题的基本概念，背景和研究现状，研究内容和研 究意义。 第二章介绍基于表单深度搜索总体架构。 第三章介绍网络爬虫原理，为了尽早尽快的找到含有表单网页，提出适合深 度搜索的爬行策略。 第四章介绍表单抽取相关知识。 8 一 第1 章绪论 ! 曼曼曼! 曼! ! ! ! 曼! 曼! ! ! i 一= ；i；i e l = = i 。皇曼! 曼曼曼! 曼曼曼曼! ! ! 曼曼曼! ! 曼! 曼! 曼! 鼍 第五章用标签分类和表单周围有用文字分类的办法对表单分类，识别有用表 单，用c e n t r o i d ，k n n ，s v m 算法进行分类，最后做实验验证。 第六章提取表单信息，自动提交，做实验验证。 最后对全文进行小结，并对今后的研究工作进行展望。 北京i f k 大学丁学硕十学位论文 2 i 概述 第2 章基于表单深度搜索总体架构 h i d d e nw e b 搜索的关键问题是根据目前网络提供这种网页的访问途径，由系 统根据有关信息生成相应的查询表单，通过提交这些表单来实现查询。所以表单 的提取分析成为关键。图2 1 是用户填写表单的工作流程，用户下载到网页以后， 浏览网页，然后填入相应查询信息，得到查询结果页面。图2 2 是本系统自动填 写表单的工作流程，下载到网页以后抽取其中的表单，提供一些规则识别有用的 表单，然后让机器自动填写、提交，得到相应的查询信息【3 羽。 图2 - 1 用户和表单的交互 f i g u r e2 1i n t e r a c t i o nb e t w e e nu s e ra n df o r m 含有表单网页 返回网页 图2 - 2 抓取器和表单的交互 f i g u r e2 - 2i n t e r a c t i o nb e t w e e nu s e ra n dc r a w l e r 第2 章基于表单深度搜索总体架构 2 2 基本原理 w e b c r a w l i n g t l 6 1 7 】主要是指通过从w e b 页面之间的链接关系，从w e b 上自 动的获取页面信息，并且随着链接不断向所需要的w e b 页面扩展的过程。实现 这过程主要是由w e b 信息采集器( w e b c r a w l e r ) 来完成的。根据应用习惯的不同， w e b 信息采集器也常称作w e bs p i d e r 、w e br 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 在同一网站内部，或是否在 同一子目录下) ，符合则将他们继续放入到待采集队列里，然后重复上面的过程， 直到采集器根据自己的策略停止采集。 h i d d e nw e b 与般的搜索不同就是对动态网页的搜索，其工作流程也就是增 加了对表单的提取分析【2 4 t2 6 - 3 0 3 1 1 。 为了清晰起见，图2 3 和图2 - 4 对比一下本文设计的c r a w l e r 与一般的c r a w l e r 的不同。 图2 - 3 一般爬行器 f i g u r e2 - 3c o m m o nc r a w l e r 图争4 深度爬行器 f ig u r e2 - 4h id d e nw e bc r a w l e r 北京工业大学= i 二学硕十学位论文 2 3 基本结构 如图2 5 所示，h i d d e nw e b 系统基本上可以划分为以下主要三个模块：c r a w l e r d o w n l o a d e r ，f o r ma n a l y z e r ，f o r mp r o c e s s o r ，图中的箭头表示数据走向。 图2 5 系统框架图 f i g u r e2 - 5a 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 ( 1 ) c r a w l e rd o w n l o a d e r 负责抓取网页。在某个站内，抓取的网页不仅有 通常的超链接下载( 用g e t 方法) ，而且有通过填写表单组成的值下载的网页( 用 g e t 和p o s t 两种方法下载网页) 。它从u r lq u e u e 中获取种子链接，然后抓取网 页，把抓取到的网页放入s t o r e h o u s e ，然后把种子u r l 放入u r ll i s t 中，其中， u r ll i s t 存放已经搜索过的u r l ，u r lq u e u e 存放待搜索的u r l 。 ( 2 ) f o r mc l a s s i f y 负责在抓取到的网页中抽取表单，利用规则初步剔除无 用表单，然后用表单分类器识别有用表单，最后把符合要求的表单放入f o r m l i s t 。 ( 3 ) f o r mp r o c e s s o r 对f o r ml i s t 中的表单进行分析，产生新的u r l 放入 u r l q u e u e 中，在自动填写表单时，需要借助名值表。所以要根据抽取的表单不 断丰富名值表。 2 4 小结 本章分析用户填写表单与系统模拟自动提交的区别，主要区别在于用户可以 用眼识别表单是否为所需要的表单，并且自动填写信息进行提交，而让系统自动 识别表单，并且自动填写提交却很困难，最后比较一般搜索流程与深度搜索流程 不同点，借鉴一般搜索的原理，给出了适合深度搜索的总体框架。 第3 章网页抓取器 本章主要介绍h i d d e nw e b 系统三个模中的c r a w l e rd o w n l o a d e r 模块。下载网 页分两部分，一部分是实验网页下载，通过超链接爬行网页，用g e t 方法提交； 一部分是下载表单提交的网页，通过表单分析，抽取后，组成的名值对，用p o s t 方法提交。 为了尽快的找到含有表单的网页，本文进行了相关调查研究，对超链接下载 部分，提出了一些适合深度搜索的方法，做了简单的实现，为以后表单分析，提 交，下载做铺垫。 3 1 网络爬虫原理 随着互联网规模的飞速增长，高效、准确地获得包含用户所需信息的网页， 日益成为需要迫切解决的问题。搜索引擎是解决这问题的一个有效方法。搜劈 引擎中最关键的一部分是网页搜索器，它由一个爬虫( c r a w l e r ，又称网页抓取器、 网络机器人、网络蜘蛛) 程序组成。所谓爬虫程序是指会自动地、永不停止地在 网络上搜索网页的程序。现在基于关键字查询的搜索引擎已经不能满足用户对搜 索的结果更准，搜索范围更广的要求。因此新一代的搜索引擎智能搜索引 擎呼之欲出。所谓智能搜索引擎就是一种分类细致精确、数据全面深入、更新及 时的面向主题的具有智能化的搜索引擎。那么新一代的搜索引擎要求爬虫等程序 能够更快更新网页，更广地搜索网页。所以做好爬虫这类程序将是搜索引擎能否 向前发展的关键。 根据抓取过程爬虫程序主要分为三个功能模块：一个是网页读取模块主要是 用来读取远程w e b 服务器上的网页内容；另一个是超链分析模块，这个模块主 要是分析网页中的超链接，将网页上的所有超链接提取出来，放入到待抓取u r l 列表中；再一个模块就是内容分析模块，这个模块主要是对网页内容进行分析， 将网页中所有h t m l 标签去掉只留下网页文字内容。 3 2 网络信息搜索策略 互联网上的信息太多，即使功能强大的爬虫程序也不可能搜集互联网上的全 部信息。因此，爬虫程序采用一定的搜索策略对互联网进行遍历并下载文档。 3 2 1 宽度优先搜索策略 宽度优先搜索策略( 又称广度优先搜索) 是最简便