基于文檔摘要的藏文網(wǎng)頁消重研究

文/李加才讓　安見才讓

1　引言

藏文網(wǎng)頁消重的研究，目的是在互聯(lián)網(wǎng)上大量的重復(fù)性和相似性的冗余信息中消除相同或相似的藏文網(wǎng)頁，全面提升搜索引擎的質(zhì)量并改善用戶的瀏覽體驗。所以，高精度而快捷地消除重復(fù)網(wǎng)頁無疑是提高搜索引擎質(zhì)量和改善用戶體驗的關(guān)鍵技術(shù)之一。

目前，藏文網(wǎng)頁消重的相關(guān)文獻很少。王海洪和戴玉剛在2009年提出的一種基于編碼統(tǒng)一的藏文網(wǎng)頁消重技術(shù)。主要思想是在藏文編碼不統(tǒng)一情況下，無論采用哪一種消除重復(fù)頁面的方法都是不可能實現(xiàn)的，所以在處理過程中必須首先統(tǒng)一編碼。為了進一步探索藏文網(wǎng)頁消重領(lǐng)域，本文的以Tf*IDF詞頻統(tǒng)計算法提取文本特征項，再根據(jù)特征項計算文檔摘要。對文檔摘要求出其信息指紋，信息指紋轉(zhuǎn)換成固定位數(shù)的二進制數(shù)值并計算其Hamming Distance來求出相似度。最后根據(jù)Hamming Distance來消除重復(fù)網(wǎng)頁和轉(zhuǎn)載網(wǎng)頁。

2　藏文網(wǎng)頁特征提取

2.1　預(yù)處理

在對藏文網(wǎng)頁提取特征項之前，還需要做預(yù)處理工作，具體步驟是用爬蟲軟件從網(wǎng)上下載好網(wǎng)頁后做識別和清除網(wǎng)頁內(nèi)的噪聲內(nèi)容（如廣告、版權(quán)信息等）的凈化處理，并提取網(wǎng)頁正文。之后對提取好的網(wǎng)頁正文內(nèi)容需要做文本分塊處理。對于在原文中沒有實際含義或不是關(guān)鍵詞的停用詞，如藏文中的等等做過濾處理。停用詞在計算Tf*IDF時并不能用作特征項來計算，因此分詞完成后和預(yù)先消除分詞結(jié)果中個的停用詞。對于爬蟲軟件下載的所有網(wǎng)頁都執(zhí)行上述預(yù)處理步驟，這樣便于后續(xù)操作的高效率運行。

2.2　Tf*IDF計算

Tf*IDF（Term Frequency * Inverse Document Frequency）算法是一種用于資訊檢索與資訊探勘的常用加權(quán)技術(shù)。其原理是用統(tǒng)計方法評估一個詞條對于一個文檔的重要程度。Tf*IDF算法作為一個從文檔中提取能代表該文檔的特征的算法，它的任務(wù)就是要將信息量小，“不重要”的詞匯從特征項空間中刪除，從而減少特征項的個數(shù)，降低特征項空間的維數(shù)。

Tf*IDF算法中的 Tf（Term Frequency）表示某個詞條在某個藏文網(wǎng)頁文檔中出現(xiàn)的頻率。

在公式（1）中所求的是某個詞條在藏文網(wǎng)頁文檔中的Tf值，其中分子nij表示詞條i在文檔j中出現(xiàn)的次數(shù)；分母表示在文檔j中出現(xiàn)的所有詞條之和。

IDF（Inverse Document Frequency）表示如果包含某個詞的藏文網(wǎng)頁文檔越少，則這個詞的區(qū)分度就越大，IDF就越大。

在公式（2）中所求的是藏文網(wǎng)頁文檔總數(shù)與包含詞條i的藏文網(wǎng)頁文檔數(shù)的比值即IDF值，其中分子|D|表示語料庫中藏文網(wǎng)頁文檔總數(shù)，分母|{j:ti∈dj}|表示包含詞條ti的藏文網(wǎng)頁文檔數(shù)j的值。如果該詞語不在語料庫中，就會導(dǎo)致被除數(shù)為零，因此一般情況下使用 |{j:ti∈dj}|+1。

對于如何獲取一個藏文網(wǎng)頁文檔的特征項，我們可以計算公式（3）得到Tf*IDF，Tf*IDF越大，則說明這個詞條對這個藏文網(wǎng)頁文檔的區(qū)分度就越高，取Tf*IDF值較大的幾個詞條，就可以當做這個藏文網(wǎng)頁文檔的特征項集合。

3　藏文網(wǎng)頁文檔摘要自動提取

藏文自動摘要是利用計算機自動編寫文摘的應(yīng)用技術(shù)，能夠通過藏文網(wǎng)頁自動文摘技術(shù)將網(wǎng)頁上較長的文本數(shù)據(jù)壓縮成一段幾百個字左右、能大體代表文本原意的摘要。

