Fig.4　Preprocessing of single text leaf node containingmultiple text information圖4　單文本葉子節(jié)點(diǎn)包含多條信息的預(yù)處理

4.1.2單文本葉子節(jié)點(diǎn)嵌套出現(xiàn)的預(yù)處理

真實(shí)網(wǎng)頁(yè)中，通常會(huì)有一些節(jié)點(diǎn)的標(biāo)簽對(duì)中直接包含文本信息，同時(shí)其子孫節(jié)點(diǎn)中嵌套了其他文本信息的情況。這一類(lèi)節(jié)點(diǎn)不符合單文本葉子節(jié)點(diǎn)的定義，但它們卻直接包含了文本信息。因此第二步預(yù)處理如圖5所示：若一個(gè)節(jié)點(diǎn)中既包含自有文本，又嵌套包含了其他文本信息，則將其自有文本構(gòu)造成一個(gè)新的單文本葉子節(jié)點(diǎn)，替代原有文本在DOM樹(shù)中的位置，構(gòu)造的單文本葉子節(jié)點(diǎn)HTML標(biāo)簽統(tǒng)一定義為。

Fig.5　Preprocessing of single text leaf nodenested with other text nodes圖5　單文本葉子節(jié)點(diǎn)嵌套出現(xiàn)的預(yù)處理

4.2基本語(yǔ)義塊定義及劃分

完成DOM樹(shù)的預(yù)處理后，所有單條文本信息都會(huì)屬于一個(gè)單文本葉子節(jié)點(diǎn)，因此獲取DOM樹(shù)中所有單文本葉子節(jié)點(diǎn)即獲取了頁(yè)面內(nèi)容的基本數(shù)據(jù)單元。

基于假設(shè)1可知，節(jié)點(diǎn)之間的語(yǔ)義相關(guān)程度可通過(guò)其LCA節(jié)點(diǎn)的深度進(jìn)行比較。DOM樹(shù)中任一節(jié)點(diǎn)t1與其他節(jié)點(diǎn)都會(huì)擁有一個(gè)LCA節(jié)點(diǎn)，其中深度最大的節(jié)點(diǎn)LCA(t1)通過(guò)假設(shè)1可以認(rèn)為是t1所屬的最小的語(yǔ)義區(qū)域，LCA(t1)中的其他節(jié)點(diǎn)與t1具有最接近的語(yǔ)義關(guān)系。因此，對(duì)一個(gè)節(jié)點(diǎn)t1來(lái)說(shuō)，定位其所屬的深度最大的LCA節(jié)點(diǎn)，對(duì)于頁(yè)面分塊具有重要意義。同時(shí)，本文認(rèn)為單文本葉子節(jié)點(diǎn)是頁(yè)面中儲(chǔ)存數(shù)據(jù)的基本單元。因此找到頁(yè)面中一塊文本信息對(duì)應(yīng)的節(jié)點(diǎn)與其他單文本葉子節(jié)點(diǎn)之間深度最大的LCA節(jié)點(diǎn)可以表示該文本信息所屬的最小語(yǔ)義區(qū)域。將定位某個(gè)節(jié)點(diǎn)的這一類(lèi)LCA節(jié)點(diǎn)的算法定義為文本最近公共祖先算法（text lowest common ancestor，TLCA）。

算法1 TLCA節(jié)點(diǎn)定位算法

輸入：t—頁(yè)面中一塊文本信息對(duì)應(yīng)的DOM樹(shù)節(jié)點(diǎn)；D—經(jīng)過(guò)預(yù)處理的DOM樹(shù)。

輸出：TLCA(t)—t節(jié)點(diǎn)所屬的深度最大的文本最近公共祖先節(jié)點(diǎn)。

1.遍歷D得到單文本葉子節(jié)點(diǎn)的集合SD

2.遍歷t得到其包含的單文本葉子節(jié)點(diǎn)的集合St

3.vector=t

4.while（vector不包含SD-St中任一節(jié)點(diǎn)）do

5.vector=vector的父節(jié)點(diǎn)

6.return vector指向的節(jié)點(diǎn)

將所有單文本葉子節(jié)點(diǎn)代入TLCA算法得到的節(jié)點(diǎn)代表了所有單條文本信息在頁(yè)面中所屬的最小語(yǔ)義區(qū)域，將這一類(lèi)最小語(yǔ)義區(qū)域定義為基本語(yǔ)義塊。

定義2獲取頁(yè)面DOM樹(shù)的單文本葉子節(jié)點(diǎn)得到頁(yè)面的基本數(shù)據(jù)單元，代入TLCA算法得到每個(gè)單文本葉子節(jié)點(diǎn)的TLCA節(jié)點(diǎn)構(gòu)成的集合可以認(rèn)為是從語(yǔ)義上對(duì)頁(yè)面進(jìn)行了最基本的分塊，將代表分塊結(jié)果的TLCA節(jié)點(diǎn)定義為基本語(yǔ)義塊節(jié)點(diǎn)。

