楊欽 楊沐昀
摘 要:本文提出了一種基于DOM樹的正文提取方法。該方法是在基于DOM樹的文本密度的正文提取算法的框架上改進(jìn)而來的?;趯?duì)文言文翻譯網(wǎng)站的觀察,本方法使用標(biāo)點(diǎn)符號(hào)密度取代原方法的文本密度。通過隨機(jī)選取50篇文言文翻譯網(wǎng)頁作為測(cè)試集,本文提出的方法獲得了更好的準(zhǔn)確率、召回率和F值。
關(guān)鍵詞:DOM;標(biāo)點(diǎn)密度;文本密度;正文提取
中圖分類號(hào):TP312 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):2095-2163(2015)04-
A Method of Webpage Content Extraction based on Point Density
YANG Qin, YANG Muyun
(School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China)
Abstract: This paper proposes a DOM based content extraction method. It is improved from the DOM based content extraction via text density. Based on the observation of classical Chinese translation websites, the paper uses point density to replace text density.50 classical Chinese translaiton webpages are randomly chosen as the test data set, the proposed method obtains better precision, recall, and F-measure.
Keywords: DOM; Point Density; Text Density; Content Extraction
0引 言
互聯(lián)網(wǎng)的快速發(fā)展使其已經(jīng)成為一個(gè)天然龐大的數(shù)據(jù)來源,而且其影響也正在日漸提升之中。搜索引擎、網(wǎng)絡(luò)數(shù)據(jù)挖掘等技術(shù)正是使用這些網(wǎng)絡(luò)數(shù)據(jù)來發(fā)現(xiàn)有用的信息和知識(shí)。具體來說,這些技術(shù)的研究對(duì)象就是網(wǎng)頁的正文內(nèi)容。但在現(xiàn)實(shí)狀況下,網(wǎng)頁的正文卻通常是和網(wǎng)頁的其他內(nèi)容如導(dǎo)航信息、廣告、版權(quán)說明等混合摻雜在一起。這些內(nèi)容和網(wǎng)頁的主題并無任何關(guān)系,而只是噪聲信息,因而對(duì)有關(guān)網(wǎng)頁課題的探索研究造成全局性的復(fù)雜且重大的影響。
基于此,為了提升網(wǎng)絡(luò)數(shù)據(jù)挖掘和信息檢索等的設(shè)計(jì)研究性能,即可利用網(wǎng)頁正文提取技術(shù)從網(wǎng)頁中去除噪聲信息提取網(wǎng)頁正文??傮w來說,正文提取可以提升相關(guān)研究的工程實(shí)際性能,并已在現(xiàn)實(shí)中獲得了廣泛的應(yīng)用。使用WEB作為語料庫吸引了自然語言處理領(lǐng)域眾多的研究者的關(guān)注參與。通過自動(dòng)下載相關(guān)網(wǎng)頁,并進(jìn)行正文提取,就可以較短的時(shí)間,較小的代價(jià)構(gòu)建一個(gè)大型語料庫。此外,移動(dòng)手機(jī)的大量普及則使得網(wǎng)頁需要適應(yīng)較小的屏幕。綜上可知,針對(duì)網(wǎng)頁進(jìn)行正文提取的需求已是日顯迫切。然而,提取網(wǎng)頁正文卻是一個(gè)困難的任務(wù)。早在2005年,Gibson等[1]就估計(jì)出網(wǎng)絡(luò)上的噪聲信息的比例將在40%~50%,并且準(zhǔn)確預(yù)言了這個(gè)比例還會(huì)不斷上升?,F(xiàn)如今,網(wǎng)頁的布局和風(fēng)格已比從前更趨復(fù)雜,這一現(xiàn)象也隨即愈加嚴(yán)重?,F(xiàn)在的網(wǎng)頁大多使用格式標(biāo)簽和
研究者提出了很多基于網(wǎng)頁統(tǒng)計(jì)信息的正文提取方法。Finn[3]等在2001年提出Body Text Extraction (BTE)算法。這個(gè)算法是為了提升數(shù)字圖書館正文分類器的準(zhǔn)確性。研究將HTML文檔表示為一系列詞和標(biāo)簽符號(hào),再通過識(shí)別單一的連續(xù)的區(qū)域來抽取正文,通常識(shí)別出來的這個(gè)區(qū)域包含最多的詞和最少的HTML標(biāo)簽。為了克服BTE方法只能發(fā)現(xiàn)一個(gè)單一的連續(xù)的文本塊的限制,Pinto等[4]把這個(gè)方法擴(kuò)展成Document Slope Curves (DSC)方法。在該方法中,視窗技術(shù)可用于定位文檔區(qū)域,在這個(gè)區(qū)域中詞標(biāo)記比標(biāo)簽標(biāo)記要更加頻繁。此次開發(fā)技術(shù)可用來提升QuASM系統(tǒng)使用網(wǎng)絡(luò)數(shù)據(jù)回答問題的性能和效率。
Debnath等[5]提出基于HTML文檔塊分割的Feature Extractor (FE)和K Feature Extractor (KFE)技術(shù)。該方法對(duì)每個(gè)塊分析了設(shè)定的特征例如文本的數(shù)量,圖像和腳本代碼,而后再通過選擇最符合某個(gè)期望特征(如最多的文本)的塊來提取正文。Gupta等[6]在2003年嘗試把不同的啟發(fā)式方法結(jié)合到Crunch的系統(tǒng)框架中。這個(gè)框架基于DOM樹,通過定義兩類過濾器發(fā)現(xiàn)并從DOM樹刪除非正文內(nèi)容。這一研究證明了,不同正文提取算法的適當(dāng)組合會(huì)產(chǎn)生比單一的方法更好的結(jié)果。此后,Gottron[7]則設(shè)計(jì)了CombineE框架。這是一個(gè)最新的集成框架,能使得正文提取算法的配置變得更加簡單。
Mantratzis等[8]在2005年提出Link Quota Filter (LQF)方法。LQF通過識(shí)別文本與超鏈接比例高的DOM元素來確定鏈接列表和導(dǎo)航信息。這個(gè)方法實(shí)際是從文檔中刪除鏈接塊來提取正文。LQF的缺點(diǎn)是算法本身依賴于結(jié)構(gòu)元素,并且只能清除超鏈接類型的噪聲。Gottron[9]在2008年提出Content Code Blurring(CCB)算法。這個(gè)方法可在具有相同格式的源碼序列中進(jìn)行正文提取。Weninger等[10]在2010年提出標(biāo)簽比例(CETR)算法。該方法使用HTML文檔標(biāo)簽比例從網(wǎng)頁中抽取正文。方法中,以行為基礎(chǔ)計(jì)算標(biāo)簽比例,再將比例結(jié)果的直方圖聚類成正文和噪聲區(qū)域。CETR算法簡潔且高效的方法,但卻容易受到網(wǎng)頁源代碼風(fēng)格變化的影響。Kohlschütter等[11]在2010年提出了一個(gè)可對(duì)網(wǎng)頁文本元素實(shí)施分類的簡單有效的應(yīng)用技術(shù)。具體就是通過分析一些淺文本特征(如平均句長、字?jǐn)?shù)以及文本位置)來識(shí)別樣板,該方法的理論基礎(chǔ)是數(shù)量語言學(xué)的隨機(jī)文本生成。
孫飛等[12]在2011年提出Content Extraction via Text Density (CETD)算法。這個(gè)方法基于DOM樹,使用DOM樹節(jié)點(diǎn)的文本密度Text Density 和Composite Text Density衡量節(jié)點(diǎn)重要性,同時(shí)結(jié)合DensitySum區(qū)分出正文區(qū)域和噪聲區(qū)域,進(jìn)而提取出正文內(nèi)容。該方法具有快速、準(zhǔn)確、通用的特點(diǎn),并且最終得到的是結(jié)構(gòu)化文本而不是大多數(shù)方法的純文本。Qureshi等[13]在2012年提出一個(gè)基于DOM樹的混合模型。研究中結(jié)合兩個(gè)不同的模型,一個(gè)模型基于統(tǒng)計(jì)特征(文本信息和鏈接密度),另一個(gè)模型則基于格式特性(如字體、風(fēng)格、位置)。Uzun等[14]在2013年提出一個(gè)兩步驟相互促進(jìn)的混合方法。其中的步驟一是使用決策樹學(xué)習(xí)得到抽取正文的規(guī)則,步驟二是利用得到的規(guī)則進(jìn)行正文提取。相應(yīng)地,Insa等[15]也在2013年提出了Words/Leafs Ratio(WLR)算法。這個(gè)方法基于DOM樹,通過分析結(jié)點(diǎn)的文字葉子比率(WLR)和結(jié)點(diǎn)的層級(jí)關(guān)系,從而識(shí)別出包含正文的塊。
2基于DOM的標(biāo)點(diǎn)密度的正文提取
這一節(jié)將主要介紹基于DOM樹的標(biāo)點(diǎn)密度的正文提取算法。本文的這一算法是參考孫飛等[12]的基于DOM樹的文本密度算法的框架上,并通過優(yōu)化改進(jìn)而最終獲得實(shí)現(xiàn)的。
2.1DOM樹
DOM(Document Object Model)的中文名是文檔對(duì)象模型,也就是一個(gè)與語言和平臺(tái)都無關(guān)的協(xié)議。該協(xié)議允許程序和腳本動(dòng)態(tài)地獲取和更新HTML等文檔的內(nèi)容、結(jié)構(gòu)和風(fēng)格。DOM提供了一系列接口,通過這些接口就可以對(duì)文檔進(jìn)行處理,并將這些處理進(jìn)行展現(xiàn)。DOM把HTML中的所有元素都定義成節(jié)點(diǎn)。DOM實(shí)際是一個(gè)樹狀結(jié)構(gòu),DOM樹通過樹的父子節(jié)點(diǎn)和兄弟節(jié)點(diǎn)來表示HTML中標(biāo)簽的嵌套關(guān)系和并列關(guān)系。使用DOM處理HTML網(wǎng)頁,實(shí)際是把HTML文檔處理成一顆樹,DOM提供各種處理接口,這樣就能通過接口以樹的形式對(duì)HTML文檔進(jìn)行訪問、處理以及呈現(xiàn)。
2.2標(biāo)點(diǎn)密度
通過對(duì)古漢語現(xiàn)代漢語相應(yīng)網(wǎng)站的觀察和分析,可以發(fā)現(xiàn)有一個(gè)比文本密度更適合的特征。文本密度把所有的文本統(tǒng)一對(duì)待,但是文本不同,對(duì)于確定一個(gè)節(jié)點(diǎn)是否為正文節(jié)點(diǎn)的作用也是不一樣的。相對(duì)于其他文本內(nèi)容來說,標(biāo)點(diǎn)符號(hào)則具有更為顯著的標(biāo)識(shí)的作用。
從古漢語現(xiàn)代漢語網(wǎng)頁可以看出,標(biāo)點(diǎn)符號(hào)只存在于正文中,不存在于噪聲信息中。其他兩個(gè)即將用到的網(wǎng)站也是這種情況?;谶@一原因,即可使用標(biāo)點(diǎn)替換文本來計(jì)算密度更能區(qū)分正文和噪聲。為了和文本密度進(jìn)行區(qū)分,可將其定義為標(biāo)點(diǎn)密度。節(jié)點(diǎn)i的標(biāo)點(diǎn)密度是節(jié)點(diǎn)i的標(biāo)點(diǎn)個(gè)數(shù)PointNumber和節(jié)點(diǎn)i的節(jié)點(diǎn)個(gè)數(shù)NodeNumber的比值。其中,PointNumber表示節(jié)點(diǎn)所有子樹的標(biāo)點(diǎn)個(gè)數(shù)之和;NodeNumber表示節(jié)點(diǎn)所有子樹的節(jié)點(diǎn)個(gè)數(shù)之和。
在算法的實(shí)現(xiàn)中,通過對(duì)DOM樹的遍歷,可以得到每一個(gè)節(jié)點(diǎn)的標(biāo)點(diǎn)個(gè)數(shù)和節(jié)點(diǎn)個(gè)數(shù)并計(jì)算出其標(biāo)點(diǎn)密度。這樣,DOM樹中的節(jié)點(diǎn)i的標(biāo)點(diǎn)密度定義如下:
(1)
式中,Pi表示節(jié)點(diǎn)i的標(biāo)點(diǎn)個(gè)數(shù),即PointNumber;Ni表示節(jié)點(diǎn)的節(jié)點(diǎn)個(gè)數(shù),即NodeNumber。當(dāng)Ni是0時(shí),令Ni=1。
PointDensity反映了網(wǎng)頁中對(duì)應(yīng)標(biāo)簽的標(biāo)點(diǎn)密度。結(jié)構(gòu)簡單且包含較多標(biāo)點(diǎn)符號(hào)的標(biāo)簽,其標(biāo)點(diǎn)密度較高;結(jié)構(gòu)復(fù)雜且包含較少標(biāo)點(diǎn)的節(jié)點(diǎn)其標(biāo)點(diǎn)密度較小。同時(shí),標(biāo)點(diǎn)密度相對(duì)文本密度更獨(dú)立于網(wǎng)站的結(jié)構(gòu),而且對(duì)正文信息和噪聲的區(qū)分也將更加有效。
基于鏈接噪聲沒有或者很少有標(biāo)點(diǎn)符號(hào)這個(gè)觀察事實(shí),所提出的標(biāo)點(diǎn)密度很必然地實(shí)現(xiàn)了對(duì)超鏈接噪聲的排除,所以此處將不再參照復(fù)雜文本密度定義復(fù)雜標(biāo)簽密度。
2.3標(biāo)點(diǎn)密度和
這里,參照文本密度和DensitySum定義標(biāo)簽密度和PointDensitySum。節(jié)點(diǎn)i的標(biāo)簽密度和定義為節(jié)點(diǎn)i的直接孩子節(jié)點(diǎn)的標(biāo)簽密度之和,其公式如下:
(2)
其中,child(i)表示節(jié)點(diǎn)i的直接孩子節(jié)點(diǎn)集合,PointDensityj表示節(jié)點(diǎn)j的文本密度。閾值的選取,將文本密度、文本密度和分別替換為標(biāo)點(diǎn)密度、標(biāo)點(diǎn)密度和。這樣,先找到標(biāo)簽密度和最大的節(jié)點(diǎn),再將body節(jié)點(diǎn)到該節(jié)點(diǎn)路徑上的最小的節(jié)點(diǎn)標(biāo)簽密度作為閾值。
2.4正文提取算法
研究使用孫飛等[16]開發(fā)的提取算法,只是將相應(yīng)的文本密度、文本密度和分別替換為標(biāo)點(diǎn)密度、標(biāo)點(diǎn)密度和。算法的輸入是網(wǎng)頁DOM樹的根節(jié)點(diǎn)R,和閾值t,輸出是網(wǎng)頁正文,算法描述如下:
(1)如果節(jié)點(diǎn)R的標(biāo)點(diǎn)密度大于閾值t,則轉(zhuǎn)(2),否則結(jié)束;
(2)找到節(jié)點(diǎn)R的子樹(包括R本身)中標(biāo)點(diǎn)密度和最大的節(jié)點(diǎn)C;
(3)將節(jié)點(diǎn)C標(biāo)記為正文節(jié)點(diǎn);
(4)對(duì)節(jié)點(diǎn)R的每個(gè)孩子節(jié)點(diǎn)提取正文。
3 實(shí)驗(yàn)
在本節(jié)中,首先介紹了實(shí)驗(yàn)數(shù)據(jù)和評(píng)價(jià)指標(biāo)。然后,對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行呈現(xiàn)和討論。
數(shù)據(jù)集
本文針對(duì)的是古漢語現(xiàn)代漢語平行篇章存在的網(wǎng)站及網(wǎng)頁。其中采用的實(shí)驗(yàn)數(shù)據(jù)是隨機(jī)抽取50個(gè)古漢語現(xiàn)代漢語平行篇章網(wǎng)頁。標(biāo)準(zhǔn)正文是通過人工方式從網(wǎng)頁采選獲得的。
3.2評(píng)價(jià)指標(biāo)
實(shí)驗(yàn)結(jié)果的評(píng)價(jià)采用準(zhǔn)確率Precision、召回率Recall和F值。設(shè)O為算法輸出的網(wǎng)頁正文,H為標(biāo)準(zhǔn)正文。把O,H看作漢字及標(biāo)點(diǎn)符號(hào)組成的字符串,那么:
(3)
(4)
(5)
其中,LCS(O,H)表示字符串O,H的最長公共子串,len(LCS(O,H))表示LCS(O,H)的長度,len(O)表示字符串O的長度,len(H)表示字符串H的長度。
3.3實(shí)驗(yàn)結(jié)果和分析
研究設(shè)計(jì)實(shí)現(xiàn)了文本密度、復(fù)雜文本密度和標(biāo)點(diǎn)密度三個(gè)正文提取算法。其在數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果對(duì)比可如表1所示。
表1 三種正文提取算法的性能比較
Tab.1 Comparison of three content extraction algorithm
方法\性能 準(zhǔn)確率 召回率 F值
標(biāo)點(diǎn)密度算法 0.891 1 1 0.942 4
文本密度算法 0.881 3 0.983 7 0.929 7
復(fù)雜文本密度算法 0.887 9 0.997 3 0.939 4
從實(shí)驗(yàn)結(jié)果可以看到,使用標(biāo)點(diǎn)密度的正文提取算法準(zhǔn)確率、召回率和F值上均要高于其他兩種方法。
4 結(jié)束語
本文提出的基于標(biāo)點(diǎn)密度的網(wǎng)頁正文提取方法,該方法的改進(jìn)創(chuàng)新主要在于使用了更為合適的標(biāo)點(diǎn)密度替換文本密度。總而言之,這一研究進(jìn)程就是基于文言文翻譯網(wǎng)站上的一個(gè)觀測(cè)事實(shí),即:正文信息含有更多的標(biāo)點(diǎn)符號(hào)而噪聲信息基本沒有標(biāo)點(diǎn)符號(hào)。由此出發(fā),本文提出的方法獲得了比文本密度更好的性能,而且在準(zhǔn)確率、召回率和F-值上都有一定的提升。
參考文獻(xiàn):
[1] PUNERA K, GIBSON D, TOMKINS A. The volume and evolution of Web Page Templates[C]// Special interest tracks and posters of the 14th international conference on World Wide Web, Chiba:ACM, 2005:830-839.
[2] RAHMAN A F R, ALAM H, HARTONO R. Content extraction from html documents[C]//1st Int. Workshop on Web Document Analysis (WDA2001), Seattle:[s.n.], 2001: 1-4.
[3] FINN A, KUSHMERICK N, SMYTH B. Fact or fiction: Content classification for digital libraries[C]// DELOS Workshops, Citeseer:Dublin, 2001:1-6.
[4] PINTO D, BRANSTEIN M, COLEMAN R, et al. QuASM: a system for question answering using semi-structured data[C]//Proceedings of the 2nd ACM/IEEE-CS joint conference on Digital libraries, New York:ACM, 2002: 46-55.
[5] DEBNATH S, MITRA P, GILES C L. Automatic extraction of informative blocks from webpages[C]//Proceedings of the Acm Sac, Santa Fe:ACM, 2005:1722-1726.
[6] GUPTA S, KAISER G, STOLFO S. Extracting context to improve accuracy for HTML content extraction[C]//Special interest tracks and posters of the 14th international conference on World Wide Web, Chiba:ACM, 2005: 1114-1115.
[7] GOTTRON T. Combining content extraction heuristics: the CombinE system[C]//Proceedings of the 10th International Conference on Information Integration and Web-based Applications & Services, Linz:ACM, 2008: 591-595.
[8] MANTRATZIS C, ORGUN M, CASSIDY S. Separating XHTML content from navigation clutter using DOM-structure block analysis[C]// Hypertext 05 Proceedings of the Sixteenth Acm Conference on Hypertext & Hypermedia, New York:ACM, 2005:145-147.
[9] GOTTRON T. Content code blurring: A new approach to content extraction[C]// Proceedings of the 2008 19th International Conference on Database and Expert Systems Application, [s.1.]:IEEE Computer Society, 2008:29-33.
[10] WENINGER T, HSU W H, HAN J. CETR: content extraction via tag ratios.[C]// Proceedings of the 19th international conference on World wide web, Raleigh:ACM, 2010:971-980.
[11] KOHLSCHUTTER C, FANKHAUSER P, NEJDL W. Boilerplate detection using shallow text features[C]//Proceedings of the third ACM international conference on Web search and data mining, NewYork:ACM, 2010: 441-450.
[12] SUN F, SONG D, LIAO L. DOM based content extraction via text density[C]// Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval, Beijing:ACM, 2011:245-254.
[13] QURESHI P A R, MEMON N. Hybrid model of content extraction[J]. Journal of Computer & System Sciences, 2012, 78(4):1248–1257.
[14] UZUN E, AGUN H V, YERLIKAYA T. A hybrid approach for extracting informative content from web pages[J]. Information Processing & Management, 2013, 49(4): 928-944.
[15] INSA D, SILVA J, TAMARIT S. Using the words/leafs ratio in the DOM tree for content extraction[J]. J. Log. Algebr. Program., 2013, 82(8): 311-325.