摘 要：傳統(tǒng)的重復(fù)文檔檢測方法是以單詞或n-grams為單位提取特征，造成特征集合過于龐大。針對該缺點，提出以句子塊作為文檔特征的提取方法，將每個文檔表示成句子長度序列，使用后綴樹快速匹配公共子串。實驗中，使用兩個標準文檔集與3種經(jīng)典方法在有效性和效率方面進行比較，結(jié)果表明新算法有較高的準確率和效率。

關(guān)鍵詞：重復(fù)文檔；后綴樹；句子塊

中圖分類號：TP312

文獻標識碼：A 文章編號：1672-7800（2015）005-0070-04

作者簡介：馮金波（1989-），男，江蘇鹽城人，江蘇大學計算機科學與通信工程學院碩士研究生，研究方向為信息檢索、數(shù)據(jù)挖掘。

0 引言

重復(fù)和近似重復(fù)（near-duplicate）文檔在人們?nèi)粘Ｉ钪薪?jīng)常出現(xiàn)。在互聯(lián)網(wǎng)中，存在著大量相似網(wǎng)頁。除常見的網(wǎng)頁轉(zhuǎn)載、抄襲外，部分重復(fù)網(wǎng)頁為少數(shù)網(wǎng)站為了提高網(wǎng)頁檢索排名，作搜索引擎優(yōu)化（SEO），使用多個URL指向同一個網(wǎng)頁及鏡像站點（mirror site），由于這些鏡像的存在使得網(wǎng)絡(luò)爬蟲在抓取網(wǎng)頁時產(chǎn)生了大量的重復(fù)網(wǎng)頁。研究表明，在一個大型爬蟲系統(tǒng)中，如Baidu、Google和AltaVista，大約有30%的網(wǎng)頁是冗余信息，即這些網(wǎng)頁和另外70%的網(wǎng)頁完全重復(fù)或近似重復(fù)[1]。

1 研究綜述

Broder[2]提出將文本中連續(xù)n個term序列作為文本的一個特征，稱之為n-shingle。然后，根據(jù)每個文檔的shingles集合計算相似度，判斷兩個文檔是否重復(fù)。如果文檔d有|d|個term，那么該文檔有|d|-n+1個shingles。所提取的shingles集合過于龐大，此后Shingle算法又增加了過濾模塊，對提取出的shingles集合進行過濾處理。M-Theobald等[3]提出的SpotSigs算法，以停用詞（stop word）作為先行詞，提取其后的k個詞形成一個spot特征碼，作為一個特征。停用詞選擇對SpotSigs算法至關(guān)重要，不同的停用詞列表會影響最終特征集。Wang等[4]提出了一種句子級別的特征提取算法，以連續(xù)的句子長度序列作為一個特征，每個特征用數(shù)值字符串表示。由于該算法沒有使用文本信息，且以連續(xù)的幾個句子為一個特征，在大規(guī)模數(shù)據(jù)集下運行效率較高。

2 基于句子塊的特征提取算法

以單詞或者n-grams為單位提取特征碼時，提取出的特征過多，為優(yōu)化性能，通常需要過濾某些特征，從一定程度上降低了準確率。本文以句子作為一個基本提取單位，將匹配出的兩個文檔間的公共句子塊作為一個特征。

圖1描述了本文算法檢測一對文檔的處理流程。首先，對文檔預(yù)處理，比如提取文檔正文內(nèi)容、分割句子及去除停用詞（stop word），把每個文檔轉(zhuǎn)換成一個字符串，其中每個字符代表一個句子的長度；然后，為匹配出所有的公共句子塊，需要找出兩個字符串的所有公共子串，因此使用后綴樹（suffix tree）處理能夠快速匹配；最后，對所得到的所有子字符串進行驗證。由于本文算法是以句子長度為基本單位，且使用了后綴樹求解公共子串問題，因此將該算法簡稱為SL+ST（Sentence Length+Suffix Tree）。

2.1 使用后綴樹匹配特征

去除每個句子中的停用詞（stop word）后，統(tǒng)計每個句子剩余的單詞個數(shù)，即句子長度。為方便編寫程序，當長度為10～35時用字母a～z替換。對本文實驗所采用的兩個數(shù)據(jù)集進行分析，發(fā)現(xiàn)去除停用詞后長度超過35的句子分別只占了0.27%和0.10%，因此對于長度超過35的句子忽略不計。

采用Kth-in-sentence選擇策略對每個句子存儲開始的兩個詞（term）作為一個過濾特征的判斷條件[5]，最終將一個文檔表示成一個句子長度序列的字符串，其中每個字符表示其對應(yīng)的句子的長度，字符串長度則代表該文檔的句子數(shù)量。

為檢測兩個文檔是否為重復(fù)文檔，需要比較這兩個文檔所對應(yīng)的字符串。文檔查重研究可以轉(zhuǎn)換成求解兩個給定字符串的公共子串問題。

文獻[6]介紹了幾種常用的求解公共子串的算法。對于兩個長度分別為m和n的字符串，動態(tài)規(guī)劃算法時間復(fù)雜度高達O（mn），而后綴樹算法是線性的，為O（m+n），本文采用后綴樹算法來求解公共子串。

2.2 特征提取示例

2.3 驗證特征

如直接將兩個文檔間連續(xù)的具有相同句子長度的一個句子塊作為一個特征，可能會選擇錯誤的句子塊。比如匹配出的句子塊雖然滿足對應(yīng)的句子長度相等這個條件，其實它們并不是相似的句子。因此需要對提取出的特征進行驗證，以過濾掉一些不相似的句子塊。

在預(yù)處理階段，每個句子存儲了開始的兩個單詞（terms），通過比較句子塊中每個句子所對應(yīng)的terms來驗證。如果句子塊中對應(yīng)的句子terms相同，則保留；如果句子塊中間有某個句子未通過驗證，則可以切分該句子塊，切分之后句子塊長度如為1則丟棄。比如一個句子塊長度為5，第三個句子不相似，那么可以切分成兩個句子塊；如果一個句子塊長度為4，第二個和第三個句子不相似，那么丟棄整個句子塊。

2.4 Jaccard相似度

提取文檔對的特征集合后，需要根據(jù)特征集合計算出這對文檔的相似度，本文使用Jaccard相似度，定義如下：

3 實驗

3.1 實驗數(shù)據(jù)集

實驗采用兩個英文文檔集：AP90-S和Twitter。這兩個文檔集都是從標準TREC數(shù)據(jù)集中生成，AP90-S是AP90的一個子集，Twitter是ClueWeb12-CatalogB中的一個子集。首先，從AP90中手動選擇6個文檔；然后將這6個文檔作為查詢語句并使用Terrier檢索系統(tǒng)搜索AP90數(shù)據(jù)集，得到6個檢索結(jié)果；最后從這6個結(jié)果中依次選擇前150個文檔，去除重復(fù)（指文檔ID相同）得到的文檔集合就是AP90-S。直接從ClueWeb12-CatalogB中選擇以twitter命名的文件夾得到的就是Twitter文檔集。AP90-S和Twitter文檔集的詳細信息見表1。