基于后綴樹的重復(fù)文檔檢測(cè)

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

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

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2015）005-0070-04

作者簡(jiǎn)介：馮金波（1989-），男，江蘇鹽城人，江蘇大學(xué)計(jì)算機(jī)科學(xué)與通信工程學(xué)院碩士研究生，研究方向?yàn)樾畔z索、數(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），使用多個(gè)URL指向同一個(gè)網(wǎng)頁及鏡像站點(diǎn)（mirror site），由于這些鏡像的存在使得網(wǎng)絡(luò)爬蟲在抓取網(wǎng)頁時(shí)產(chǎn)生了大量的重復(fù)網(wǎng)頁。研究表明，在一個(gè)大型爬蟲系統(tǒng)中，如Baidu、Google和AltaVista，大約有30%的網(wǎng)頁是冗余信息，即這些網(wǎng)頁和另外70%的網(wǎng)頁完全重復(fù)或近似重復(fù)[1]。

1 研究綜述

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

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

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

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

2.1 使用后綴樹匹配特征

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

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

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

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

2.2 特征提取示例

2.3 驗(yàn)證特征

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

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

2.4 Jaccard相似度

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

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)數(shù)據(jù)集

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