張小娣 宋余慶

(江蘇大學(xué)科技信息研究所 鎮(zhèn)江 212013)

·信息檢索·

基于網(wǎng)頁正文邏輯段落和長句提取的網(wǎng)頁去重算法

張小娣 宋余慶

(江蘇大學(xué)科技信息研究所 鎮(zhèn)江 212013)

網(wǎng)頁去重是提高網(wǎng)絡(luò)檢索效果的有效途徑。針對現(xiàn)有網(wǎng)頁去重算法的不足和網(wǎng)頁正文的結(jié)構(gòu)特征，提出一個基于網(wǎng)頁正文邏輯段落和長句提取的網(wǎng)頁去重算法。該方法通過用戶檢索關(guān)鍵詞將網(wǎng)頁正文物理段落結(jié)構(gòu)表示成邏輯段落，在此基礎(chǔ)上提取邏輯段落中的長句作為網(wǎng)頁特征碼實(shí)現(xiàn)相似網(wǎng)頁判斷。實(shí)驗(yàn)證明，該方法提高了篇幅短小的鏡像網(wǎng)頁和近似鏡像網(wǎng)頁的去重效果。

網(wǎng)頁去重 邏輯段落 長句提取 句子相似度

1 引言

近年來，由于網(wǎng)絡(luò)和信息技術(shù)的快速發(fā)展，網(wǎng)絡(luò)資源日益豐富，互聯(lián)網(wǎng)上的信息快速增長。根據(jù)中國互聯(lián)網(wǎng)絡(luò)信息中心2011年1月的統(tǒng)計報告[1]，自2003年開始，中國的網(wǎng)頁規(guī)?；颈３址鲩L，2010年網(wǎng)頁數(shù)量達(dá)到600億個，年增長率78.6%。網(wǎng)頁的規(guī)模說明了互聯(lián)網(wǎng)內(nèi)容的豐富程度，用戶面對如此海量的信息，利用搜索引擎進(jìn)行信息檢索已經(jīng)成為一個重要途徑。報告顯示“2010年，搜索引擎用戶規(guī)模3.75億，……搜索引擎在網(wǎng)民中的使用率增長了8.6個百分點(diǎn)，達(dá)81.9%，躍居網(wǎng)民各種網(wǎng)絡(luò)應(yīng)用使用率的第一位”[1]。搜索引擎已經(jīng)成為網(wǎng)民上網(wǎng)的主要入口，國內(nèi)各大搜索引擎運(yùn)營廠商不斷提高其服務(wù)能力和水平。但用戶在搜索信息的時候常常會發(fā)現(xiàn)，返回結(jié)果中存在大量重復(fù)信息。為提高搜索引擎的檢索效率，減輕用戶獲取有效信息的時間和成本，甄別和去除重復(fù)網(wǎng)頁是一個有效途徑。

