基于LCA分塊算法的大學科研人員信息抽取*

Fig.4　Preprocessing of single text leaf node containingmultiple text information圖4　單文本葉子節點包含多條信息的預處理

4.1.2單文本葉子節點嵌套出現的預處理

真實網頁中，通常會有一些節點的標簽對中直接包含文本信息，同時其子孫節點中嵌套了其他文本信息的情況。這一類節點不符合單文本葉子節點的定義，但它們卻直接包含了文本信息。因此第二步預處理如圖5所示：若一個節點中既包含自有文本，又嵌套包含了其他文本信息，則將其自有文本構造成一個新的單文本葉子節點，替代原有文本在DOM樹中的位置，構造的單文本葉子節點HTML標簽統一定義為。

Fig.5　Preprocessing of single text leaf nodenested with other text nodes圖5　單文本葉子節點嵌套出現的預處理

4.2基本語義塊定義及劃分

完成DOM樹的預處理后，所有單條文本信息都會屬于一個單文本葉子節點，因此獲取DOM樹中所有單文本葉子節點即獲取了頁面內容的基本數據單元。

基于假設1可知，節點之間的語義相關程度可通過其LCA節點的深度進行比較。DOM樹中任一節點t1與其他節點都會擁有一個LCA節點，其中深度最大的節點LCA(t1)通過假設1可以認為是t1所屬的最小的語義區域，LCA(t1)中的其他節點與t1具有最接近的語義關系。因此，對一個節點t1來說，定位其所屬的深度最大的LCA節點，對于頁面分塊具有重要意義。同時，本文認為單文本葉子節點是頁面中儲存數據的基本單元。因此找到頁面中一塊文本信息對應的節點與其他單文本葉子節點之間深度最大的LCA節點可以表示該文本信息所屬的最小語義區域。將定位某個節點的這一類LCA節點的算法定義為文本最近公共祖先算法（text lowest common ancestor，TLCA）。

算法1 TLCA節點定位算法

輸入：t—頁面中一塊文本信息對應的DOM樹節點；D—經過預處理的DOM樹。

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

1.遍歷D得到單文本葉子節點的集合SD

2.遍歷t得到其包含的單文本葉子節點的集合St

3.vector=t

4.while（vector不包含SD-St中任一節點）do

5.vector=vector的父節點

6.return vector指向的節點

將所有單文本葉子節點代入TLCA算法得到的節點代表了所有單條文本信息在頁面中所屬的最小語義區域，將這一類最小語義區域定義為基本語義塊。

定義2獲取頁面DOM樹的單文本葉子節點得到頁面的基本數據單元，代入TLCA算法得到每個單文本葉子節點的TLCA節點構成的集合可以認為是從語義上對頁面進行了最基本的分塊，將代表分塊結果的TLCA節點定義為基本語義塊節點。

基本語義塊節點中允許嵌套包含基本語義塊節點的情形，例如圖2的真實頁面中，單條文本信息Text1與t2（Text2與Text3組成的基本語義塊）在語義上具有平等關系。可以看出，基本語義塊代表的不是頁面劃分的最小區域，而是某個單文本葉子節點所屬的最小語義區域。

找到基本語義塊節點的意義在于：為頁面中單條文本信息找到其所屬的最小語義區域，每個單文本葉子節點都對應一個基本語義塊，基本語義塊的集合就是對頁面的一種初步分塊結果。

4.3有效語義塊定義及識別

4.3.1現有的網頁分塊層次及其不足

對頁面中有效信息的分塊層次，Liu等人[2]在MDR（mining data records）算法中首先提出將頁面劃分為Data Record與Data Region兩個層次。其中Data Record是儲存單條完整信息的基本單位，例如頁面中一件商品的名字、屬性等完整信息，而Data Region是由具有相似結構的Data Record聚合而成的一塊區域，例如頁面中多個商品的Data Record在一起構成了Data Region。現有方法大多采用Record與Region兩個層次對頁面進行分塊。

