（计算机应用技术专业论文）deep+web数据抽取和语义标注技术研究.pdf

江苏大学硕士学位论文 摘要 w e b 数据库根据用户提交的请求，将其内容以h t m l 页面的形 式动态呈现出来，这些信息称之为d e e pw e b 资源。而h t m l 语言的 特点是在w e b 上发布的，内容多样，形式各异，使得w e b 上的数据 处于杂乱无序的状态，给数据集成系统的建立造成了极大的困难。因 此，需要通过各种技术手段将网页中的无结构或者半结构化数据抽取 出来。同时为了使抽取获得的数据具有更高的使用价值，这些数据应 该被应用程序所理解，必须为其添加语义注释。 本文重点分析了d e e pw e b 数据抽取和语义标注的已有技术，并 在此基础上分别提出了一种基于模板的数据抽取方法和一种基于包 装器的语义标注方法，最后整合上述研究模块，设计和实现了一个面 向求职领域的垂直搜索引擎系统。 本文主要研究的内容包括： ( 1 ) 研究如何从一系列同模板生成的网页中检测出其背后的模 板，并利用模板将嵌入的数据自动抽取出来。给出了模板生成问题的 形式化描述，提出了一种新颖的模板生成方法，并利用生成的模板从 实例网页中抽取数据。与现有方法相比，该方法能适用“列表页面” 和“详细页面”两种类型网页。通过在多个领域实例站点上实验，说 明新方法在不降低已有方法准确率的情况下能进一步提高抽取的召 回率。 ( 2 ) 为了准确且完整地对抽取的数据进行语义标注，提出一种基 于包装器的语义标注方法。该方法利用多个标注源进行组合标注，有 效解决了单标注源标注率不高问题；同时针对标注不完全问题，提出 了利用多个数据源的互补关系进行标注；最后生成高效率的标注包装 江苏大学硕士学位论文 器对抽取结果自动标注。实验结果证明，该方法提高了标注的准确率 和效率。 ( 3 ) 设计和实现了一个面向求职领域的垂直搜索引擎系统，并将 上文提出的技术在该搜索引擎上的应用做了分析。实际应用表明，该 系统可以取得较好的效果。 关键词：d e e pw r e b ，数据抽取，语义标注，垂直搜索，数据集成 江苏大学硕士学位论文 a b s t r a c t a f t e rr e c e i v i n gt h er e q u e s ts u b m i t t e db yu s e r , w e bd a t a b a s ew i l l r e t u r nq u e r yr e s u l t si nt h ef o r mo fh t m l p a g e sd y n a m i c a l l y t h ew h o l e i n f o r m a t i o ne m b e d d e di nt h e s ep a g e sc a l l e dd e e pw e b t h eh t m l p a g e s a r ep u b l i s h e do nw e bw i t hv a r i o u sc o n t e n ta n dd if f e r e n tf o r m s ，m a k i n g d a t ao nt h ew e bs e m i s t r u c t u r e do re v e nu n s t r u c t u r e d t h e s e c h a r a c t e r i s t i c sb r i n gg r e a td i f f i c u l t i e st ot h ee s t a b l i s h m e n to ft h ew e b i n t e g r a t i o ns y s t e m s t h e r e f o r e ，s e m i s t r u c t u r e da n du n s t r u c t u r e dd a t ao n t h ew e bn e e d e dt ob ee x t r a c t e d t h r o u g h a v a r i e t y o ft e c h n o l o g y m e a n w h i l e ，i no r d e rt om a k et h ee x t r a c t e dd a t aah i g h e rv a l u e ，s e m a n t i c a n n o t a t i o n sm u s tb ea d d e ds ot h a tt h e s e d a t ac a nb e u n d e r s t o o db y a p p l i c a t i o np r o g r a m t h i sp a p e ra n a l y z e se x i s td a t ae x t r a c t i o na n ds e m a n t i ca n n o t a t i o n m e t h o d s ，t h e np r o p o s e san e wa p p r o a c ho fd a t a e x t r a c t i o nb a s e do n t e m p l a t e a n da na p p r o a c ho fs e m a n t i ca n n o t a t i o nb a s e do nw r a p p e r f i n a l l y , av e r t i c a l s e a r c h e n g i n e f o rj o bd o m a i ni s p r e s e n t e d a n d a c c o m p l i s h e d t h em a i nw o r k so ft h i sp a p e ri n c l u d e ： ( 1 ) t h er e s e a r c hi st oa u t o m a t i c a l l yg e n e r a t et e m p l a t eb e h i n dt h e s e t e m p l a t e g e n e r a t e dw e bp a g e sa n de x t r a c te m b e d d e dd a t a t h et e m p l a t e g e n e r a t i o np r o b l e m i sf o r m a l i z e d an o v e lt e m p l a t eg e n e r a t i o nm e t h o di s p r e s e n t e d a n dt h eg e n e r a t e dt e m p l a t e sa r eu s e dt oe x t r a c td a t af r o m i i i 江苏大学硕士学位论文 i n s t a n c e p a g e s c o m p a r i n g w i t h e x i s t i n gr e s e a r c h ，t h i s m e t h o di s a p p l i c a b l ef o rb o t h l i s tp a g e s a n d d e t a i lp a g e s t h ee x p e r i m e n to n s e v e r a ld o m a i n si n d i c a t et h a tt h en o v e lm e t h o dg r e a t l yi m p r o v er e c a l lo n t h eb a s eo fh i g ha c c u r a c y ( 2 ) t oa n n o t a t ee x t r a c t e dd a t aa c c u r a t e l ya n dc o m p r e h e n s i v e l yi n d e e pw e b ，t h i sp a p e rp r o p o s e sam e t h o db a s e do nw r a p p e rf o ra u t o m a t i c s e m a n t i ca n n o t a t i o n s e v e r a la n n o t a t o r sw e r ec o m b i n e dt o i m p r o v e a c c u r a c y t o s e t t l ea n n o t a t i o n i n c o m p l e t ep r o b l e m ，c o m p l e m e n t a r y r e l a t i o n s h i pb e t w e e n d a t as o u r c e sw a su s e d a tl a s t ，aw r a p p e rw h i c hc a n a n n o t a t ee x t r a c t e dd a t ai nh i g he f f i c i e n c yw a sg e n e r a t e d t h ee x p e r i m e n t s h o w st h a tt h ea p p r o a c ha c h i e v e sh i g h e ra c c u r a c ya n de f f i c i e n c y ( 3 ) a c c o m p l i s hav e r t i c a ls e a r c hs y s t e mf o rj o bd o m a i na n da n a l y z e t h ea p p l i c a t i o no ft h et e c h n o l o g ym e n t i o n e da b o v e p r a c t i c a la p p l i c a t i o n s h o w st h a tt h es y s t e mc a no b t a i nb e t t e rr e s u l t s k e y w o r d s ：d e e pw e b ，d a t ae x t r a c t i o n ，s e m a n t i ca n n o t a t i o n ，v e r t i c a l s e a r c h ，d a t ai n t e g r a t i o n i v 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文 的规定，同意学校保留并向国家有关部门或机构送交论文的 复印件和电子版，允许论文被查阅和借阅。本人授权江苏大 学可以将本学位论文的全部内容或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和 汇编本学位论文。1 保密口，在年解密后适用本授权书。 本学位论文属于 不保密面。 学位论文作者弥棚碜精教师签名翔 砂1 每芦具3 j 日 j 争口碡知a 日 f 时乞 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指 导下，独立进行研究工作所取得的成果。除文中已经注明引 用的内容以外，本论文不包含任何其他个人或集体已经发表 或撰写过的作品成果。对本文的研究做出重要贡献的个人和 集体，均已在文中以明确方式标明。本人完全意识到本声明 的法律结果由本人承担。 学位论文作者签名：7 物膨缪 日期：乡矽夕年朔州日 江苏大学硕士擘位论文 11 研究背景 第一章绪论 随着i n t e m e t 的发展和w e b 上信息的快速增加，人们可以通过搜索引擎找到 自己需要的信息。但是，近年来网络朝着深度方向发展，大批高价值、高质量的 信息隐藏在网络的深处。这些信息没有静态链接，很难被传统搜索引擎发现，主 要存储在w e b 数据库中，只有在被查询时才会由w e b 服务器动态生成页面返回 给访问者( 如图l1 所示) ，这类页面被称为d e e pw e b “。反之，将可以通过超 链接或者传统搜索引擎访问到的页面称为s u r f a c e w e b 。d e e p w e b 与s u r f a c e w e b 的本质区别在于，s u r f a c ew e b 包括的内容基本都是非结构化的h t m l 信息，对 搜索引擎而言是相对可见的，因此x 被称为v i s i b l ew e b ；而d e e pw e b 的内容存 储在w e b 中可访问的在线数据库中，是相对不可见的，于是又被称为i n v i s i b l e w e b 。 b 目l1 d e e p w e b 馘据获取过程 与s u r f a c ew e b 相比，d e e pw e b 蕴藏了更加丰富，更加专业的信息。根据近 年来研究调查表明1 1 1 2 1 1 3 1 ： ( 1 ) d e e p w e b 包含的可访问公共信息量是s u r f a c e w e b 的4 0 0 - 5 0 0 倍。d e e p w e b 包含7 5 0 0 t b 的信息，而s u r f a c ew e b 包含的信息容量只有1 9 t b 。 ( 2 ) d e e pw e b 大约有3 0 7 0 0 0 个站点，4 5 0 0 0 0 个后台数据库和1 2 5 8 0 0 0 个查 询接口，其中约4 5 为结构化数据库。 江苏大学硕士学位论文 ( 3 ) 平均看，d e e pw 曲站点的月访问量比s u r f a c ew e b 站点高出5 0 ，并且 与s u r f a c ew e b 站点相比有更多的链接。可是那些典型的大型深度d e e pw e b 在 互联网搜索领域却不知名。 ( 4 ) d e e pw e b 站点在信息内容范围上比一般s u r f a c ew e b 站点更专更深。 d e e pw e b 包含的有效高质内容总量至少是s u r f a c ew e b 的1 0 0 0 到2 0 0 0 倍。 ( 5 ) 超过一半的d e e pw e b 内容都保存在专业领域的数据库中。9 5 的d e e p w e b 信息都是面向公共访问的，而不是需要付费或者订阅的。 ( 6 ) 虽然一些d e e pw e b 目录服务已经开始索引w e b 数据库，但是它们的覆 盖率比较小，仅为0 2 15 6 。 ( 7 ) w e b 数据库查询接口往往位于站点浅层，9 4 之多的大量w e b 数据库查 询接口可以在站点前3 层发现。 综上所述，d e e pw e b 具有信息量大、价值高、质量优、结构化好等特点， 然而d e e pw e b 的数据来源于后台数据库，要访问这些资源的唯一途径是填写 d e e pw e b 站点提供的查询表单，因此用户为了查找某领域内自己感兴趣的信息， 往往需要逐个反复地填写各个w e b 站点的查询表单。很显然，对于用户来说， 这一查找过程是枯燥而又机械的。为了有效地利用d e e pw e b 资源，采取的方法 是进行大规模d e e pw e b 数据集成。目f j i ，d e e pw e b 数据集成的研究主要包括以 下几个关键问题：d e e pw e b 数据库的发现、w e b 数据库的分类、查询接口的集 成、w e b 数据库的选择、w e b 数据抽取、语义标注、结果整合等。 本文主要针对数据抽取模块和语义标注模块进行详细的介绍和深入的研究， 尤其是在语义标注方面，目前在这方面的工作还在初步阶段，最后将本文研究的 技术运用到垂直搜索引擎上。 1 2 国内外研究现状 d e e pw e b 信息获取与集成至今仍是一个新兴的研究领域，虽然在该领域已 经开展了大量的研究工作，但其中仍有很多急待解决的问题。 目前，国内在d e e pw e b 搜索和挖掘方面的研究尚处于学习、跟踪和探索阶 段。d e e pw e b 领域的研究单位及相关报道还比较少，尚只有中国人民大学数据 库研究小组在这方面有较深入的研究。由于普通搜索引擎目前还不能提供对 2 江苏大学硕士学位论文 d e e pw e b 的搜索服务，因此，分类目录服务是目前检索d e e pw e b 的一个重要途 径，国内在这方面也出现了一些d e e pw e b 分类目录服务站点，但仍处于手工收 集和整理阶段，还不能实现自动化或半自动化索引处理。 国外已有d e e pw e b 4 1 、i n v i s i b l ew e b l 5 1 、b r i g h tp l a n e t 1 】三家公司生产相关产 品，但通过对比分析可以得出如下结论：这三家公司的产品均采用半自动化方式， 人工干预较多。尽管他们在产品中加入了d e e pw e b 信息挖掘功能，但目前还没 有提供中文d e e pw e b 信息服务。 国外大学的研究小组主要有以下贡献： 1 伊利诺斯大学的m e t a q u e r i e r l 6 j 研究小组 该小组在m e t a e x p l o r e r 项目的基础上建立了一个m e t a q u e r y 系统，目的是有 效获取w 曲上的结构化信息。首先，m e t a e x p l o r e r 项目的一个研究重点在于发 现和重构w e b 数据库，并建立一个可搜索的数据源知识库。特别是，该项目开 发了一个w e b 数据库搜索引擎，它可以有效发现含有w e b 数据库的站点，并通 过构建模型来描述这些数据库，而封装器用于自动抽取这些模型中的参数，从而 重组和索引可搜索的w e b 数据库。其次，m e t a e x p l o r e r 项目的另一个研究重点 在于集成在线数据库。在大规模信息集成的过程中，其主要研究了动态信息集成 技术。与传统的信息检索不同，该小组设计的m e t a q u e r y 系统是动态执行的，即 可以将实时发现的新数据源加入系统中，同时动态选择合适的数据源，并将用户 查淘进行相应转换，从而获取用户查询结果。 2 斯坦福大学的w e b b a s e i7 j 研究小组 h d a v u l c u 、j f r e i r e 等人提出并设计了w e b b a s e 的框架，它可以通过工具帮 助用户实现特定领域的复杂搜索服务。 3 斯坦福大学的h i w e t 8 j 研究小组 h i d d d e nw 曲e x p o s e r ( h i w e ) 是s t a n d f o r d 大学另一个研究项目。r a g h a v a n 和 g a r c i a m o l i n a 设计了一个可以抽取d e e pw e b 信息的爬虫。在此系统中爬虫管理 器负责管理搜集过程，并对下载的w e b 页面进行分析，将包含表单的页面送到 表单处理器中处理。表单处理器首先从页面中抽取表单结构，并从预先准备好的 数据集中选择数据自动填写表单，然后将合成的u r l 提交给爬虫管理器。由于 表单需要系统自动完成填写，所以要求用户预先准备好相应的表单数据集。h i w e 江苏大学硕士学位论文 只能面向特定的领域使用，而且必须在人工帮助下完成，因此存在很大的局限性。 4 华盛顿大学的s h o p b o t l 9 1 研究小组 s h o p b o t 是一个针对消费产品的比较代理，它利用特定领域的启发式方法来 填写表单以比较其领域内的商业产品。s h o p b o t 的操作过程分为两个阶段：离线 学习阶段和在线产品比较阶段。在学习阶段，确定填写站点表单的方法，并对产 品站点结果页面进行分析，从而获取其站点模式信息。在比较阶段，利用得到的 站点模式结构来抽取结果信息，找出满足用户要求价格最优的产品，最终将这些 产品的信息输出。从中可以看出，该小组的研究领域非常狭窄，不适用于大规模 的信息集成。 5 哥伦比亚大学的q p r o b e r l l 0 1 研究小组 哥伦比亚大学的p a n a g i o t i sg i p e i r o t i s 等人研究了自动分类w e b 页面所对应 的后台数据库的方法。他们首先使用机器学习技术生成一组基于规则的分类器 ( c l a s s i f i e r ) ，然后将分类器转变成查询u r l ，并对后台数据库进行查询，计算 查询结果数。最后该算法通过分析查询结果对数据库进行分类。他们的研究只集 中在如何分类文档数据库上面，然而多数d e e pw r e b 数据库提供的内容却是结构 化的数据。 此外，微软亚洲研究院早在2 0 0 4 年就提出如何基于接口中的关键字来抽取 d e e pw - e b 站点内容的方法【1 1 】，并在此基础上，开发了第三代搜索引擎。第三代 搜索不仅要对深层互联网进行挖掘，找出更多的结果，还要更加智能化、人性化， 能够理解用户需要什么结果。 1 3 论文的研究重点 国内外研究现状表明，d e e pw e b 受到越来越多的关注。对d e e pw e b 研究的 根本目的是为了能够自动地获取利用自由分布在整个w 曲上的d e e pw 曲中丰富 的信息，为信息集成和信息挖掘提供服务。 d e e pw e b 数据抽取和语义标注是d e e pw e b 数据集成和挖掘工作的重要部 分。基于这种认识，本文着重对d e e pw e b 数据抽取技术和语义标注技术进行深 入的研究，主要研究内容如下： ( 1 ) 为了克服现有方法需要一系列启发式规则的问题，利用d e e pw e b 页面 4 江苏大学硕士学位论文 大多是根据请求从后台数据库中读取数据并动态填充模板生成的这一特性，提出 一种基于模板的d e e pw e b 数据抽取方法，力求使抽取结果更准确、效率更高。 ( 2 ) 针对单个标注源标注率不高问题，提出利用多个标注源进行组合标注； 同时针对单个数据源信息不全面导致的部分属性无法标注的问题，提出利用多个 数据源的互补关系来同步标注；最后避免对同类结果页面重复标注过程，考虑生 成包装器实现自动标注。 ( 3 ) 最后设计和实现了一个面向求职领域的垂直搜索引擎系统。 1 4 论文的结构安排 本文共分为7 章，具体结构安排如下： 第一章首先给出d e e pw e b 的概念及其特性，随后阐述国内外d e e pw 曲的 研究现状和主要研究成果，最后给出本文的研究重点和结构安排。+ 第二章首先概述d e e pw 曲数据集成框架，并简单介绍各模板的功能，然后 介绍w e b 数据抽取和语义标注的概念及其技术分类，尤其是分析出数据抽取对 象的特点和指出当前语义标注技术的不足。 第三章研究分析d e e pw e b 数据抽取技术。本章首先介绍本文数据抽取方法 所用到的相关技术，并给出了模板生成问题的形式化描述。随后提出了一种新颖 的模板生成方法，利用生成的模板实现数据的自动抽取。 第四章研究分析d e e pw e b 语义标注技术。首先对语义标注问题进行描述， 随后在d e e pw e b 数据抽取得到的结果基础上，提出了基于包装器的自动语义标 注方法。 第五章首先简单介绍垂直搜索引擎技术。然后，在上文的基础上设计和实现 了一个面向求职领域的垂直搜索引擎系统，对本文提出的技术在垂直搜索引擎上 的应用进行分析。 第六章对本文提到的方法和技术进行实验，并通过对实验结果的分析，验证 本文提出方法的有效性和可行性。 第七章对本文工作进行总结和展望。 5 江苏大学硕士学位论文 第二章工作基础 随着i n t e m e t 的飞速发展，人们希望从w e b 中获取更多有用的信息，因此 d e e pw e b 受到国内外研究者的关注，越来越多的研究成果发表在高级别会议和 期刊上。对d e e pw e b 进行研究就是为了对其中的海量异构信息进行集成，从而 为用户提供一个统一的访问途径来自动获取分布在整个d e e pw e b 上的信息。本 章对d e e pw e b 数据集成的整体框架进行了概述，然后对集成系统涉及到的两个 关键技术进行了分析。 2 1 d e e pw e b 数据集成概述 面对纷繁复杂的w e b 数据库，用户为了获得所需信息，会遇到一系列的问题， 往往不知所措。比如，一个用户刚来到一个新的城市工作，他可能需要通过网络 寻找一些租房、找工作、买车等信息，那么他如何找到w e b 上的数据库，如何 挑选出关于房屋、工作和车的那些数据库，如何从某个领域( 比如，工作) 的成 千上万的数据库中找到一系列相对比较相关的w e b 数据库? 而且即使是在一类 w e b 数据库中，每个查询接口的设计也是不尽相同的，因此为了能正确地提交查 询，他必须了解每个数据库查询接口的填写细节；由于各数据库的内容存在一定 的重叠，所以返回的查询结果中必然有很多重复的数据，需要进一步的处理；然 而各结果页面的设计存在很大差异，没有明确的模式，合并和去重的过程也十分 困难；经过上述这些步骤之后，才能得到用户需要的结果。可见，整个过程非常 复杂，仅仅依靠用户手工处理是非常烦琐耗时的，因此迫切需要一种自动的方法 帮助用户高效地完成这些复杂的工作，这也就是d e e pw e b 数据集成的目标。 图2 1 给出了d e e pw | e b 数据集成系统框架。从图中可以看出，d e e pw 曲数 据集成框架共分为两大模块1 1 2 l ：集成查询接口的生成和对集成查询接口上查询 的处理。每个模块又包含若干处理单元，这些处理单元互相衔接，缺一不可。下 面，对系统中各部分的功能作简单描述。 6 江苏大学硕士学位论文 集成查询接1 3 生成模块查询处理模块 图2 1d e e pw e b 数据集成系统框架 2 1 1 集成查询接口生成模块 e b 该模块整体的功能是在w e b 中发现w e b 数据库并对其按领域进行分类，在 每个分类上对所有查询接口集成，为用户提供一个统一的查询接口，使之可以同 时向多个实际的查询接口提交查询，即达到同时访问属于同一领域的多个w 曲 数据库的目的。 查询接口生成模块共有四个主要的子模块：w e b 数据库的发现、查询接口模 式的抽取、基于领域w e b 数据库的分类和查询接口集成。w e b 数据库的发现是 指从w e b 中发现具有一个真正w e b 数据库的网站，然后从中发现可访问这个 w e b 数据库的查询接口。查询接口模式的抽取是对前一步获得的查询接口中所包 含的属性进行分析和抽取，获得一个查询接口的模式信息。w e b 数据库的分类是 指根据已得到的查询接口的模式信息确定其对应w e b 数据库所属的领域，即按 照领域对w e b 数据库进行分类。查询接口的集成是对属于同一个领域的查询接 口进行集成，得到一个全局的查询接口。 7 江苏大学硕士学位论文 2 1 2 查询处理模块 当用户在集成的查询接口上填写并提交查询，需要将该查询转化到对各个本 地查询接口的查询，提交后各个w e b 数据库会返回符合查询的结果页面，从这 些结果页面中将查询结果抽取出来并添加语义注释，由于各个w e b 数据库之间 具有自主性和异质性，因此所产生的结果数据格式也是各不相同，需要将这些格 式各异的数据形成统一的格式，最终得到可被自动处理的数据格式。 查询处理模块包括领域的映射、w e b 数据库的选择、查询转换、结果抽取、 语义标注、实体识别和结果合并7 个子模块。领域映射是指将用户提交的查询关 键字与领域自动匹配，并把查询关键字自动提交到相应领域的集成查询接口中； w e b 数据库的选择是指从属于该领域的所有w e b 数据库中选择出合适子集，使 得既能够得到令人满意的查询结果，又可以最大限度地降低所需花费的代价；查 询转换是指将在集成查询接口提交的查询转化为要访问的w e b 数据库的各个本 地查询接口上的查询；w e b 数据抽取是指从得到的查询结果页面中将结果数据全 部抽取出来，并保存为下一步可处理的模式；语义标注是指对抽取出的数据赋予 一个特定的含义，以便于实现数据的合并；实体识别是指从不同w e b 数据库获 得的结果中发现表示现实世界同一实体的数据，这一步是为了可以去掉结果中重 复数据，即降低数据的冗余度；结果合并是指把从不同w e b 数据库获得的查询 结果以统一的表现形式呈现给用户。在d e e pw e b 数据集成的查询处理中，数据 抽取和语义标注将在第三章和第四章作详细地介绍和研究。 2 2w e b 数据抽取技术 w e b 信息抽取( w e bi n f o r m a t i o ne x t r a c t i o n ，简称为w 曲i e ) 是将w e b 作为信 息源的一类信息抽取。目前w e b 上的数据大部分以h t m l 来描述，主要目的是 为了显示，让人通过浏览器浏览。其缺乏对数据本身的描述，不含清晰的语义信 息，模式也不太明确。这使得应用程序无法直接利用w e b 上的海量信息，造成 极大的资源浪费，这迫切需要一些自动化工具帮助人们在海量信息源中迅速找到 真正需要的信息。w e b 信息抽取技术的研究正是在这种背景下产生的。 w e b 信息抽取研究的正是如何将分散在半结构化h t m l 页面中的信息提取 8 江苏大学硕士学位论文 出来，并以结构化、语义更为清晰的模式表示。它为用户在w e b 中查询数据、 应用程序直接利用w e b 数据提供了便利【l3 1 。 w e b 信息抽取与浏览器上的信息检索和查询有着本质差异，它们处理信息 的粒度也大不相同【1 4 1 。现有搜索引擎只能根据用户提交的关键词返回一组u r l ， 用户还必须逐一浏览其对应的w e b 页，采用人工方式来定位最终的信息。由于 搜索引擎本身不能直接定位到所需的数据，因此更谈不上为数据增加语义。而 w e b 信息抽取是从w e b 页面所包含的半结构化信息中识别用户感兴趣数据并将 其转化为语义和结构更为清晰的模式( x m l 、关系型数据等) 的过程。该过程可以 形式化的描述为l l5 】：对于给定包含数据的网页p 找到一个映射m a p ，这个映射 m a p 可以将网页p 中的数据映射到一个结构化的数据集s t r u c t u r e dd a t a s e t 中， 并且这个映射m a p 还能用于从与p 类似的其它网页中抽取出相关的数据。它为 w e b 查询提供了更为精确的方法，使得w e b 信息的再利用成为可能。 2 2 1w e b 数据抽取技术的分类 目前普遍的w e b 数据抽取方式是编写特定的抽取程序，主要具备两个功能： 搜寻、发现并抽取特定的数据；以适当的格式保存数据供进一步处理，比如x m l 和关系模式。其中最大的挑战是如何从页面上大量的数据中完整准确地发现查询 结果。当把w e b 数据库中的信息以h t m l 页面的表现形式展现时，数据库相关模 式结构信息就完全丢失了。对页面抽取的一个主要目的就是通过把信息以结构化 的格式存储来反转这个过程。 目前这个研究领域已经丌展了大量的研究工作，有了很多w e b 数据抽取的 工具，按使用的技术大致可以分为几类，下面分别作简要介绍。 基于包装器开发语言的抽取技术 采用这类技术的w e bi e 通常提供一种特殊的专用语言来替代通用语言，如 j a v a ，p e r l 等语言( 这些语言也广泛用于生成包装器 ) ，用以帮助用户生成包装器。 采用这类信息抽取技术的典型系统有m i n e r v a t l6 1 ，t s i m m i s f l 7 1 ，w e b o q l t l 8 1 等。 下面结合t s i m m i s 和w e b o q l 来说明这种类型的w e bi e 。 t s i m m i s 是最早的一种手工生成包装规则的w e b 信息抽取系统之一，其目 标是以一体化的方式获取不同信息源的信息并且保证所获取信息的一致性。其重 9 江苏大学硕士学位论文 点是开发支持这种包装过程的语言和工具。它的包装器模块接受的输入为人工描 述的规则，例如页面上目标数据的位置，以及如何将这些数据重新打包成一个对 象等等。人工输入规则的形式是一个三元组 ， 其中模式信息告诉包装器如何取得数据，信息来源指明需要分析的输入信息，存 储变量用于存储结果。t s i m m i s 输出的对象类型为o e m ( o b j e c te x c h a n g em o d e l ) 格式，包含了所需的数据及其结构信息。 w e b o q l 提供了一种类似于s q l 的语言，能够用来w | e b 查询。w e b o q l 采 用了一种称之为h y p e r t r e e 的数据结构，它类似于d o m 树结构，节点问的有向 弧具有t a g ，s o u r c e ，t e x t 三个属性，分别对应于标签名，h t m l 代码片段和非 标签文本。w e b o q l 能够模拟嵌套关系代数中所有运算的能力，能够计算任意 二元关系上的传递闭包，并提供了类似s q l 中“s e l e c t f r o m w h e r e 结构的查询 方式。w e b o q l 为x q u e r y 规范的形成做出了贡献。 基于h t m l 树结构的抽取技术 这种技术依赖于h t m l 文档的树形结构特征来实现数据的抽取。在开始抽 取数据之前，通过解析得到h t m l 文档的树形表示，然后利用“树 完成抽取。 采用这类信息抽取技术的典型系统有w 4 f 1 19 1 ，x w r a p l 2 0 1 ，r o a d r u n n e r 2 1 1 ， m d r 2 2 1 ，m d r i l l 2 3 】等。下面来说明这几种类型的w e bi e 。 w 4 f ( w y s i w y gw 曲w r a p p e rf a c t o r y ) 是一种能够生成w e b 包装器的j a v a3 2 具 包。包装器生成分成三个独立的步骤：检索( r e t r i e v a l ) 、抽取( e x t r a c t i o n ) 和映射 ( m a p p i n g ) 。在检索阶段，系统通过h t t p 协议，获取w 曲文档，然后通过清洗 等步骤，生成解析树( p a r s et r e e ) ；在抽取阶段，系统应用抽取规则，从分析树中 抽取信息，并存储成w 4 f 的内部格式n s l ( n e s t e ds t r i n gl i s t ) ；在映射阶段，n s l 被传递给高一级应用，响应采用h e l ( h t m le x t r a c t i o nl a n g u a g e ) 语言描述的抽 取请求。 x w r a p 系统通过对h t m l 页面格式信息的处理来假设页面的语义结构。系 统的工作过程分成两个阶段：结构分析阶段和来源相关的( s o u r c e s p e c i f i c ) x m l 生成阶段。在第一个阶段，x w r a p 抓取，清洗网页，并生成页面的树状结构。 然后识别数据区域，感兴趣的语义块，并通过和用户的交互，发现有用的页面分 块的层次结构信息。在第二个阶段，系统基于内容符号( t o k e n ) 和嵌套层次说明， l o 江苏大学硕士学位论文 生成x m l 模版，并构造一个来源相关的x m l 生成器。 r o a d r u n n e r 其方法是进一步发掘h t m l 文档内在的特征来自动产生抽取规 则。通过比较样本页面得到一个结果模式，从这个模式可以推测出一个能够识别 出样本页面中的实例。为了准确地捕获在样本页面所有可能的结构变量，必须提 供多于两个的样本页面。所有的抽取过程都基于这样一个算法：比较样本页面的 标签结构产生规则的表达式来处理结构之间不匹配的情况。过程完全自动化是 r o a d r u n n e r 独一无二的特性。它可以说是第一个完全自动的抽取工具，具有罩 程碑的意义。但它对模式的推导时间复杂性是指数量级，因此在大量样本页面的 情况下代价过高。 m d r 和m d r i i 这两种抽取方法都是由美国l l l i n o i s 大学同一研究小组提出， 其独特的地方在于能够十分准确地在d o mt r e e 中完成对多记录页面的抽取。它 们的实现关键在于利用页面的嵌套结构和表现特征把查询结果从整个页面中分 离出来，并将结果中的多个记录彼此精确地划分，其意义是把每个记录作为现实 世界的实体对待，首先从这个角度完成第一步抽取，第二步把每一条记录从属性 的角度进行分解。m d r 把标签树中节点的路径看作一个字符串，并使用了比较 字符串编辑距离的思想从数据区中发现代表数据记录的结点，而m d r i i 则是以 树的结构信息代替标签字符串，从而达到对数据记录更准确的识别结果。对于结 果页面中记录的界定在文献【2 4 1 中早已提出，随着对页面结构和布局的不断认识， 这种方式被重新加以发展深化。 基于自然语言处理的抽取技术 自然语言处理技术通常用于自由文本中的信息抽取，也适用于结构良好的文 本。基于自然语言处理的w e b 信息抽取技术，通常包括句法分析，语义标注， 对象识别和抽取规则生成等步骤。采用这类信息抽取技术的典型系统有 w h i s k l 2 5 1 ，r a p i e r 2 6 1 ，s r v t 2 7 1 等。下面结合r a p i e r 和w h i s k 来说明这种类 型的w e bi e 。 r a p i e r ( r o b u s ta u t o m a t e dp r o d u c t i o no fi n f o r m a t i o ne x t r a c t i o nr u l e s ) ，采用 了自底向上的，由一般到具体的学习算法。从最具体的规则开始，然后用更一般 的规则进行替代。r a p i e r 的抽取规则建立在分隔符和内容描述的基础上，利用 了句法和语义信息描述所表达的规则。抽取规则由三个不同的模式过程组成，首 江苏大学硕士学位论文 先是前填充者( p r e f i l l e r ) 模式，它是待匹配文本之前的文本的模式；其次是填充者， 即待匹配目标文本的模式；最后是后填充者( p o s t f i l l e r ) ，它是待匹配文本之后的 文本的模式。 w h i s k 能够应用于各种类型的文档，包括结构化的文档以及自由文档。它 采用了覆盖学习算法生成多槽( m u l t i s l o t ) 抽取规则。w h i s k 规则建立在正则表达 式模式基础之上，该表达式标识了目标短语出现的上下文和短语之问的分隔符。 此外，系统需要一些手工标记过的训练实例来指导抽取规则的建立，并对生成的 规则进行有效性测试。w h i s k 规则生成的归纳方式是自项向下的，从能够覆盖 全部实例的一般规则开始，然后不断地往规则中添加项( t e r m ) 。 基于包装器归纳的抽取技术 采用这种技术的w e bi e ，根据事先由用户标记的样本实例，应用机器学习 方式的归纳算法，生成基于分界符的抽取规则。其中分界符实质上是对感兴趣语 义项上下文的描述，即根据语义项的左右边界来定位语义项。这类信息抽取方式 和基于自然语言处理方式的信息抽取技术最大的不同在于它仅仅是用语义项的 上下文信息来定位信息，并没有使用语言的语法约束信息。采用这类信息抽取技 术的典型系统有w i e n 2 8 1 ，s o f l m e a l y l 2 9 1 ，s t a l k e r i 3 0 1 等。下面结合s o f t m e a l y 和s t a l k e r 来说明这种类型的w e bi e 。 s o f t m e a l y 是一个通过归纳法，从样本中学习抽取规则，然后从半结构化网 页中抽取信息的系统。为了处理缺失属性和属性排列等问题，s o f t m e a l y 中引入 了有限状态变换器f s t ( f i n i t e s t a t et r a n s d u c e r ) 的概念。一个f s t 由两个部分构成： b o d yt r a n s d u c e r ，用于从页面中提取含有记录元组的区域；t u p l et r a n s d u c e r ，从b o d y t r a n s d u c e r 生成的b o d y 中抽取元组。每个不同的属性排列在t u p l et r a n s d u c e r 中都 有一条从开始状态到结束状态的路径，状态代表待抽取的属性以及一些冗余状 态，状态的转换取决予上下文规则的匹配，状态间的有向弧标明了相应的上下文 规则及输出字符。这里的上下文规则描述了相邻属性之间的分隔符等信息，系统 通过从训练样例中学习，归纳出上下文规则。为了能处理属性的排列问题，系统 需要学习各种可能的排列次序。 s t a l k e r 引入了内嵌目录( e m b e d d e dc a t a l o g ，e c ) 的概念，用以描述半结构 化的文档结构。e c 呈树状结构，叶子表示待抽取的属性，中间的非叶子节点表 1 2 江苏大学硕士学位论文 示元组的列表。对于e c 树中的每个节点，s t a l k e r 包装器算法将生成一条规 则用于抽取这个节点，同时还需要对这个节点进行分解，生成单个的元组。因此， s t a l k e r 将从复杂文档中抽取数据的任务分解成从高层次到低层次的一系列任 务。此外，为了处理缺失属性等问题，包装器要多次扫描文档。s t a l k e r 采用 了线性覆盖算法( s e q u e n t i a lc o v e r i n ga l g o r i t h m ) ，首先生成线性标志自动机( 1 i n e a r l a n d m a r ka u t o m a t a ) ，覆盖尽可能多的训练正例；然后系统试图生成新的自动机 以覆盖剩余的例子，一直到所有的训练例子都被覆盖为止。这时，s t a l k e r 返 回一个被称之为s l g ( 简单标记语法) 的解决方法，其每个分支都对应一个学 习获得的标记自动机。 基于模型的抽取技术 采用这类技术