目前我國對于相似網(wǎng)頁檢測算法的研究有：基于全文分段匹配的去重算法[2]；基于網(wǎng)頁關(guān)鍵詞的去重算法[3,4]；基于網(wǎng)頁特征碼的去重算法[5-7]；基于鏈接的去重算法[8,9]；基于網(wǎng)頁結(jié)構(gòu)的去重算法[10]；基于長句提取的網(wǎng)頁去重算法[11]；基于語義的網(wǎng)頁去重算法[12]等?，F(xiàn)有的技術(shù)從不同角度解決網(wǎng)頁重復(fù)問題，按照網(wǎng)頁特征碼提取的粒度可以分為三類：①基于詞級別的粒度進(jìn)行特征提取[3]；②基于多個詞組成的特征串和基于長句進(jìn)行特征提取[7]；③基于段落或整篇網(wǎng)頁內(nèi)容進(jìn)行特征提取[2]。由于互聯(lián)網(wǎng)上存在海量信息，重復(fù)網(wǎng)頁的辨別不僅需要考慮精度也需要考慮速度。網(wǎng)頁特征碼的粒度越小計算速度越慢，粒度越大計算速度越快。基于詞級別的粒度比較小，對于大規(guī)模信息檢索實(shí)用性不強(qiáng)；基于整篇網(wǎng)頁內(nèi)容的粒度最大，雖然速度快，但是對正文細(xì)微的區(qū)別無法辨別，精度不高。近年來提出的網(wǎng)頁去重算法采用一種折中的方法，如基于網(wǎng)頁正文結(jié)構(gòu)的網(wǎng)頁去重算法和長句提取的去重算法。基于網(wǎng)頁正文結(jié)構(gòu)去重算法的基本原理是將網(wǎng)頁文本的自然段編號，使用該編號代替自然段本身生成一棵目錄結(jié)構(gòu)樹，并通過目錄結(jié)構(gòu)的相似程度來判斷網(wǎng)頁的重復(fù)程度。該方法在很大程度上節(jié)省了時空開銷，適用于大規(guī)模的相似度計算；但是對于無小標(biāo)題式文本，該算法就演變?yōu)榘醋匀欢芜M(jìn)行分段簽名；對于自然段中有丟字、加字但是主題內(nèi)容相同的重復(fù)網(wǎng)頁則無法檢測出來。長句提取去重算法的思想是：首先提取網(wǎng)頁正文中所有長句中字?jǐn)?shù)最多的m個句子。不足m個句子的網(wǎng)頁，保留所有的長句。然后對每個句子進(jìn)行摘要，將得到的摘要值組成向量集合作為網(wǎng)頁指紋進(jìn)行相似度判斷。該算法缺點(diǎn)是：當(dāng)網(wǎng)頁正文內(nèi)容較少時，該算法則演變?yōu)榛谡W(wǎng)頁內(nèi)容進(jìn)行去重，因此該算法對于篇幅短小的網(wǎng)頁內(nèi)容去重?zé)o能為力。基于上述分析，本文提出了一種基于網(wǎng)頁正文邏輯段落和長句提取的網(wǎng)頁去重算法。

2 網(wǎng)頁正文邏輯段落劃分

目前基于網(wǎng)頁正文結(jié)構(gòu)的網(wǎng)頁去重算法針對的是傳統(tǒng)的物理段落，即依照自然段作為劃分依據(jù)，給各個段落按照在正文中層次的不同賦予不同的權(quán)值，進(jìn)而使用這些段落進(jìn)行相似匹配，這種方法帶有一定的機(jī)械性。如果物理段落中包含的信息過少，容易導(dǎo)致特征詞數(shù)較少，則無法表征該網(wǎng)頁內(nèi)容，容易出現(xiàn)匹配率較低的現(xiàn)象。因此，本文以用戶查詢關(guān)鍵詞為基礎(chǔ)，建立了一種以用戶查詢關(guān)鍵詞為中心的邏輯段落結(jié)構(gòu)，在此基礎(chǔ)上提取邏輯段落中的長句作為網(wǎng)頁特征碼實(shí)現(xiàn)相似網(wǎng)頁判斷，提高網(wǎng)頁去重效果。

2.1 涉及到的中文分詞策略

本文采用基于多層隱馬模型的漢語詞法分析系統(tǒng)ICTCLAS(Institute of Computing Technology，Chinese Lexical Analysis System )，該系統(tǒng)由中國科學(xué)院計算技術(shù)研究所研制，具有中文分詞、未登錄詞識別等功能。分詞策略為：首先將專有名詞切出，剩下的部分采取雙向分詞策略。如果兩種分詞策略結(jié)果相同，則直接輸出結(jié)果；如果結(jié)果不一致，則輸出最短路徑的那個結(jié)果。將用戶輸入的關(guān)鍵詞保存在集合K中，把K中的關(guān)鍵詞進(jìn)行分詞，將結(jié)果存放在集合T中，T={t1，t2，…，tn}。

