陳亞峰++郭一帆++王崢

【摘 要】 對(duì)主題網(wǎng)頁去重技術(shù)進(jìn)行了綜述，結(jié)合已有算法的缺點(diǎn)，提出了一種基于主題詞語義與距離的網(wǎng)頁去重算法。該方法通過對(duì)用戶輸入的關(guān)鍵詞進(jìn)行語義標(biāo)注后分詞檢索，計(jì)算分詞子集在網(wǎng)頁文本中的距離，來判斷網(wǎng)頁與主題的相關(guān)度以及網(wǎng)頁之間的相似度。同時(shí)避開了網(wǎng)頁文本向量空間維數(shù)大的不足，在一定程度上考慮到了網(wǎng)頁的語義信息。

【關(guān)鍵詞】 網(wǎng)頁去重 語義分詞與距離 去重

目前大多數(shù)搜索引擎采用基于關(guān)鍵詞的方法返回用戶所需信息，這些信息的冗余度通常很高，很多不相關(guān)的信息沒有進(jìn)行有效的組織。因此人們迫切地希望擁有一種方法，能夠自動(dòng)的將與特定主題相關(guān)的信息分類匯總后，供用戶查閱。主題搜索引擎的出現(xiàn)使得用戶能夠?qū)μ囟ㄖ黝}相關(guān)信息的進(jìn)行獲取，然而在信息采集過程中如何對(duì)搜索回來的頁面進(jìn)行分類，在下一次信息采集的過程中讓爬蟲主動(dòng)發(fā)現(xiàn)主題相關(guān)頁面，并去除相關(guān)頁面中的重復(fù)或近似重復(fù)的頁面成為搜索引擎的研究熱點(diǎn)之一。

1 網(wǎng)頁去重技術(shù)綜述

搜索引擎的工作原理主要分為三個(gè)部分：網(wǎng)頁抓取，網(wǎng)頁處理，提供檢索服務(wù)。網(wǎng)頁去重是搜索引擎預(yù)處理技術(shù)的關(guān)鍵部分，主要是由于web上存在大量的重復(fù)信息，有統(tǒng)計(jì)信息表明，網(wǎng)頁的重復(fù)率平均為4，即用戶通過一個(gè)URL在互聯(lián)網(wǎng)上看到一篇相似網(wǎng)頁的同時(shí)，平均還有三個(gè)URL不同的網(wǎng)頁給出的內(nèi)容相同或近似相同。因此為了提高搜索引擎的工作效率，網(wǎng)頁去重在整個(gè)搜索引擎的工作中是必不可少的。

國外對(duì)于網(wǎng)頁去重的研究最初主要是針對(duì)大型文件系統(tǒng)的近似鏡像文檔檢測(cè)算法上的研究，后來這些算法又被拓展應(yīng)用到數(shù)字化圖書館項(xiàng)目以及搜索引擎系統(tǒng)中。美國Arizona大學(xué)的研究人員對(duì)于大型文件系統(tǒng)中的相似文件采用了計(jì)算文檔的重疊程度的方法來進(jìn)行實(shí)現(xiàn)。國內(nèi)，網(wǎng)頁去重重點(diǎn)還是對(duì)網(wǎng)頁去重的算法進(jìn)行研究。大連理工大學(xué)韓冰主要研究了大規(guī)模的網(wǎng)頁文本去重和科技論文抄襲檢測(cè)。江蘇大學(xué)呂霞提出了一種基于關(guān)鍵詞和特征碼的網(wǎng)頁去重K-CC算法，在分析國內(nèi)外目前比較通用的幾種去重技術(shù)的基礎(chǔ)上，提出了一種基于關(guān)鍵詞和特征碼的網(wǎng)頁去重K-CC算法。

2 基于主題詞語義分詞與距離的網(wǎng)頁去重算法的背景

傳統(tǒng)的特征碼實(shí)現(xiàn)的精確匹配完全可以與先進(jìn)的檢索系統(tǒng)聯(lián)系起來，其去重效率比較高，是一種去重的好方法。但是該方法的缺點(diǎn)是：

（1）特征碼所實(shí)現(xiàn)的是精確匹配，并不能有效的檢測(cè)出轉(zhuǎn)載所造成的近似的重復(fù)網(wǎng)頁；（2）在沒有利用網(wǎng)頁文本結(jié)構(gòu)信息的前提下，極有可能會(huì)發(fā)生長(zhǎng)度不同甚至差別懸殊的文本被視為相同網(wǎng)頁的情況；（3）作為可以產(chǎn)生特征碼的標(biāo)志的句號(hào)有時(shí)也并不會(huì)在網(wǎng)頁文本中出現(xiàn)，也有可能只出現(xiàn)在文章的末尾，或者出現(xiàn)在版權(quán)信息和超鏈接中，而所有這些都會(huì)導(dǎo)致特征碼產(chǎn)生重大錯(cuò)誤。