基本語(yǔ)義塊節(jié)點(diǎn)中允許嵌套包含基本語(yǔ)義塊節(jié)點(diǎn)的情形，例如圖2的真實(shí)頁(yè)面中，單條文本信息Text1與t2（Text2與Text3組成的基本語(yǔ)義塊）在語(yǔ)義上具有平等關(guān)系?？梢钥闯觯菊Z(yǔ)義塊代表的不是頁(yè)面劃分的最小區(qū)域，而是某個(gè)單文本葉子節(jié)點(diǎn)所屬的最小語(yǔ)義區(qū)域。

找到基本語(yǔ)義塊節(jié)點(diǎn)的意義在于：為頁(yè)面中單條文本信息找到其所屬的最小語(yǔ)義區(qū)域，每個(gè)單文本葉子節(jié)點(diǎn)都對(duì)應(yīng)一個(gè)基本語(yǔ)義塊，基本語(yǔ)義塊的集合就是對(duì)頁(yè)面的一種初步分塊結(jié)果。

4.3有效語(yǔ)義塊定義及識(shí)別

4.3.1現(xiàn)有的網(wǎng)頁(yè)分塊層次及其不足

對(duì)頁(yè)面中有效信息的分塊層次，Liu等人[2]在MDR（mining data records）算法中首先提出將頁(yè)面劃分為Data Record與Data Region兩個(gè)層次。其中Data Record是儲(chǔ)存單條完整信息的基本單位，例如頁(yè)面中一件商品的名字、屬性等完整信息，而Data Region是由具有相似結(jié)構(gòu)的Data Record聚合而成的一塊區(qū)域，例如頁(yè)面中多個(gè)商品的Data Record在一起構(gòu)成了Data Region?，F(xiàn)有方法大多采用Record與Region兩個(gè)層次對(duì)頁(yè)面進(jìn)行分塊。

這種分塊形式在Deep Web中有較好的效果，因?yàn)橹T如商品信息等網(wǎng)頁(yè)是從數(shù)據(jù)庫(kù)中讀取數(shù)據(jù)后通過(guò)模板動(dòng)態(tài)生成的[18-19]，所以Data Record之間不論是從DOM樹(shù)結(jié)構(gòu)特征上還是從視覺(jué)特征上都具有強(qiáng)相似性，且Data Record會(huì)以并列的形式組成Data Region。但在大學(xué)人員頁(yè)面中，由于是開(kāi)發(fā)者人工生成靜態(tài)網(wǎng)頁(yè)，結(jié)構(gòu)之間的規(guī)律性沒(méi)有Deep Web中嚴(yán)謹(jǐn)，如果采用上述分塊形式，“Data Record”不一定會(huì)以并列形式組成“Data Region”，可能會(huì)有嵌套的形式出現(xiàn)（如圖3所示），并且還會(huì)出現(xiàn)“Data Record”中包含“Data Region”和“Data Region”中包含“Data Region”等情形。例如圖3的左圖中，t1與t3是Data Record，t2是由t4與t5兩個(gè)Data Record組成的Data Region，而t1、t2與t3又并列組成了t0，一個(gè)新的Data Region，此時(shí)出現(xiàn)了“Data Region”中包含“Data Region”的情形；同樣是圖3的左圖中，若將t1的標(biāo)簽去掉，則t0既是Text1所屬的Data Record，也是t2與t3所屬的Data Region，此時(shí)出現(xiàn)了“Data Record”中包含“Data Region”的問(wèn)題。

4.3.2有效語(yǔ)義塊定義

針對(duì)大學(xué)人員頁(yè)面的特點(diǎn)，不采用Data Record與Data Region兩層劃分的方法，而是在上一節(jié)提出的基本語(yǔ)義塊的基礎(chǔ)上，提出有效語(yǔ)義塊的概念以及基于有效語(yǔ)義塊的頁(yè)面分塊方法。

基本語(yǔ)義塊僅僅從結(jié)構(gòu)上獲取了單條文本信息所屬的最小語(yǔ)義區(qū)域，并不一定包含完整的人員信息。結(jié)合假設(shè)1，可以認(rèn)為，從單個(gè)人員所屬的基本語(yǔ)義塊節(jié)點(diǎn)向上搜索其祖先節(jié)點(diǎn)，通過(guò)信息的邊界識(shí)別，可以找到既儲(chǔ)存該人員盡可能多的信息，又不引入其他人員信息的節(jié)點(diǎn)。將找到的這一類(lèi)節(jié)點(diǎn)定義為有效語(yǔ)義塊節(jié)點(diǎn)。下面給出詳細(xì)定義。

定義3從單個(gè)人員信息所屬的基本語(yǔ)義塊節(jié)點(diǎn)出發(fā)，向上搜索祖先節(jié)點(diǎn)，得到的包含單個(gè)人員信息且不引入新的人員信息的最大區(qū)域?qū)?yīng)的節(jié)點(diǎn)為有效語(yǔ)義塊節(jié)點(diǎn)?！白畲髤^(qū)域”的概念是：當(dāng)前節(jié)點(diǎn)包含了單個(gè)人員及其一定量的信息，但如果繼續(xù)向上搜索TLCA節(jié)點(diǎn)，則會(huì)引入新的人員及其信息。