2.2 邏輯段落劃分

邏輯段劃分算法描述：

定義1：網(wǎng)頁正文內(nèi)容預(yù)處理即經(jīng)過分詞后過濾掉沒有實(shí)際意義的虛詞和停用詞。

定義2：V表示網(wǎng)頁正文內(nèi)容經(jīng)過分詞、預(yù)處理后剩下的實(shí)詞集合；Vt表示檢索關(guān)鍵詞。

定義3：P表示網(wǎng)頁正文第i個自然段經(jīng)過分詞后實(shí)詞集合的個數(shù)。

定義4：假設(shè)網(wǎng)頁正文有m個自然段，則Vim表示從第i個自然段到第m個自然段之間經(jīng)過分詞后的實(shí)詞集合。

定義5：定義V和Vi的笛卡爾乘積如下：

V·Vi+1=∑wiwk(0≤i≤P-1，0≤k≤Pi)

輸入：經(jīng)過去噪后的網(wǎng)頁正文。

輸出：包含了邏輯段劃分信息的text。

處理過程：

(1)去噪后的網(wǎng)頁正文處理成原始自然段集合Natual()，假設(shè)共有m個自然段；

(2)每個自然段經(jīng)過分詞處理后得到一個包含實(shí)詞的二維集合PreNatual()；

(3)統(tǒng)計包含查詢關(guān)鍵詞的詞段i；

(4)初始化index，提取邏輯段邊界。

分析:①若i=0，則把Natual(i)加入text中，并提取該邏輯段的查詢關(guān)鍵詞，index=i；否則，i=i+1。

②若0

③若i=m-1，提取該邏輯段的查詢關(guān)鍵，并把Natual(i)加入text中；否則，把Natual(index+1)至Natual(i)加入text中。

3 長句提取算法

句子是話語的最小單位，卻是語言的最大單位，若干句子組成段落。句子既有組篇功能也有表意功能。長句能夠很好地表征網(wǎng)頁。首先，長句作為網(wǎng)頁特征可以保證不容易重復(fù)。中文常用字有6700多個，任意兩個句子重復(fù)的概率約為1/(6700k)，當(dāng)k的值較大時，重復(fù)的概率非常低。另外，相對于完整的段落，句子要短很多，被干擾的概率也較低。本文的長句有別于語法上定義的用句號分隔的句子，將長句定義為長度不少于k個字的句子。如果網(wǎng)頁正文較長，能提取的長句可能很多。為了減小存儲特征空間，僅保留所有長句中最長(字?jǐn)?shù)最多)的m個句子；對于不足m個句子的網(wǎng)頁，保留所有的長句。然后使用MD5算法計算這些長句的摘要，將這些摘要作為網(wǎng)頁的特征。MD5算法可以把任意長度的數(shù)據(jù)作為輸入，然后產(chǎn)生一個128比特(16字節(jié))的摘要作為輸出。根據(jù)多次試驗(yàn)設(shè)定長句k值取9，即每個句子至少9個漢字(16個字節(jié))，如果字?jǐn)?shù)太多的話，特征易受干擾；字?jǐn)?shù)太少，網(wǎng)頁特征表征性不高。根據(jù)MD5算法，即使超出8個漢字的長句也能用16個字節(jié)來表示，因此可以節(jié)省存儲空間。如上所述，一張網(wǎng)頁的特征可以定義為：

其中，S為該網(wǎng)頁的長句集合，|S|表示集合中長句的數(shù)量。

4 基于網(wǎng)頁正文邏輯段落和長句提取的網(wǎng)頁去重算法

4.1 系統(tǒng)設(shè)計