由于目前大多數(shù)搜索引擎是通過關(guān)鍵詞匹配來完成用戶的檢索請(qǐng)求的，考慮到正文文本語義的復(fù)雜性我們對(duì)關(guān)鍵詞的語義進(jìn)行標(biāo)注，作為網(wǎng)頁檢索的主題詞，并且利用不同關(guān)鍵詞組合的語義及其之間的距離差因素作為評(píng)判標(biāo)準(zhǔn)。故提出了一種基于主題詞語義分詞與距離的網(wǎng)頁去重方法。

3 基于主題詞語義分詞與距離的網(wǎng)頁去重算法的背景

把主題詞（Ks）按詞組形式分成若干個(gè)詞組的模糊集合S，S中詞組的組合必須具有一定語義。然后在給定文本中記錄每個(gè)詞組wi在文本中的位置pi，j，pi，j組成Pi，然后比較所有Pi分量組成的向量的距離差，若距離差L不小于某個(gè)值Kd（模糊評(píng)判標(biāo)準(zhǔn)閥值），則與主題相關(guān)，若小于Kd，則與主題無關(guān)。在不大于Kd中，若L在某個(gè)區(qū)間[a，b]（此區(qū)間是認(rèn)定為重復(fù)置信區(qū)間），若在此區(qū)間，則認(rèn)定為重復(fù)，否則認(rèn)定為不同類。具體模型和方法如下：

（1）設(shè)主題詞為Ks

（2）Ks分拆的模糊集合S為：

S={w1，w2，…，wm}

（3）wi在文本中出現(xiàn)位置的向量：Pi=（pi，1，pi，2，…，pi，k），1≤i≤m，ki∈N

若：wi在文本中沒有出現(xiàn)，則Pi=

（4）語義位置向量V={vi︱vj=（pi，j1，p2，j2，…，pm，jm），1≤jj≤ki}

注：若Pi=，則pi，ji不記入向量中。

（5）計(jì)算V中每個(gè)向量分量差分集合D={di︱dj=△vj=（pi，j-pi-1，ji-1）}

（6）根據(jù)D中的值來判斷主題是否相關(guān)，包括不相關(guān)、相關(guān)（包括重復(fù)（強(qiáng)相關(guān)）或不同類（弱相關(guān)））。

4 相關(guān)性判別方法

判別指標(biāo)用下式表示：

r=∩pi

若r=則不相關(guān)，否則相關(guān)。也可以用向量空間V的維數(shù)r=Dim（V））來判別，若r

重復(fù)性判別方法：在相關(guān)的情況下，判別主題內(nèi)容是否接近或相同。

首先記：

該式表明模糊集S中前m-1個(gè)詞的長(zhǎng)度總合。

（1）若兩文本（S1，S2）內(nèi)容一樣，則兩個(gè)D1=D2應(yīng)相同。（2）若一個(gè)文本S1包含另一文本S2，則D1D2。

注：這里的包含關(guān)系不是di∈D2，則d i∈D1，而是d i∈D2，要么di∈D1，要么di與D1中的某個(gè)dj相差的值小于主觀認(rèn)定的某個(gè)值Kd。把置信區(qū)間[a，b]置為[1，L]，則Kd∈[1， L]可以認(rèn)為主題的語義相同，可以去重，否則認(rèn)為不同即不同類。一般取L=Kd，否則，視查詢文本復(fù)雜度主觀設(shè)定。

通過下面例子對(duì)算法進(jìn)行具體的說明：用戶輸入關(guān)鍵詞“鄭州游覽區(qū)”，得到如下四段網(wǎng)頁文本，用模糊搜索集合S{}表示為：S{鄭州，黃河，游覽區(qū)}。對(duì)應(yīng)的標(biāo)記集合中的各元素為：鄭州—>w1，黃河—>w2，游覽區(qū)—>w3。

文檔A：“黃河游覽區(qū)位于鄭州市北郊的黃河游覽區(qū)是20世紀(jì)70年代才在黃河之濱在荒山上開始建設(shè)的著名風(fēng)景游覽區(qū)，到20世紀(jì)80年代中期，它已有了相當(dāng)?shù)囊?guī)模，不僅成為鄭州市最重要的游覽區(qū)，而且成為馳名中外的華夏歷史文化紀(jì)念地。”例子中：