每個(gè)單文本葉子節(jié)點(diǎn)對(duì)應(yīng)屬于一個(gè)基本語(yǔ)義塊，而每一個(gè)包含人員信息的基本語(yǔ)義塊對(duì)應(yīng)屬于一個(gè)有效語(yǔ)義塊。有效語(yǔ)義塊的定義是以單個(gè)人員為核心找到包含其信息的最大區(qū)域，但有效語(yǔ)義塊不一定只包含單個(gè)人員信息，因?yàn)榛菊Z(yǔ)義塊本身有可能包含多個(gè)人員信息。例如基本語(yǔ)義塊節(jié)點(diǎn)t中包含3個(gè)單文本葉子節(jié)點(diǎn)，結(jié)構(gòu)是“rel1：name1 name2”，雖然其中有多個(gè)人員，但對(duì)人員name1而言，t既是基本語(yǔ)義塊節(jié)點(diǎn)，又是有效語(yǔ)義塊節(jié)點(diǎn)，其中包含了name1的關(guān)系信息rel1，若向上繼續(xù)尋找TLCA節(jié)點(diǎn)，則會(huì)引入新的人員及其信息“rel2：name3”。因此節(jié)點(diǎn)t對(duì)人員name1而言，是包含name1所有信息的最大區(qū)域，且向上搜索TLCA節(jié)點(diǎn)會(huì)引入新的帶有信息的人員，從而t對(duì)于人員name1而言是符合定義3的有效語(yǔ)義塊節(jié)點(diǎn)。

4.3.3有效語(yǔ)義塊的邊界識(shí)別

通過(guò)對(duì)隨機(jī)取樣的大學(xué)人員頁(yè)面進(jìn)行觀察，發(fā)現(xiàn)人員信息有關(guān)系信息與屬性信息兩種類(lèi)型，對(duì)應(yīng)的邏輯結(jié)構(gòu)如圖6所示。

Fig.6　Two logical forms of faculty information ineffective semantic bocks圖6　有效語(yǔ)義塊中人員信息的兩種邏輯結(jié)構(gòu)

邏輯結(jié)構(gòu)（a）中，是在一個(gè)關(guān)系前導(dǎo)詞后掛載其映射的所有人員名字，對(duì)單個(gè)人員而言，關(guān)系前導(dǎo)詞就是其擁有的信息。在這一類(lèi)邏輯結(jié)構(gòu)中，人員名字呈塊狀出現(xiàn)，擁有共同的關(guān)系前導(dǎo)詞，因此可以認(rèn)為塊狀的人員名字具有同質(zhì)性，關(guān)系前導(dǎo)詞后掛載一個(gè)人員、一塊人員、多塊人員或者嵌套出現(xiàn)的人員塊，在邏輯結(jié)構(gòu)上都可認(rèn)為是“rel：Name_Block”形式。

邏輯結(jié)構(gòu)（b）中，一條人員記錄包含了一個(gè)人員的名字信息及其屬性信息，其中屬性信息可以是屬性名、屬性值以及并不屬于單文本葉子節(jié)點(diǎn)的個(gè)人圖片等。

結(jié)合定義3及對(duì)人員信息邏輯結(jié)構(gòu)的分析，可以給出有效語(yǔ)義塊邊界識(shí)別算法。

算法2有效語(yǔ)義塊邊界識(shí)別算法

輸入：t—基本語(yǔ)義塊節(jié)點(diǎn)。

輸出：基本語(yǔ)義塊所屬的有效語(yǔ)義塊節(jié)點(diǎn)。

1.Ift中不包含人名信息then

2.return NULL

3.else if（t中僅有一條人名信息）then

4.vector=t

5.While TLCA（vector）僅有一條人名do

6.vector=TLCA（vector）

7.return vector指向的節(jié)點(diǎn)

8.else if（t有多條人名信息andt只包含人名信息）

then

9.vector=t

10.While TLCA（vector）只有人名信息do

11.vector=TLCA（vector）

12.return vector指向的節(jié)點(diǎn)

13.else//t有多條人名信息且含有非人名信息

14.returnt

15.end if

其中，TLCA()函數(shù)是對(duì)算法1的調(diào)用；第5～6行的判定是為了找出單個(gè)人員擁有的屬性信息的邊界；第10～11行的判定是為了找出關(guān)系前導(dǎo)詞映射下所有人名信息的邊界。

5　有效語(yǔ)義塊對(duì)齊及信息抽取

