web数据抽取工具综述.docx
《web数据抽取工具综述.docx》由会员分享，可在线阅读，更多相关《web数据抽取工具综述.docx（15页珍藏版）》请在冰点文库上搜索。
web数据抽取工具综述
A Brief Survey of Web Data Extraction Tools
Web数据抽取工具综述 译/Matrox
摘要
近年来的文献表明，研究人员已经开始试图解决在从网页中提取数据时面临的问题。
该问题的重要性在于，一旦完全抽取出页面中的数据，即可按照类似传统数据库的方式对其进行处理。
这些文献的方法借鉴了其他领域的技术，例如自然语言处理，语言和语法，机器学习，信息检索，数据库，和本体论等等。
这些方法各具特色，以至于对它们作直接比较困难重重。
本文提出了一种用于区分Web数据抽取工具的分类法，同时简要介绍了文献中提及的数种主要的Web数据提取工具，并对其进行定性分析。
我们希望这项工作能起到抛砖引玉的效果，期待将来出现对Web数据抽取技术及相关工具的更全面的研究。
1.介绍
随着互联网爆炸式的发展，很多主题信息已经可以从网上获取。
这为用户以不同方式搜集信息提供了方便。
通常，用户以在浏览器上浏览网页，搜索关键词等方式查找网络中的数据，然而这些检索方式有一定的局限性。
浏览器不适合定位特定的数据项，因为数据项对应的超链接通常冗长的令人生厌，并且可能已经失效。
使用搜索引擎有时比单纯的浏览网页更有效率，但它往往一次返回大量数据，这远远超过了用户的处理能力。
因此，尽管Web数据是完全公开的并可随时浏览，但是它也不像传统数据库那样，可以方便的查询或修改。
为了改善Web数据的处理效果，一些研究人员诉诸于数据库领域。
然而，数据库本身是由结构化数据组成的，因此传统的数据库技术无法直接应用于对Web数据的处理。
作为一种网路上结构化数据的标准，XML技术为解决这项问题带来了一丝曙光，然而这种技术并没有对处理已存在的Web数据提供一种通用的方式。
事实上，半结构化或非结构化数据已经大量存在于网络中，并仍在不断增多。
所以，一种解决这个难题的可能的方式是先从网络资源中提取出数据，再将其填入数据库以待下一步处理。
传统的Web数据抽取方式是构建专门的“包装器”程序来识别数据并将其转化为适当的格式，如XML、关联式表格等。
对于包装器而言，最具挑战性的任务是从大量的无价值文本段（例如，标记，内联代码，导航条等）中提取有用的信息。
这些数据可能是扁平结构的，也可能结构比较复杂或隐含了多层次的结构，而这一点往往并不确定。
这意味着数据可能会出现结构性的变化。
包装器必须具备承受这种变化的能力，并对其作相应的处理。
人工创建的包装器有很多众所周知的缺点，主要是难以书写与维护。
不过最近出现了很多改进的包装器创建工具[ 3，4，8，9，10，11，14，16，18，20， 23，28，30，31 ] 。
这些工具是基于几个不同的技术的，如描述性语言[ 4 ，9 ，16 ] ， HTML结构分析[ 10，23，31 ] ，自然语言处理[ 14，28，32 ] ， 机器学习[ 8，18，20] ，数据建模[ 3，30] ，本体论[11]。
构建用于抽取Web数据的包装器的问题描述如下：
给出包含一组隐藏对象的网页S，然后确定一个映射W以将S中的所有对象填入数据仓库R。
映射W必须能从S的任意相似页面S'中识别并抽取数据。
我们使用的术语“相似页面”由经验得出，通常指的是同一个站点或Web服务中的页面，例如同一个网上书店。
从这个角度来说，包装器其实就是映射W的一个实现。
所有包装器生成工具的共同目标之一是产生高度准确与健壮的包装器，同时包装器构建者的工作量要尽可能小。
但我们即将看到，实际应用中创建者将不得不对包装器的自动化程度和灵活性进行权衡。
随着越来越多Web数据抽取工具涌现，对它们的功能与特性进行分析的需求逐渐增多。
本文将简要地介绍一些文献中提出的Web数据抽取工具，并探讨每个工具对Web数据抽取技术的一些重要特性的支持程度。
比较Web数据抽取技术的先驱是网站RISE[26]。
这个网站提供了应用了机器学习或自然语言处理等各种技术的工具的实验结果，包括STALKER [28]，WHISK [32]， SRV [14],，WIEN [20]， 和 RAPIER [8]。
这些定量结果是由工具的开发者自己提供的。
遗憾的是，很少有可以直接比较不同工具生成结果的情况。
在文献[27]中，Muslea对比了不同类型机器学习算法所抽取的模式。
然而，尚未有能更全面分析Web数据提取工具方法，主要原因是难以建立一个一般化框架来评比这些工具。
本文在此方向进行了初步的尝试。
本文结构安排如下，第2节介绍一种针对Web数据抽取工具的分类方法。
第3节概述文献中提及的几个重要的数据抽取工具。
第4节定性分析这些工具。
第5节最后给出结论。
2.一种.Web数据抽取工具的分类方法
本节提出了一种为我们已研究过的工具进行分组的分类法。
分组的依据是每种工具生成包装器的主要技术手段，包括：
基于包装器专用语言的， 以HTML为中间件的，基于自然语言处理的，基于包装器归纳的，基于模型的和基于本体的Web数据抽取方法。
尽管此分类法易于叙述，但事实上一个工具可能包含两种以上不同的技术手段。
不过这种分类法对理解现有的Web数据抽取方法有所帮助，也有益于评估基于某技术的工具对特定应用的适应性。
下面我们将分别描述每种分类的主要特征。
开发包装器的专用语言
解决包装器生成问题的第一个办法是提供协助用户创建包装器的专用语言。
这种语言用于替代传统的程序语言，如Perl和Java。
目前这种技术手段仍比较流行，其比较著名的工具有Minerva [9], TSIMMIS [17], 和Web-OQL [4]。
其他如FLORID [24] 和Jedi [19]等也比较有代表性，但这几个工具不在本文讨论之列。
以HTML为中间件的工具
这类工具依靠HTML文件固有的结构特点进行数据抽取。
在抽取之前，其首先将HTML文档解析成一个可以反映HTML标记层次的解析树,然后半自动地或自动地创建提取规则，并将规则作用于解析树。
此类工具的代表是W4F [31], XWRAP [23], 和RoadRunner[l0]。
另一个可被认为是基于此类技术的工具是Lixto [5],
基于自然语言处理的工具
一些工具已经采用了自然语言处理 （NLP） 技术，用来对自然语言文档提取抽取规则并抽取相关数据。
这些技术通常以词性标注和语义标注作为过滤器， 来构建短语与句子成分间的关系，并以此导出基于句法语义约束条件的过滤规则。
这些约束条件有助于判断同一个文档中的相关信息。
以NLP为基础的工具通常适合提取主要由类似电报风格的自由文本组成的网页，例如工作列表，公寓出租广告，研讨会通知等等。
此类技术的代表工具有 RAPIER [8]， SRV [14]， and WHISK [32]。
包装器归纳工具
包装器的归纳工具从一组训练样例中归纳出基于分隔符的抽取规则。
这些工具和基于NLP的工具之间最大的差别在于，它们并不依赖于语言约束，而是依赖于数据的格式化特征。
这个特点决定了这种工具比基于NLP的工具更适合于抽取HTML文档。
其代表有：
WIEN[20]，SoftMealy[18]和STALKER[28]。
基于模型的工具
这些工具需要用户操作图形界面，从中建立文档中有价值对象的结构模型，“教”工具学会如何识别文档中的对象，从而抽取出这些对象。
代表工具有：
NoDoSE[3]，DEByE[21,30]。
基于本体的工具
前面介绍的所有技术依赖文档中的数据结构特征产生规则或模式，然后进行抽取。
然而，数据抽取也可仅依赖数据本身。
给定一个特定的应用领域，可以利用本体来定位数据信息，并构建对象。
最具代表性的基于本体的工具是由 Brigham Young大学创建的Data Extraction Group [11]。
3.Web数据抽取工具概述
本节将概述已研究过的Web数据抽取工具。
尽管试图阐述近期文献中所有有代表性的工具，但我们的研究尚不彻底，所以本节内容并未涉及所有已知的工具。
本节提及的所有工具均在第2节的分类中有所介绍。
3.1 开发包装器的专用语言
Minerva——作为Araneus系统[25]的重要组件，Minerva[9]是典型的包装器语言。
Minerva结合了以文法为基础的技术与传统程序语言的特点。
Minerva的语法以EBNF风格定义：
对每一个文档定义一个生成器，根据终结符与其他非终结符定义一个生成器非终结符的结构。
Minerva以一个可以搜索与重构文档的编辑器作为补充，该编辑器提供了正常文本编辑器具备的各种基本操作。
为了处理Web数据中的不规则项，Minerva提供了一个明确的程序处理机制来解决语法分析器中的异常。
对于每一个文法生成器，用户可在其中添加一段包含了编辑器代码的异常处理规则。
一旦生成器解析失败，程序将抛出异常并作相应的异常处理。
TSIMMIS——与众多半结构化数据管理组件类似，TSIMMIS[17]可以由用户编写的规范文件来配置包装器。
规范文件由一个定义抽取步骤的命令序列组成。
每一个命令的形式是[变量，源，模式]，其中变量代表抽取结果，源代表输入文档（比如，一个网页），模式允许匹配源中感兴趣的数据。
变量中储存的数据可被用作后续命令的输入。
一个基于规范文件的抽取器解析HTML页面，定位并抽取感兴趣的数据。
所有过程结束时，变量集将持有抽取结果。
尽管我们并未将TSIMMIS定义为正式的包装器语言，但考虑到其在信息抽取历史上的重要价值，我们把它加入这篇综述。
Web-OQL——。
Web-OQL最初的目的是提供在Web上执行类似SQL查询的服务。
Web-OQL是一种描述性的查询语言，能够定位在HTML页面上的数据块。
为了达到这个目标，包装器将页面解析为抽象的语法树hypertree来表示页面。
根据该语言的语法，用户可以书写在hypertree上定位数据的查询语句，并以合适的格式（如，表格）输出这些数据。
以上就是Web-OQL的数据抽取过程。
此外，程序还支持对hypertree的导航操作。
3.2 以HTML为中间件的工具
W4F——W4F[31]是一个用于创建包装器的工具包。
W4F将包装器构建过程分为3个阶段：
用户首先描述如何存取文档，然后描述应当抽取哪部分数据，最后声明抽取的数据以何种结构存储。
一旦在网络中根据至少一条检索规则检索到一个文档，HTML解析器将根据文档对象模型（DOM）[34] 创建一棵解析树。
抽取的数据将以W4F的内部格式NSL（嵌套字符串列）的形式存储起来。
最后，根据特定的匹配规则将NSL结构输出给高级应用程序。
W4F中用以定义抽取规则的语言被称为HEL（HTML提取语言）。
W4F提供了向导程序，以协助用户书写用于抽取树节点数据的抽取规则。
对于一个给定的Web文档，程序呈现给用户一个带有额外注释的相同文档。
用户点击感兴趣的信息段，然后由向导程序返回相应的抽取规则。
向导程序并不能处理数据项的集合。
所以用户如果选取多个同类型的数据项，必须在路径表达式中增加集合项，以书写健壮的抽取规则。
XWRAP——另一个重要的基于HTML结构的半自动化抽取工具是XWRAP[23]。
它自身是一个组件库，包含了包装器的基础构建块，以及对用户友好的接口，以降低工作量。
在执行抽取过程之前，XWRAP首先“清洗”错误的HTML标签和语法错误，然后将文档转化为一棵解析树。
它通过大量的操作步骤引导用户，使其在每一步中选择库中恰当的组件。
最后，XWRAP针对特定源输出包装器（Java代码）。
在对象抽取过程中，XWRAP创建了针对HTML页面定制的启发式数据抽取规则。
用户可以任选六条启发式规则之一来定位感兴趣的信息。
如果用户对抽取结果感到满意，抽取进程将继续运行。
用户可以通过限制或减少每个对象中组件的数量来重定义抽取过程，也可以指定元素的数据类型。
若抽取结果令人满意，用户可以为每个抽取的元素输入标签名，然后继续包装器生成步骤。
RoadRunner——RoadRunner[10]深入地探索了HTML文档的固有特征，并自动生成包装器。
它比较两个属于同一个“页面类”的HTML文档的结构，为其中包含的数据生成一个模式，并依此模式推断出在相似页面（或属于同一个“类”的页面）中识别属性实例的语法。
为了正确识别出属于相同页面类的网页集的所有可能的结构变形，可以提供多个页面作为训练集。
所有的抽取过程以一个比较样本页标签结构和处理结构不匹配的算法为基础。
以这种方式，算法可以发现如元组，列表和变形的结构特征。
值得注意的是，此过程是全自动的，不需要用户介入。
这是RoadRunner独有的特点。
3.3基于自然语言处理的工具
RAPIER （健壮的信息抽取规则自动生成系统）——RAPIER的目标是从自由文本中抽取数据。
它以一篇文档作为输入，并以一个填充好的模板指出需要被抽取的数据。
此模板用来学习模式并从槽中抽取数据。
学习算法混合了几种归纳逻辑语言工具的技术，并学习无边界的模式。
模式中包含单词和围绕数据的词性标签带来的约束。
这些模式由三个明确的槽组成：
Pre-,Post-,和Filler。
前两者表示左右定界符，后者描述待抽取数据的结构。
RAPIER抽取每个输入文档那个的单个记录项，因此也被称为是“单槽的”[32]。
SRV——以一组给定的训练集为基础，SRV[14] 是用来从文本文档中学习抽取规则的工具。
它依赖一组可以是“简单”或“关联”的“面向词块特征”的集合。
简单特征的功能是将词块映射为某个离散的值，例如，word，puctuation，或numeric。
关联特征将词块映射为另一个词块，例如，prev-token 或next-token。
学习规则以识别并归纳训练集的特征为基础。
默认特征集中大量已存的针对HTML的特征（例如in-title或after-title）使SRV能从HTML文档中抽取数据。
SRV也是一个“单槽”工具。
WHISK ——WHISK[32] 是另一个用来从文本文档中抽取数据的工具。
此工具从一组给定的训练文档集中归纳抽取规则。
从一个空规则集开始，系统选取迭代项并呈现给用户一组待标记的示例。
用户使用图形接口来为实例中待抽取的属性添加标签。
然后WHISK通过标记的示例创建规则，并测试规则的准确性。
这些规则以一种正则表达式形式的模式为基础，这些模式可以识别相关短语的上下文和用于抽取这些短语的定界符。
WHISK是“多槽的”，能够抽取文档中的多个记录。
3.4包装器归纳工具
WIEN——WIEN[20]是包装器归纳工具的先驱。
系统以一组标记好数据项的页面集作为输入，并返回与标注页相一致的包装器。
系统假定页面具有预定义的结构，并根据特定的归纳规则生成特定的包装器。
举例来说，如果页面具有HLRT结构（例，具有头、主体和尾的页面，主体内具有多个元组的数据，数据由左、右两个组件描述），将生成一个HLRT包装器。
WIEN生成的包装器不能处理嵌套结构或半结构化数据的变形。
SoftMealy——类似于WIEN，SoftMealy[18]是一个包装器归纳工具，其由一种特殊种类的自动机生成抽取规则，此自动机被称为“有限状态变换机”（FST）。
FST由输入/输出符号表，状态集和边组成。
为了处理结构变形，FST的每个状态可以有多个边。
在抽取文档前，包装器将HTML文本切分成词块，然后算法根据训练集中切分出的分隔符（词块）毗邻的标识形成的上下文归纳抽取规则。
FST以一个词块序列作为输入，并用一套具有上下文规则的分界符进行匹配并决定状态转化。
一个FST仅由一个元组类型创建。
如果文档中有多种类型的元组，系统将为每个元组创建一个FST。
STALKER——WIEN和SoftMeal所使用的技术在STALKER[28]中得到深入发展。
STALKER可以抽取分层的数据，训练例子由用户提供。
（1）用户需选择若干样例页面并把有用的数据（即所谓“ EC 树”的叶子）标记出来。
（2）页面被标记后，系统可生成一符号序列，用来表示页面的内容，还生成代表信息点开始的符号索引。
符号系列和通配符被作为定位标志，用于找到页面上的数据。
分装器归纳算法产生抽取规则并表示为简单的标志语法。
此法可处理文本，但不能处理链接信息。
网页文档用所谓的“内嵌目录”（ECT ）表示。
那是一个树形结构，其内部节点或是同构的信息点列表，或是异构信息点元组。
根节点是整篇文档，任一节点的内容代表其父节点内容的一个接续。
通过ECT，STALKER能处理嵌套的分层对象。
3.5 基于模型的工具
NoDoSE（西北文档结构抽取器）——NoDoSE [3]是一个半自动化的用以从半结构化文档中提取数据的交互工具。
通过图形化的用户接口，用户可按层次关系分解文档，划出感兴趣的区域并描述它们的语义。
文档的分解过程分多个级别。
对于每一级的分解，用户通过一个复杂的结构创建一个对象，然后用一个简单的结构将它在其他对象中分解。
在用户“教”工具如何建造对象后，他可以让NoDoSE学习如何鉴别文档中的其他对象。
这通过一个组件实现，该组件尝试从用户构建的对象中推断文档的语法。
当前版本的NoDoSE可以解析纯文本或HTML页面。
DEByE（实例数据抽取）——DEByE[21,30]是一种交互工具，把简单页面的样本对象集合作为输入，产生能够从其它类似页面（例：
同一个站点的页面）抽取新对象的抽取模式。
DEByE的特征是具有一个用户界面，允许用户用样本页中抽取的数据组装嵌套表格（可能有结构变化）。
组装后的表格是样本页待鉴定对象的实例。
DEByE根据这些实例生成用于标明结构的对象抽取模式（OEP）和环绕待抽取对象的文本。
然后将这些OEP连同目标页提供给一个自底向上算法作为输入，识别此页面的原子值，并以OEP的结构为向导组装复杂的对象。
3.6 基于本体的工具
这种方法的主要代表是Brigham Young大学（BYU）的Data Extraction Group[11]。
在他们的工具中，本体事先被创建出来以描述用户感兴趣的数据，包括关系，出现的词汇和上下文关键字。
通过解析此本体，该工具能自动的识别与抽取给定的输入文档中的数据，并存入数据库。
在应用本体之前，程序必须自动抽取含有感兴趣的“项”（或记录）的数据块。
为了正常运作，必须先由领域专家耐心的创建本体。
从积极的角度看，如果本体做够典型，抽取将高度自动化。
此外，用这种个方式创建的包装器具有相当的弹性（例，即使源页面的格式化特征改变包装器仍能良好运行）与适应性（例，包装器可处理同一领域内不同的源）。
事实上，这些特性是这种方法独有的。
为了方便起见，我们将把这个工具称为BYU工具。
另外一种基于本体的数据抽取工具是X-tract[1]，一种植物学文字说明的抽取工具。
由于它只工作在非常特定的领域，我们在此不做讨论。
4.定性分析
在这一节，我们将分析这些研具对信息抽取技术中比较重要的特征的支持程度。
我们提出了以下几个特征：
自动化程度，是否支持复杂的对象，页面内容，使用简便，XML输出，对非HTML源的支持和弹性与适应性。
4.1自动化程度
自动化程度对任何信息抽取系统来说都是一个重要的指标。
这关系到生成包装器过程中用户的工作量。
关于自动化的问题，包装器生成专用语言仍然需要人工书写代码，但是也提供了一些可以简化任务的特性，而通用语言并不具备这一点。
对于Minerva，TSIMMIS和Web-OQL这些工具，用户必须自行检查文档，找出分割有价值对象的标签，然后写程序来分离数据区。
换而言之，寻找分界符的任务是人工完成的。
以HTML为中间件的工具通常具备了高度的自动化。
然而，为了使这种自动化确实有效，目标页中的HTML标签必须具有高度一致性。
不幸的是，大部分常见的网页并不具备这一点。
举例来说，XWRAP的组件库中有大量的大量的启发式规则，其用以处理不同类型的HTML结构标记（如，表格，列表等）。
通过运用这些启发式规则并寻求用户反馈，该工具能高效地从某种类型的页面集中抽取数据。
W4F通过HTML抽取语言（HEL）来定义抽取规则。
它的特点是具备一个抽取向导程序，通过向导程序可以对用户选取的一段信息生成正则路径表达式。
由于向导程序不能处理数据项的集合，对同类型的多个数据项感兴趣的用户必须人工书写抽取规则来生成路径表达式。
也就是说，抽取过程是半自动的。
RoadRunner，如之前所述，是全自动的。
其特别之处在于，抽取程序假定目标页面集由某个特定数据源（如，某个数据库）生成。
然后通过一些启发式规则从样本页的HTML标签层次关系中“重构”这个数据源的模式。
这免除了用户提供目标模式或待抽取数据的实例的责任。
基于自然语言处理，包装器归纳，和模型建立的工具被认为是半自动的，尽管包装器生成过程是全自动的，但用户必须提供学习样本。
正如之前已经谈到的，BYU工具需要由相关领域的专家人工构建本体才能正常工作。
在此之后，如果本体有足够的代表性，抽取过程将是全自动的，并且可以为同领域的其他数据源服务。
事实上，这个特征对于此技术来说是独特的。
然而在被证明确实有效之前，本体构建往往是一件繁重的工作。
4.2 对复杂对象的支持
大多数网络上的数据隐含了一种复杂的结构。
这种结构是松散的，并呈现出半结构化数据典型的多变特点。
更进一步的是，Web数据很多时候以多层嵌套的层次化结构组织，这样包装器生成工具就被期以能够恰当地处理这些复杂对象。
异常处理机构和编辑器语言是Minerva的重要特征，这使它便于处理Web数据中常见的变化结构。
当某个部分的语法错误时，它们用来恰当的重构那些有价值的数据。
为了呈现复杂的对象，TSIMMIS采用了对象交换模型（OEM）[29]。
OEM是一个灵活的模型，它非常适合呈现半结构化数据。
OEM中的数据以一张图来呈现。
图的最上层有特定的根对象，同时带有零个或多个嵌套的子对象。
Web-OQL能够查询结构不规则的页面。
与其采用的hypertrees（有序的弧形标记树）一样，该语言允许对象以层次嵌套和可变结构的形式呈现。
W4F中用来定义抽取规则的语言HEL提供了用来创建复杂结构对象的操作符。
比如，通过fork[31]操作符，用户可以把分布在不同位置的单结构数据组织在一起。
这个操作符可以用来创建复杂或不规则的结构。
在任何情况下，用户也可以书写抽取代码来处理复杂结构。
另一方面，XWRAP只能处理隐含定义在HTML格式的源页面中的嵌套或变形结构。
可以通过鉴定那些形成页面或内结构（如，列，行，子片段）的顶级HTML结构（如，片段，表格）来确定源页面的嵌套层次。
RoadRunner采用了一种以嵌套类型的思想为基础的的类似方法，即允许呈现任意的由列表和元组组成的嵌套结构。
在SoftMealy中，包装器以FST的形式呈现，其每个状态可能有多个边缘。
这使得包装器代码中可以呈现变形结构，并处理结构上的变形。
然而，SoftMealy并不处理嵌套结构。
相比之下，由于使用了被称为“内嵌目录树”的形式来描述网页中内含的数据，STALKER的表达能力更强。
这种形式将目标页的结构呈现为一棵树，其中内含节点代表可以被分解的复杂对象，外部节点（叶子）代表需要被抽取的源数据项。
这使其可以处理嵌套结构。
结构上的变形也可以通过从用户提供的训练集中抽取分离的规则来处理。
NoDoSE维护一棵映射树，通过此树将文档中的结构元素映射到文件的文本内容上。
树上的每个节点代表文档中的一个结构组件，比如列表中的一个元素或记录项中的一个域。
在DEByE中，潜在数据模型[21,22]扩展了通常处理嵌套表格的思路，它允许在内部层次中展现结构变化。
尽管这个模型不如XML或OEM强大，它也足够表达具有层次结构或结构变形的数据。
RAPIER，SRV，WHISK和WIEN既不支持嵌套对象也不支持结构变化的对象。
4.3页面内容
页面内容包含了包装器生成器应用的两种基本类型：
具有半结构化数据的页面和具有半结构化文本的页面。
为了举例说明，考虑图1和图2中呈现的页面，其分别是包含半结构化数据和半结构化文本的页面。
包装器生成语言（Minerva与Web-OQL），以HTML为中间件的工具（W4F，XWRAP，和RoadRunner），包装器归纳工具（WIEN，SoftMea
升级会员 