P1={8，73}

P2={1，13}

P3={3，15，45，80}

V={（8，1，3）；（8，1，15）；（8，1，45）；（8，1，80）；（ 8，13，3）；（8，13，15）；

（8，13，45）；（8，13，80）；（73，1，3）；（73，1，15）；（73，1，45）；（73，1，80）；

（73，13，3）；（73，13，15）；（73，13，45）；（73，13，80）；}

DA={9，21，51，86，15，7，37，73，74，86，116，151，70，62，92，127}

文檔 B：“桃花峪黃河特大橋工程北起鄭焦晉高速公路，南接鄭州西南繞城高速公路，途經(jīng)焦作武陟縣、鄭州滎陽市，全長(zhǎng)28.64公里。其中，黃河特大橋長(zhǎng)7.69公里，北連接線長(zhǎng)8.92公里，南連接線長(zhǎng)12.02公里。主橋位于鄭州黃河風(fēng)景區(qū)西側(cè)桃花峪村附近，北望嘉應(yīng)觀、跨御壩，南臨漢霸二王城，跨黃河中下游分界線桃花峪，俯瞰黃河游覽區(qū)。大橋建成后將為沿黃風(fēng)景名勝旅游發(fā)展提供便利，成為桃花峪綜合旅游的基礎(chǔ)性工程和新的景觀線”。

P1={23，42，89}

P2={4，57，91，124，138}

P3={140}

文檔C：“本網(wǎng)獨(dú)家現(xiàn)場(chǎng)連線人民網(wǎng)河南視窗記者辛靜表示，北京時(shí)間15時(shí)48分，鄭州發(fā)生了日偏食現(xiàn)象，通過觀測(cè)眼鏡可以清晰看到太陽被吞噬掉一個(gè)小邊。記者所在的鄭州黃河游覽區(qū)觀測(cè)點(diǎn)聚集了上百名群眾，大家都得到了相關(guān)機(jī)構(gòu)免費(fèi)派發(fā)的專業(yè)觀測(cè)眼鏡，并且很專注的在欣賞著日偏食景觀，群眾們的心情都十分激動(dòng)”。

P1={32，71}

P2={73}

P3={75}

文檔D：“位于鄭州市北郊的黃河游覽區(qū)是20世紀(jì)70年代才在黃河之濱在荒山上開始建設(shè)的著名風(fēng)景游覽區(qū)，到20世紀(jì)80年代中期，它已有了相當(dāng)?shù)囊?guī)模，成為鄭州市最重要的游覽區(qū)。”

P1={3}

P2={9}

P3={11，40，73}

在上面的例子中分別得到了文檔A、B、C、D中模糊集合S中出現(xiàn)元素的位置集合和語義位置向量集合V的值。由公式計(jì)算得到向量分量差分集合：

D1={9，21，51，86，15，7，37，73，74，86，116，151，70，62，92，127}

D2=（155，115，117，107，117，174，98，98，98，98，221，115，51，51）

D3={43，4}

D4={8，37，70}

置信區(qū)間為[1，4]。

分析D4，D4中37，70在D1中出現(xiàn)，8與D1中的7、9差1，在置信區(qū)間內(nèi)，可以去重，而D4中任何元素與D2中元素差都不在置信區(qū)間內(nèi)，可以認(rèn)為不同類；D4維數(shù)與D3維數(shù)不同可以認(rèn)為不同類，也可看出元素差不在置信區(qū)間內(nèi)，認(rèn)為不同類。

依次類推，D1，D2，D3，屬于不同類。

5 結(jié)語

提出的一種基于主題詞語義與距離的網(wǎng)頁去重算法，通過對(duì)用戶輸入的關(guān)鍵詞進(jìn)行語義標(biāo)注后分詞檢索，計(jì)算分詞子集在網(wǎng)頁文本中的距離，來判斷網(wǎng)頁與主題的相關(guān)度以及網(wǎng)頁之間的相似度。該方法避開了網(wǎng)頁文本向量空間維數(shù)大的不足，并在一定程度上充分考慮到了網(wǎng)頁的語義信息。

參考文獻(xiàn)：

[1]樊小超.基于機(jī)器學(xué)習(xí)的中文文本主題分類及情感分類研究[D].南京：南京理工大學(xué)，2014.