通過(guò)基于LCA的網(wǎng)頁(yè)分塊算法，可以得到符合圖6中邏輯結(jié)構(gòu)的有效語(yǔ)義塊。有效語(yǔ)義塊僅僅是從某單個(gè)人員所屬的基本語(yǔ)義塊出發(fā)，得到包含該人員信息且不引入新的帶有信息的人員的最大區(qū)域，因此有效語(yǔ)義塊會(huì)盡可能多地保存單個(gè)人員具有的信息。但有的信息并不是存在于某個(gè)特定的有效語(yǔ)義塊中，而是屬于有效語(yǔ)義塊之間共有的特征信息。因此在獲取所有有效語(yǔ)義塊后，需要將有效語(yǔ)義塊對(duì)齊來(lái)識(shí)別這一部分不存在于有效語(yǔ)義塊中但仍屬于人員信息的部分。

通過(guò)觀察隨機(jī)取樣的大學(xué)人員頁(yè)面的組織結(jié)構(gòu)，發(fā)現(xiàn)不論是存有關(guān)系信息還是存有屬性信息的有效語(yǔ)義塊，通常都會(huì)與同類(lèi)型有效語(yǔ)義塊進(jìn)行對(duì)齊合并。

5.1關(guān)系信息的有效語(yǔ)義塊對(duì)齊

圖7給出了存有關(guān)系信息的有效語(yǔ)義塊的兩種對(duì)齊示例。其中（a）結(jié)構(gòu)的特點(diǎn)是：一些儲(chǔ)存有關(guān)系信息的有效語(yǔ)義塊可以構(gòu)成一塊更大的語(yǔ)義區(qū)域并擁有共同的關(guān)系前導(dǎo)詞。在真實(shí)的頁(yè)面中，例如有效語(yǔ)義塊“教授xxx xx”與“副教授xx xxx”可能會(huì)擁有共同的關(guān)系前導(dǎo)詞“在職教師”。（b）結(jié)構(gòu)的特點(diǎn)是：有效語(yǔ)義塊作為表格中的一行存在，這些有效語(yǔ)義塊擁有共同的TLCA節(jié)點(diǎn)，即整個(gè)表格對(duì)應(yīng)的節(jié)點(diǎn)，且這些有效語(yǔ)義塊在共同的TLCA節(jié)點(diǎn)中擁有一個(gè)兄弟語(yǔ)義塊。兄弟語(yǔ)義塊不包含人員信息，但包含了關(guān)系（rel）信息。兄弟語(yǔ)義塊中rel信息的位置可以與有效語(yǔ)義塊中Name_Block的位置對(duì)齊，從而組成表格結(jié)構(gòu)，表格的第一行與第一列作為關(guān)系前導(dǎo)詞，以二維映射方式得到每個(gè)Name_Block具有的二元關(guān)系信息。

Fig.7　Two typical alignments of relation information圖7　關(guān)系信息的有效語(yǔ)義塊對(duì)齊示例

以這兩種典型的關(guān)系信息對(duì)齊方式為例，可以將關(guān)系型有效語(yǔ)義塊的對(duì)齊與抽取過(guò)程總結(jié)如下：首先尋找一個(gè)關(guān)系信息型有效語(yǔ)義塊的TLCA節(jié)點(diǎn)，如果TLCA節(jié)點(diǎn)中包含有其他關(guān)系信息型有效語(yǔ)義塊，且這些有效語(yǔ)義塊之間沒(méi)有其他語(yǔ)義塊，則開(kāi)始對(duì)齊工作。接下來(lái)，如果在這些有效語(yǔ)義塊之前存在一個(gè)非人員信息的兄弟語(yǔ)義塊，那么獲取兄弟語(yǔ)義塊中可能儲(chǔ)存有rel信息的單文本葉子節(jié)點(diǎn)和基本語(yǔ)義塊所處的位置坐標(biāo)，將位置坐標(biāo)與關(guān)系型有效語(yǔ)義塊中的Name_Block坐標(biāo)進(jìn)行對(duì)齊。如果對(duì)齊成功，則可按照?qǐng)D7（b）中的關(guān)系表形式從TLCA節(jié)點(diǎn)中提取所有關(guān)系映射下的Name_Block；如果對(duì)齊不成功，則按照?qǐng)D7（a）中的人名塊形式對(duì)TLCA節(jié)點(diǎn)進(jìn)行信息抽取。

5.2屬性信息的有效語(yǔ)義塊對(duì)齊

圖8給出了存有屬性信息的有效語(yǔ)義塊的兩種對(duì)齊示例。其中（a）結(jié)構(gòu)的特點(diǎn)是：每個(gè)人員的名字、屬性名、屬性值和個(gè)人圖片等信息單獨(dú)形成一塊，在真實(shí)頁(yè)面中通常以類(lèi)似卡片的格式出現(xiàn)，通過(guò)上文提出的方法可以將這一塊對(duì)應(yīng)的節(jié)點(diǎn)識(shí)別為一個(gè)有效語(yǔ)義塊，這些有效語(yǔ)義塊可能會(huì)有共同的關(guān)系前導(dǎo)詞存在。（b）結(jié)構(gòu)的特點(diǎn)是：有效語(yǔ)義塊作為表格中的一行存在，包含且僅包含了單個(gè)人員的名字和所有屬性值信息，這些有效語(yǔ)義塊擁有共同的TLCA節(jié)點(diǎn)，且在TLCA節(jié)點(diǎn)中擁有一個(gè)兄弟語(yǔ)義塊。兄弟語(yǔ)義塊中不包含人員信息，但包含了屬性名（Attr_ Name）信息，兄弟語(yǔ)義塊中Attr_Name信息的位置可以與有效語(yǔ)義塊中Attr_Value的位置對(duì)齊，從而組成表格結(jié)構(gòu)，表頭中存放了所有人員共有的Attr_ Name。

