樂丁惕

(閩江學(xué)院 計算機(jī)科學(xué)系，福建 福州350108)

隨著Internet和通信技術(shù)的快速發(fā)展和廣泛普及，Web頁面數(shù)量急劇增加，已成為人們獲取信息的主要渠道之一.目前，主流的搜索引擎基本上只收集了Internet上的靜態(tài)頁面(Surface Web)，而這些靜態(tài)頁面只是其中小部分信息，其余大部分信息存放于Web中的在線數(shù)據(jù)庫，對傳統(tǒng)的搜索引擎是不可見的，這部分信息稱為深度網(wǎng)頁(Deep Web)［1］.

Deep Web信息集成系統(tǒng)是為了有效利用海量的Deep Web信息而提出的解決方案，Web數(shù)據(jù)抽取是Deep Web信息集成系統(tǒng)的關(guān)鍵，是指通過技術(shù)手段將Web頁面上的數(shù)據(jù)抽取出來，保存為XML文檔或關(guān)系模式［2］.對DEIP(Data Extraction based on Index Path)算法進(jìn)行了改進(jìn)，首先將Deep Web查詢結(jié)果頁面規(guī)范化為XML格式，然后在遍歷XML文檔的過程中確定待抽取數(shù)據(jù)路徑集合，最后根據(jù)該集合完成數(shù)據(jù)抽取.

1 數(shù)據(jù)規(guī)范化

Web數(shù)據(jù)抽取是指將Web作為信息源，把分布在其上的用戶感興趣的查詢結(jié)果抽取出來［3］.然而，由于Web文檔普遍是由半結(jié)構(gòu)化標(biāo)記語言HTML組成的，其語法規(guī)則比較寬松，且網(wǎng)站往往會在網(wǎng)頁中加入大量的修飾性屬性.因此返回的網(wǎng)頁文件無法直接用于數(shù)據(jù)抽取，需要進(jìn)行預(yù)處理:

1)補(bǔ)全未配對的tag;

2)濾掉修飾性屬性.

以上過程稱之為數(shù)據(jù)規(guī)范化，獲取更易于數(shù)據(jù)抽取的XML文件.

2 DEIP算法

不同的網(wǎng)站，其頁面布局風(fēng)格往往有極大的差異，有效數(shù)據(jù)的存儲位置也大不相同.但對于同一個網(wǎng)站而言，輸入關(guān)鍵詞后其返回的不同頁面中，有效數(shù)據(jù)的存儲位置是相同的.換句話說，對于同一個網(wǎng)站返回的動態(tài)頁面，其主要數(shù)據(jù)是存放在同一個tag中.只要找到這個tag在網(wǎng)頁中的“位置”，就能對該網(wǎng)站的所有動態(tài)網(wǎng)頁自動地進(jìn)行數(shù)據(jù)抽?。?］.

DEIP算法的具體過程及說明如下:

輸入:由HTML網(wǎng)頁文件轉(zhuǎn)換成的XML在內(nèi)存形成的DOM樹.

輸出:所有記錄的索引路徑.

步驟1 深度優(yōu)先遍歷DOM樹，為每一個Text結(jié)點建立索引路徑;

步驟2 確定候選數(shù)據(jù)區(qū).

假設(shè)輸入N個關(guān)鍵詞Key1，Key2，…，KeyN，將它們逐個與步驟2中的每一個Text結(jié)點的內(nèi)容進(jìn)行匹配，篩選出所有包含這N個關(guān)鍵詞的索引路徑，假設(shè)一共找到了K(K≥N)條，分別計作:IPath［1］，IPath［2］，…，IPath［K］［5］.

此處存在2種情況，一種是只找到K=N條索引路徑，即符合所有關(guān)鍵詞的記錄各有1條，這K條索引路徑處于DOM樹中同一個數(shù)據(jù)記錄子樹中;另一種是找到了K＞N條索引路徑，即符合所有關(guān)鍵詞的記錄數(shù)不止1條，一般情況下，這K條索引路徑處在不同的數(shù)據(jù)記錄子樹中，具體如下:

1)K=N 時，確定 IPath［1］，IPath［2］，…，IPath［K］的最大公共前綴結(jié)點 Nj，計算 Nj的兄弟結(jié)點的個數(shù)countsibling(Nj)，如果countsibling(Nj)＜Crecord(指網(wǎng)站返回的一個頁面中的記錄數(shù))，繼續(xù)向上找其父結(jié)點Nj.parent，直至 countsibling(Nj.parent)＞ Crecord.結(jié)點 Nj或 Nj.parent就是主數(shù)據(jù)區(qū)所在子樹的根節(jié)點.

2)K=N 時，確定 IPath［1］，IPath［2］，…，IPath［K］的最大公共前綴結(jié)點 Nj.結(jié)點 Nj就是主數(shù)據(jù)區(qū)所在子樹的根結(jié)點.

步驟3 確定最佳數(shù)據(jù)區(qū).

在確定候選數(shù)據(jù)區(qū)后，考慮到數(shù)據(jù)區(qū)子樹中可能會包含噪聲數(shù)據(jù)，會影響到數(shù)據(jù)抽取的準(zhǔn)確率，所以需要再次匹配關(guān)鍵詞去掉噪聲數(shù)據(jù)，確定最佳數(shù)據(jù)區(qū).本步驟也有2種處理方式:

1)當(dāng)K=N時，判斷Nj或者Nj.parent和它們的兄弟子樹是否包含關(guān)鍵詞，如果包含，將其子樹下的所有文本抽取出來，并將這些子樹的根結(jié)點的索引路徑存儲下來，否則直接丟棄.

2)當(dāng)K＞N時，判斷Nj的各個孩子結(jié)點Nj.children子樹是否包含關(guān)鍵詞，如果包含關(guān)鍵詞，將其子樹下的所有文本抽取出來，并將這樣的孩子結(jié)點Nj.children的索引路徑存儲下來，否則直接丟棄［6］.

3 DEIP算法舉例

如圖1所示，圖中Table，TR，TD結(jié)點表示元素結(jié)點，D+數(shù)字節(jié)點表示Text節(jié)點.

圖1 XML文檔片段的DOM樹

圖中部分標(biāo)記對應(yīng)的XML片段如下:

設(shè)共有2個關(guān)鍵詞Key1，Key2，結(jié)果頁面中的數(shù)據(jù)記錄數(shù)Crecord=10.此處僅說明K＞N時的情況:

假設(shè)包含 Key1 的有 D1，D3，D4，D7，D10，包含 Key2 的有 D2，D5，D8，D11.

步驟1 獲得9條索引路徑，分別為:

存放于索引路徑數(shù)組L中.

步驟2 此時K＞N，故直接求取9條索引路徑的最長公共前綴maxPrefix，得到

則maxPrefix即為候選數(shù)據(jù)區(qū)根結(jié)點的索引路徑.

步驟3 對候選數(shù)據(jù)區(qū)進(jìn)行除噪處理.

判斷table的各個孩子子樹是否包含Key1或Key2，若包含，則記錄下該子樹根結(jié)點的索引路徑，否則直接丟棄.得到

這3條索引路徑即為網(wǎng)站的包裝器Wrapper.

4 DEIP算法的不足及改進(jìn)

僅從HTML代碼的角度考慮，算法的執(zhí)行結(jié)果覆蓋了所有關(guān)鍵詞存在的區(qū)域.然而，在現(xiàn)實世界中，能夠與關(guān)鍵詞匹配的數(shù)據(jù)未必就是有效數(shù)據(jù).用戶上網(wǎng)查詢信息時，是通過輸入1個或多個關(guān)鍵詞來描述某領(lǐng)域的一類事物的.這些關(guān)鍵詞相互關(guān)聯(lián)，輸入的關(guān)鍵詞越多，對該事物的描述就越細(xì).因此，在反饋給用戶的結(jié)果網(wǎng)頁中，關(guān)鍵詞也應(yīng)以組合的形式存在.