[2]何佳.基于社會(huì)化標(biāo)注的網(wǎng)頁搜索算法綜述[J].小型微型計(jì)算機(jī)系統(tǒng)，2014（06）.endprint

P1={8，73}

P2={1，13}

P3={3，15，45，80}

V={（8，1，3）；（8，1，15）；（8，1，45）；（8，1，80）；（ 8，13，3）；（8，13，15）；

（8，13，45）；（8，13，80）；（73，1，3）；（73，1，15）；（73，1，45）；（73，1，80）；

（73，13，3）；（73，13，15）；（73，13，45）；（73，13，80）；}

DA={9，21，51，86，15，7，37，73，74，86，116，151，70，62，92，127}

文檔 B：“桃花峪黃河特大橋工程北起鄭焦晉高速公路，南接鄭州西南繞城高速公路，途經(jīng)焦作武陟縣、鄭州滎陽市，全長(zhǎng)28.64公里。其中，黃河特大橋長(zhǎng)7.69公里，北連接線長(zhǎng)8.92公里，南連接線長(zhǎng)12.02公里。主橋位于鄭州黃河風(fēng)景區(qū)西側(cè)桃花峪村附近，北望嘉應(yīng)觀、跨御壩，南臨漢霸二王城，跨黃河中下游分界線桃花峪，俯瞰黃河游覽區(qū)。大橋建成后將為沿黃風(fēng)景名勝旅游發(fā)展提供便利，成為桃花峪綜合旅游的基礎(chǔ)性工程和新的景觀線”。

P1={23，42，89}

P2={4，57，91，124，138}

P3={140}

文檔C：“本網(wǎng)獨(dú)家現(xiàn)場(chǎng)連線人民網(wǎng)河南視窗記者辛靜表示，北京時(shí)間15時(shí)48分，鄭州發(fā)生了日偏食現(xiàn)象，通過觀測(cè)眼鏡可以清晰看到太陽被吞噬掉一個(gè)小邊。記者所在的鄭州黃河游覽區(qū)觀測(cè)點(diǎn)聚集了上百名群眾，大家都得到了相關(guān)機(jī)構(gòu)免費(fèi)派發(fā)的專業(yè)觀測(cè)眼鏡，并且很專注的在欣賞著日偏食景觀，群眾們的心情都十分激動(dòng)”。

P1={32，71}

P2={73}

P3={75}

文檔D：“位于鄭州市北郊的黃河游覽區(qū)是20世紀(jì)70年代才在黃河之濱在荒山上開始建設(shè)的著名風(fēng)景游覽區(qū)，到20世紀(jì)80年代中期，它已有了相當(dāng)?shù)囊?guī)模，成為鄭州市最重要的游覽區(qū)?！?/p>

P1={3}

P2={9}

P3={11，40，73}

在上面的例子中分別得到了文檔A、B、C、D中模糊集合S中出現(xiàn)元素的位置集合和語義位置向量集合V的值。由公式計(jì)算得到向量分量差分集合：

D1={9，21，51，86，15，7，37，73，74，86，116，151，70，62，92，127}

D2=（155，115，117，107，117，174，98，98，98，98，221，115，51，51）

D3={43，4}

D4={8，37，70}

置信區(qū)間為[1，4]。

分析D4，D4中37，70在D1中出現(xiàn)，8與D1中的7、9差1，在置信區(qū)間內(nèi)，可以去重，而D4中任何元素與D2中元素差都不在置信區(qū)間內(nèi)，可以認(rèn)為不同類；D4維數(shù)與D3維數(shù)不同可以認(rèn)為不同類，也可看出元素差不在置信區(qū)間內(nèi)，認(rèn)為不同類。

依次類推，D1，D2，D3，屬于不同類。

5 結(jié)語

提出的一種基于主題詞語義與距離的網(wǎng)頁去重算法，通過對(duì)用戶輸入的關(guān)鍵詞進(jìn)行語義標(biāo)注后分詞檢索，計(jì)算分詞子集在網(wǎng)頁文本中的距離，來判斷網(wǎng)頁與主題的相關(guān)度以及網(wǎng)頁之間的相似度。該方法避開了網(wǎng)頁文本向量空間維數(shù)大的不足，并在一定程度上充分考慮到了網(wǎng)頁的語義信息。

參考文獻(xiàn)：

[1]樊小超.基于機(jī)器學(xué)習(xí)的中文文本主題分類及情感分類研究[D].南京：南京理工大學(xué)，2014.

[2]何佳.基于社會(huì)化標(biāo)注的網(wǎng)頁搜索算法綜述[J].小型微型計(jì)算機(jī)系統(tǒng)，2014（06）.endprint

