改進的基于布爾模型的網頁查重算法

摘 要：提出一種基于布爾模型的網頁查重算法，利用布爾模型尋找適當的特征，建立索引以減少網頁文檔之間的比較次數。實驗驗證了這種算法的性能，并取得了較好的效果。

關鍵詞：網絡； 特征； 布爾模型； 相似網頁

中圖法分類號：TP301.6文獻標識碼：A

文章編號：1001—3695(2007)02—0036—04

1 引言

如今，網絡中的數據呈現出爆炸式增長的趨勢，以Web為例，據可靠估計，其增長速度可以達到每六個月翻一番，2004年年底，最大的搜索引擎可以索引到的Web網頁的數目大概為80億—100億，這還只是Web數據的一小部分。

微軟曾作過一個試驗，從網絡中下載了150 000 000個網頁，下載這些網頁耗費了11周的時間。實驗發現這些網頁中有29.2%是相似網頁，而且這些相似網頁中還有22.2%是完全重復的（一字不差）；另外相似網頁十分穩定地存在，一對相似的網頁在10個星期以后極有可能還是相似的網頁。從該實驗可以看出，網絡中存在大量的相似網頁，它們降低了網頁采集器的工作效率，浪費了一些數據挖掘工具的資源，使用戶的工作效率下降，如何能夠盡可能準確地去除這些重復的網頁就是我們所面臨的問題。

2 網頁查重的起源

早在20世紀70年代初，就有學者研究阻止大規模拷貝程序的技術和軟件。但是這只是用于復制檢測，也就是剽竊檢測，其目的在于知識產權的保護，Ottenstein在1976年提出了基于屬性計數法(Attribute Counting)檢測軟件剽竊的方法。但是，單純的屬性計數法拋棄了太多的程序結構信息，導致錯誤率太高。Verco和Wise[8]在1996年指出，對于僅僅使用屬性計數法的檢測算法，增加向量維數并不能降低錯誤率。改進屬性計數法的措施就是加入程序的結構信息，結合結構度量(Structure Metrics)，也稱為控制流(Control-flow)來檢測剽竊。現在檢測程序復制都是用各種方法綜合屬性計數和程序結構度量[11—13]。Parker等人[11]和Clough[12]分別對上述的各種程序復制檢測方法作了詳細的介紹和評述。

在二十年后，出現了自然語言的復制檢測，這一部分就涉及到了網頁查重技術。1993年，Arizona大學的Manber提出了一個Sif[6]工具，用于在大規模文件系統中尋找內容相似的文件。Sif工具提出了近似指紋(Approximate Fingerprints)，就是用基于字符串匹配的方法來度量文件之間的相似性。這個思路被后來很多的文本復制檢測系統所采用。1995年，Stanford大學的Brin和Garcia-Molina等人在“數字圖書館”工程中首次提出了COPS(Copy Protection System，文本復制檢測機制)系統與相應算法[13]，COPS系統框架為以后的自然語言文本復制檢測系統奠定了基礎。Garcia-Molina和Shivakumar等人又提出了SCAM(Stanford Copy Analysis Method)[14]原型改進COPS系統，用于發現知識產權沖突。SCAM借鑒了信息檢索技術中的向量空間模型(Vector Space Model)，使用基于詞頻統計的方法來度量文本相似性。后來Garcia-Molina和Shivakumar等人還在SCAM的基礎上提出了dSCAM模型[15]，將檢測范圍從單個注冊數據庫擴展到分布式數據庫上以及在Web上探測文本復制的方法。同期，貝爾實驗室的Heintze開發了KOALA[16]系統用于剽竊檢測。KOALA系統采用與Sif基本相同的方法，與之類似的方法還有Broder等人提出的Shingling[17]方法。到了2000年，Monostori等人建立了MDR(Match Detect Reveal)原型[18]。MDR采用后綴樹(Suffix Tree)來搜尋字符串之間的最大子串。

3 網頁查重算法相關研究

3.1 DSC和DSC-SS算法

DSC(Digital Syntactic Clustering)[17]及其改進DSC-SS(Super Shingle)[1]兩種算法是由Broder在1997年提出的。DSC將文章按n個字一組分成一個Shingle，整篇文章就由w個Shingles組成。再根據一種過濾策略（如每n個Shingles中取一個），過濾出其中的一些Shingles，由這些被選中的Shingles參加比較。由此可見，過濾策略是影響算法效率的關鍵。DSC所使用的過濾算法是每25個Shingles中保留一個，但是這種方法極大地損害了算法的精確性，很多完全不同的文檔被判斷為相似的文檔；當文檔數目較多時，比較次數極大地損害了該算法的效率。它的改進DSC-SS則是使用Super Shingles，即將幾個Shingles合在一起形成一個Super Shingle，這樣與其比較多個Shingles，還不如比較一個Super Shingle，減少了比較的次數。但是這種算法對于較為短小的文檔而言卻是個災難，在處理短小文檔時正確率將大幅下降。

3.2 I-Match算法