IBM公司的H.P. Luhn提出的提出了一種基于詞頻統(tǒng)計的自動摘要算法，其原理是利用算法找出那些包含信息最多的句子，而句子的信息量可用“關(guān)鍵詞”來衡量。Luhn提出用"簇"（cluster）表示關(guān)鍵詞的聚集，所謂"簇"就是包含多個關(guān)鍵詞的句子片段。

圖1：“簇”圖

如圖1所示，被框起來的部分即為一個“簇”?！癬_”表示普通詞條，“*”表示關(guān)鍵詞。當在一條句子中包含了多個關(guān)鍵詞，那么這個包含多個關(guān)鍵詞的句子片段稱之為“簇”。可設(shè)一個閾值，Luhn建議的閾值是4或5。也就是說，如果兩個關(guān)鍵詞之間有5個以上的其他詞，就可以把這兩個關(guān)鍵詞分在兩個簇。在本文中特用事先計算好的Tf*IDF特征項來代替關(guān)鍵詞，這樣就變成了包含特征項的句塊為“簇”。

對于每個“簇”，可計算其權(quán)值。如公式（4）所示：

其中wij表示包含特征項i的“簇”j的長度，分子中tij表示在“簇”j中包含特征項i的數(shù)量，tij的二次冪即分子。分母jlenght表示“簇”j的長度。

比如：如圖1所示，“簇”1共有7個詞條，其中4個為特征項。

最后，找出包含權(quán)值最高的“簇”的句子（比如5句），把他們合在一起，就構(gòu)成了一個文檔的自動摘要。

4　摘要信息指紋計算

產(chǎn)生信息指紋的關(guān)鍵算法是偽隨機數(shù)產(chǎn)生器算法（PRING)。最早的PRING算法是由計算機之父馮諾伊曼提出來的。他的辦法非常簡單，就是將一個數(shù)的平方掐頭去尾，取中間的幾位數(shù)。比如一個四位的二進制數(shù) 1001（相當于十進制的9），其平方為01010001(十進制的81）掐頭去尾剩下中間的四位0100。當然這種方法產(chǎn)生的數(shù)字并不很隨機，也就是說兩個不同信息很有可能有同一指紋?，F(xiàn)在常用的 MersenneTwister 算法要好得多。

本文用Visual Studio C#語言來編程，對藏文網(wǎng)頁摘要計算的信息指紋是傳統(tǒng)Hash計算，同過string類庫的GetHash()方法得到一串偽隨機數(shù)，并將該偽隨機數(shù)轉(zhuǎn)換為固定位數(shù)的二進制數(shù)值作為其新的信息指紋。對于二進制信息指紋則可以通過Hamming Distance來計算藏文網(wǎng)頁文檔相似度，最后可通過相似度計算來判斷哪些網(wǎng)頁是近似重復(fù)網(wǎng)頁。

5　相似度計算

5.1　Hamming Distance計算

Hamming Distance即海明距離，兩個碼字的對應(yīng)比特取值不同的比特數(shù)稱為這兩個碼字的海明距離。計算海明距離可對要比較的兩串信息指紋進行異或（xor）運算，并計算出異或運算結(jié)果中1的個數(shù)。例如110和011這兩個位串，對它們進行異或運算，其結(jié)果是：

異或結(jié)果中含有兩個1，因此110和011之間的漢明距離就等于2。

計算兩篇藏文網(wǎng)頁信息指紋的海明距離也是類似，對另個藏文網(wǎng)頁固定位數(shù)的二進制信息指紋做異或運算，并統(tǒng)計出1的個數(shù)即可求得兩篇藏文網(wǎng)頁的海明距離。

5.2　藏文網(wǎng)頁相似度計算

在求得兩篇藏文網(wǎng)頁的海明距離后，至于相似度的計算可通過公式（5）完成。

最后關(guān)于消重計算，可根據(jù)海明距離設(shè)置一個閾值。例如，當兩篇網(wǎng)頁的海明距離小于3時，可判斷這兩篇網(wǎng)頁是轉(zhuǎn)載的或重復(fù)的，即可處理消重工作，在數(shù)據(jù)庫中只保留一篇網(wǎng)頁。

6　結(jié)語

本文根據(jù)藏文網(wǎng)頁的特征結(jié)構(gòu)提取文檔摘要，對文檔摘要計算其信息指紋并將其轉(zhuǎn)換成固定位數(shù)的二進制數(shù)值，對二進制數(shù)值計算海明距離。根據(jù)海明距離可計算相似度，又可設(shè)置閾值判斷該藏文網(wǎng)頁是否重復(fù)或轉(zhuǎn)載網(wǎng)頁。經(jīng)測試，本文研究的消重算法雖然準確率差強人意，還需進一步探索研究。但是算法整體簡捷快速，時間復(fù)雜度較低，查全率較高。適用于在處理復(fù)雜的搜索引擎工作時粗略地計算網(wǎng)頁消重工作，對搜索引擎的整體運算而言在不拖延計算時間的同時卻又能顯著的提高其性能。