本系統(tǒng)由四個模塊組成。網(wǎng)頁去噪模塊使用參考文獻(xiàn)13的算法[13]實(shí)現(xiàn)，即將HTML文檔看作字符和標(biāo)簽組成的序列，通過對HTML標(biāo)記進(jìn)行統(tǒng)計，最后生成只含有主題內(nèi)容的HTML文檔；網(wǎng)頁正文邏輯段落提取模塊使用前文介紹的算法實(shí)現(xiàn)；長句提取模塊使用前文介紹的長句提取算法實(shí)現(xiàn)；相似度判斷模塊使用下面介紹的雙層相似度計算方法。

圖1 網(wǎng)頁去重系統(tǒng)圖

4.2 相似度判斷

本文將網(wǎng)頁相似度的計算劃分為2個層次，包括句子與句子的相似度計算、段落與段落之間的相似度計算。

(1)句子相似度計算如下：

兩個句子的相似度由詞形相似度和詞序相似度決定，詞形相似度起主要作用，詞序相似度起次要作用。因此句子A、B相似度表示為：

Sim(A,B)=λ1·WordSim(A,B)+λ2·OrdSim(A，B)

其中，λ1，λ2為常數(shù)，且λ1+λ2= 1，相似度的數(shù)值在0～1之間，數(shù)值越接近1則相似度越低。相似句子查找算法描述如下：

輸入：Input, InTab, LenTab, corpora；

輸出：相似句S；

for each word in Input；

計算非零的SameWC(Input, S)；

根據(jù)LenTab計算SameWC(Input,S)排在前K1句子的WordSim(Input, S)；

根據(jù)corpora計算WordSim(Input, S)的OrdSim(Input, S)；

輸出最相似句。

(2)段落相似度的計算過程如下：

段落相似度是由句子相似度計算出的，設(shè)兩個段落分別為t1、t2，sm、sn為段落中的句子，則段落表示如下：

t1= {s11,s12,…, s1m}

t2= {s21,s22,…, s2n}

5 實(shí)驗(yàn)結(jié)果和分析

實(shí)驗(yàn)網(wǎng)頁集來源于人工收集的1500篇網(wǎng)頁，其中包括1000篇不相同網(wǎng)頁，完全重復(fù)的網(wǎng)頁和部分重復(fù)的網(wǎng)頁數(shù)目分別是205篇和295篇，調(diào)用本文去重算法對網(wǎng)頁測試集進(jìn)行實(shí)驗(yàn)，算法的評價指標(biāo)使用查全率(Recall)、查準(zhǔn)率(Precision)和響應(yīng)時間。

通過與現(xiàn)有的一些去重算法進(jìn)行比較，實(shí)驗(yàn)結(jié)果如表1所示。

表1 同現(xiàn)有去重算法比較

圖2 響應(yīng)時間

從實(shí)驗(yàn)結(jié)果可以看出：

(1)基于正文邏輯段落和長句去重算法去重的精確率和查全率都能達(dá)到99%以上，去重效果較好，表明該算法采用的特征碼能有效的代表網(wǎng)頁信息?；谡慕Y(jié)構(gòu)樹算法提取的網(wǎng)頁特征是自然段，提取粒度大，干擾信息多，因此查全率相對較低；基于長句提取算法提取的特征粒度是長句，對于篇幅短小的網(wǎng)頁正文則變?yōu)榛谡W(wǎng)頁內(nèi)容的特征提取，查全率較低；基于正文結(jié)構(gòu)和長句提取算法提取網(wǎng)頁正文的物理段落，對于沒有段落標(biāo)識符的網(wǎng)頁則無法提取段落結(jié)構(gòu)，因此查準(zhǔn)率相對較低。

(2)從響應(yīng)時間圖可以看出，特征碼數(shù)目越多，算法所需時間就越多。在特征碼一定時，特征碼的長度越長，所需比較時間越長。從空間效率上來講本算法能夠滿足大規(guī)模網(wǎng)頁去重的要求，具有實(shí)用價值。

6 結(jié)論