Fig.8　Two typical alignments of attribute information圖8　屬性信息的有效語(yǔ)義塊對(duì)齊示例

通過(guò)結(jié)構(gòu)對(duì)比，可以發(fā)現(xiàn)卡片形式的對(duì)齊方式與人名塊形式的對(duì)齊方式實(shí)質(zhì)上是同一種方法，而屬性表形式的對(duì)齊方式與關(guān)系表形式的對(duì)齊方式實(shí)質(zhì)上也是同一種方法，因此這里不再贅述屬性型有效語(yǔ)義塊的對(duì)齊與抽取方法。

6　實(shí)驗(yàn)結(jié)果與分析

6.1實(shí)驗(yàn)設(shè)置

數(shù)據(jù)集：采集了8所中國(guó)大學(xué)的245個(gè)學(xué)院的所有人員列表頁(yè)面，共計(jì)1 641個(gè)。本文的實(shí)驗(yàn)?zāi)康脑谟跍y(cè)試所提方法在大量真實(shí)的人員列表頁(yè)面中是否具有普遍適用性，因此不對(duì)數(shù)據(jù)集頁(yè)面的類(lèi)型和特點(diǎn)進(jìn)行統(tǒng)計(jì)分析，后文將直接分析實(shí)驗(yàn)結(jié)果。

評(píng)價(jià)指標(biāo)：本文的信息抽取流程包含有效語(yǔ)義塊識(shí)別，有效語(yǔ)義塊對(duì)齊，抽取所有關(guān)系映射下的人員信息。其中，如果有效語(yǔ)義塊的識(shí)別與對(duì)齊能準(zhǔn)確識(shí)別例如圖7與圖8中這樣的區(qū)域，那么最后的抽取只需要使用前面的對(duì)齊信息就能準(zhǔn)確得到人員信息。有效語(yǔ)義塊的對(duì)齊結(jié)果直接影響抽取的效果，因此將對(duì)有效語(yǔ)義塊的對(duì)齊結(jié)果進(jìn)行人工標(biāo)注及評(píng)價(jià)。評(píng)價(jià)指標(biāo)是：在一個(gè)頁(yè)面中通過(guò)有效語(yǔ)義塊對(duì)齊后識(shí)別出的區(qū)域中，如果包含了人員所有的屬性信息和所屬的關(guān)系映射，則將該對(duì)齊結(jié)果標(biāo)記為“正確”，否則標(biāo)記為“錯(cuò)誤”。最后根據(jù)標(biāo)注結(jié)果計(jì)算對(duì)齊結(jié)果的準(zhǔn)確率、召回率與F1值。計(jì)算公式如下：

基準(zhǔn)系統(tǒng)：由于實(shí)驗(yàn)數(shù)據(jù)集不同，無(wú)法進(jìn)行直接對(duì)比實(shí)驗(yàn)，從而采用文獻(xiàn)[2]中的MDR方法作為基準(zhǔn)系統(tǒng)。并且本文與MDR方法均是基于DOM樹(shù)結(jié)構(gòu)的頁(yè)面分塊方法，因此選取MDR方法作為基準(zhǔn)系統(tǒng)。由于樹(shù)的相似度閾值難以確定，文獻(xiàn)[2]原文中取閾值為0.3，本文實(shí)驗(yàn)中取0.3、0.5與0.7共3個(gè)閾值分別進(jìn)行對(duì)比實(shí)驗(yàn)，統(tǒng)計(jì)對(duì)應(yīng)閾值下對(duì)數(shù)據(jù)區(qū)域識(shí)別的效果。

人名信息識(shí)別：MDR方法中未給出人名識(shí)別方法，為保證實(shí)驗(yàn)結(jié)果的準(zhǔn)確性，將在提出的系統(tǒng)與基準(zhǔn)系統(tǒng)中使用相同的人名信息識(shí)別方法。大學(xué)人員頁(yè)面中的人名信息是以條目形式出現(xiàn)，無(wú)上下文信息，因此實(shí)驗(yàn)中結(jié)合中文人名的構(gòu)造規(guī)則，使用漢語(yǔ)人名姓氏庫(kù)文件匹配得到符合規(guī)則的候選人名，然后通過(guò)常用詞詞典匹配可排除“黨委”、“學(xué)工”等通常作為先導(dǎo)詞的關(guān)系型噪聲信息，通過(guò)候選人名的重復(fù)度與位置信息比對(duì)可排除“文科樓”、“第一批”等通常會(huì)重復(fù)在不同人員中出現(xiàn)的屬性型噪聲信息。本文重點(diǎn)討論基于LCA分塊方法的人員信息抽取，因此不對(duì)人名信息識(shí)別與去噪部分進(jìn)行詳細(xì)闡述。

