Web數據抽取技術研究初探

摘要:該文給出了數據抽取過程中需要的基本定義，描述了數據抽取所基于的頁面生成模型。同時給出了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 基本定義

定義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)。

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

一般來說，從一個大的互聯網站點給定的一個實際頁面集合，在頁面編碼中，人工選擇正確的模板和數據值時一般不會有任何疑問。而要達到的目標恰恰是解決實際網頁的抽取問題，也即能夠生成被“人”認為是正確的模板和數據值。

如上所述，為了將頁面模板推導出來，可以將頁面中的所有標記加以識別區分，判斷標記是模板標記值還是數據值。將所有屬于模板的標記區分出來后，再利用這些標記完成模板的建立和其后的數據抽取。因此，為了將數據標記和模板標記區分開來，可以利用頁面中的標記的不變/變動特性來達到區分的效果。同一類網頁所使用的模板是固定不變的，而變化部分則是嵌入到這些模板標記中的數據值，因此，通過分析網頁中的標記是否具有變動性質就可以完成區分工作。但是，實際工作依然很困難。

第一，模板標記中的標記值和數據集合中的標記值可能相同，也就是會出現同樣的標記扮演不同角色的情況。

第二，在頁面中出現的可選項和分離項使得不變/變動的性質難以區分，從而使得模板推導更加復雜。

分離項可能具有多種表示方式，比如，“姓名”或“地址”就可能會出現由于語言習慣或地域的不同而使用不同的表示方式。同樣的，日期的表示格式等也屬于此類問題，而且表示方法更多:可以表示成“日期/月份/年份”或是“月份/日期/年份”等。

因此，在實際的模板推導中由于這些問題將會導致最終的推導結果出現很多不同可能的模板。此時與這些模板相對應的抽取出來的數據也就不盡相同。也就是所謂的存在沖突模式(Ambiguity Schema)。目前，已經證明了想要推導出一個無沖突的模式屬于一個NP完全問題。因此，抽取問題的關鍵，在于如何找到一個更好的或者說最佳的模板用于數據抽取。

1.3.2 數據抽取原理

EXALG是由Arvind與Hector二人于SIGMOD2003提出的數據抽取系統。該方法使用了類似RoadRunner的模型，希望將生成Web文檔的模板推導出來，然后再根據得到的模板，來抽取采用同樣結構的Web文檔中的相關數據值。

這兩種方法的歸納方式不同。EXALG不是逐個比較兩個網頁中的標記，而是提出了出現向量(Occurrence Vector)和等價類(Equivalence Class)的概念。通過統計最大最頻繁的等價類和角色區分來推導模板。EXALG對于給出頁面集合，可以發現頁面中所隱含的模板，并通過模板將數據抽取出來。

根據Arvind二人提供的數據和他們發布的EXALG系統的實際使用情況，可以發現EXALG對于原來已有的其它方法來說有了很大的進步;而本文給出的抽取方法，對于抽取的數據在正確性和完整性方面做得更加完善。

本文的抽取方法，是受EXALG的啟發得到，所以稱之為EXALG+方法。它可分為兩個階段。在第一個階段用于發現與生成輸入頁面的未知模板中相同的類型構造器相聯系的標記的集合。在第二個階段則使用上面生成的集合推導出模板。然后，推導得到的模板被用來抽取頁面的編碼值。以上兩個階段的工作完全由機器完成，是無需人工參與的過程。

第一個階段，利用出現頻繁程度作為向量，用來表示一個標記串在所有網頁中的出現頻率，并且利用原作者提出的等價類概念，即具有相同出現向量的標記串，聚集到同一個有序的標記串集合中。由于等價類中的所有標記串在相同模板的作用下，會產生同樣的出現頻率，因此，利用這種特點將所有合法的等價類尋找出來，然后將這些等價類中的標記串轉換成最后的模板。

可以將HTML文檔看作一棵DOM樹。首先，將頁面中所有相同的字串根據其DOM樹路徑位置的不同來區分其扮演的角色，將其稱為特定標記串。然后，將所有扮演相同角色的特定標記串按其出現次數組成出現向量，然后將所有具有相同出現向量的特定標記串聚合在一起，形成一個等價類。在這一步驟中，可能會出現一些不合法的等價類，利用第三步將這些不合法的等價類去除。這些不合格等價類在被過濾掉的同時釋放該類所包含的所有特定標記串，并將特定標記串中一些與頁面意義不一致的個體過濾掉。這一步利用了當特定標記串出現在不同等價類的區間位置不同而具有不同的意義這一特性，可以把這些具有相同值的特定標記串進一步地區分開來，并反復形成新的等價類，過濾掉不合法的等價類，得到一個最頻繁出現的等價類集合。到此為第一個階段階段，稱為等價類生成階段。本文的主要改進工作都是在這個階段完成的。對應于這部分的模塊稱之為等價類生成模塊(Equivalence Class Generation Module:ECGM)。隨后，將這些等價類作為輸出傳送到第二個階段的模板分析模塊(Template Analysis Module)，由這個模塊產生最后的輸出。其流程如圖2所示。

第二個階段，即模板建立和值抽取模塊。該模塊的輸入是一個由第一個階段生成的頻繁等價類集合和一個使用標記串描述的頁面集合，其輸出是一個模板和一個對應頁面值的集合。該模塊由兩個子模塊組成，模板生成子模塊和值抽取子模塊。對于數據抽取技術，一旦獲得了正確的模板之后，值抽取是一個非常直觀的過程，在此不作贅述。

這些頻繁等價類集合中，存在一個最重要的等價類，<1，1，…，1>，將其稱為基本等價類。該等價類的特殊性在于，該集合中所有的標記串出現各個頁面僅一次，比如常見HTML文檔中的等標記串組合均屬此列。另外，一般來說等標記串通常是一個頁面的開始標記串和結束標記串，因此，該基本等價類的頁面的范圍往往是最廣泛的，模板構建模塊即由此等價類開始構建模板。然后利用先深搜索方式，對于每個等價類的非空區間位置，判斷是否為數據嵌入位置，或者該區間是否嵌入了另外一個等價類。如果該位置為數據嵌入位置，則跳轉到該等價類的下一個非空的區間位置;如果該位置為一個等價類的嵌入位置，則進入嵌入等價類的非空區間再次進行判斷，直到將所有的等價類的非空區間遍歷完全，即可構造出一個完整的頁面模板。

1.4 小結

文章給出了數據抽取過程中需要的基本定義，描述了數據抽取所基于的頁面生成模型。同時給出了EXALG+這種數據抽取方法的基本流程，并給出了這種方法的抽取流程圖。

參考文獻:

[1] Xi W P，Li X，Jiang K，et al.Information Extraction Technology for Web Forums[J].Computer Engineering，2005，31(4):34-37.

[2] Chinchor N，Marsh E.MUC-7 Information Extraction Task Definition(version 5.1)[C].Proceedings of the Seventh Message Understanding Conference，1998:210-221.

[3] 宋靜靜，李振坤.基于Wrapper技術的Web數據處理系統研究[J].計算機應用研究，2004(12):298-300.

[4] 李效動，股毓清.基于DOM的Web信息提取[J].計算機學報，2002，25(5):526-533.

[5] 張紹華，徐林昊，楊文柱.基于樣本實例的Web信息抽取[J].河北大學學報:自然科學版，2001(4):431-437.