P1={8，73}

P2={1，13}

P3={3，15，45，80}

V={（8，1，3）；（8，1，15）；（8，1，45）；（8，1，80）；（ 8，13，3）；（8，13，15）；

（8，13，45）；（8，13，80）；（73，1，3）；（73，1，15）；（73，1，45）；（73，1，80）；

（73，13，3）；（73，13，15）；（73，13，45）；（73，13，80）；}

DA={9，21，51，86，15，7，37，73，74，86，116，151，70，62，92，127}

文檔 B：“桃花峪黃河特大橋工程北起鄭焦晉高速公路，南接鄭州西南繞城高速公路，途經(jīng)焦作武陟縣、鄭州滎陽市，全長(zhǎng)28.64公里。其中，黃河特大橋長(zhǎng)7.69公里，北連接線長(zhǎng)8.92公里，南連接線長(zhǎng)12.02公里。主橋位于鄭州黃河風(fēng)景區(qū)西側(cè)桃花峪村附近，北望嘉應(yīng)觀、跨御壩，南臨漢霸二王城，跨黃河中下游分界線桃花峪，俯瞰黃河游覽區(qū)。大橋建成后將為沿黃風(fēng)景名勝旅游發(fā)展提供便利，成為桃花峪綜合旅游的基礎(chǔ)性工程和新的景觀線”。

P1={23，42，89}

P2={4，57，91，124，138}

P3={140}

文檔C：“本網(wǎng)獨(dú)家現(xiàn)場(chǎng)連線人民網(wǎng)河南視窗記者辛靜表示，北京時(shí)間15時(shí)48分，鄭州發(fā)生了日偏食現(xiàn)象，通過觀測(cè)眼鏡可以清晰看到太陽被吞噬掉一個(gè)小邊。記者所在的鄭州黃河游覽區(qū)觀測(cè)點(diǎn)聚集了上百名群眾，大家都得到了相關(guān)機(jī)構(gòu)免費(fèi)派發(fā)的專業(yè)觀測(cè)眼鏡，并且很專注的在欣賞著日偏食景觀，群眾們的心情都十分激動(dòng)”。

P1={32，71}

P2={73}

P3={75}

文檔D：“位于鄭州市北郊的黃河游覽區(qū)是20世紀(jì)70年代才在黃河之濱在荒山上開始建設(shè)的著名風(fēng)景游覽區(qū)，到20世紀(jì)80年代中期，它已有了相當(dāng)?shù)囊?guī)模，成為鄭州市最重要的游覽區(qū)?！?/p>

P1={3}

P2={9}

P3={11，40，73}

在上面的例子中分別得到了文檔A、B、C、D中模糊集合S中出現(xiàn)元素的位置集合和語義位置向量集合V的值。由公式計(jì)算得到向量分量差分集合：

D1={9，21，51，86，15，7，37，73，74，86，116，151，70，62，92，127}

D2=（155，115，117，107，117，174，98，98，98，98，221，115，51，51）

D3={43，4}

D4={8，37，70}

置信區(qū)間為[1，4]。

分析D4，D4中37，70在D1中出現(xiàn)，8與D1中的7、9差1，在置信區(qū)間內(nèi)，可以去重，而D4中任何元素與D2中元素差都不在置信區(qū)間內(nèi)，可以認(rèn)為不同類；D4維數(shù)與D3維數(shù)不同可以認(rèn)為不同類，也可看出元素差不在置信區(qū)間內(nèi)，認(rèn)為不同類。

依次類推，D1，D2，D3，屬于不同類。

5 結(jié)語

提出的一種基于主題詞語義與距離的網(wǎng)頁去重算法，通過對(duì)用戶輸入的關(guān)鍵詞進(jìn)行語義標(biāo)注后分詞檢索，計(jì)算分詞子集在網(wǎng)頁文本中的距離，來判斷網(wǎng)頁與主題的相關(guān)度以及網(wǎng)頁之間的相似度。該方法避開了網(wǎng)頁文本向量空間維數(shù)大的不足，并在一定程度上充分考慮到了網(wǎng)頁的語義信息。

參考文獻(xiàn)：

[1]樊小超.基于機(jī)器學(xué)習(xí)的中文文本主題分類及情感分類研究[D].南京：南京理工大學(xué)，2014.

[2]何佳.基于社會(huì)化標(biāo)注的網(wǎng)頁搜索算法綜述[J].小型微型計(jì)算機(jī)系統(tǒng)，2014（06）.endprint