這種分塊形式在Deep Web中有較好的效果，因為諸如商品信息等網頁是從數據庫中讀取數據后通過模板動態生成的[18-19]，所以Data Record之間不論是從DOM樹結構特征上還是從視覺特征上都具有強相似性，且Data Record會以并列的形式組成Data Region。但在大學人員頁面中，由于是開發者人工生成靜態網頁，結構之間的規律性沒有Deep Web中嚴謹，如果采用上述分塊形式，“Data Record”不一定會以并列形式組成“Data Region”，可能會有嵌套的形式出現（如圖3所示），并且還會出現“Data Record”中包含“Data Region”和“Data Region”中包含“Data Region”等情形。例如圖3的左圖中，t1與t3是Data Record，t2是由t4與t5兩個Data Record組成的Data Region，而t1、t2與t3又并列組成了t0，一個新的Data Region，此時出現了“Data Region”中包含“Data Region”的情形；同樣是圖3的左圖中，若將t1的標簽去掉，則t0既是Text1所屬的Data Record，也是t2與t3所屬的Data Region，此時出現了“Data Record”中包含“Data Region”的問題。

4.3.2有效語義塊定義

針對大學人員頁面的特點，不采用Data Record與Data Region兩層劃分的方法，而是在上一節提出的基本語義塊的基礎上，提出有效語義塊的概念以及基于有效語義塊的頁面分塊方法。

基本語義塊僅僅從結構上獲取了單條文本信息所屬的最小語義區域，并不一定包含完整的人員信息。結合假設1，可以認為，從單個人員所屬的基本語義塊節點向上搜索其祖先節點，通過信息的邊界識別，可以找到既儲存該人員盡可能多的信息，又不引入其他人員信息的節點。將找到的這一類節點定義為有效語義塊節點。下面給出詳細定義。

定義3從單個人員信息所屬的基本語義塊節點出發，向上搜索祖先節點，得到的包含單個人員信息且不引入新的人員信息的最大區域對應的節點為有效語義塊節點。“最大區域”的概念是：當前節點包含了單個人員及其一定量的信息，但如果繼續向上搜索TLCA節點，則會引入新的人員及其信息。

每個單文本葉子節點對應屬于一個基本語義塊，而每一個包含人員信息的基本語義塊對應屬于一個有效語義塊。有效語義塊的定義是以單個人員為核心找到包含其信息的最大區域，但有效語義塊不一定只包含單個人員信息，因為基本語義塊本身有可能包含多個人員信息。例如基本語義塊節點t中包含3個單文本葉子節點，結構是“rel1：name1 name2”，雖然其中有多個人員，但對人員name1而言，t既是基本語義塊節點，又是有效語義塊節點，其中包含了name1的關系信息rel1，若向上繼續尋找TLCA節點，則會引入新的人員及其信息“rel2：name3”。因此節點t對人員name1而言，是包含name1所有信息的最大區域，且向上搜索TLCA節點會引入新的帶有信息的人員，從而t對于人員name1而言是符合定義3的有效語義塊節點。

4.3.3有效語義塊的邊界識別

通過對隨機取樣的大學人員頁面進行觀察，發現人員信息有關系信息與屬性信息兩種類型，對應的邏輯結構如圖6所示。

Fig.6　Two logical forms of faculty information ineffective semantic bocks圖6　有效語義塊中人員信息的兩種邏輯結構

邏輯結構（a）中，是在一個關系前導詞后掛載其映射的所有人員名字，對單個人員而言，關系前導詞就是其擁有的信息。在這一類邏輯結構中，人員名字呈塊狀出現，擁有共同的關系前導詞，因此可以認為塊狀的人員名字具有同質性，關系前導詞后掛載一個人員、一塊人員、多塊人員或者嵌套出現的人員塊，在邏輯結構上都可認為是“rel：Name_Block”形式。

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

結合定義3及對人員信息邏輯結構的分析，可以給出有效語義塊邊界識別算法。

算法2有效語義塊邊界識別算法