6.2實(shí)驗(yàn)結(jié)果及分析

表1顯示了對(duì)數(shù)據(jù)集中的1 641個(gè)大學(xué)人員頁(yè)面進(jìn)行人員信息所屬區(qū)域定位的結(jié)果。

Table 1　Experimental results on 1 641 real faculty list pages表1　1 641個(gè)人員頁(yè)面數(shù)據(jù)區(qū)域識(shí)別結(jié)果

從表1可以看出，隨著閾值的提高，MDR分塊算法的準(zhǔn)確率會(huì)有提高，而召回率會(huì)降低。因?yàn)殚撝堤岣叽鞤ata Region中對(duì)Data Record之間的相似度要求更嚴(yán)格，所以準(zhǔn)確率會(huì)上升而召回率會(huì)降低。

TLCA分塊及有效語(yǔ)義塊對(duì)齊算法在準(zhǔn)確率上與不同閾值的MDR分塊算法相差不大，是因?yàn)椴徽撌峭ㄟ^(guò)有效語(yǔ)義塊對(duì)齊還是通過(guò)計(jì)算Data Record之間的相似度，都能夠有效過(guò)濾噪聲信息；而有效語(yǔ)義塊的邊界識(shí)別也是以盡可能不引入噪聲信息為前提。

TLCA分塊及有效語(yǔ)義塊對(duì)齊算法在召回率上相對(duì)不同閾值的MDR分塊算法均有較顯著提升。這是因?yàn)樵诖髮W(xué)人員頁(yè)面中作為非Deep Web的人工靜態(tài)頁(yè)面，普遍會(huì)有修飾與冗余標(biāo)簽的存在，在MDR算法中這些標(biāo)簽會(huì)降低實(shí)際上應(yīng)該相關(guān)的Data Record之間的相似度，從而對(duì)Data Region的識(shí)別造成干擾，所以會(huì)有較多的Data Region被遺漏；而LCA分塊算法實(shí)質(zhì)上是一種自底向上尋找祖先節(jié)點(diǎn)的方法，在尋找祖先節(jié)點(diǎn)的過(guò)程中不會(huì)受到修飾標(biāo)簽與冗余標(biāo)簽的影響，所以在大學(xué)人員頁(yè)面中有較好的召回率。

除了人名信息識(shí)別錯(cuò)誤造成準(zhǔn)確率與召回率下降，實(shí)驗(yàn)結(jié)果中影響TLCA分塊及有效語(yǔ)義塊對(duì)齊算法效果的主要限制在有效語(yǔ)義塊對(duì)齊這一步。真實(shí)頁(yè)面中，有少數(shù)情況并沒(méi)有嚴(yán)格區(qū)分人的屬性信息與關(guān)系信息，或者有的信息同時(shí)屬于屬性類(lèi)和關(guān)系類(lèi)，因此無(wú)法對(duì)齊有效語(yǔ)義塊而導(dǎo)致人員信息區(qū)域的識(shí)別會(huì)遺漏信息。這一類(lèi)頁(yè)面的示例如圖9所示，在準(zhǔn)確識(shí)別出每個(gè)人員所屬的有效語(yǔ)義塊，即表格中名字與屬性信息所在的一行后，依照有效語(yǔ)義塊對(duì)齊的方法得到的格式是“rel：card card”這種類(lèi)型，而無(wú)法識(shí)別出表頭中的“職稱”、“性別”等屬性名信息。在該類(lèi)型頁(yè)面中，出現(xiàn)這種問(wèn)題的原因是“xx學(xué)系”既是所有人員共有的關(guān)系前導(dǎo)詞，又是所有人員共有的“單位”屬性名對(duì)應(yīng)的屬性值，對(duì)這種既是關(guān)系信息，又是屬性信息的部分難以對(duì)齊，最后不論采用哪種對(duì)齊方法，得到的區(qū)域都會(huì)遺漏一部分人員信息。針對(duì)這種情況，提出一種加入人工干預(yù)的解決思路。例如圖9中，首先對(duì)“xx學(xué)系”這一類(lèi)具有雙重類(lèi)型的詞進(jìn)行人工標(biāo)注，識(shí)別出“xx學(xué)系”僅位于第一個(gè)人員的有效語(yǔ)義塊中且可以與存有表頭信息的兄弟節(jié)點(diǎn)對(duì)齊；然后對(duì)表頭節(jié)點(diǎn)預(yù)處理刪掉“單位”，對(duì)第一個(gè)人員的有效語(yǔ)義塊預(yù)處理刪掉“xx學(xué)系”，將表格作為屬性表對(duì)齊后抽取所有人員屬性信息；最后給每個(gè)人員加上屬性“單位：xx學(xué)系”和關(guān)系前導(dǎo)詞“xx學(xué)系”。

Fig.9　Asituation where effective semantic blocks can hardly align圖9　有效語(yǔ)義塊難以對(duì)齊的頁(yè)面示例

