（计算机应用技术专业论文）Web页面中结构化数据抽取的实现与应用.pdf

中文摘要 万维曜瓣飞速发展使得w e b 中存在的各种结构化数据信息数量与躁俱增。 然而，w e b 中可访问到的海量的结构化数据信息大都以半结构化的h t m l 网页文 档形式出现，很难被各种应用程序直接获取和使用。因此，旨在实现自动获取 h 斌网页中结构化数据的w e b 傣怠抽取技术已经戚力当今的一个研究热点。霉 前，已经有大量针对w e b 信息抽取的研究，并且出现了许多基于不同原理的w e b 信息抽取技术。 、 本文主要研究并提国了两种畿够处理特定类型网页的w e b 信息抽取方法： 第一秭方法用来处理相蹰模板生成的网页。它以一组周模板生成的网页为输 入，自动推断网页的生成模板，并利用获取的模板生成相应的网页包装器，实现 同模板网页中的结构化数据抽取。其中算法e x a l g基于 算法的核t j u e x a l g ，貉思想，利用h t m l 文档的树形结构对网页模板进行逐层推断。 ， 第二种方法主要处理网页中含有的某一专业领域中的特定半结构化文本。它 根据指定文本的特征而制定规贝f j ，并使用规则和特定字典来获取文本中含有的结 构讫数据，弱时使用一种字段名模糊匹配酶语义技术对获取数据浆类型进行爨动 标注。 两种方法的实验结果表明：第一种w e b 信息抽取方法在大多数情况下可以 正确的抽取结构化数据，第二种方法则需要在人工帮勃下进行信息抽取工作，或 者作为其他抽取系统的辅助丽使用。 论文在最后简要介绍了面向创新领域网络搜索引擎的系统框架，以及上述两 种w e b 信息抽取方法在该系统中的应瘸。 关键词：h t m l 网页结构化数据信息抽取网页模板等价类 a b s t r a c t t h er a p i d l yg r o w i n go ft h ei n t e r a c tm a k e st h ev o l u m no fs t r u c t u r e dd a t a i n f o r m a t i o ni nt h ew e bi n c r e a s i n gd a yb yd a y h o w e v e r , m o s to ft h i sm a s s i v e i n f o r m a t i o nw h i c hc a nb ea c c e s s e di nt h ew e bi sp r e s e n t e di nt h ef o r mo f s e m i s t r u c t u r e dh t m ld o c u m e n t s ，m a k i n gt h ei n f o r m a t i o nh a r dt ob eu s e db y s o m e a p p l i c a t i o n s 。t h e r e f o r e ，at e c h n i q u en a m e dw e bi n f o r m a t i o ne x t r a c t i o n ，w h i c hi st o g e tt h es t r u c t u r e dd a t aa u t o m a t i c l yf r o mh t m ld o c u m e n t s ，i sb e c o m i n gac u r r e n t h o t s p o tt o d a y a tp r e s e n t ，t h e r eh a sb e e n al o to fr e s e a r c ho nh o wt oe x t r a c t i n f o r m a t i o nf r o mw e bp a g e sa n dt h e r ei sa l s oaw i d er a n g eo fw e bi n f o r m a t i o n e x t r a c t i o nt e c h n i q u e s ，w h i c ha r eb a s e do nd i f f e r e n tp r i n c i p l e s h at h i sp a p e r , w ep r e s e n tt w om e t h o d so fe x t r a c t i n gs t r u c t u r e dd a t af r o ms p e c i f i c t y p e so fw e bp a g e s t h ef i r s tm e t h o di su s e dt od e a lw i t ht h ep a g e sw h i c ha r eg e n e r a t e db yt h es a m e t e m p l a t e i tt a k e s ，a si n p u t ，as e to ft e m p l a t e g e n e r a t e dp a g e s ，d e d u c e st h eu n k n o w n t e m p l a t eu s e dt og e n e r a t et h ep a g e s ，a n dm a k e st h ew r a p p e r st oe x t r a c tt h ev a l u e s e n c o d e di nt h ep a g e s 。t h ea l g o r i t h me x a l q j u p r e s e n t e di nt h i sp a p e ri sb a s e do n t h ea l g o r i t h m n a m e de x a l g , a n dd e d u c e st h eu n k n o w nt e m p l a t el a y e rb yl a y e ro n t h ed o mt r e eo f h t m ld o c u m e n t s 。 t h es e c o n di st oe x t r a c ti n f o r m a t i o nf r o ms o m es e m i s t r u c t u r e dt e x ti nw e b p a g e si ns o m es p e c i f i cd o m a i n i te x t r a c t st h es t r u c t u r e dd a t ai nt h et e x t su s i n gt h e r u l e sa n dt h es p e c i f i ch u m a n - m a k ed i c t i o n a r ya c c o r d i n gt ot h ef e a t u r e so ft h et e x t s ， a n da u t o m a t i c a l l ya n n o t a t e st h ee x t r a c t e dd a t au s i n gas e m a n t i ct e c h n i q u en a m e d f i e l d - n a m ef u z z ym a t c h i n g t h er e s u l t so fo u r e x p e r i m e n t s o nt h et w oa b o v em e t h o d si n d i c a t et h a tt h ef i r s to f o u rm e t h o d sc a nc o r r e c t l ye x t r a c ts t r u c t u r e dd a t ai np a g e si nm o s tc a s e s ，w h i l et h e s e c o n ds h o u l dc o o p e r a t ew i t ho t h e rt e c h n i q u et om a k et h er e s u l t ss a t i s f a c t o r i n g 。 a tl a s t , av e r t i c a lw e bs e a r c he n g i n es y s t e mw h i c hf a c e si n n o v a t i o nt e c h n i q u e s i n f o r m a t i o ni si n t r o d u c e da sa na p p l i c a t i o no ft h et w ok i n do fw e bi n f o r m a t i o n e x t r a c t i n gm e t h o d s k e yw o r d s - h t m lp a g e ，s t r u c t u r e dd a t a , i n f o r m a t i o ne x t r a c t i o n ，t e m p l a t e ， e q u i v a l e n tc l a s s 独创性声明 本入声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得基鲞盘鲎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所散的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：王姥 签字日期：翻7年多月7 7 目 学位论文版权使用授权书 本学位论文作者完全了解苤鲞叁鲎有关保留、使用学位论文的规定。 特授权盘窒基堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密螽适用本授权说臻) 学位论文 乍者签名： 上蒋 王一 导师签名：? l 岔膨 签字困期：更? 年厂月i7 网签字日期：跏7 年厂月7 日 第一牵绪论 第一章绪论 1 1w e b 信息抽取技术的发展背景 随着互联网的飞速发展及其网上用户的增多，网络上可访阂到的各魏信息数 据也在成倍增长。如今，互联网已经发展成为一个全球的、巨大的、分布和共享 的信息空间。不过，尽管在互联网中存在着大量的涉及各个专业领域的数据资源， 健其中的绝大多数并不向普通的嬲络用户提供直接访闻的权限，丽是通过某个网 站将所含的各项信息数据嵌入到相关网站的网页中，以h t m l 文档的形式出现在 w e b 上，限制网络用户只能通过网页测览器浏览查看信息数据，从而将自己隐藏 在所属网站髓背蜃，不能被用户直接访闯。然丽数据以这样的方式在网络上显示， 缺乏对数据自身的描述，其语义信息相对模糊，模式也不太明确，最终往往导致 一些应用程序无法直接解析并利用w e b 上的海量信息，从而造成了网络资源的 浪费。 另外，当前绝大多数网络用户对网上信息的查询都依赖于网络搜索弓l 擎。面 搜索引擎仅能通过关键字匹配对网络中的海量网页进行筛选查找，最后返回给用 户一组包含关键字的网页的链接作为查询结果。但由于大多数阙页中都含有与其 主题信息无关的“噪音 内容，如导航栏，广告链接等，因此搜索孳| 擎返回结果 的准确性有可能受到干扰；并且，用户为了获取所需的信息，必须通过人工方式 逐个浏览各个结果网页，自行查找所需数据信息，从而导致大量时间的浪费。 因她，为了解决上述阅题，增强网络中隐藏的结构化数据的可用性，增加网 页中数据的语义信息，人们提出了种新的w e b 信息处理技术w - c b 信息抽 取技术( w e bi n f o r m a t i o ne x t r a c t i o n ) 。w e b 信息抽取技术通过“包装”现有h t m l 信息数据源，将网页中的信息数据获取并以受为结构他、语义更加清晰的方式发 布出来，为应用程序利用w e b 中的数据提供了可能。 1 2w e b 信息抽取技术的难点 为了实现上述的w e b 信息抽取，研究人员做了大量分析和试探性的工作。最 初，人们曾以为只要采用某些简单的技术方法，即可将臣联网中所能访问到的结 构化信息轻易地抽取出来并为各种w e b 应用程序所利焉。然焉，实际情况却远毖 人们想像的要复杂和困难的多。因为，w e b 网络中存在的信息数据许多都以半结 构化的形式出现，并且这些结构的形式不但多种多样，而且还经常发生变化。因 第一章绪论 此，若要使某种应用程序能够直接利用w e b 中的信息数据，其程序的开发者将会 面对如下的许多难题i l j ： 首先，必须能够对包含有用户感兴趣的数据的h t m l 网页文档进行定位； 其次，必须能够确定用户感兴趣的数据在w e b 网页中的位置，并创建各种 可靠的规则对这些数据进行抽取； 再次，用来创建抽取规则的系统必须具有足够的通用性和易实现性，使其可 以对w e b 网络上可能出现的各种各样不同格式的网页进行信息抽取； 最后，由于互联网上各个信息网站经常改变其所含网页的格式设置与内容， 因此，信息抽取系统必须有能力正确应对这种w e b 网页结构上的频繁变化，保 证信息抽取的顺利进行。 而当前，大多数针对w e b 信息抽取的研究都将研究重点放在w e b 网页中的 数据的准确定位上，各种已有的w e b 信息抽取系统一般都通过使用系统生成的 包装器( w r a p p e r ) 来对某个特定信息源进行信息抽取。这些包装器把网页中含有的 半结构化数据转换成某种规范形式，并最终形成标准形式的结构化数据，从而使 得数据可以直接被应用程序利用或写入指定数据库。然而，绝大多数的自动信息 抽取系统只能够正确处理格式种类数量有限的h t m l 文档，并且不能很好的应对 文档中可能出现的结构变化。因此，在现实世界中存在着许多文档结构复杂的数 据源，其中的许多数据源单纯依靠当前的一种信息抽取系统难以进行正确的解释 和处理。 而理想中一个真正高效的信息抽取系统则应该能够正确的解释和处理各种 不同类型的网页，进行可靠的信息抽取，并流畅的应对网页结构的各种变化。一 旦处理网页的结构发生变化，系统应该能够对其进行识别并采用相应的信息抽取 技术进行处理。除此之外，系统还应具有良好的移植性，能够适用于各种不同的- 领域和数据对象类型。， 可以看出，一个高效的w e b 信息抽取系统的实现十分复杂，并且其中很有 可能结合运用多种不同的信息抽取技术以弥补相互的不足。因此，为了实现这种 高效的w e b 信息抽取系统，更好的进行w e b 信息抽取，许多技术研究人员和组 织从各种不同的角度出发，依据不同的方法原理对w e b 信息抽取技术做了大量 的研究工作，并获得了许多十分有价值的研究成果。 1 3w e b 信息抽取技术国内外研究情况 w e b 信息抽取技术需求的增加和各项相应研究工作的深入，推动了w e b 信 息抽取技术的发展。目前，已经出现了多种类型的w e b 信息抽取工具和系统。 第一章绪论 尽管这些工具和系统中大多数都是通过网页包装器来最终实现对某个数据源中 结构化数据的获取，然两其采用的方法原理和涉及的磅究领域却都不尽相同。 依据其识别定位w e b 网页中用户感兴趣数据的方法原理的不同，人们对各种 w e b 信息抽取系统和相关技术做了大致的分类f 1 2 ，3 1 ，其中的主要类型有：基于本 体的信患抽取( o n t o l o g y - b a s e de x t r a c t i o n ) 、基予位置的信息抽取( p o s i t i o n - b a s e d e x t r a c t i o n ) 、基于自然语言处理方式的信息抽取烈l p b a s e de x t r a c t i o n ) 、基于包装 器归纳方式的信息抽取( w r a p p e r - i n d u c t i o n b a s e de x t r a c t i o n ) 、和基于w e b 查询的信 息抽取( w e b q u e r y b a s e de x t r a c t i o n ) 。 1 3 1 基于本体的信息抽取 基于本体的信息抽取技术一般只针对某一已知的领域，通过使用各种知识和 属性来描述所要获得的数据，包括数据具有的各种关系，词汇外观( 1 e x i c a l a p p e a r a n c e ) ，上下文出现的关键字等。它不依赖于w e b 网页的h t m l 文档结构， 因此对网页结构的变化具有天生的抵抗性。其缺点是相应系统的实现需要大量相 关领域的专业知识，系统的冒标数据在嘲页中定要有唯一的标签进行标记，相 应系统的使用范围受到所针对领域的限制，因此可移植性不强。 采用这种方式的w e b 信息抽取系统有：b r i g h a my o n gu n i v e r s i t y 信息抽取小组 开发的信息抽取工具 4 1 ，希i q u i x o t 系统【5 ，6 】等。 以b y u 系统为例：b y u 系统事先需要由领域知识专家采耀人工的方式对某 一应用领域的o n t o l o g y ( 包括对象的模式信息、常位，关键字的描述信息，其中常 值和关键字提供了语义项的描述信息) 进行书写描述。系统根据边界分割符和启 发信息将源文档分割为多个描述某一事物( 如汽车广告) 不同实例的无绩构的文 本块，然后根据o n t o l o g y 中常值和关键字的描述信息产生抽取规则，对每个无结 构的文本块进行抽取获得各语义项的值，最后将抽取出的结果放入根据o n t o l o g y 的描述信息生成的数据库中强】。 1 3 2 基于使置的信惠抽取 基于位箴的信息抽取技术利用h t m l 文档天生具有的树形结构特征来实现 h t m l 文档孛的信息抽取。萁系统通常先把h t m l 文档按照其中的h t m l 标签解析成 d o m 树的形式，再通过某种方法把所要抽取的数据定位在树的某个层次位置上， 最后通过自动或半自动的方式生成一个相应的正则表达式( r e g u l a re x p r e s s i o n ) 形 式的抽取规则，通过使用规受| j 将数据从文档中提取出来。使用这类方法进行信息 抽取的准确率和召回率都极高，其输入也只需要相应的若干示例网页，因此适用 于各个不同的知识领域。缺点是天生对结构性的过分依赖，使得它在应对网页结 第一肇绪论 构变化时非常被动。 采用基于位置的信息抽取黧w e b 信息抽取系统毽括：l i x t o 7 , s 系统， x w r a p 9 1 ，r o a d r u n n e r t l 0 1 ，w 4 f 1 1 1 和i e p a d 【1 2 】。本文第二章中提出的e x a l gt j u 算法也属于这种类型。 鉴于上述的基于本体的信息抽取和基于位嚣的信息抽取两种方法其优缺点 的互补性极强，某些信息抽取系统有机地结合了这两种信息抽取方法，实现了一 个宙适应的高效的信息抽取系统( a d a p t i v ei n f o r m a t i o ne x t r a c t i o n ) ，如a m o r p h i c 信 息抽取系统【l 】；该系统使用基于位置的信息抽取方法对网页进行处理，得到正则 表达式形式麴包装器，并进行信息抽取；一旦遇到阚页结构发生交纯的情况，通 过基于本体的方法，自动进行包装器的修改与恢复，从而增强系统的健壮性。 l 。3 。3 基于自然语言处理方式的信息抽取 基于自然语言处理方式的信息抽取技术主要适用于源文档中包含大量文本 的情况( 特别针对于合乎文法的文本) ，在一定程度上借鉴了自然语言处理技术， 利用子旬结构、短语和子句问的关系建立基于语法和语义的抽取规则实现信息抽 取。譬前粟雳这种原理豹典型豹系统有r a p i e r 1 羽，s r v 堋，w h i s k 1 翻。其优点是 利用了自然语言处理技术的思想，适用于含有大量文本的w e b 网页处理。缺点是 没有利用w e b 网页h t m l 文档独特于文本文档的树状层次特性。 以基于自然语言处理方式的典型代表w h i s k 为铡：对于自密文本，系统首 先根据分割符将源文档分割成多个实例( 每个实例是一个语义相关的文本块，如 在一个广告页面，每一则广告为一个实例) 。在交互式的环境下，系统每次呈现 给用户一组实例。用户在可视化的环境下根据系统提供的实例标记出感兴趣的信 息势定义模式。系统使耀语法分析嚣和语义类( 如人名、机构名) 分析器，分析出 用户标记信息的语法成分和对应的语义类，生成基于语法标记和语义类标记的抽 取规则，实现信息抽取【3 】。 1 3 4 基于包装器归纳方式的信息抽取 基于包装器归纳方式的信息抽取，需要爝户自己标记组h t m l 文档作为样本 实例输入系统。系统将输入的样本实例作为训练样例，按照一定的偏置规则进行 学习，著最终归纳生成一组有效蕊抽取规则作为包装器，对h 疆n 文档进行抽取。 其优点在于不受应用领域和h t m l 文档结构的太多限制，大部分此类型信息抽取系 统最终生成并使用基于定界符的抽取规则，而这种规则使用灵活，表述性很强。 采用这种原理技术的典型系统有s t a l k e r 强l ，w i e n 1 列，以及主要用来包装h t m l 文档中t a b l e s 和l i s t s 的w l j 。 第一章绪论 其中，s 山跹r 系统是根据用户事先标记的样本页面和用户以嵌入式分类 封形式提供蠡g 页瑟结构傣息，应焉逐步覆盖算法，逐步j | 鹭纳生成基于定界符的抽 取规则，实现层次的信息抽取。w i e n 系统中事先由用户标记样本页面，系统根 据页面逻辑结构的不同，使用不同的启发式归纳算法生成不同的包装器。如，如 果菜页两具有h l r t 结构( 页面由h e a d ，b o d y ，t a i l 三部分，其中b o d y 由多个可 使用左右标记分割的记录的列表组成) ，则产生一个h l r t 包装器【3 】。 l 。3 。5 基于w e b 查询的信息抽取 基予w e b 查询的w e b 信息抽取系统比较少见，是具有w e b 技术风范的信息抽 取。它将w e b 信息抽取转化为使用标准的w e b 查询语言对w e b 文档的查询，具有 通用性。其代表系统n w e b o q l 1 9 , 2 0 。 w e b o q l 是类似于s q l 语句的w 曲查询语言，它具有定位感兴趣信息和结构 重构的功能。系统利用w e b o q l 语言提出了一种通用的h t m l 包装器框架。系统 首先将输入的w e b 文档解析成棵抽象的h t m l 语法树h y p e r t r e e ，然后用户在信息 抽取之前根据页面的结构和标记写出合适的查询语句实现信息抽取。该系统试图 将w e b 信息抽取转化为w e b 查询，但著没有看到其实现。w e b 。o q l 仅作为一种 w e b 查询语言出现，并为x q u e r y 规范的形成作出贡献【3 1 。 1 4 论文工作说明 本论文主要针对两类网页的信息抽取问题进行研究，提出了相应的信息抽取 方法，并将其应用到一个面向匈新领域的垂直搜索弓| 擎的系统建设中。论文中各 部分工作的内容大体如下： 1 论文在第二章提出了一种处理相同模板网页的信息抽取方法一一 e x a l gt j u 算法。e x a l g h t m l 文档的树型结构对网页模板进行逐层推导，最终实现对同模扳生成网页 的模板推断和结构化数据抽取。 2 论文在第三章提出了一种针对某一领域网页中的特定半结构化文本的信息 抽敬方法。通过这种方法，某些半结构文本中的特定数据信息w 以被提取出 来，并进行自动标注。 3 论文第四章中简要介绍了作者参与建设的面向创新领域的垂真搜索引擎的 系统框架，并对系统内部的w e b 信息抽取模块巾上述两种信息抽取技术的相 。关运用与主要的工作流程做了简单描述。 第二章狸同模扳页面豹模板推断窝结构纯数据抽取 第二章相同模板页面的模板推断和结构化数据抽取 2 1 介绍 上章已经提到，在w e b 网络中存在的海量信息数据，大多数都是以半结 构化h t m l 文档的形式存在于网络上，很难为应用程序所直接获取和使用，因此 对相应信息的查询和使用存在着许多不便，入们迫切需要一种w e b 信息抽取技 术将网页中的结构化数据抽取出来。但由于w e b 网络上的霹页复杂多样，通过 一种技术将所有的结构化数据从各种网页中抽取出来实际上是难以实现的。因 此，人们对w e b 信息抽取技术的研究都将其处理的对象范围限制在某些特定类 型或领域的网页上，从而降低了实现w e b 信息抽淑的难度。 而通过观察人们发现，互联网中的许多网站具有如下特点：同一网站中包含 羞大量结构相似的网页，并且这些网页内部含有的信息数据具有相同的结构模 式，而网页闯内容不同的部分大都是这些信息数据的组成部分。之所以产生这种 情况，是因为上述这些网站中的网页一般都是通过动态网页生成技术，将相同结 构模式的结构化数据嵌入到某个固定的网页模板而生成。而这种模式相同的结构 化数据大都由网站从某个数据源( 如一个关系型数据库) 中获得。学界把这种结 构相似的一组网页称之力一组具有相同模扳的w e b 网页。 在现实生活中，许多商品信息网站，如图书销售n j n c h i n a p u b 2 2 】( 图2 - 1 ) 等，其中单个商品信息所对应的页面大都属于这种其有相同模板的网页。如果能 够将这类网页中含有的结构化数据信息抽取进来，并存入至l 某个数据系统被应用 程序所使用，那么对这些商品的信息查询将会变得更加方便灵活。 第二章相同模板页面的模扳推断和结构化数据抽取 网页1 罾蟊 网页2 图2 - 1c h i n a - p u b 中两个图书信息网页 为了解决相同模板的网页中的结构化数据抽取问题，人们提出了各种不同的 信息抽取方法和技术。其中，较早期使用的信息抽取技术需要程序员根据自己对 指定网页模板的了解而手工编写相应的抽取规则，然后再将这些规则输入到包装 器生成程序获取相应的网页包装器，并最终实现结构化数据的抽取。而近期的新 型抽取系统则以人工标注过的少量网页作为训练样本，自主学习网页模板的相应 知识并生成对应的网页包装器，如前面提到过的w e b 信息抽取系统x w a r p ， w l e n ，s t a l k e r 等。然而，可以看出，上述这些信息抽取技术和系统对网页 模板相关知识的获取都要依赖于人工的输入，但人工输入的过程既要消耗大量的 时间叉容易产生错误。因此，为了避免人工输入所带来的各种问题，有些研究者 又提出了一些不需人工输入即可进行网页模板推断和信息抽取的方法与技术。其 中比较有名的有13 2 节中提到的r o a d r u n n e r 和1 e p a d 。然而r o a d r u n n e r 和i e p a d 虽然在处理w e b 网页信息抽取的问题上具有一定的优势与特点，但两 种方法自身仍存在蓍不一些可避免的缺点和问题。例如，两种方法都认为h t m l 文档中的标签是网页模板的一部分，但实际中存在着许多与其不相符的情况，如 u r l 链接类型的数据被包含在h t r a l 标签 中网页的文车数据中常夹杂的许 多与格式有关的标签 、( b r 、p ) 、 等都有可能是文本数据内容的一部 分。 因此。为了更好的解决相同模板网页的模板推断和信息抽取问题，在本章的 下面，论文研究井提出了一种基于位置的信息抽取方法e x i ot i u 算法。 e x a l gt j u 算法基于一种名为e x a l g 算法口q 的核心思想，在对相同模板网页的 处理过程中不需人工输入，并且在向题的公式化定义和算法的核心思想上与 i l 盏1 ：i 第二章糖露模板页西的模板推凝和结构纯数据抽取 r o a d r u n n e r 和i e p a d 前两种系统有着根本性的不同，因此能够在一定程度上避 免避现与上述两种方法相同的问题。 2 2 问题的描述与定义 2 。2 。l 模型与问题的公式化定义 要处理具有耱同模板t 臻w e b 照贾，首先要为具有相同模板的网页下一个明确 的定义，即：如果有一组具有相同模板的网页存在，则认为其中的所有网页都是 由具有相同结构模式s 的不同结构化数据值x i 与x i 所对应的模板实例t ( x i ) 按照 定规则整合到一起所形成的一个整体，瘸公式可将其表示成如下的形式： 鼻= x io t ( x j ) ，( 1 i 弹) 其中，c 表示具有相同模板的网页集合p = e ”，只 中的任意一个网页，n 为集合中的网页个数；x ，表示网页置中所含的结构化数据；丽t ( x ，) 则表示对应 结构化数据x ；所形成的模板实例；符号“o ”表示以特定豹方式进行组合。 ( 鑫：露) ( c ：忍) c o ：曼) 霪2 2 ：网页集合p 国：最) 第二章相同模板页面的模板推断和结构化数据抽取 如图2 - 2 中表示的一个网页集合p ，其中包含的网页个数n = 4 ，各个网页所 表现出来的数据实例x ；的组成部分分散在对应网页中的各个位置，其在图中网页 的h t m l 源码中以斜体字动耐的形式标记，而网页中组成模板实例的所有符号 以黑体字a b c d 的形式标记。 由图2 2 可以看出，定义中的网页模板t 并不是一个静态的固定不变的有序 字符串集合，模板t 的相同也不是指t 在各个网页的实例中所有字符和符号的 出现次数与顺序位置完全相同。实际上的模板t 的相同是指生成所有模板实例所 使用的以结构化数据变量x 为参数的函数t ( x ) 是相同的，即t 代表的是模板生 成函数t ( 曲。 另外，通过大量观察与经验，人们普遍认为，函数t ( x ) 是以一个有穷自动机 的形式存在的，所以，对t ( x ) 的推断实际上是对一个正则文法的推断过程，属于 正则文法推断的范畴。 因此，要解决具有相同模板的w e b 网页的结构化数据抽取问题，所设计的 算法的实现应该分成两部分： 1 通过输入的网页集合p = 只l1 f n ) ，推断出p 中网页的相同模板t ； 2 利用己求得的模板t ，生成同类网页的包装器w r a p p e r ，进而对同类网 页进行信息抽取，从而得到所有网页只所对应的结构化数据实例x ，。 而在对模板t ，即t ( x ) 进行推断之前，必须首先对t ( x ) 的参数结构化数 据x 的结构组成和表现形式做一个明确的规定，然后再对模板t ( x ) 的具体形式做 出针对性的规范。下面两节就为结构化数据和模板构成做一个详细的定义与描 述。为了便于理解，在下面所作的各个定义后面都以图2 2 中的网页集合p 为例 进行直观的举例说明。 2 2 2 结构化数据的形式定义 若将一个数据值集合中的所有元素按照某种特定的结构组合在一起，其形成 的有机整体就是结构化数据x 的一个实例，而所使用的结构被称为结构化数据x 的模式s 。 尽管结构化数据的模式和其中的子结构种类繁多，然而这些结构的类型可以 通过递归的方式定义为以下三种： a ) 基础类型：是表示数据值集合中基本元素的类型，不可再分割，记为符 号b 。它指代了一个“词”( t o k e n ) ，是组成文本的最基本的单位元素。 ( 在文献【2 1 介绍的e x a l g 算法思想中，t o k e n 被定义为h t m l 文档中文 第二章禳同模板页嚣的摸板推断和缀构纯数据抽取 本内容的一个词或一个h t m l 标签。为了区分t o k e n 在代表数据符号串和 模板符号牢时的不同，论文中把表示数据信息的t o k e n 称之为d a t a t o k e n ， 如图2 2 中斜体字字符串；把表示模板信息的t o k e n 称之为 t e m p l a t e t o k e n ，如图2 2 中黑体字字符串；d a t a - t o k e n 与t e m p l a t e t o k e n 共同组成了p a g e t o k e n ，p a g e t o k e n 代表罄网页中的所有t o k e n 。) b ) 有序n 元组类：如果互，疋，疋分别表示数据的某种结构类型，则由这 些结构类型组成的有序表互，如，l 表示一个新的结构类型，即有序 n 元组类。而将夏，疋，瓦这些类型组合生成新类型 的构 造器记为有序n 元组构造器。 c ) 集合类：若丁是某一种类型，则集合 n 也是一个类型，即集合类。将类 型r 构造成类型 n 的构造器记为集合构造器。 相应的，上述三种数据结构类型对应的数据实例其定义也以相同的方式表示如 下： a ) 基础类型b 的一个实例是数据集合中的一个基本数据元素。 b ) 有序n 元组类型 的实例可写为 ，其中 i ii ：，i 。分别为互，t9 - 。9 疋各类型的相应实例。 c ) 结构类型 码的一个实例是一个集合 8 ；，e ：，e 。 ，丽其中e i ( 1 i 冬删) 为 类型r 的一个实例。 按照上箍数据结构类型的定义，可以对图2 2 中的4 个网页所包含的结构化 数据做如下分析： 图2 2 中的圜个网页p l ，p 2 ，p 3 ，p 4 所含的所有数据元素的集合依次为： d t = d a t a b a s e s ，j o h n ，7 ， ； d 2 = d a t am i n i n g ，j e f f ，2 ，j a n e ，6 ， ； d 3 = q u e r yo p t ，j o h n ，8 ，) ； 、 d 4 = t r a n s a c t i o n s 。 4 个数据集合中的所有元素都是某个基础类型b 的一个实例，如书名 “d a t a b a s e s ”，“d a t am i n i n g ”等，对应的类型记为b 1 。 若设4 个网贾所含结构化数据的模式相同，记为s ，则通过网页的部分结构 的重复性发现：模式s 中存在有序3 元组类型，在各个阙页中对应的有序3 元组 实例分别为j o h n ，7 ， ； x 2 一 d a t am i n i n g ， ； x 4 = 。 而网页中的结构化数据x 的模式为s = 。 文献 2 l 】中还提到过两种特殊的结构类型：( r ) ? 和( 互l 疋) 。( 乃? 表示在当 前位置，r 类型的结构化数据最多出现一次，也可能不出现，它等价于 及，其 中 丁) ，的集合构造器r 将集合中丁类型实例的个数限制在0 和i 上；( 互i 疋) 表示 当前位置出现互或互类型的结构化数据，等价于 ，其巾集合构 造器爻和矗的其中一个把集合类的实侧个数限制为1 ，焉另个限制为0 。 至此，网页中结构化数据的形式定义基本已经完整。而实际中，一个结构化 数据x 的模式s 一般是在将其从数据源( 数据库或其他数据系统) 中取潞的过程 串决定的。焉一璧某个结构化数据x 被从数据源中获取，网站就要根据其模式s 确定相应的模板t ，并将其编码生成一个新的h t m l 网页。至于编码生成网页的 过程，则需要下面介绍的网页创建模型和模板的共同参与。 2 2 3 网页生成模型和模板 在使用模板生成网页的过程中，网页生成模型( m o d e lo fp a g ec r e a t i o n ) 首 先从网站的数据库中得到结构化数据x 和x 具有的结构模式s 。然后网页生成模型 使用对应模式s 的模板r 对s 审包含的各个类型构造器瓦进行相应的编码映射，得 到对应的字符串或有序字符串集合t ( r ；) ，即所谓的模板实例。最后网页生成模 型将所有的t ( r ，) 与x 中的相应数据值进行组合，最终得到一个字符串2 ( t ，x ) ，即 为网页p 的源代码。图2 3 为网页生成模型静流程示意黧： 第二豢耀同模投页面的模叛推断移缀构纯数据攒取 图2 - 3 网页生成模型 而其中模板t 关于数据类型构造器f 的映射丁( r ) 根据f 的类型不同，具体内 容形式分别如下： 小若f 是一个有序n 元组构造器，则t ( o 是- - 4 n + 1 个字符串组成的有 序集合 c ：。cm 川) ； 。 b ) 若f 是一个集合构造器，则联f ) 是一个字符串s ) 【。 为更清晰蕊表嘴联f ) 的映射过程，举例如下： 例2 1 ：如图2 - 2 中的4 个网页，已知其结构化数据模式s = 。 设数据类型正吠b 2 ，b 3 ，b 4 龟，疋= 互 码，则s 联b 1 ，乏f l 。 其中有序2 元组类型b 1 ，乏 霸的类型构造器为，则 f ( 0 )= b o o k n a m e ， r e v i e w s ， ； 有序3 元组类型互b 2 ，b 3 ，b 4 扬酸类型构造器为奶，则 r ( r ，) = r e v i e w e rn a m e ， r a t i n g ， t e x t b ，跏 ； 集会类型乏一 夏) 强的类型构造器为乃，则 r ( f 3 ) = s ；= “舻”。 盘此可见，霹页生成模型通过对应s 的模板誓熬映射函数r ( f ) ，生成了网 页中的所有t e m p l a t e t o k e n 并将其按照一定的先后顺序和嵌套关系输出。 丽五仃，x ) 作为网页创建模型中的编码丞数，其在函数丁( 力的基础上定义如 下： 第二章相同模板页面的模板推断和结构化数据抽取 a ) 如果x 属于一个基础类型b ，字符串a ( t ，x ) 则是x 本身，即对应各种模 板t 和基础类型b 的实例e ，都有力( 丁，e ) = s 。，其中s 。表示实例e 的字符 串表示； b ) 如果x 是一个形如( x ，x 。) ，的有序n 元组类型的一个实例，其中有 序n 元组类型构造器为f ，且r ( r ) = ( c ，c 州) ，则名p ，x ) 为字符串： c 1 2 ( t ，x 1 ) c 2 2 ( r ，x 2 ) ( 丁，x 。) c ； c ) 如果x 是一个形如 e i ，e 2 ，e m ，的集合，t ( r ) = s ，则4 ( r ，x ) 是字符 串z ( t ，e i ) s 2 ( t ，e 2 ) s s a ( t ，e 。) 。 由此可见，一4 ( r ，x ) 函数输出返回的是一个字符串，包含d a m t o k e n 和 t e m p l a t e t o k e n ，即2 ( t ，x ) 将网页中与结构化数据x 相关的所有p a g e t o k e n 按顺序 输出。而当x 为一个完整的结构化数据时，2 ( t ，x ) 即为x 对应的整个网页的编 码。 2 2 4 综述与问题 综上所述，网页创建过程中网站首先从相应数据源中获取结构化数据x ，并 得到其结构类型模式s ，使用s 所对应的模板t s ，进行针对x 的网页编码，最终得 到输出的字符串五( r s ，z ) ，即为传递数据x 信息的网页p 的编码，从而生成网页。 这一系列的步骤构成了网页创建模型的工作流程。 而论文中所要完成的w e b 信息抽取其目标恰恰是实现网页创建的逆过程，即 在获得多个具有相同模板的网页 p ，的基础上，通过某种算法推断出网页生成所 使用的模板t 8 ，进而得到网页集合 p 中所包含的全部结构化信息x ，最终实现网 页的结构化数据抽取。 然而，前面已经提到过，网页模板t 的推断属于有穷自动机和正则文法的推 断，输入的网页为相应正则文法的正例。这为模板t 的学习和推断制定了一个偏 置假设，即认为最终的目标模板应该以某种正则语言的形式存在。实际中也正是 如此。但是，理论上正则文法及其相应的有穷自动机仅凭有限数量的正例是不能 进行推断的，因此，对于一个给定的包含有相同模板n 个网页的集合 p ，9 , , - 9 p 。 中， 按照上述两节中的定义和正则文法知识可知，存在多个不同的模板t 1 ，t 2 ， t m 都能够与相应的数据值集合 x ，9 - 9 x 。) 一起生成指定的网页，即所能求出的符 合条件的模板并不是唯一的。 因此，如何在一个所有可能解的集合中选择一个最优解作为最后求得的模 板，这是在进行网页生成模板的推断过程中所必须解决的问题。而这个问题的解 决需要求助于新的偏置假设，使所属的算法在众多的模板t l ，t 2 ，t m 中按照 第二章摇霹模板页面酶棱叛推断帮结构讫数据抽凝 某固定的规则选磁唯一的模板t i 。e x a l g 算法中的思想为其提供了一种近似的 解决方案。 2 3e x a l g 算法思想及分析 2 3 1e x a l g 算法思想简介 文献【2 l 】中介绍了w e b 信息掬教算法e x a l g 的大体思想。e x a l g 算法主要 用来解决具有相同模板的网页中结构化数据抽取的问题。它以一组具有同模板生 成的网页集合为输入，按照2 2 节中的问题定义对网页集合中结构化数据的模式 s 和相应模板誓5 进行推断，从而获得网页模板t ，并利用模板t 生成相应的网燹包 装器w r a p p e r ，最终实现对具有相同模板网页中所含的结构化数据实例x 的获取。 e 地g 算法