輸入：t—基本語義塊節點。

輸出：基本語義塊所屬的有效語義塊節點。

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指向的節點

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

then

9.vector=t

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

11.vector=TLCA（vector）

12.return vector指向的節點

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

14.returnt

15.end if

其中，TLCA()函數是對算法1的調用；第5～6行的判定是為了找出單個人員擁有的屬性信息的邊界；第10～11行的判定是為了找出關系前導詞映射下所有人名信息的邊界。

5　有效語義塊對齊及信息抽取

通過基于LCA的網頁分塊算法，可以得到符合圖6中邏輯結構的有效語義塊。有效語義塊僅僅是從某單個人員所屬的基本語義塊出發，得到包含該人員信息且不引入新的帶有信息的人員的最大區域，因此有效語義塊會盡可能多地保存單個人員具有的信息。但有的信息并不是存在于某個特定的有效語義塊中，而是屬于有效語義塊之間共有的特征信息。因此在獲取所有有效語義塊后，需要將有效語義塊對齊來識別這一部分不存在于有效語義塊中但仍屬于人員信息的部分。

通過觀察隨機取樣的大學人員頁面的組織結構，發現不論是存有關系信息還是存有屬性信息的有效語義塊，通常都會與同類型有效語義塊進行對齊合并。

5.1關系信息的有效語義塊對齊

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

Fig.7　Two typical alignments of relation information圖7　關系信息的有效語義塊對齊示例

以這兩種典型的關系信息對齊方式為例，可以將關系型有效語義塊的對齊與抽取過程總結如下：首先尋找一個關系信息型有效語義塊的TLCA節點，如果TLCA節點中包含有其他關系信息型有效語義塊，且這些有效語義塊之間沒有其他語義塊，則開始對齊工作。接下來，如果在這些有效語義塊之前存在一個非人員信息的兄弟語義塊，那么獲取兄弟語義塊中可能儲存有rel信息的單文本葉子節點和基本語義塊所處的位置坐標，將位置坐標與關系型有效語義塊中的Name_Block坐標進行對齊。如果對齊成功，則可按照圖7（b）中的關系表形式從TLCA節點中提取所有關系映射下的Name_Block；如果對齊不成功，則按照圖7（a）中的人名塊形式對TLCA節點進行信息抽取。

5.2屬性信息的有效語義塊對齊

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

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

通過結構對比，可以發現卡片形式的對齊方式與人名塊形式的對齊方式實質上是同一種方法，而屬性表形式的對齊方式與關系表形式的對齊方式實質上也是同一種方法，因此這里不再贅述屬性型有效語義塊的對齊與抽取方法。

6　實驗結果與分析

6.1實驗設置

數據集：采集了8所中國大學的245個學院的所有人員列表頁面，共計1 641個。本文的實驗目的在于測試所提方法在大量真實的人員列表頁面中是否具有普遍適用性，因此不對數據集頁面的類型和特點進行統計分析，后文將直接分析實驗結果。

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

基準系統：由于實驗數據集不同，無法進行直接對比實驗，從而采用文獻[2]中的MDR方法作為基準系統。并且本文與MDR方法均是基于DOM樹結構的頁面分塊方法，因此選取MDR方法作為基準系統。由于樹的相似度閾值難以確定，文獻[2]原文中取閾值為0.3，本文實驗中取0.3、0.5與0.7共3個閾值分別進行對比實驗，統計對應閾值下對數據區域識別的效果。

人名信息識別：MDR方法中未給出人名識別方法，為保證實驗結果的準確性，將在提出的系統與基準系統中使用相同的人名信息識別方法。大學人員頁面中的人名信息是以條目形式出現，無上下文信息，因此實驗中結合中文人名的構造規則，使用漢語人名姓氏庫文件匹配得到符合規則的候選人名，然后通過常用詞詞典匹配可排除“黨委”、“學工”等通常作為先導詞的關系型噪聲信息，通過候選人名的重復度與位置信息比對可排除“文科樓”、“第一批”等通常會重復在不同人員中出現的屬性型噪聲信息。本文重點討論基于LCA分塊方法的人員信息抽取，因此不對人名信息識別與去噪部分進行詳細闡述。

