龙源期刊网 http://www.qikan.com.cn
Web数据抽取技术研究初探
作者：李春艳,徐保民
来源：《电脑知识与技术》2009年第35期
摘要:该文给出了数据抽取过程中需要的基本定义,描述了数据抽取所基于的页面生成模型。同时给出了EXALG+这种数据抽取方法的基本流程,并给出了这种方法的抽取流程图。 关键词:数据抽取;EXALG+数据抽取方法;抽取流程图
中图分类号:TP311 文献标识码:A文章编号:1009-3044(2009)35-9920-03 Preliminary Study on Web Data Extraction Technology LI Chun-yan, XU Bao-min
(Beijing Jiaotong University, Beijing 100000, China)
Abstract: In this paper, a basic definition of the data extraction process has been given and Described a page generation modelof the data extraction. It has also given the basic processandExtraction Flow of EXALG + data extraction method.
Key words: data extraction; eXALG +data extraction method; extraction flow
随着互联网的出现,Web文档的信息抽取逐渐成为亟待解决的问题。一个Web文档就是一个网页,网页与纯文本的结构差别很大,主要表现为网页中存在大量的标记,这些标记将网页要显示的文本内容分隔开来。大量的标记为网页信息抽取提供了更多可利用的信息,从而可以开发各种不同于传统信息抽取的方法对网页进行信息抽取。
常见的动态网页是由相应数据库中结构化的数据值嵌入模版生成的。EXALG系统也是将动态网页中的模版推导出来,然后利用推导得到的模版来进行同类Web文档上数据抽取工作。该系统初看起来是一个很成功的模版推导系统,但经验证发现该系统还存在着一定的不足。本文正是在EXALG的基础上,提出了改进的抽取算法,即EXALG+算法。 1 数据类型定义
一个页面的模板和内容是由数据类型(Data Types)和数据值,也即数据实例(Instance)所构建而成的。数据格式是多种属性通过一种固定的序列进行排列而成。其中每种属性都可能是诸如字串,可选项或分离项等其它数据形式,由此,可以对数据类型作出递归定义。其中,分离项和可选项是数据抽取技术中通用的定义。 1.1 基本定义
龙源期刊网 http://www.qikan.com.cn
定义1.1:基本数据类型由符号β表示。它描述了一个标记串,是一个页面文本的基本单元。在本文中,标记定义为一个单词(Word)或一个HTML的固有标签。
该数据类型的实例为各种标记(Token)所组成的字串,有dom(β)={s|s从属于string}。特别地,定义一个特殊的字串,记做Φ,表示为空字串的数据类型,也可以称之为NULL数据类型。 定义1.2:若T1,T2,…,Tn是数据类型,则序列集合也为数据类型。其中T1,T2,…,Tn至少有一个非空。称数据类型是由 T1,T2,…,Tn以n维元组构造器构造而成的类型。
类型< T1,T2,…,Tn>的一个实例为形如的一个元组,其中i1,i2,…,in分别为类型T1,T2,…,Tn所对应的数据实例。将实例i1,i2,…,in称为元组的元组属性。
定义1.3:如果T为数据类型,则集合{T}也是一个类型。称集合{T}是由类型T通过集合构造器构造而成的类型,有dom({T})={e1,e2,…,ei | e从属于dom(T)}。
类型{T}的实例为元素{e1,e2,…,em}的集合,其中,ei(1≤i≤m)均为类型T的一个实例。 由此,本文中将类型的实例称作“值”,将符号“”和“{}”称作类型构造器符号,将元组构造器和集合构造器统称为类型构造器,并通过记号“”和“{}”来区分。 1.2 分离项和可选项
一般来说,一个模板的建立主要由两种构造器以及构造器所使用的基本类型组成。这两种构造器一般分别为元组构造器和集合构造器。另外,在网页页面中同时还普遍存在着两种其它形式的类型构造器,分别为可选项和分离项两种类型构造器。
例如,在浏览Chinapub网站的时候看到的图书信息,这些书中有的是国内作者编著的书籍,有的是翻译过来的书籍。后一种书籍中会有“译者”这个选项,则其中“译者”就可以看作是可选项;而相应的国内作者所著的书籍中,有时候也会有中文版和外文版。如果在这本书籍的介绍页面当中仅可能出现一种版式,就是分离项的形式。
定义1.4:如果T为数据类型,则可选项(T)?也是一种数据类型,称为可选项类型。有dom((T)?)=dom(T)∪{?椎}={ei|ei∈dom(T)∪?椎}。并称数据类型(T)?是由类型T通过可选项构造器构造而成。
定义1.5:如果T1,T2都是数据类型,则(T1|T2)也是一种数据类型,有
dom((T1|T2))=dom(T1)∪dom(T2)={axi|ali∈dom(T1),or a2i∈dom(T2)},称为分离项类型。其中(T1|T2)是由类型T1,T2通过分离项构造器构造而成。
每一种数据类型都可以用数据类型树来抽象表示,而且该树具有一定的层次结构,称这种用来表示数据类型的树为抽象模式树(Abstract Schema Tree,AST)。
龙源期刊网 http://www.qikan.com.cn
1.2 页面生成模型
本节给出由动态页面产生模板的页面生成模型。如图1所示,一个值X,通过使用一个模板T而被编码到一个实际页面中。用λ(T,X)表示编码页面结果。
定义1.6:一个模式S的模板,即将S中的每一个的类型构造器τ映射到一个有序的标记串集合T(τ)中,同时有如下特性。
1) 若τ是一个n维元组构造器,则T(τ)是一个标记串的序列,形如。其中Cτ1,…,Cτn+1为n+1个标记串。
2) 若τ是一个集合构造器,则T(τ)是一个标记串。
为区分不同的模板,把模板T记做TS,用于表示该模板是为模式S作作的定义。也就是说,在编码函数λ(T,X)给定的时候,将模式S的实例X嵌入到模板T上,而此时,可以使用编码函数,对该实例X可以按下列方式嵌入。
第一,如果X是基本类型β,则λ(T,X)就作为x自身输出到页面上。
第二,如果X为n维元组的形式,形如,则λ(T,X)作为一个有序的标记串输出到页面上,形如C1λ(T,X1)C2λ(T,X2)…λ(T,Xn)Cn+1。其中,X是模式S中的类型构造器对应的实例,T(τ)=。 第三,如果X是形如{e1,e2,…,em}τs的一个集合,则λ(T,X)为一个有序标记串输出到页面上,形如λ(T,e1)Sλ(T,e2)S…λ(T,em)。其中T(τs)=S。
第四,如果X是形如(X)?的可选项,λ(T,X)输出的实例为X或空字串Φ。
第五,如果X为形如X=(X1|X2)的分离项,则函数λ(T,X)为λ(T,X1)和λ(T,X2)二者其中的一个输出到页面上。
1.3 数据抽取
本文中的数据抽取是针对Web文档进行的,是一种根据网页的相似性结构自动找到网页中的数据并归纳出抽取规则的完全自动化的抽取方法。网页中的许多标记和文字的出现常常是频繁的,所以可以根据这些标记形成等价类,推导出生成网页的结构模板,并利用这个模板抽取需要的数据。
1.3.1 数据抽取定义
定义1.7:给定一个具有n个页面的集合P,其中Pi=λ(T,xi)(1