7　結(jié)束語(yǔ)

從大學(xué)網(wǎng)站中抽取所有關(guān)系映射下的人員信息，對(duì)于學(xué)術(shù)社交網(wǎng)絡(luò)的構(gòu)建有重要意義。針對(duì)大學(xué)科研人員列表頁(yè)面的特點(diǎn)，提出了一種基于LCA對(duì)頁(yè)面進(jìn)行語(yǔ)義劃分的TLCA算法，并在此基礎(chǔ)上提出了有效語(yǔ)義塊的識(shí)別及對(duì)齊方法用于人員列表信息的抽取。通過(guò)在真實(shí)的大學(xué)人員列表頁(yè)面中進(jìn)行實(shí)驗(yàn)，證明了本文方法具有普遍適用性，且能夠克服現(xiàn)有網(wǎng)頁(yè)分塊方法在大量的大學(xué)人員列表頁(yè)面中的一些缺陷。但在實(shí)際測(cè)試中發(fā)現(xiàn)少量頁(yè)面的結(jié)構(gòu)中使用有效語(yǔ)義塊對(duì)齊方法會(huì)造成人員信息的部分丟失，在后續(xù)的研究中，需要解決有效語(yǔ)義塊對(duì)齊方法在更加復(fù)雜情況中的局限性。

References:

[1]Tang Jie,Zhang Jing,Yao Limin,et al.ArnetMiner:extraction and mining of academic social networks[C]//Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Las Vegas, USA,Aug 24-27,2008.New York,USA:ACM,2008:990-998.

[2]Liu Bing,Grossman R,Zhai Yanhong.Mining data records in Web pages[C]//Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Washington,USA,Aug 24-27,2003.New York, USA:ACM,2003:601-606.

[3]Liu Bing,Zhai Yanhong.NET—a system for extracting Web data from flat and nested data records[C]//Proceedings of the 6th International Conference on Web Information Systems Engineering,New York,USA,Nov 20-22,2005. Berlin,Heidelberg:Springer,2005:487-495.

[4]Zhao Hongkun,Meng Weiyi,Yu C.Mining templates from search result records of search engines[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,San Jose,USA,Aug 12-15,2007.New York,USA:ACM,2007:884-893.

[5]Lerman K,Getoor L,Minton S,et al.Using the structure of Web sites for automatic segmentation of tables[C]//Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data,Paris,France,Jun 13-18,2004.New York,USA:ACM,2004:119-130.

[6]Hong J L,Siew E G,Egerton S.Information extraction for search engines using fast heuristic techniques[J].Data& Knowledge Engineering,2010,69(2):169-196.

[7]Gao Le,Zhang Jian,Tian Xianzhong.Improvement and Implementation of VIPS algorithm[J].Computer Systems& Applications,2009,18(4):65-69.

[8]Chakrabarti D,Kumar R,Punera K.A graph-theoretic approach to webpage segmentation[C]//Proceedings of the 17th International Conference on World Wide Web,Beijing,China,Apr 21-25,2008.New York,USA:ACM,2008: 377-386.

[9]Ravikumar S,Chakrabarti D,Punera K.Method for seg-menting webpages by parsing webpages into document object modules(DOMs)and creating weighted graphs:U.S. Patent 7,974,934[P].2011-07-05.

[10]Cai Deng,Yu Shipeng,Wen Jirong,et al.VIPS:a visionbased page segmentation algorithm,MSR-TR-2003-79[R]. Microsoft,2003.

[11]Chakrabarti D,Mital M R,Hajela S,et al.Automatic visual segmentation of webpages:U.S.Patent 8,255,793[P].2012-08-28.

[12]Liu Xinyue,Lin Hongfei,Tian Ye.Segmenting webpage with Gomory-Hu tree based clustering[J].Journal of Software,2011,6(12):2421-2425.

[13]Chen Yu,Ma Weiying,Zhang Hongjiang.Detecting Web page structure for adaptive viewing on small form factor devices[C]//Proceedings of the 12th International Conference on World Wide Web,Budapest,Hungary,May 20-24,2003. New York,USA:ACM,2003:225-233.

[14]Thamviset W,Wongthanavasu S.Structured Web information extraction using repetitive subject pattern[C]//Proceedings of the 2012 9th International Conference on Electrical Engineering/Electronics,Computer,Telecommunications and Information Technology,Phetchaburi,Thailand,May 16-18, 2012.Piscataway,USA:IEEE Computer Society,2012:1-4.

[15]Thamviset W,Wongthanavasu S.Information extraction for deep Web using repetitive subject pattern[J].World Wide Web,2014,17(5):1109-1139.

[16]álvarez M,Pan A,Raposo J,et al.Extracting lists of data records from semi-structured Web pages[J].Data&Knowledge Engineering,2008,64(2):491-509.

[17]Miao G,Tatemura J,Hsiung W P,et al.Extracting data records from the Web using tag path clustering[C]//Proceedings of the 18th International Conference on World Wide Web,Madrid,Spain,Apr 20-24,2009.New York,USA:ACM, 2009:981-990.

[18]He Bin,Patel M,Zhang Zhen,et al.Accessing the deep Web [J].Communications of theACM,2007,50(5):94-101.

[19]Furche T,Gottlob G,Grasso G,et al.OXPath:a language for scalable data extraction,automation,and crawling on the deep Web[J].The VLDB Journal,2013,22(1):47-72.

附中文參考文獻(xiàn):

[7]高樂(lè),張健,田賢忠.基于視覺(jué)的Web頁(yè)面分塊算法的改進(jìn)與實(shí)現(xiàn)[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2009,18(4):65-69.

YI Chenhui was born in 1991.He is an M.S.candidate at School of Computer,Wuhan University.His research interest is Web data extraction.

易晨輝（1991—），男，湖北鄂州人，武漢大學(xué)計(jì)算機(jī)學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)閃eb數(shù)據(jù)抽取。

LIU Mengchi was born in 1962.He received the Ph.D.degree from University of Calgary in 1992.Now he is a professor and Ph.D.supervisor at Wuhan University,and tenured professor at University of Regina.His research interests include database theory and systems,data model,XML and Web data management,etc.

劉夢(mèng)赤（1962—），男，湖北武漢人，1992年于卡爾頓大學(xué)獲得博士學(xué)位，現(xiàn)為武漢大學(xué)特聘教授、博士生導(dǎo)師，加拿大里賈納大學(xué)終身教授，主要研究領(lǐng)域?yàn)閿?shù)據(jù)庫(kù)理論與系統(tǒng)，數(shù)據(jù)模型，XML，網(wǎng)絡(luò)數(shù)據(jù)管理等。在國(guó)內(nèi)外期刊及學(xué)術(shù)會(huì)議上發(fā)表論文100余篇，主持和承擔(dān)多項(xiàng)國(guó)家杰出青年科學(xué)基金（外籍）、國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃（973計(jì)劃）、加拿大國(guó)家自然科學(xué)與工程基金等項(xiàng)目。