本文提出并設(shè)計了一種以用戶查詢關(guān)鍵詞為中心，基于網(wǎng)頁正文邏輯段落算法和長句提取算法的一種新的網(wǎng)頁去重算法。該算法不僅解決了正文中添加信息的近似鏡像網(wǎng)頁的去重，還增強(qiáng)了篇幅短小網(wǎng)頁的去重效果。試驗(yàn)表明，該方法相對于基于正文結(jié)構(gòu)樹算法[10]和長句提取算法有更高的查全率和查準(zhǔn)率，可以很好地輔助搜索引擎對搜索結(jié)果進(jìn)行過濾。

[1] 中國互聯(lián)網(wǎng)絡(luò)信息中心. 中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計報告:2011年1月[R/OL]. [2011-04-12]. http://www.cnnic.net.cn/dtygg/dtgg/201101/P0201101193289 60192287.pdf.

[2] 彭曙蓉. MD5算法在消除重復(fù)網(wǎng)頁算法中的應(yīng)用[J]. 電腦知識與技術(shù),2005(29):15-16.

[3] 謝 蕙. 基于用戶查詢關(guān)鍵詞的網(wǎng)頁去重方法研究[J]. 現(xiàn)代圖書情報技術(shù),2008(7):43-46.

[4] 樊 勇. 基于主題的網(wǎng)頁去重[J]. 電腦開發(fā)與應(yīng)用,2008(4):4-6.

[5] 姚新波. 基于特征串的網(wǎng)頁去重算法[J]. 科技信息,2008(28):411.

[6] 王 哲. 基于特征碼的網(wǎng)頁去重算法研究[J]. 山東電大學(xué)報,2009(1):14-16.

[7] 吳平博. 基于特征串的大規(guī)模中文網(wǎng)頁快速去重算法研究[J]. 中文信息報,2003(2):28-35.

[8] 龔秋艷. 簡單高效的URL消重的方法[J]. 計算機(jī)應(yīng)用,2010(1):49-50.

[9] 高 凱. 網(wǎng)頁去重策略[J]. 上海交通大學(xué)學(xué)報,2006(5):775-777.

[10] 魏麗霞. 基于網(wǎng)頁文本結(jié)構(gòu)的網(wǎng)頁去重[J]. 計算機(jī)應(yīng)用, 2007(11):2854-2856.

[11] 黃 仁. 基于正文結(jié)構(gòu)和長句提取的網(wǎng)頁去重算法[J]. 計算機(jī)應(yīng)用研究,2010(7): 2489-2491.

[12] 樊 勇,鄭家恒. 網(wǎng)頁去重方法研究[J]. 計算機(jī)工程與應(yīng)用,2009(12):141-143.

[13] 劉艷敏. Web頁面主題信息抽取研究與實(shí)現(xiàn)[J]. 計算機(jī)工程與應(yīng)用,2006(12):146-148.

DetectionandEliminationofSimilarWebPagesBasedonLogicalParagraphsandExtractionofLongSentences

Zhang Xiaodi, Song Yuqing

Institute of Science and Technology Information of Jiangsu University, Zhenjiang 212013, China

The technology of detection and elimination of similar web pages is an effective way to improve the effect of network retrieval. Because of the inadequacy of algorithm and the structural features of webpage texts, an algorithm, based on logical paragraphs and extraction of long sentences to detect and delete similar web pages, is proposed in this paper. Through retrieval keywords, this method expresses webpage’s physical paragraph structures as logical paragraphs. Based on that, long sentences are extracted from logical paragraphs as similar characteristics code of webpages. The experiment results show that this method can improve the effectiveness of short webpages and eliminating similar webpages in retrieval.

detection and elimination of similar web pages； logical paragraphs； extraction of long sentences； sentence similarity

TP391

張小娣，女，1979年生，碩士研究生，研究方向：搜索引擎，發(fā)表論文1篇；宋余慶，男，1959年生，教授，博導(dǎo)，主要研究方向：信息安全、醫(yī)學(xué)圖像處理，發(fā)表論文數(shù)篇。