基于文檔摘要的藏文網頁消重研究

文/李加才讓　安見才讓

1　引言

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

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

2　藏文網頁特征提取

2.1　預處理

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

2.2　Tf*IDF計算

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

Tf*IDF算法中的 Tf（Term Frequency）表示某個詞條在某個藏文網頁文檔中出現的頻率。

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

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

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

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

3　藏文網頁文檔摘要自動提取

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

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

圖1：“簇”圖

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

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

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

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

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

4　摘要信息指紋計算

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

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

5　相似度計算

5.1　Hamming Distance計算

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

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

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

5.2　藏文網頁相似度計算

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

最后關于消重計算，可根據海明距離設置一個閾值。例如，當兩篇網頁的海明距離小于3時，可判斷這兩篇網頁是轉載的或重復的，即可處理消重工作，在數據庫中只保留一篇網頁。

6　結語

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