基于主題詞語義分詞與距離的去重算法
2014-09-02 02:42:55陳亞峰郭一帆王崢
中國科技縱橫 2014年15期
陳亞峰++郭一帆++王崢
【摘 要】 對主題網頁去重技術進行了綜述，結合已有算法的缺點，提出了一種基于主題詞語義與距離的網頁去重算法。該方法通過對用戶輸入的關鍵詞進行語義標注后分詞檢索，計算分詞子集在網頁文本中的距離，來判斷網頁與主題的相關度以及網頁之間的相似度。同時避開了網頁文本向量空間維數大的不足，在一定程度上考慮到了網頁的語義信息。
【關鍵詞】 網頁去重 語義分詞與距離 去重
目前大多數搜索引擎采用基于關鍵詞的方法返回用戶所需信息，這些信息的冗余度通常很高，很多不相關的信息沒有進行有效的組織。因此人們迫切地希望擁有一種方法，能夠自動的將與特定主題相關的信息分類匯總后，供用戶查閱。主題搜索引擎的出現使得用戶能夠對特定主題相關信息的進行獲取，然而在信息采集過程中如何對搜索回來的頁面進行分類，在下一次信息采集的過程中讓爬蟲主動發現主題相關頁面，并去除相關頁面中的重復或近似重復的頁面成為搜索引擎的研究熱點之一。
1 網頁去重技術綜述
搜索引擎的工作原理主要分為三個部分：網頁抓取，網頁處理，提供檢索服務。網頁去重是搜索引擎預處理技術的關鍵部分，主要是由于web上存在大量的重復信息，有統計信息表明，網頁的重復率平均為4，即用戶通過一個URL在互聯網上看到一篇相似網頁的同時，平均還有三個URL不同的網頁給出的內容相同或近似相同。因此為了提高搜索引擎的工作效率，網頁去重在整個搜索引擎的工作中是必不可少的。
國外對于網頁去重的研究最初主要是針對大型文件系統的近似鏡像文檔檢測算法上的研究，后來這些算法又被拓展應用到數字化圖書館項目以及搜索引擎系統中。美國Arizona大學的研究人員對于大型文件系統中的相似文件采用了計算文檔的重疊程度的方法來進行實現。國內，網頁去重重點還是對網頁去重的算法進行研究。大連理工大學韓冰主要研究了大規模的網頁文本去重和科技論文抄襲檢測。江蘇大學呂霞提出了一種基于關鍵詞和特征碼的網頁去重K-CC算法，在分析國內外目前比較通用的幾種去重技術的基礎上，提出了一種基于關鍵詞和特征碼的網頁去重K-CC算法。
2 基于主題詞語義分詞與距離的網頁去重算法的背景
傳統的特征碼實現的精確匹配完全可以與先進的檢索系統聯系起來，其去重效率比較高，是一種去重的好方法。但是該方法的缺點是：
（1）特征碼所實現的是精確匹配，并不能有效的檢測出轉載所造成的近似的重復網頁；（2）在沒有利用網頁文本結構信息的前提下，極有可能會發生長度不同甚至差別懸殊的文本被視為相同網頁的情況；（3）作為可以產生特征碼的標志的句號有時也并不會在網頁文本中出現，也有可能只出現在文章的末尾，或者出現在版權信息和超鏈接中，而所有這些都會導致特征碼產生重大錯誤。
由于目前大多數搜索引擎是通過關鍵詞匹配來完成用戶的檢索請求的，考慮到正文文本語義的復雜性我們對關鍵詞的語義進行標注，作為網頁檢索的主題詞，并且利用不同關鍵詞組合的語義及其之間的距離差因素作為評判標準。故提出了一種基于主題詞語義分詞與距離的網頁去重方法。
3 基于主題詞語義分詞與距離的網頁去重算法的背景
把主題詞（Ks）按詞組形式分成若干個詞組的模糊集合S，S中詞組的組合必須具有一定語義。然后在給定文本中記錄每個詞組wi在文本中的位置pi，j，pi，j組成Pi，然后比較所有Pi分量組成的向量的距離差，若距離差L不小于某個值Kd（模糊評判標準閥值），則與主題相關，若小于Kd，則與主題無關。在不大于Kd中，若L在某個區間[a，b]（此區間是認定為重復置信區間），若在此區間，則認定為重復，否則認定為不同類。具體模型和方法如下：
（1）設主題詞為Ks
（2）Ks分拆的模糊集合S為：
S={w1，w2，…，wm}
（3）wi在文本中出現位置的向量：Pi=（pi，1，pi，2，…，pi，k），1≤i≤m，ki∈N
若：wi在文本中沒有出現，則Pi=
（4）語義位置向量V={vi︱vj=（pi，j1，p2，j2，…，pm，jm），1≤jj≤ki}
注：若Pi=，則pi，ji不記入向量中。
（5）計算V中每個向量分量差分集合D={di︱dj=△vj=（pi，j-pi-1，ji-1）}
（6）根據D中的值來判斷主題是否相關，包括不相關、相關（包括重復（強相關）或不同類（弱相關））。
4 相關性判別方法
判別指標用下式表示：
r=∩pi
若r=則不相關，否則相關。也可以用向量空間V的維數r=Dim（V））來判別，若r 重復性判別方法：在相關的情況下，判別主題內容是否接近或相同。 首先記： 該式表明模糊集S中前m-1個詞的長度總合。 （1）若兩文本（S1，S2）內容一樣，則兩個D1=D2應相同。（2）若一個文本S1包含另一文本S2，則D1D2。 注：這里的包含關系不是di∈D2，則d i∈D1，而是d i∈D2，要么di∈D1，要么di與D1中的某個dj相差的值小于主觀認定的某個值Kd。把置信區間[a，b]置為[1，L]，則Kd∈[1， L]可以認為主題的語義相同，可以去重，否則認為不同即不同類。一般取L=Kd，否則，視查詢文本復雜度主觀設定。 通過下面例子對算法進行具體的說明：用戶輸入關鍵詞“鄭州游覽區”，得到如下四段網頁文本，用模糊搜索集合S{}表示為：S{鄭州，黃河，游覽區}。對應的標記集合中的各元素為：鄭州—>w1，黃河—>w2，游覽區—>w3。 文檔A：“黃河游覽區位于鄭州市北郊的黃河游覽區是20世紀70年代才在黃河之濱在荒山上開始建設的著名風景游覽區，到20世紀80年代中期，它已有了相當的規模，不僅成為鄭州市最重要的游覽區，而且成為馳名中外的華夏歷史文化紀念地。”例子中：
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：“桃花峪黃河特大橋工程北起鄭焦晉高速公路，南接鄭州西南繞城高速公路，途經焦作武陟縣、鄭州滎陽市，全長28.64公里。其中，黃河特大橋長7.69公里，北連接線長8.92公里，南連接線長12.02公里。主橋位于鄭州黃河風景區西側桃花峪村附近，北望嘉應觀、跨御壩，南臨漢霸二王城，跨黃河中下游分界線桃花峪，俯瞰黃河游覽區。大橋建成后將為沿黃風景名勝旅游發展提供便利，成為桃花峪綜合旅游的基礎性工程和新的景觀線”。
P1={23，42，89}
P2={4，57，91，124，138}
P3={140}
文檔C：“本網獨家現場連線人民網河南視窗記者辛靜表示，北京時間15時48分，鄭州發生了日偏食現象，通過觀測眼鏡可以清晰看到太陽被吞噬掉一個小邊。記者所在的鄭州黃河游覽區觀測點聚集了上百名群眾，大家都得到了相關機構免費派發的專業觀測眼鏡，并且很專注的在欣賞著日偏食景觀，群眾們的心情都十分激動”。
P1={32，71}
P2={73}
P3={75}
文檔D：“位于鄭州市北郊的黃河游覽區是20世紀70年代才在黃河之濱在荒山上開始建設的著名風景游覽區，到20世紀80年代中期，它已有了相當的規模，成為鄭州市最重要的游覽區。”
P1={3}
P2={9}
P3={11，40，73}
在上面的例子中分別得到了文檔A、B、C、D中模糊集合S中出現元素的位置集合和語義位置向量集合V的值。由公式計算得到向量分量差分集合：
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}
置信區間為[1，4]。
分析D4，D4中37，70在D1中出現，8與D1中的7、9差1，在置信區間內，可以去重，而D4中任何元素與D2中元素差都不在置信區間內，可以認為不同類；D4維數與D3維數不同可以認為不同類，也可看出元素差不在置信區間內，認為不同類。
依次類推，D1，D2，D3，屬于不同類。
5 結語
提出的一種基于主題詞語義與距離的網頁去重算法，通過對用戶輸入的關鍵詞進行語義標注后分詞檢索，計算分詞子集在網頁文本中的距離，來判斷網頁與主題的相關度以及網頁之間的相似度。該方法避開了網頁文本向量空間維數大的不足，并在一定程度上充分考慮到了網頁的語義信息。
參考文獻：
[1]樊小超.基于機器學習的中文文本主題分類及情感分類研究[D].南京：南京理工大學，2014.
[2]何佳.基于社會化標注的網頁搜索算法綜述[J].小型微型計算機系統，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：“桃花峪黃河特大橋工程北起鄭焦晉高速公路，南接鄭州西南繞城高速公路，途經焦作武陟縣、鄭州滎陽市，全長28.64公里。其中，黃河特大橋長7.69公里，北連接線長8.92公里，南連接線長12.02公里。主橋位于鄭州黃河風景區西側桃花峪村附近，北望嘉應觀、跨御壩，南臨漢霸二王城，跨黃河中下游分界線桃花峪，俯瞰黃河游覽區。大橋建成后將為沿黃風景名勝旅游發展提供便利，成為桃花峪綜合旅游的基礎性工程和新的景觀線”。
P1={23，42，89}
P2={4，57，91，124，138}
P3={140}
文檔C：“本網獨家現場連線人民網河南視窗記者辛靜表示，北京時間15時48分，鄭州發生了日偏食現象，通過觀測眼鏡可以清晰看到太陽被吞噬掉一個小邊。記者所在的鄭州黃河游覽區觀測點聚集了上百名群眾，大家都得到了相關機構免費派發的專業觀測眼鏡，并且很專注的在欣賞著日偏食景觀，群眾們的心情都十分激動”。
P1={32，71}
P2={73}
P3={75}
文檔D：“位于鄭州市北郊的黃河游覽區是20世紀70年代才在黃河之濱在荒山上開始建設的著名風景游覽區，到20世紀80年代中期，它已有了相當的規模，成為鄭州市最重要的游覽區。”
P1={3}
P2={9}
P3={11，40，73}
在上面的例子中分別得到了文檔A、B、C、D中模糊集合S中出現元素的位置集合和語義位置向量集合V的值。由公式計算得到向量分量差分集合：
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}
置信區間為[1，4]。
分析D4，D4中37，70在D1中出現，8與D1中的7、9差1，在置信區間內，可以去重，而D4中任何元素與D2中元素差都不在置信區間內，可以認為不同類；D4維數與D3維數不同可以認為不同類，也可看出元素差不在置信區間內，認為不同類。
依次類推，D1，D2，D3，屬于不同類。
5 結語
提出的一種基于主題詞語義與距離的網頁去重算法，通過對用戶輸入的關鍵詞進行語義標注后分詞檢索，計算分詞子集在網頁文本中的距離，來判斷網頁與主題的相關度以及網頁之間的相似度。該方法避開了網頁文本向量空間維數大的不足，并在一定程度上充分考慮到了網頁的語義信息。
參考文獻：
[1]樊小超.基于機器學習的中文文本主題分類及情感分類研究[D].南京：南京理工大學，2014.
[2]何佳.基于社會化標注的網頁搜索算法綜述[J].小型微型計算機系統，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：“桃花峪黃河特大橋工程北起鄭焦晉高速公路，南接鄭州西南繞城高速公路，途經焦作武陟縣、鄭州滎陽市，全長28.64公里。其中，黃河特大橋長7.69公里，北連接線長8.92公里，南連接線長12.02公里。主橋位于鄭州黃河風景區西側桃花峪村附近，北望嘉應觀、跨御壩，南臨漢霸二王城，跨黃河中下游分界線桃花峪，俯瞰黃河游覽區。大橋建成后將為沿黃風景名勝旅游發展提供便利，成為桃花峪綜合旅游的基礎性工程和新的景觀線”。
P1={23，42，89}
P2={4，57，91，124，138}
P3={140}
文檔C：“本網獨家現場連線人民網河南視窗記者辛靜表示，北京時間15時48分，鄭州發生了日偏食現象，通過觀測眼鏡可以清晰看到太陽被吞噬掉一個小邊。記者所在的鄭州黃河游覽區觀測點聚集了上百名群眾，大家都得到了相關機構免費派發的專業觀測眼鏡，并且很專注的在欣賞著日偏食景觀，群眾們的心情都十分激動”。
P1={32，71}
P2={73}
P3={75}
文檔D：“位于鄭州市北郊的黃河游覽區是20世紀70年代才在黃河之濱在荒山上開始建設的著名風景游覽區，到20世紀80年代中期，它已有了相當的規模，成為鄭州市最重要的游覽區。”
P1={3}
P2={9}
P3={11，40，73}
在上面的例子中分別得到了文檔A、B、C、D中模糊集合S中出現元素的位置集合和語義位置向量集合V的值。由公式計算得到向量分量差分集合：
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}
置信區間為[1，4]。
分析D4，D4中37，70在D1中出現，8與D1中的7、9差1，在置信區間內，可以去重，而D4中任何元素與D2中元素差都不在置信區間內，可以認為不同類；D4維數與D3維數不同可以認為不同類，也可看出元素差不在置信區間內，認為不同類。
依次類推，D1，D2，D3，屬于不同類。
5 結語
提出的一種基于主題詞語義與距離的網頁去重算法，通過對用戶輸入的關鍵詞進行語義標注后分詞檢索，計算分詞子集在網頁文本中的距離，來判斷網頁與主題的相關度以及網頁之間的相似度。該方法避開了網頁文本向量空間維數大的不足，并在一定程度上充分考慮到了網頁的語義信息。
參考文獻：
[1]樊小超.基于機器學習的中文文本主題分類及情感分類研究[D].南京：南京理工大學，2014.
[2]何佳.基于社會化標注的網頁搜索算法綜述[J].小型微型計算機系統，2014（06）.endprint