定義1 記錄Record 即返回頁面中的一組數(shù)據(jù).這組數(shù)據(jù)在網(wǎng)頁中相鄰或相近存放，且應(yīng)包含用戶輸入的所有關(guān)鍵詞至少各一次.記錄是描述用戶想要獲取的信息的最小單位，可由其包含的各個關(guān)鍵詞在DOM樹中的深度及各個關(guān)鍵詞之間的相對位置關(guān)系組成.

特別地，在網(wǎng)頁中往往存在一些無用的零散數(shù)據(jù)，包含了部分的關(guān)鍵詞.而多個零散數(shù)據(jù)組合在一起，便形成了一條偽記錄.

定義2 有效數(shù)據(jù) 即用戶在返回的網(wǎng)頁中希望看到的數(shù)據(jù)信息.記錄中的數(shù)據(jù)，即為有效數(shù)據(jù).而一些分散在網(wǎng)頁中的數(shù)據(jù)，即使能夠匹配部分的關(guān)鍵詞，也不一定是有效數(shù)據(jù).

定義3 主數(shù)據(jù)區(qū) 有別于前文中數(shù)據(jù)區(qū).若一網(wǎng)頁文件中僅存在1個數(shù)據(jù)區(qū)，或有1個數(shù)據(jù)區(qū)的記錄數(shù)比其他數(shù)據(jù)區(qū)都要多，則稱之為主數(shù)據(jù)區(qū).主既表示該數(shù)據(jù)區(qū)擁有網(wǎng)頁中最豐富的有效數(shù)據(jù)，也表示這是用戶本次查詢的主要結(jié)果.

以百度搜索為例，其返回的網(wǎng)頁中數(shù)據(jù)主要分布在2個數(shù)據(jù)區(qū)中，如圖2中所示.

若用戶輸入Keyword，其期望看到的是DataArea1中的數(shù)據(jù)，而不是DataArea2中的數(shù)據(jù).

圖2 百度搜索數(shù)據(jù)區(qū)

DEIP算法在紛繁冗雜的網(wǎng)頁文件中找到了穩(wěn)定存在的數(shù)據(jù)區(qū)，從而實現(xiàn)了對特定網(wǎng)站的一次生成，自動抽取，這是一個簡潔而極富創(chuàng)意的算法.然而，該算法中不存在記錄這一定義，更準(zhǔn)確地說，所有能夠匹配關(guān)鍵詞的信息都是有效數(shù)據(jù).由于算法的執(zhí)行是基于DOM樹進(jìn)行的，無法識別無用的零散數(shù)據(jù)，使得實際上找到的數(shù)據(jù)區(qū)根結(jié)點在DOM樹中的層次比實際層次小得多，因而包含了大量冗余信息.

分析DEIP算法中的步驟1可以發(fā)現(xiàn)，筆者指定要求深度優(yōu)先遍歷是有原因的.根據(jù)上述定義可知，記錄和偽記錄的區(qū)別在于其包含的N個關(guān)鍵詞在網(wǎng)頁中的分布情況，記錄中各個數(shù)據(jù)均相鄰或相近存放，作為數(shù)據(jù)的整體被＜Div＞＜/Div＞或＜Table＞ ＜/Table＞包圍(即記錄中的Text節(jié)點均在同一子樹中)，而偽記錄中的數(shù)據(jù)則無規(guī)律地分散在整個網(wǎng)頁中.深度優(yōu)先遍歷使得處于同一數(shù)據(jù)區(qū)的記錄在數(shù)組中相鄰存放，同一條記錄中的Text節(jié)點索引路徑也在數(shù)組中相鄰存放，可以將網(wǎng)頁中的數(shù)據(jù)集散情況體現(xiàn)到Text節(jié)點索引路徑數(shù)組中.由于去掉了所有不匹配關(guān)鍵詞的Text結(jié)點，記錄定義中的有效數(shù)據(jù)相鄰或相近存放在數(shù)組中可簡單地認(rèn)為是相鄰存放，因而可以通過遍歷索引路徑數(shù)組來區(qū)分記錄和偽記錄.為便于比較，改進(jìn)算法仍然采用DEIP算法中的示例XML代碼，具體如下:

對索引路徑數(shù)組L進(jìn)行遍歷.

由于D1匹配Key1，D2匹配Key2，且二者相鄰存放，說明此時已找到了一條記錄.將該記錄中各關(guān)鍵詞的相對位置保存起來，此處為

Deep是求取結(jié)點在DOM樹中深度的函數(shù).Key1Pos，Key2Pos和relativePos就組成了當(dāng)前數(shù)據(jù)區(qū)中記錄的模版.

D3匹配關(guān)鍵詞Key1，說明此時可能進(jìn)入了另一條記錄中，也可能D3只是無用的零散數(shù)據(jù).繼續(xù)向前，D4同樣匹配Key1，表達(dá)了2個信息:

1)D3是無用的零散數(shù)據(jù);

2)已離開當(dāng)前記錄模版能表示的范圍.

忽略D3，繼續(xù)向前遍歷.D5匹配關(guān)鍵詞Key2，說明又找到了一條記錄.同樣記下當(dāng)前記錄模版，

D7匹配 Key1，D8 匹配 Key2，且

同樣地，D10匹配Key1，D11匹配Key2，

3條記錄均可由同一記錄模板描述，因此這3條記錄處于同一數(shù)據(jù)區(qū)中.

綜上所述，共得到2個記錄模板，即得到了2個數(shù)據(jù)區(qū)，DataArea1:D1，D2;DataArea2:D4，D5，D7，D8，D10，D11.

由于DataArea2中的“記錄”數(shù)多于DataArea1，故其為主數(shù)據(jù)區(qū)，其索引路徑為其中所有索引路徑的最長公共前綴，

在步驟3中，對主數(shù)據(jù)區(qū)進(jìn)行除噪操作，得

相比DEIP算法，獲得的包裝器更加精確，且僅包含有效數(shù)據(jù).

5 小結(jié)

將用戶角度的需求與具體的網(wǎng)頁文件結(jié)構(gòu)相結(jié)合，通過對有效數(shù)據(jù)記錄的形式化定義，構(gòu)建出由小整體到大整體、逐步獲取網(wǎng)頁中數(shù)據(jù)的模式，在此基礎(chǔ)上給出了DEIP的改進(jìn)算法.本文提出的數(shù)據(jù)抽取機(jī)制不僅解決了原算法對網(wǎng)頁的高冗余，更使得抽取出的數(shù)據(jù)按記錄存放，各歸其位，為之后的語義標(biāo)注等工作提供了極大的方便.

［1］GHANEM ，M T AREF W G .Databases deepen the Web［J］.IEEE Computer，2004，73(1):116 －117.

［2］馬安香，張斌，高克寧.基于結(jié)果模式的Deep Web數(shù)據(jù)抽?。跩］.計算機(jī)研究與發(fā)展，2009，46(2):22－23.

［3］單菁，王習(xí)特，劉桐.支持Deep Web數(shù)據(jù)庫集成的圖書搜索系統(tǒng)［J］.計算機(jī)研究與發(fā)展，2011，48(Z2):33－34.

［4］魏永剛，袁方.Deep Web數(shù)據(jù)抽取及語義標(biāo)注研究［D］.保定:河北大學(xué)，2010.

［5］YUAN L，LI Z H，CHEN S L.Ontology-Based annotation for Deep Web data［J］.Journal of Software，2008，19(2):237 －245.

［6］SAHUGUET A，AZAVANT，F(xiàn).Building intelligent Web applications using lightweight wrappers［J］.Data and Knowledge Engineering，2010，36(3):283 －316.