（模式识别与智能系统专业论文）海量web信息智能获取技术研究.pdf

中国科学技术大学硕士学位论文 摘要 摘要 随着w e b 信息的爆炸性增长，如何及时有效地从网络上查找到真正所需要 的信息，已经成为研究者所面i 临的难题。搜索引擎技术在这种背景下应运而生 并得到了快速发展。但越来越多的应用要求搜索对象，不应仅局限于静态页面， 还必须包括更多数量的动态页面。 本论文的研究围绕着网络智能搜索和获取问题展开，主要着眼于深层数据 源的发现技术，封装器半自动化构建方法，以及移动a g e n t 应用于搜索领域的 若干问题研究。基于本文思想所开发的系统，在实际应用中，取得了较好的效 果。归纳起来，本文主要工作和贡献如下； l 对目前主流的搜索引擎技术做了广泛的调查和总结，包括基于静态页 面的搜索、基于主题的搜索和元搜索。 2 提出了一种网络深层数据源发现的方法。在表单模型的基础上，使用 迭代尝试填单并分析判断返回页面的方法，发现网上的深层数据源， 且准确提取页面中的动态数据区域。 3 实现了网络信息抽取的方法。分析了应用于无结构化半结构化资料抽 取的三种方法：自然语言处理、统计学习、有限状态转换机。基于海 量半结构化页面信息抽取速度和效果的考虑，本文着重介绍了基于有 限状态转换机的网络抽取技术，并将它应用于所设计的系统之中。 4 研究了移动a g e n t 应用于搜索的若干问题。移动a g e n t 技术是一个全 新的搜索计算模型，代表了传统搜索技术发展的方向。本文着重研究 了移动a g e n t 应用于智能搜索领域需要解决的若干问题。 关键词：搜索引擎；信息抽取；移动a g e n t ；智能搜索；抽取规则 中国科学技术大学硕士学位论文 摘要 a b s t r a c t c o n f r o n t e dw i t ht h eh u g es c a l eo fo n l i n ei n f o r m a t i o n i th a sb e e na c r i t i c a ip r o b l e mh o wt of i n dd e s i r a b l ei n f o r m a t i o ne f f e c t i v e l ya n dt i m e l y r e c e n t l y , s e a r c he n g i n e ( s e ) w h i c hi se x p e c t e dt os o l v et h ep r o b l e mh a s b e e nt h ef o c u so fm a n yr e s e a r c h e r s b u tm o r ea n dm o r ea p p l i c a t i o n se x p e c t m o r er e s o u r c e ，n o to n l yt h es t a t i cw e bp a g e s b u ta l s ot h eh u g ed y n a m i c p a g e s w h i c hi si n v i s i b l et ot h et r a d i t i o n a is e a r c he n g i n e t h ec r a w l e ro ft r a d i t i o n a is e a r c he n g i n es u r f st h ei n t e m e tb yh y p e r l i n k s t h ed e e pw e bc r a w l e rs h o u l db e c o m es m a r t e r , s ot h a ti tc o u l dk n o wh o wt o 俐i naf o r n la n dh o wt oa n a l y z et h es e a r c hr e s u l t ai o to fd e e pd a t as o u r c e w i l ib ef o u n da n dai o to fs t r u c t u r eo fd y n a m i cd a t aa r e aw i l lb ee x t 阳c t e d w h e nt h ed e e pw e bc r a w l e rs u r f st h ei n t e r n e ta n di t e r a t i v e l yf i lj | nt h ef o r n l s a c c o r d i n gt ot h er e q u i r e m e n t so fi n t e l l i g e n c es e a r c ha n di n t e l l i g e n c e a c q u i s i t i o n t h i sd i s s e r t a t i o nm a i n l yf o c u s e do nh o wt of i n dd e e pw e bs o u r c e h o wt og e n e r a t ew r a p p e r ss e m i a u t o m a t i c a l l y ，a n dh o wt oa p p l ym o b i l ea g e n t t os e a r c he n g i n e t h em a i nw o r ka n dc o n t r i b u t i o n si nt h i st h e s i si n c l u d e ： 1 s u m m a r i z e da n da n a l y z e dt h ep o p u l a rt e c h n i q u e so fs e a r c he n g i n e ， i n c l u d i n gs t a t i cw e bs e a r c h f o c u s e ds e a r c ha n dm e t a - s e a r c h 2 am e t h o dl sp r o p o s e dt os o l v et h ep r o b l e mo ff i n d i n gt h ed e e pw e b t o p i c a lr e s o u r c e p r o p o s e dam e t h o do ff i l l i n gt h ef o r m ，a n a l y z i n gt h e r e s u l t ，a n de x t r a c t i n gt h es t r u c t u r eo fd y n a m i cd a t aa r e a 3 a na p p r o a c ho fw e bj n f o r m a t i o ne x t r a c t i o ni s d e s i g n e da n d i m p l e m e n t e d s of a ra st h ei n f o r m a t i o ne x t r a c t i o ni sc o n c e r n e d s e v e r a ik i n d so fa p p r o a c h e sa r ei n t r o d u c e d e s p e c i a l l yt h ef i n i t es t a t e t r a n s d u c e r 4 s o m ep r o b l e m sa n ds o l u t i o n so fm o b i l ea g e n ta r ep r o p o s e d m o b i l e a g e n ta n dj t sa p p l i c a t i o n i nl h ed i s t r i b u t e di n f o r m a t i o ns e a r c h i n g s y s t e mi san o v e im o d u l e w h i c hg u i d e st h es e a r c hs y s t e m st r e n do f n e x tg e n e r a t i o n k e y w o r d ：s e a r c he n g i n e i n f o r m a t i o ne x t r a c t i o n m o b i l ea g e n t ，i n t e l l i g e n c e s e a r c h ，e x t r a c t i o nr u l e s n 中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究 工作所取得的成果。除已特别加以标注和致谢的地方外，论文中 不包含任何他人已经发表或撰写过的研究成果。与我一同工作的 同志对本研究所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权， 即：学校有权按有关规定向国家有关部门或机构送交论文的复印 件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：是差星 纠年多月1 日 中国科学技术大学硕士学位论文海量w e b 信息智能获取技术研究 第一章绪论 这一章将介绍与本论文研究工作有关的一些基本背景情况。主要内容包括： 提出问题的背景，拟要研究解决的问题，有关应用的发展情况，以及本论研究 工作的基本内容，最后还介绍了本论文内容的组织情况。 1 1 问题的研究背景 自九十年代初开始，在不到二十年时间里互联网就己发展成为经济、社会、 文化、教育以及娱乐等各方面的重要组成部分，已成为我们工作和生活中不可 或缺的一员。互联网发展成为各种信息发布和接受的共享平台，目前各大传统 产业无一不在积极使用互联网。在信息新时代，及时有效处理互联网上的海量 信息，能把握先机，创造先机发展壮大：反之，就有可能被汹涌的信息化大潮 吞没。 互联网上流通的信息量正呈现爆炸性的增长势头。2 0 0 7 年1 月2 3 日，中国 互联网络信息中心( c n n i c ) 发布第1 9 次中国互联网络发展状况统计报告。 报告显示，截至2 0 0 6 年底，我国网民人数达到了1 3 7 亿，占中国人口总数的 1 0 5 。估计仅我国网站数约为8 4 3 万个，拥有网页总数约有4 4 7 亿个。据 c n n i c 调查显示目前网民选择获取信息的主要途径，为网络4 7 4 ，电视 3 0 6 ，报纸1 5 7 ，其他媒体所占比例更少 互联网的基本功能就是，信息的发布与信息的接受。任何人都能够通过互 联网在全世界范围内获取到网上所提供的各种信息，并且也可以将自己的内容 方便地添加到互联网上，供其他网民无偿或者有偿获取。目前互联网上所有的 信息流量都是紧紧围绕着这两个方面展开。如：商家产品及服务信息的发布， 以及互联网用户的信息搜索与信息获取等。为帮助广大互联网用户有效地使用 互联网上的浩瀚信息，众多新技术新思想不断涌现。从最初的网站黄页开始， 到互联网门户站点，到如今大行其道的搜索引擎，再到正处初始阶段的垂直信 息搜索服务。垂直搜索较之传统搜索弓l 擎，专业数据量更大，粒度更小，结构 化更好，对用户更加有用。以下就农业主题举一个例子：如何从各大农业门户 网站主页出发，准确有效地搜索出用户所需要的涉农数据( 包括时序数据信息) 。 一搜索出各大农网上所发布的每日价格信息。 - 搜索出各大农网上所发布的供求信息。 中国科学技术大学硕士学位论文 绪论 - 搜索出各大农网上所发布的农业新闻和农业技术。 搜索出各大农网上的图片视频信息。 目前的互联网信息搜索与获取技术，包括有关的智能搜索与获取技术方法 的研究成果，尚无法有效解决以上所述的需求问题。具体就是：如何从多个主 题网站出发，用智能学习方法自动搜索与获取知识，然后基于此知识，完成对 网站所需要信息的搜索与抽取工作。 1 2 基本研究情况 目前人们从网上获取信息的工具主要是浏览器，而获取的方式通常有以下 三种方式：第一，直接向浏览器提交网站主页地址，例如h t t p ：w w w u s t c e d u c n ： 第二，通过浏览门户网站，随机冲浪或者按目录浏览，来寻找到所感兴趣的信 息；第三，通过提交关键词给搜索引擎，再从一堆返回结果中查找最贴近的搜 索记录。这三种获取方式都是有一大批使用用户：第一种方式应用于想全面了 解此网站的用户；第二种应用于读报式的信息获取；第三种适用于零星了解所 关心内容的用户，但不知道哪里能够找到相关信息，通过搜索引擎技术提供一 个相关内容网址及摘要集合，从中找出自己最需要的内容。前两种方式涉及到 的技术层面东西比较少，本节就搜索引擎技术，详细阐述当前信息搜索和获取 方向的研究情况。 1 2 1 网页通用搜索方法 在互联网发展的初期，只有有限的数量的网站，人们凭着记忆就能很容易 地直接访问感兴趣地网站。但随着互联网的兴起、流行，人们所面对最大的挑 战不再是数据量的缺少，而是如何从海量数据中找出自己所需要的数据。数据 的越来越多，这种需求就变得越来越迫切，靠人工浏览方式来寻找变得不合时 宜，于是搜索引擎技术诞生了。1 9 9 4 年，真正意义上的互联网搜索引擎l y c o s 面世。而当y a h o o 搜索引擎出现以后，网民开始熟悉并使用搜索引擎来找寻自 己的信息。到今天，g o o g l e 、b a i d u 等搜索引擎被广泛认知，搜索引擎进入了他 的黄金时代。当前，互联网通用搜索引擎成为互联网上获取信息的基本技术和 工具。根据c n n i c 的统计报告i 我国搜索引孥使用频率是仅收发邮件和浏览新 闻业务排列第三位，高达5 1 5 l l l 。按照信息获取方法和服务提供方式的不同， 2 中国科学技术大学硕士学位论史海量w e b 信息智能获取技术研究 搜索引擎可以分为以下三大类： 1 ) 目录式搜索引擎：以人工方式或半自动方式搜集信息。由人工形成网站摘 要，并将该网站归划为已定分类系统中某类，提供目录浏览和直接检索服 务。目录索引虽然有搜索功能，但严格意义上算不上是网页的搜索，而是 网站搜索。用户完全可以不用进行关键词( k e y w o r d s ) 查询，仅靠分类目 录也可找到需要的网站。该类搜索引擎因为加入了人的智能，所以信息准 确、导航质量高，缺点是需要人工介入、维护量大、信息量少、信息更新 不及时。这类搜索引擎的代表是：y a h o o ，l o o k s m a r t 等。 2 ) 网页搜索引擎：由一个称为爬虫( c r a w l e r ) 的机器人程序以某种策略自 动地在互联网中发现和搜集信息，由索引器为搜集到的信息建立索引，由 检索器根据用户的查询输入检索索引库，并将查询结果返回给用户。该类 搜索引擎的优点是信息量大、更新及时、毋需人工干预，缺点是返回信息 过多无关信息，用户必须从结果中进行筛选。这类搜索引擎的代表是： g o o g l e 、a l t a v i s t a 、e x c i t e 、l y c o s ；国内代表为：百度、“天网”等。 在没有特殊说明情况下，本文所讨论的搜索引擎都是指这种网页搜索引 擎。 3 ) 元搜索引擎：这类搜索引擎自己并不收集网站或网页信息，也没有自己的 数据，而是将用户的查询请求同时向多个搜索引擎递交，将返回的结果进 行汇集和处理返回给用户。这类搜索引擎的优点是可以优化现有搜索引擎 的返回结果，做迸一步精细处理；缺点是不能够充分提升搜索引擎的性能 和效率。这类搜索引擎的代表是w e b c r a w l e r ，i n f o m a r k e t 等。 网页搜索引擎就是全文索引搜索技术，该技术来源于信息检索( i n f o r m a t i o n r e t r i e v a l ，i r ) 领域。其所处理的网页与网页内容无关，故被称为通用搜索引擎。 该搜索技术主要g q _ - - 个功能模块，其分别是：网页信息获取、网页预处理和在 线查询服务。 _ 网页信息获取。 搜索引擎是一个网络应用软件系统，工作在网上动态变化的海量网页数据 集上，并且这些网页不会主动送到系统中来，而是需要由系统去抓取。在网络 比较通畅的情况下，下载一篇网页大约需要1 秒钟，如果等到用户查询时候才 去抓取成千上万的网页，一个个处理分析，显然不能满足用户要求。所以大规 中国科学技术大学硕士学位论文 绪论 模的搜索引肇服务的基础都是建立在一批预先搜集好的网页。 具体的搜集过程是将w e b 上的网页集合看成是一个有向图，搜集的过程从 给定起始u r l 集合s ( 或者说“种子”) 开始，沿着网页中的连接，按照广度优 先、或深度优先、或者其它什么策略遍历整个图，不停地从s 中删除访问过的 页面u r l ，建立连接，发送请求，接收请求下载相应的网页，在存储此页面同 时解析出网页中地超链接u r l 。将未访问过的那些u r l 加入到集合s 中，直到s 未空或者某个预定条件满足。下载下来的页面就是信息获取的结果，也是搜索 引擎技术的计算基础。整个过程就像一个蜘蛛( s p i d e r ) 在互联网( w e b ) 上爬 行( c r a w l ) 。其实真正的系统都是多个“蜘蛛”同时爬。但研究告诉我们，传 统搜索引擎往往只对互联网海洋上的表层网页数据感兴趣，并且像撒网捕鱼一 样将那些静态页面下载收集到自己服务器上处理，其过程如图卜l 所示。 一静嚣他5 图1 一l 互联网表层网页模型 理论上搜索引擎c r a w l e r 是可以遍历互联网有向图的，但是实际上受计算 资源和时间的限制，任何搜索引擎都不可能将w e b 上的网页搜集完全，通常都 是在某个条件满足时结束搜集过程。因此，能优先搜集到那些重要网页的策略 是好的策略。研究表明“，广度优先策略所得到的网页集合要优于深度优先所 得到的集合。这是因为互联网上重要的信息，一般位于容易被访问的位置。 一网页预处理： 得到海量原始网页集合，只是搜索引擎的第一步，一个合适的数据结构是 查询子系统工作的核心和关键。现行最有效的数据结构是“倒排文 睾”：倒排文 件是用文档中所含关键词作为索引，文档作为索引目标的一种结构；利用这样 的数据结构，由用户输入的关键词，软件能够快速找到那些包含这些关键词的 文档，并且能够在此基础上做与或非等逻辑运算，大大提高查询效率和灵活度。 预处理就是包含从上一步所形成的网页集合，到形成俩捧文件的处理过程。网 页预处理具体包含四步：关键词提取、重复网页的消除、链接分析和网页重要 程度计算。 关键词提取。能够代表一篇网页的内容，最重要的就是用所含的关键词( 特 征值) 。由于岍札文档的多样性，许多网页在内容上比较随意，不仅文字 中国科学技术大学硕士学位论文 海量w e b 信息智能获取技术研究 不规范，往往还有大量与主题正文无关的信息出现( 如广告条，导航条， 版权说明等) 。研究表明。在提取关键词之前。去除掉这些噪声数据，非 常有利于正文提取的质量和精度的提高。对于中文网页，就是利用中文分 词软件，将一篇网页正文切分成很多词，同一个词可能在一篇网页中多次 出现。去掉停用词后，一篇网页有效词语数量大约在2 0 0 左右。 重复网页的消除。数字化和网络化的信息发布平台为网页的复制和转载带 来了便利，天网统计表明。网页的重复率大约为4 。对于用户在网上冲浪 的体验来说，这使得用户接受同一信息的机会增大了3 倍，是件好事：但 对搜索引擎来说，无意义缝消耗了计算资源，只要提供一个就够了。假设 内窖完全相同的网页为镜像网页，主题内容相同的网页为转载网页，再假 设镜像网页是转载网页的一个特例。则所谓网页消重就是指如何去除掉网 页集合中的转载网页的过程。几乎所有的消重算法都是基于这样一个基本 思想：为每个文档计算出一组指纹，如果两个文档拥有一定数量相同的指 纹，财认为这两个文档内容重叠性比较高，二者转载可能性比较大。 各种具体算法在选择计算文档指纹以及如何计算指纹相似度上有较大 的差别。举一个例子，文献 4 1 采用了一种对全文分段签名的算法。这种算 法把一篇网页按照一定原则分成n 段，然后对每一段进行数字签名计算出 其指纹，于是每一篇文档就可以用n 个指纹来表示。对于两篇文档，当它 们有n 个签名中有m ( 阀值) 个相同时，慰认为它们是相互转载的网页。 链接分析。对于纯文本文档来说，系统面对的仅仅是内容文字信息，所能 计算依据也只是内容所包含的关键词集合，以及这些关键词在文档中出现 的频率之类的统计量。而对h t m l 文档来说，所能使用的信息除了这些， 还有那些浏览时不可见的标签链接。这些标签是用于指示浏览器如何显示 内客，这些不同类型的显示方式也反映了被标签所包围的信息强弱程度。 如( h 1 和 之间的信息很可能比在( h 5 和( h 5 之间的信息更加重要。 g o o g l e 提出了两种重要改进来提高对网页描述的精度，以此来帮助改 进信息检索的质量。一个是p a g e r a n k 技术，另一个就是充分利用网页中 链接文字信息( a n c h o rt e x t ) 来描述所指向网页的内容。例如网页b 里 面所攒述的都是是“农业新闻”，但是b 里面并不见得就一定有这个关键 词，仅靠其自身关键词分析的搜索引擎是不能优先返回此页面。但是有另 一网页a 正用“农业新闻”作为链接信息指向该网页，则能够很好利用链 接信息的搜索引擎应该能够最优先返回网页b ，从而满足用户的搜索需求。 中田科学技术大学硕士学位论文绪论 网页重要程度计算。搜索引擎实际上追求的是一种统计意义上的满意，按 照人们在科技文献重要性的评估方式，核心思想就是“被引用多的就是重 要的”。在浩瀚的网页数据库中，每张网页都缺乏足够让人信服的自我描 述的能力，而被众多链接所指向的网页往往是重要的。g o o g l e 创立的 p a g e r a n k 技术就是这种思想的成功体现。具体来说，假如网页a 有一个指 向网页b 的链接，g o o g l e 就认为“网页a 投了网页b 一票”。g o o g l e 根据 网页被链接的数量来评定其重要性。如果说，最后指向a 的网页数为1 0 0 ， 而指向b 的网页数只有l o ，则说明网页a 比网页b 更加重要。 p a g e r a n k 具体计算方法“：设页面集合 p 1 鹃或 中的每一个页面 都指向页面i ，且设c ( i ) 为页面i 的指出页面的个数，则该页面i 的 p a g e r a n k 值为：p r ( i ) = ( 1 一d ) + d ( ( j p r ( 片) c ( 最) ) + + ( j p 尺( 只) c ( 只) ) ) 其中d 为一个衰减因子，一般在o 8 5 之间。p r ( i ) 值越大，网页p i 的权威 值就越高。该算法离线计算出浩瀚资源中各个网页独立于查询词的重要性 指标( 也就是和查询内容无关) ，作为将来排序中的一个重要参考数值。 在线查询服务。 从一个原始网页集合s 开始，预处理后将得到对s 的一个子集的元素的某 种内部表示，这种表示构成了查询服务的基础。查询代理接受用户输入的查询 短语，切分后，从到排序文件中检索获碍包含查询短语的页面并返回给用户。 根据用户输入的查询短语，产生结果集合，是检索倒排索引的过程。首先 对用户输入的查询短语分词，获得查询q 的向量表示，q = ，f 2 ， ，然后执 行检索逻辑运算，从而得到相关网页集合。接下来的工作就是相关网页的排序 问题。在p a g e r a n k 算法出现以前，人们习惯采用传统信息检索领域基于词汇词 频的方法：目前搜索引擎主流的排序算法是使用的在预处理阶段所计算出的每 个页面的p a g e r a n k 值，按照其重要程度从大到小排成一个结果列表。 一个搜索引擎的质量好坏，与以下几个因素相关： o 互联网页面覆盖程度。显然一个搜索引肇的网页数据库中包含的网页越 多，它就越有能力为用户提供更多的网页检索查询结果，也意味着它需要 的硬件设备资源越庞大，以及它的网页索引处理算法也越先进。目前主流 搜索引擎都是数十亿级的数据库。 互联网页面查询质量。描述搜索引擎检索查询质量的指标通常有两个：分 6 中国科学技术大学硕士学位论文 海量w e b 信息智能获取技术研究 别是查准率和召回率。前者就是检索出的相关文档占全部检索出来的文档 的比例，描述的是检索查询的准确率；后者就是检索出相关文档占全部相 关文档的比例，描述的是检索查询结构的完全性。这两个参数通常是相互 矛盾的，一般衡量信息检索质量都是用在不同召回率水平下的查准率值来 进行比较。 互联网页面查询速度。随着g o o g l e 将一次查询相应速度做进1 秒的水平， 目前主流搜索引擎一般都能够做进1 秒的相应速度。查询检索的速度越快， 其搜索引擎的查询能力就越强。 互联网页面更新快慢。互联网是一个动态变化的环境，作为一个优秀的搜 索引擎，其网页数据库内容也应能及时反映这种变化适应整个互联网真实 表示，网页更新率越高，就意味着需要更多的网页搜索硬件资源，以及更 先进的网页更新管理策略和算法。 1 2 2 网页主题搜索方法 通用搜索引擎的排序算法( 如p a g e r a n k 算法) ，不关心网页内容，将所能 访问到的网页都放在一个水平上进行被引用次数计算，这样做显然不符合网页 重要性真实表达，其描述的往往是网页的流行程度。例如，偏冷专业领域里的 顶尖网页被引用次数也没有介绍娱乐明星网页被引用的次数多。网络信息局部 化正成为互联网特征之一，用户希望能在其所关注领域( 即使是冷门专业) 内 搜索到最完备的领域信息，能更精确更快速地检索最重要的领域信息。而主题 信息一般只占整个互联网很小的一部分，并且具有分散性，因此通用搜索引擎 基于宽度优先或者深度优先搜索策略都难以达到该期望水平。于是面向主题的 搜索系统应运而生。面向主题搜索系统的主要任务就是利用有限的网络带宽， 存储容量和较少的时间，抓取尽可能多的主题网页，在此专题网页数据库里用 基于链接分析技术、网页重要性计算技术，做出领域内重要性排序。这可满足 该领域用户的主题查询，方便用户研究使用领域内容。 主题信息搜索的主要方法来源于s c h a k r a b a r t i 在1 9 9 9 年所构建的 f o c u s e dc r a v l i n g 系统嘲。该系统首先由用户从某一开放的分类目录体系如 y a h o o 中选取若干个子类节点作为主题信息，这些节点所包含的一些页面作为 训练集，构造一个分类器。当抓取到一个新的页面p 时，首先提交到分类器进 行相关度预测，如果页面p 是一个正例( 页面与主题信息的相关度超过一个阀 中国科学技术大学硕士学位论文 绪论 值) ，则由p 指向的超链接放入工作队列作为待抓取的链接。否则p 被剪枝，其 所指向的超链接也不进一步抓取。在实际应用中，分类器构造和特征值选择尤 为关键，设计的不好就会产生“主题漂移”现象。面向主题的搜索具有以下优 点：搜索频率足够高，保证周期短暂的网页也能被检索到：有较高的领域数量 覆盖量和搜集质量；占用的带宽资源、计算资源较少，服务的质量较高。 1 2 3 网页深层数据搜索 有了基于主题的搜索系统还是不够，主题搜索系统所搜集的网页也大多是 静态页面，而整个w e b 就像一个深不见底的海洋，这个海洋中数据可分成两个 层次，表层网页( s u r f a c ew e b ) 和深层网页( d e e pw e b ) 。表层包含的主要是“静 态网页”( 不通过提交查询信息即可获得的页面) ，底层包含的主要是“动态网 页”( 需要通过提交查询信息获得含有内容的网页) 。目前传统搜索引擎技术主 要关注表层页面，就像一条捕鱼的船，总是偏好那些位于表层的网页，而对位 于更深层的动态网页则鞭长莫及。这也就是为什么目前网站建设者想让自己的 网站更多地被搜索引擎收录，就要尽可能多地使用静态链接，以适应搜索引擎 的这种偏好。 在互联网早期，网络上的信息主要以静态网页形式存在；而随着电子商务 发展和网络互动的需求，静态网页无法实现，更多的大型网站便转向底层数据 库和动态网页结合的技术来构建网站。这些动态页面事先并不存在，它是根据 用户查询条件从数据库中取出相关的内容，动态形成查询结果，以页面形式返 回给用户。所谓的i n v i s i b l ef e b 并不确切，因为这类网页只是相对于传统搜 索引擎来说不可见，对于用户来说还是可见的。传统搜索引擎c r a w l e r 的工作 是通过“c l i c k ”( 点击) 动作完成的，无法进行“t y p e ”( 输入) 动作，更没有 思考分析能力，这点造成需要生成用户查询条件的那些动态网页无法被访问到。 根据d e e pf e b 白皮书“研究得出结论，深层所包含的数据较之表层数据， 不但数量巨大而且结构化程度高，专业化程度好，在农业、教育等领域具有巨 大的使用价值( 如图卜2 所示) 。总的来书深层数据具有以下若干特点： 静态网页有1 9 t 字节量，深层网页至少7 5 0 0 t 的数据量，是表层数据总量 的4 0 0 一5 0 0 倍： 至少2 0 万个网站底层是基于数据量庞大的数据库，而且9 5 以上的数据 库是对所有用户公开的； 中国科学技术大学硕士学位论文海量w e b 信息智能获取技术研究 。深层数据具有更快的更新效率，更大的更新数量： 比静态网页具有更加专业、更加结构化、更加组织完好的信息和知识； 0 深层数据的内容更加适用专业需求、更加符合市场需求； 其中一多半的深层数据内容是基于专业数据库，具有极大的复用价值。 图卜2 互联网数据模型 要能使得d e e pw e b 页面对于搜索引擎可见，就需要新的爬虫算法。d e e pw e b 爬虫的设计需要解决两大问题：爬虫必须能理解查询接口，爬虫必须能提交有 效查询词且获取查询结果。也就是解决传统搜索引擎爬虫不能“t y p e ”( 输入) 的问题，赋予爬虫填表读单的智能，这是国内外一个比较热的研究方向。图1 - 3 所展示的是一个互联网搜索模型，理想的搜索引擎不但能够收集到表层网页， 并且有能力渗入网络深层，收集那些数量更大、质量更高、格式更优的动态网 页。 中国科学技术大学硕士学位论文绪论 传 互联网搜索引擎模型 深层e _ ：三 连 占未 菩善 图1 3 互联网搜索引擎模型 w e b 专业数据库 7 d e e p w e b ( i n v i s i b l ew e b ) 1 2 4 网页信息抽取 随着计算机、互联网应用和普及，人类所面l 临的知识获取匮乏问题得到解 决，但伴随着出现了如何有效使用散落在网上海量数据的问题。搜索技术的出 现使得人类有足够的脑力来控制知识爆炸时代的困惑和无赖，极大扩展了人类 的获取知识的有效能力。但用户仍然需要从大量搜索结果中找寻所需，资料越 多，搜索覆盖越低，需要用户参与的工作就越多。如何才能帮助用户格式化海 量资料? 为弥补信息检索( i n f o r m a t i o nr e t r i e v a l ，i r ) 的不足，学者们在2 0 世纪 6 0 年代提出了信息抽取( i n f o r m a t i o ne x t r a c t i o n ，i e ) 概念。信息抽取是指从 一段文本中抽取指定的一类信息( 例如事件、事实) ，井将其形成结构化的数据 填入数据库的过程。信息抽取的输入是原始文本，而其输出的是固定格式的信 息点。信息点从各种各样的文档中被抽取出来，然后以统一的形式集成在一起， 这就是信息抽取的主要任务( 如图1 - 4 所示) 。信息以统一的形式集成在一起的 好处是方便比较和重复使用，例如比较不同招聘和商品价格信息，还可为数据 自动化处理系统提供研究数据，例如使用数据挖掘方法发现和解释数据模型。 1 0 中国科学技术大学硕士学位论文海量w e b 信息智能获取技术研究 呤甚 脚卜4 信息抽取示例 信息抽取技术并不试图全面理解整篇文档，只是对文档中包含相关信息的 部分进行分析，至于哪些信息是相关的，那将由系统设计时确定下来。信息抽 取技术对于从大量的文档中抽取需要的特定事实来说是非常有用的。互联网上 就存在着这么一个文档库。在网上，同一主题的信息通常分散存放在不同网站 上，表现的形式也各不相同。若能将这些信息收集在一起，用结构化形式储存， 那将是有益的。成功的信息抽取系统将会把互联网交成巨大的数据库。 信息抽取分为无结构信息抽取、结构化信息抽取和半结构化信息抽取。无 结构信息指新闻报道、研究报告等自由式文本。处理这类信息的信息抽取系统 通常使用自然语言处理技术实现，其抽取规则主要建立在词法或句法的基础上， 从人工标注的语料库中自动学习获得。目前无结构信息抽取的水平还难以和入 的能力相比。结构化信息指存放在数据库里的文本信息，或根据事先规定的格 式生成的文本信息。通过描述格式就可以实现这类信息的信息抽取，抽取准确 度也较高。半结构化信息介于无结构信息和结构化信息之间，通常缺少严格语 法约束，也没有统一的格式，如网页信怠、求职简历等。 1 3 本文的工作 1 3 ，1 深层数据发现技术 互联网不仅存储大量的静态页面，而且存储更大量的随查询条件而生成的 动态页面。如：股票查询，商品价格查询，飞机票务查询都是动态页面。静态 页面比较容易处理，只要顺着超链接所指即可获取：动态页面因有入的查询行 为，需要更智能更专业的搜索技术。目前的搜索引擎都比较偏好收集静态网页。 为解决这一问题，动态页面模型被抽象出来。从此模型中可发现动态网页 背后的数据接口。继而提出一个在网络上发现主题相关的动态数据的方法，并 中国科学技术大学硕士学位论文绪论 利用相似查询结果d o m 树相减方法，准确提取出动态区域的数据结构。 1 3 2 半自动化封装器实现技术 发现含有深层数据的网页的目的是为了信息抽取。半结构化网页的抽取工 作现在主要基于封装器系统，研究智能抽取系统某种程度就演变成为研究封装 器自动化、半自动化生成的问题。在此领域研究中已经提出了相当多的研究成 果，也诞生几个著名的软件抽取系统。本节将详细分析几种成熟的半自动化封 装器理论基础及其实现技术，并详细介绍s o r m e a l y 算法，应用该算法于本系 统中。 1 3 3 移动a g e n t 的研究 移动a g e n t 是当前人工智能研究的一个热点，将移动a g e n t 应用于网络信 息获取是a g e n t 研究的一个热点方向，特别适用于将来网络中多计算终端( 如 手持设备) ，大数据量( 基于图片或视频内容算法) 的分布式搜索环境。移动 a g e n t 的研究包括诸如：移动a g e n t 服务器、通信机制、协作机制、安全机制、 容错机制等。本文设计出一个基于a g e n t 的系统，半自动地代理用户发现动态 资源，携带上封装器任务，每天定时获取动态数据信息并格式化所获得的数据。 1 4 论文组织 本文的组织安排如下： 第一章，分析了传统搜索引擎研究背景和相关技术，阐述了深层网络数据 及传统搜索引擎所面i 临的技术难点问题，给出本文的主要研究内容和研究方案。 第二章，分析了动态网页模型，提出了基于实例的关键词库构建方法，提 出互联网深层数据智能搜索发现方法。 第三章，介绍信息抽取的历史背景，阐述信息抽取技术和封装器生成技术 之间关系，实现了半自动化封装器生成算法。 第四章，介绍移动a g e n t 的定义，系统结构和若干关键技术，及移动a g e n t 在网络信息获取中的应用。 第五章，介绍了系统的设计目标，设计思想，实现结构和获得效果。 第六章，总结全文，并提出迸一步的工作方向。 中目科学技术大学硕士学位论文海量w e b 信息智能获取技术研究 第二章信息智能搜索研究 2 i 智能搜索问题描述 本节所描述的智能搜索，其搜索对象不再是静态页丽，而是位于互联网底 层( 相对与静态页面来说) 的动态网页。智能搜索所要解决的问题是：从给定 的若干网站集合出发，寻找主题相关的深层数据源，并根据网页之间的超链接 信息，寻找相连网站中的主题相关深层数据源，整个过程几乎自动完成。主题 相关性判定由主题词库描述，主题词库事先人工给定或由实例页面训练生成。 下面是本文智能搜索三个相关任务的描述： 1 ) 根据网站首页地址，搜索网站每日更新的价格数据源，通过相关超链接分 析，发现所指向的其他网站是否有价格数据源，如有则存储该数据源地址。 2 ) 根据网站首页地址，搜索到不定时发布的供求信息数据源，并通过相关超 链接分析，发现所指向的其他网站是否也有大量供求信息数据源，如有则 存储该数据源地址。 3 ) 根据网站首页地址，搜索到农业主题的新闻数据源，通过超链分析，发现 其他网站新闻数据源，如有则存储。 价格、供求之类的信息每日大量更新，与股票信息同属于时序数据范畴， 如此大量的数据一般存于各种类型的数据库中，位于互联网深层。用户只有提 交查询条件才能显示出来，现有的搜索引擎缺少足够的主题知识，无法模拟用 户提交查询条件，故这些数据对于传统搜索引擎往往不可见。 但这些数据是领域研究中不可或缺的重要资料，研究如何在浩瀚的互联网 上有效搜索至g 这些数据源是一个重要的研究方向。本节将介绍一种通过实例训 练获得主题词汇的方法，并且通过这些主题词汇构造主题相关查询条件，提交 给网站系统，从而自动发现分布在网络上尚且不为人所察觉的深层信息数据源。 该方法的提出，为后面所介绍的抽取系统提供了大量数据源支持。 2 2 深层资源查询模型 从网站商业角度来看，网络上存在着无限的商机，为吸引消费者的目光， 每个网站设计者无不费尽心思，设计出绚丽的界面，用以提供购买欲望。而从 研究人员角度来看，绚丽的界面设计无疑是程序分析模块的额外负担，那些真 中国科学技术大学硕士学位论文 信息智能搜索研究 实的数据才是最重要的。透过现象看本质：在绚丽的界面装扮下，互联网深层 数据源往往隐身于页面查询f o r m 或者说“服务接口”后面，用户通过提交查 询条件才能检索出他们所需要的数据，这种架构适合数据庞大、每日递增的海 量数据源的发布。事实上，这种数据不但数量庞大而且格式统一、可信度高， 具有很强的研究意义。许多应用程序都需要大量这样的数据做支持，更多的一 些数据处理软件甚至极大地依赖于这些高质量数据( 比如：商品比价系统) 。所 以，基于查询条件的深层数据搜索问题能在最近几年激起了许多研究兴趣。 深层网络爬虫与传统搜索引擎爬虫相比有一个本质的不同【，就是有没有 输入填单能力。图2 一l 左半部分所显示的是用户填写表单使用深层数据库的几 个步骤：浏览表单，填写表单，提交表单，浏览查询结果，获得所需数据。图 2 i 右半部分显示的是由深层网络爬虫模拟用户进行相同的交互浏览活动。可以 看出表单( f o r m ) 就是深层数据源对外的一个接口，通过f o r m 就可以访问到 存储在数据库里的格式化数据，所以发现那些查询f o r m 也就相当于找到了深 层数据源的钥匙。一个页面上表单的表示可以从下面几个方面来阐述：表单模 型，主题相关和返回页面。 _w口mn m ” ) u 蝌i 孤汹飘d m 村o - w 培岛衄劬_ t d 油 图2 1 深层爬虫模拟用户填单过程 1 ) 表单模型：搜索表单( s e a r c hf o r m ) 是后台数据库的大门，只有通过表 单，才能访问到后面的数据库。抽象地说，一个表单f 通常会包括以下若 干组成部分：f = ( ( 巨，易，e ) ，s ，肘) 。其中瞩，易，e ) 是表单f 的元 素( 例如，l a b e l ，t e x t 等) ，s 是表单提交行为的相关信息( 例如，提交 页面信息，各元素i d 信息等) ，m 是表单的其他信息( 例如，该表单所在 页面u r l ) 。模型中所涉及到的抽象内容依赖于网络爬虫具体实现的细节。 2 ) 主题相关：深层数据网络爬虫与传统搜索引擎爬虫不一样，一个表单后面 的数据库的主题往往是单一而固定的，不可能包含有各种主题数据。这决 定了深层网络爬虫不可能如传统搜索引擎爬虫那样能够爬取各科各类主 1 4 中国科掌技术大学硕士学位论文 海量w e b 信息智能获取技术研究 题的网页，一定是主题相关的搜索。例如：电子产品分析的爬虫所能发现 的数据资源只可能是那些电子产品介绍、电子产品报价之类的列表信息。 3 ) 返回页面：返回页面作为一种查询结果列表返回给用户或者网络爬虫，供 给用户或者爬虫从中获取所需数据。网络爬虫必须能从这些返回页面中测 试出正常数据页面和非正常出错页面，并能够从正常数据页面中抽取出所 需数据，并且经过格式化后存储于数据库。 2 3 深层资源发现方法 设计一个深层数据源爬虫实际上是很困难的。首先，这样的网络爬虫应该 能够像人那样理解分析、处理网页表单。其次，还需要这样的爬虫能够向表单 中填写相关的查询词汇。简单地说，就是要求搜索算法不但能够像传统搜索引 擎那样顺着超链接漫游在互联网上，而且还要够智能，可以模拟用户“填单” 行为。设计一个能够完全像人一样的填单算法是困难的，需要涉及到自然语言 理解和诸多专业知识；但设计一个针对特定主题的表单填写算法是可以做到的， 因为其专业知识可事先设定好。下面将介绍一种基于农业主题的深层数据搜索 发现方法。 2 3 1 从样本中获取主题词库 表单查询是基于主题关键词，自动查询系统面对的第一个问题就是如何选 择主题关键词。人工构造主题关键词库是一个朴素的解决思路，一个更好的方 法是从若干实例页面中自动提取主题关键词。自动构建主题词库可以低成本、 迅速地构建一个研究领域的关键词。其主要思想：查询关键词一定会高频率出 现结果页面中，通过迭代查询产生大量同主题结果页面，并统计这些页面，从 中提取出高频率出现的词作为主题关键词，如表2 1 所示。 本方法使用了迭代式构建关键词库，从一个填写表单开始，候选关键词从 有限个主题关键词开始，或者从初始查询页面开始，不断用这些候选关键词尝 试着填写表单。若查询返回页面中有一定数目的物品数据则显示该词是主题关 键词可能性很大，将该词加入主题关键词库；若查询数目为空或非常少则可认 为该词为非关键词，应该不再处理该词。新的查询页