I-Match[1]是伊利若伊理工在2002年提出的一種方法。該方法首先還是將文檔分成一個個Shingles，然后根據IDf（逆文檔頻率）的值決定哪些Shingle參與比較，使用tx=log N/n，其中N是集合中文檔的總數目，n是這些文檔中出現了Shingle x的文檔的數目。這樣越是出現次數多的Shingle，就越不容易出現在參加比較的Shingle中。這種方法和信息檢索中的分類方法有些相似。它的缺點就是IDF值受到語料集合的限制，是非常不穩定的。

3.3 基于標點符號的特征串算法

這種方法類似于一個檢索系統，只是檢索系統所要查詢的是出現了關鍵詞（被查詢的詞）的所有網頁，而這個系統需要返回的是所有與被查詢網頁相同的網頁集合。所以這就需要提取出網頁的特征，以便進行索引。首先除去網頁中可能產生干擾信息的廣告、導航信息等，只從正文部分提取特征，以句號為標記，在每個句號的前后各取五個字[7]，這樣就構成了網頁的特征；再將這些特征進行比較，這樣就可以高效找到重復網頁。由于在讀入網頁時就可以計算出特征碼，所以除了比較之外，整個過程是線性的。

還有一種提取特征碼的方法就是每隔一個標點只取一個字[2]，這種提取特征的方法與上面的方法差不多。

這些特征串在進行比較時采取尋找最大公共子串的方法，然后判斷公共子串的長度占總長度的多少來決定是否判斷為相似的網頁。

3.4 TF-IDF在網頁查重中的應用

TF-IDF算法被廣泛應用于自然語言處理的分類聚類算法中[5]。TF就是特征c在文檔中的出現次數，IDF則是該特征的逆文檔頻率，將它應用于查重，其正確率以及召回率都較高，但是它的效率不理想，也比較難以確定特征的個數，這是它的缺點。

3.5 eRulemaking算法

eRulemaking[19]算法是CMU在2005年提出的，它首先從文檔集合中按照長度將數據集合分成一個個小的數據集合，然后找出每個小的數據集合中重復次數最多的文檔（完全重復）作為該數據集合中的種子，該集合中其他的文檔則優先與種子文檔進行比較。

在尋找種子文檔時，使用的是基于特征串的查重算法，從文檔中固定位置取出特征，計算一個指紋值；余下的文檔與種子文檔比較時采用VSM的方法，特征選擇則是依靠特征的IDF值。

但是IDF值是依賴于語料集合的，對于不同的語料集合，其中相同的文檔抽取出的特征也有可能是不同的，IDF值的不穩定是eRulemaking的不足。

4 基于布爾模型的網頁查重算法

4.1 關于重復的定義

一直以來，對于重復的定義都非常模糊，沒有一個清晰的定義。一字不差可以理解為重復，字面上意義相近也可以理解為重復。對于重復各人都有自己的定義。

Conrad對于重復的定義是：如果兩篇文章之間有超過80%的用詞相同，而且長度相差不超過正負20%，則這兩篇文章就是重復的。另外他認為現在對于網頁查重的研究忽視了對正文部分結構差異的研究，他還試圖將重復的網頁按照正文部分的結構分成Excerpt，Elaboration，Insertion，Focus和Revision五類。Excerpt表示一對相似的網頁正文部分第一段是完全一樣的，而Elaboration則意味著正文的中間若干段是相似的。

Pugh（Work for Google）對于重復的定義就要簡單得多：如果兩篇文章之間有超過r個特征相同，則它們就是相似的。

由于Conrad的定義需要明確找出兩篇重復的網頁中哪一篇是拷貝，所以在不考慮網頁其他特征（如創建時間、站內鏈接關系等）的情況下，我們很難判斷重復網頁中哪一篇是拷貝，因此在利用布爾模型的查重算法中，對于重復的定義就是使用Pugh對重復的定義。

在第3節中所介紹的eRulemaking算法中就使用了Pugh關于重復的定義。

4.2 算法描述

該算法是利用布爾模型進行查重，將每篇文章表示為一個二進制數，若是符合比較條件的兩篇文章，則將兩個二進制數異或，結果中為1的特征則是兩篇文章不同的特征，計算出兩篇文章中的不同特征個數后，再判斷是否需要它們比較。本文提出了相異度的概念，相似度=1-相異度。使用這種算法可以忽略大量常用停用詞的影響，如in，and，the等，這樣讀取文檔時就不需要特別過濾常用詞，節約了處理文檔和提取特征的時間。

4.2.1 優化策略

語料集合較大時，文檔之間兩兩比較的次數就相當巨大，這是所有網頁查重算法的瓶頸。在使用布爾模型的網頁查重算法中，兩篇文檔之間是否需要比較取決于它們的特征個數而不是文檔長度，當特征的總個數差別在閾值d之內的時候，就異或其二進制碼；否則直接判定它們不同。