6.2實驗結果及分析

表1顯示了對數據集中的1 641個大學人員頁面進行人員信息所屬區域定位的結果。

Table 1　Experimental results on 1 641 real faculty list pages表1　1 641個人員頁面數據區域識別結果

從表1可以看出，隨著閾值的提高，MDR分塊算法的準確率會有提高，而召回率會降低。因為閾值提高代表Data Region中對Data Record之間的相似度要求更嚴格，所以準確率會上升而召回率會降低。

TLCA分塊及有效語義塊對齊算法在準確率上與不同閾值的MDR分塊算法相差不大，是因為不論是通過有效語義塊對齊還是通過計算Data Record之間的相似度，都能夠有效過濾噪聲信息；而有效語義塊的邊界識別也是以盡可能不引入噪聲信息為前提。

TLCA分塊及有效語義塊對齊算法在召回率上相對不同閾值的MDR分塊算法均有較顯著提升。這是因為在大學人員頁面中作為非Deep Web的人工靜態頁面，普遍會有修飾與冗余標簽的存在，在MDR算法中這些標簽會降低實際上應該相關的Data Record之間的相似度，從而對Data Region的識別造成干擾，所以會有較多的Data Region被遺漏；而LCA分塊算法實質上是一種自底向上尋找祖先節點的方法，在尋找祖先節點的過程中不會受到修飾標簽與冗余標簽的影響，所以在大學人員頁面中有較好的召回率。

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

Fig.9　Asituation where effective semantic blocks can hardly align圖9　有效語義塊難以對齊的頁面示例

7　結束語

從大學網站中抽取所有關系映射下的人員信息，對于學術社交網絡的構建有重要意義。針對大學科研人員列表頁面的特點，提出了一種基于LCA對頁面進行語義劃分的TLCA算法，并在此基礎上提出了有效語義塊的識別及對齊方法用于人員列表信息的抽取。通過在真實的大學人員列表頁面中進行實驗，證明了本文方法具有普遍適用性，且能夠克服現有網頁分塊方法在大量的大學人員列表頁面中的一些缺陷。但在實際測試中發現少量頁面的結構中使用有效語義塊對齊方法會造成人員信息的部分丟失，在后續的研究中，需要解決有效語義塊對齊方法在更加復雜情況中的局限性。

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.

附中文參考文獻:

[7]高樂,張健,田賢忠.基于視覺的Web頁面分塊算法的改進與實現[J].計算機系統應用,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—），男，湖北鄂州人，武漢大學計算機學院碩士研究生，主要研究領域為Web數據抽取。

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.

劉夢赤（1962—），男，湖北武漢人，1992年于卡爾頓大學獲得博士學位，現為武漢大學特聘教授、博士生導師，加拿大里賈納大學終身教授，主要研究領域為數據庫理論與系統，數據模型，XML，網絡數據管理等。在國內外期刊及學術會議上發表論文100余篇，主持和承擔多項國家杰出青年科學基金（外籍）、國家重點基礎研究發展計劃（973計劃）、加拿大國家自然科學與工程基金等項目。

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年于武漢大學獲得博士學位，現為湖北大學副教授、碩士生導師，主要研究領域為數據庫，智能信息系統，社交網絡等。在國內外期刊及學術會議上發表論文10余篇，承擔和參與國家自然科學基金、國家重點實驗室開放課題、國家杰出青年科學基金、國家重點基礎研究發展計劃（973計劃）等項目。

*The National Natural Science Foundation of China under Grant No.61202100(國家自然科學基金);the Open Foundation of State Key Laboratory of Software Engineering under Grant No.SKLSE2012-09-20(軟件工程國家重點實驗室開放基金).

Received 2015-07,Accepted 2015-09.

CNKI網絡優先出版: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

文獻標志碼：A

中圖分類號：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