HU Jie was born in 1977.She received the Ph.D.degree from Wuhan University in 2010.Now she is an associate professor and M.S.supervisor at Hubei University.Her research interests include database,intelligent information system and social network,etc.

胡婕（1977—），女，湖北漢川人，2010年于武漢大學(xué)獲得博士學(xué)位，現(xiàn)為湖北大學(xué)副教授、碩士生導(dǎo)師，主要研究領(lǐng)域?yàn)閿?shù)據(jù)庫(kù)，智能信息系統(tǒng)，社交網(wǎng)絡(luò)等。在國(guó)內(nèi)外期刊及學(xué)術(shù)會(huì)議上發(fā)表論文10余篇，承擔(dān)和參與國(guó)家自然科學(xué)基金、國(guó)家重點(diǎn)實(shí)驗(yàn)室開(kāi)放課題、國(guó)家杰出青年科學(xué)基金、國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃（973計(jì)劃）等項(xiàng)目。

*The National Natural Science Foundation of China under Grant No.61202100(國(guó)家自然科學(xué)基金);the Open Foundation of State Key Laboratory of Software Engineering under Grant No.SKLSE2012-09-20(軟件工程國(guó)家重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金).

Received 2015-07,Accepted 2015-09.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2015-09-07,http://www.cnki.net/kcms/detail/11.5602.TP.20150907.1039.002.html

+Corresponding author:E-mail:c_hui_y@163.com

文獻(xiàn)標(biāo)志碼：A

中圖分類(lèi)號(hào)：TP391

doi:10.3778/j.issn.1673-9418.1508055

Information Extraction of University Research Faculty Based on LCA SegmentationAlgorithm*

YI Chenhui1+,LIU Mengchi1,HU Jie2
1.School of Computer,Wuhan University,Wuhan 430072,China
2.School of Computer Science and Information Engineering,Hubei University,Wuhan 430062,China

Abstract:Conventional information extraction methods of semi-structured pages usually assume that valid data have relatively strong structural similarity,divide the page into data records and data region with similar characteristics and then extract from them.However,faculty list pages of universities mostly are written artificially and filled by human beings instead of automatic generation by using templates,so their structure is not rigorous.This paper proposes a faculty information extraction method based on LCA(lowest common ancestor)segmentation algorithm,introduces the connection between LCAand semantic relation into Web segmentation,and presents the new concepts of basic semantic blocks and effective semantic blocks.After converting the page into a DOM(document object model)tree and the preprocessing,the page is divided into the basic semantic blocks with LCA algorithm firstly.Then the basic semantic blocks are merged into their corresponding effective semantic blocks with complete personnel information.Finally, according to the alignment of effective semantic blocks,all faculty information mapped by all relationships in current page is gotten.The experimental results show that the proposed method still has high precision and recall rates in thesegmentation and extraction of quantities of real university research faculty list pages by compared with the MDR (mining data records)algorithm.

Key words:information extraction;lowest common ancestor(LCA);basic semantic block;effective semantic block; relational mapping