在得到二進制碼異或的結果之后，如何比較結果將在第4.2.3節中詳細描述。另外一點就是在讀取文檔的過程中慢慢建立一個索引。該索引的數據結構如表1所示。

其中id代表特征的唯一表示，Doic表示出現了該特征的文檔的唯一標識符。當兩篇文檔相互比較而結果為相異時，就將它們分別插入它們之間不同的特征鏈表中。當再有新的文檔需要比較時，根據該文檔中出現的特征，選擇應該與它相比的集合，以減少比較次數。

4.2.2 矩陣的稀疏表示

特征的個數有九萬多個，如果用普通的線性存儲方式十分浪費空間，所以采取一般的二元組表示法：

id二進制值

id為該特征在詞表中唯一的表示標志，二進制值為0表示文檔中沒有該特征，為1表示該特征出現過。在建立文檔的詞表過程中，只有二進制值為1的特征；二進制值為0的特征只出現在比較的過程中。

4.2.3 相異度的計算

當兩篇文檔需要比較時，最好的情況就是所有的特征均不同，結果為0，此時的相異度就為1。當有1/5以上的特征不同時，則判定兩篇文檔為非相似文檔；如有1/5以下的特征不同，則需要計算這些不同特征總的頻度（TF）。表2為相異度的計算實例。

T表示文檔中出現的特征，D表示特征t是否在文檔Doc中出現過（0表示沒有出現，1表示出現了，這就是布爾模型），TF表示特征t在文檔中的出現頻率，Result表示兩篇文檔之間D的異或結果：Result=D1 D2。

對于兩篇文檔i和j，假設它們符合比較的條件（第4.2.1節中所述的條件），則它們的相異度計算公式為

式中tfw，i表示特征w在文檔i中的頻率，在計算分子時，要去掉在兩篇文檔中頻率均較高的T4。在表2中，按式（1）計算出F1，2=0.714，則文檔1和文檔2的相似度為S12=1-F12=0.286，結果是文檔1和文檔2不同。

4.2.4 實驗結果

實驗使用的語料為WT10G（隨機取了其中的2.3G），硬件平臺為P4 1.4GHz，4GB內存。

采取F值作為算法比較的依據：F=2×p×r/(p+r)，其中p為正確率，r為召回率。

對比算法為TF-IDF（特征的維數為20）和基于標點符號的特征串算法。實驗結果如表3所示。各算法的綜合性能比較如圖1所示。

5 實驗分析

由表3可以看到，Bool-Model與TF-IDF的F值相差不太大，效果稍微好一點，但是Bool-Model的速度幾乎比TF-IDF快了1Mbps以上，效率比TF-IDF高一些。這兩種算法在掃描全文、提取特征和計算詞頻這部分是相同的，但是TF-IDF在文檔兩兩比較時只是在判斷全文長度時過濾了一次，而Bool-Model利用兩篇文檔之間不同的特征個數再過濾了一次，所以其文檔兩兩之間的比較次數比TF-IDF少了很多，速度加快了一些。

基于標點符號的特征串算法只需要定位文章中標點符號的位置，無需掃描全文，但是它的代價是比較次數較多，隨著語料集合的增加，比較的次數慢慢增多，速度也會逐漸下降，比較次數與語料大小成線性關系，這是該算法的主要瓶頸。它的效果比Bool-Model和TF-IDF算法要差一些。

TF-IDF的正確率比Bool-Model稍高，如果將特征的維數取得更多，TF-IDF的正確率可以達到100%，但是效率會下降。而Bool-Model就不存在這樣的問題，如果需要提高正確率，只需要控制文檔的二進制碼異或后結果中為1的特征個數即可。閾值改變了，但是文檔之間的比較次數不會增加，所以效率不會下降太多。

基于標點符號的特征串算法只限于找到100%重復的文檔（一字不差），所以有大量的重復文檔它無法確定，其正確率為100%。

Bool-Model的召回率比TF-IDF稍高一些，由于Bool-Model判定重復的依據沒有TF-IDF那么強勢，所以它分辨UYT 出來的重復文檔肯定會比TF-IDF要多。而且Pugh對于重復的定義原本就有缺陷：即使兩篇文檔有超過r個特征相同，在r不是文檔特征總數的情況下，這兩篇文檔就不可能100%相似，所以使用Bool-Model必然會出現兩篇文檔被錯誤判斷成重復的情況。

既然基于標點符號的特征串算法只能找到100%重復的文檔，顯然有大量稍作修改的重復文檔它是無法確定的，這也是其召回率較低的原因。

微軟的實驗可以驗證網絡中的數據，雖然增長速度較快，但是不同的網頁還是占了大部分，有70%以上的網頁是不同的。如果能使用某種機制快速找出那些不同的網頁，也就不需要兩兩計算文檔之間的相似度了。

6 結論和展望

本文提出了一種基于布爾模型的網頁查重算法，利用布爾模型，減少了集合中文檔之間比較的次數，得到了一個較為滿意的結果。與TF-IDF算法以及基于標點符號的算法相比，其性能要優越得多。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。