高翔，李兵

1.北京大學(xué)匯豐商學(xué)院，廣東深圳 518055

2.對(duì)外經(jīng)濟(jì)貿(mào)易大學(xué)信息學(xué)院，北京 100029

◎信號(hào)處理◎

中文短文本去重方法研究

高翔1，李兵2

1.北京大學(xué)匯豐商學(xué)院，廣東深圳 518055

2.對(duì)外經(jīng)濟(jì)貿(mào)易大學(xué)信息學(xué)院，北京 100029

針對(duì)中文短文本冗余問題，提出了有效的去重算法框架?？紤]到短文本海量性和簡(jiǎn)短性的特點(diǎn)，以及中文與英文之間的區(qū)別，引入了Bloom Filter、Trie樹以及Sim Hash算法。算法框架的第一階段由Bloom Filter或Trie樹進(jìn)行完全去重，第二階段由Sim Hash算法進(jìn)行相似去重。設(shè)計(jì)了該算法框架的各項(xiàng)參數(shù)，并通過仿真實(shí)驗(yàn)證實(shí)了該算法框架的可行性及合理性。

文本去重；中文短文本；Bloom Filter；Trie樹；SimHash算法

1 引言

近年來，隨著我國(guó)計(jì)算機(jī)科學(xué)技術(shù)的迅猛發(fā)展，微博客、BBS、即時(shí)通訊工具等通過中文短文本形式承載信息的各項(xiàng)傳播技術(shù)日益普及。短文本信息的迅猛增長(zhǎng)，在為信息決策帶來豐富資料來源的同時(shí)，也產(chǎn)生了大量冗余、無效的重復(fù)信息。龐大的重復(fù)信息集，不僅大量占用了系統(tǒng)的存儲(chǔ)空間，同時(shí)也不利于針對(duì)短文本信息進(jìn)行有效的數(shù)據(jù)挖掘，對(duì)于信息決策的準(zhǔn)確性與及時(shí)性都會(huì)造成影響。因而迫切需要有效的中文短文本去重方法應(yīng)用于企業(yè)與研究實(shí)踐。

2 國(guó)內(nèi)外研究進(jìn)展

對(duì)于文本去重技術(shù)，根據(jù)算法原理的不同將其分為兩類[1-3]，一類采用基于字符串的比較方法（基于語法的方法）。1994年，sif系統(tǒng)[4]的提出，使得在大規(guī)模文件系統(tǒng)中尋找內(nèi)容相似的文件成為可能。雖然并未涉及文本去重的相關(guān)技術(shù)，但是其率先提出的“信息近似指紋”思想，已經(jīng)被之后的很多文本去重系統(tǒng)所應(yīng)用（Heintze的KOALA系統(tǒng)[5]與Border等人[6]提出的“Shingling”便一脈相承了sif的思想原理）。1995年，Brin與Garcia-M olina首次提出了文本復(fù)制檢測(cè)系統(tǒng)——COPS[7]，為以后的檢測(cè)系統(tǒng)搭建了基本框架。2000年，采用后綴樹搜尋字符串間最大子串的MDR原型由M onostori等人[8]建立，隨后又針對(duì)存儲(chǔ)部分進(jìn)行了改進(jìn)[9]。而YAP3[10]與MDR類似，也是通過字符串匹配算法直接在文檔中搜尋最大的匹配字符串。2002年，Chow dhury等人采用與sif相同的技術(shù)原理，開發(fā)出了I-M atch系統(tǒng)[11]。I-M atch假設(shè)的前提是不考慮高頻詞與低頻詞對(duì)語義的影響，忽略了語義分析導(dǎo)致I-M atch算法的精度不是很高。針對(duì)其精度不高的問題，文獻(xiàn)[12]提出了可以利用隨機(jī)化的方法來解決。

另一類是基于詞頻統(tǒng)計(jì)的方法（基于語義的方法）。1995年，Shivakumar與Garcia-M olina建立了基于向量空間模型的SCAM[13-14]，隨后又提出了dSCAM[15]。1997年，針對(duì)主流的基于語句比較的檢測(cè)方法，Antonio等人另辟蹊徑，設(shè)計(jì)了CHECK原型[16]。CHECK將文檔分解為樹型結(jié)構(gòu)，再利用向量點(diǎn)積法來比較文檔相似度，有效地解決了檢測(cè)速度慢以及檢測(cè)率低的問題。2003年，Jung-Sheng Yang與Chih-Hung Wu[17]提出用圖結(jié)構(gòu)來存儲(chǔ)測(cè)試文本，并比較相似性的方法。之后的SimHash[18]與Spotsig[19]算法重視了語義的層面，對(duì)特征值進(jìn)行了有效的選取。

由此可見，目前文本去重技術(shù)已有了長(zhǎng)遠(yuǎn)的發(fā)展。但就目前而言，中文文本去重技術(shù)，主要是借鑒已有的英文文本去重方法，應(yīng)用于中文網(wǎng)頁的查重[20]。針對(duì)目前日益增多卻尚未有效利用的中文短文本信息，就目前查閱資料的情況來看，國(guó)內(nèi)在此領(lǐng)域的去重技術(shù)的研究還并不完善。由于短文本具有海量性，簡(jiǎn)短性兩大特征[21]，因而目前適用于網(wǎng)頁去重，文件去重的聚類去重算法或者分段去重算法，因?yàn)闀r(shí)間復(fù)雜度的原因[22-23]不能直接應(yīng)用于中文短文本的去重。

鑒于此，提出了將Bloom Filter或者Tire樹算法，與SimHash算法有效結(jié)合的算法框架，從而可以高效而精準(zhǔn)地完成對(duì)中文短文本的去重處理工作。第三章對(duì)研究模型作出了整體介紹。第四章對(duì)模型中涉及的三種主要算法進(jìn)行了簡(jiǎn)要介紹與設(shè)計(jì)。第五章主要是通過仿真算例對(duì)設(shè)計(jì)模型進(jìn)行實(shí)驗(yàn)研究，以驗(yàn)證模型的有效性與可行性。最后部分則總結(jié)了實(shí)驗(yàn)結(jié)論，指出了文章的創(chuàng)新與不足之處。

3 研究模型

在認(rèn)識(shí)到短文本海量性、簡(jiǎn)短性兩大特征的基礎(chǔ)之上，本文同時(shí)考慮到了中英文之間的差別，以特征碼提取為算法的基礎(chǔ)思想，選取Bloom Filter24]與改進(jìn)后的Trie樹[25]進(jìn)行中文短文本去重的算法設(shè)計(jì)工作，并在時(shí)間復(fù)雜度、準(zhǔn)確率以及內(nèi)存分配方面進(jìn)行了研究。除此之外，基于上述兩種算法的研究?jī)H僅可以去除短文本信息中完全重復(fù)的部分，而無法對(duì)十分相似的文本進(jìn)行甄別并有效地去除，故在數(shù)據(jù)集中仍然存在少部分的相似文本，在一定程度上會(huì)對(duì)信息的統(tǒng)計(jì)產(chǎn)生影響，從而影響決策的有效性。比如在微博客的統(tǒng)計(jì)中，他人對(duì)于一條原創(chuàng)微博客在更改一兩字之后進(jìn)行轉(zhuǎn)發(fā)，統(tǒng)計(jì)時(shí)仍需將其單獨(dú)算作一條原創(chuàng)微博客。在此種情況下，為了對(duì)經(jīng)過完全重復(fù)去重之后的短文本信息再進(jìn)行相似重復(fù)去重，本文又引入了Sim Hash算法。

由此可見，本文整體的研究模型為：（1）提取中文短文本數(shù)據(jù)集，進(jìn)行數(shù)據(jù)預(yù)處理；（2）數(shù)據(jù)集首先經(jīng)過Bloom Filter或者Trie樹進(jìn)行完全重復(fù)去重；（2）繼而通過Sim Hash算法進(jìn)行相似重復(fù)去重；（4）得到去重后結(jié)果集。

圖1 算法框架圖

4 基本算法設(shè)計(jì)

由于在現(xiàn)實(shí)情況下，文本內(nèi)容是人的自然語言，大量文本數(shù)據(jù)會(huì)呈現(xiàn)出半結(jié)構(gòu)化以及非結(jié)構(gòu)化的特征。因而，在文本數(shù)據(jù)中不僅僅存在大量完全重復(fù)的文本，同時(shí)也有一些相似重復(fù)的文本。而在相似重復(fù)文本比較中，相似性的比較往往需要較大的時(shí)間與空間開銷，所以，一般情況下不易直接對(duì)大批量的文本數(shù)據(jù)進(jìn)行重復(fù)的查詢與處理工作。針對(duì)這種特點(diǎn)，為了有效地去除重復(fù)，在短文本處理的第一階段，將Bloom Filter與Trie樹的算法思想引入，主要基于以下兩點(diǎn)。由于出錯(cuò)率的犧牲，Bloom Filter跳出了時(shí)間復(fù)雜度與空間復(fù)雜度不可兼得的情況[26]，因而在保證速度的同時(shí)，空間占用率極低；而對(duì)于Trie樹而言，其本身較之于Hash，有著更快的速度。

4.1 Bloom Filter設(shè)計(jì)

Bloom Filter是由Howard Bloom在1970年提出，是一種基于散列函數(shù)的數(shù)據(jù)查找算法。對(duì)于某一條數(shù)據(jù)元素，可以快速檢測(cè)其是否為集合中的一個(gè)成員。與普通的散列表相比，它的優(yōu)勢(shì)在于，可以大幅度地節(jié)省空間。但是，這種算法存在著一定的錯(cuò)判率，即對(duì)于查找檢測(cè)的請(qǐng)求，其會(huì)返回“數(shù)據(jù)存在（有可能錯(cuò)誤false positive）”以及“數(shù)據(jù)不在集合內(nèi)（必然不存在）”兩種結(jié)果。由此可見，Bloom Filter算法是通過犧牲出錯(cuò)率來換取時(shí)間與空間。在此算法中誤判的概率為：

其中n為數(shù)據(jù)集中元素的個(gè)數(shù)，k為Hash函數(shù)個(gè)數(shù)，m為分配位向量的大小。

對(duì)于Bloom Filter的設(shè)計(jì)而言，關(guān)鍵點(diǎn)在于位向量大小的設(shè)計(jì)以及Hash函數(shù)的選擇。二者直接影響到Bloom Filter去重的出錯(cuò)率。在內(nèi)存中開辟出一塊大小為m的位向量區(qū)域，并選取了穩(wěn)定性能較好的BKDR Hash與AP Hash作為散列函數(shù)。

Bloom Filter算法的具體設(shè)計(jì)如下：

（1）初始化一塊5×104bit的位向量區(qū)域。

（2）對(duì)于待處理的n項(xiàng)短文本數(shù)據(jù)集S={s1，s2，…，sn}中的si(i=1，2，…，n)取BKDR Hash得k1與AP Hash 得k2。

（3）其中取（size為位向量大?。?/p>

（4）查看上述得到的mark1與mark2是否在位向量中已經(jīng)置為1，若其中一個(gè)為1，或者全部為1，則si(i=1，2，…，n)為重復(fù)文本，需要予以刪掉；若全部為0，則置為1。

4.2 Trie樹的設(shè)計(jì)

Trie樹，即字典樹。由于其可以獲得比Hash表更高的查詢效率，故在字符串查找、前綴匹配等中應(yīng)用很廣泛。Trie樹的核心思想是空間換時(shí)間。利用字符串的公共前綴來降低查詢時(shí)間的開銷以達(dá)到提高效率的目的。對(duì)于Trie樹而言，其基本的性質(zhì)有（1）根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)外每一個(gè)節(jié)點(diǎn)都只包含一個(gè)字符；（2）從根節(jié)點(diǎn)到某一節(jié)點(diǎn)，路徑上經(jīng)過的字符連接起來，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串；（3）每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符都不相同。為了更為直觀的表示，假設(shè)存在單詞組，可得其對(duì)應(yīng)字典樹。

圖2 Trie樹（字典樹）示意圖

英文全部由26個(gè)字母構(gòu)成，Trie樹的思想源泉就來源于對(duì)英文字典的查詢。但是，考慮到常用中文有大約2 000多字，據(jù)此建立Trie樹則不切實(shí)際?；诖朔N考慮，筆者對(duì)Trie樹做出了改進(jìn)。對(duì)于中文短文本集合A=(a1，a2，…，an)中的任意一個(gè)中文字符串a(chǎn)i，經(jīng)過散列函數(shù)得到整型變量Val，并取NVal=Val2之后，針對(duì)一組的NVal構(gòu)建數(shù)字Trie樹。

改進(jìn)后的Trie樹具體設(shè)計(jì)如下：

（1）初始化根節(jié)點(diǎn)，構(gòu)建Trie樹。

（2）對(duì)于中文短文本集合A=(a1，a2，…，an)中的任意一個(gè)中文字符串a(chǎn)i，經(jīng)過散列函數(shù)（使用Visual Studio 2010 C#內(nèi)置Hash函數(shù)）得到整型變量ki。

（3）取Nki=k2i，則Nki由m位數(shù)字構(gòu)成(x1，x2，…，xm)。

（4）取其第一個(gè)數(shù)字x1，遍歷Trie根節(jié)點(diǎn)下子節(jié)點(diǎn)，若存在x1，則取x2，遍歷與x1相等的子節(jié)點(diǎn)下的節(jié)點(diǎn)；若不存在，則創(chuàng)建一個(gè)節(jié)點(diǎn)為x1，并將剩余數(shù)字依層次在新建節(jié)點(diǎn)下建立節(jié)點(diǎn)。

4.3 Sim Hash算法設(shè)計(jì)

對(duì)于SimHash而言，其是一種降維的技術(shù)，輸入的一個(gè)向量通過程序運(yùn)算之后輸出一個(gè)m位的簽名值。在文本數(shù)據(jù)處理中，其輸入的向量為文本的特征向量集合（每個(gè)特征值配以一定的權(quán)重值）。而對(duì)于特征值的有效選取，直接決定了去重算法精度，在這一問題上I-M atch算法，Shingling算法以及SpotSig算法提供了基于語義以及基于語法的方法?？紤]到中文短文本的簡(jiǎn)短性，借鑒了Shingling的特征值選取方法的思想，即選擇對(duì)連續(xù)的若干個(gè)單詞的串（即下文所提到的Shingle）進(jìn)行操作。具體而言，若選取Shingle的長(zhǎng)度為W，那么就會(huì)生成N-W+1個(gè)Shingle，然后通過Hash函數(shù)，可以得到N-W+1個(gè)Hash值。據(jù)此輸入SimHash進(jìn)行運(yùn)算：

（1）將一個(gè)m維的向量V初始化為0。

（2）將取到文檔的每個(gè)特征碼運(yùn)用Hash算法哈希為m位Hash值。應(yīng)用這些m位的Hash值，可以將向量V的f個(gè)元素增加或者減少其所對(duì)應(yīng)的權(quán)重值的大小。比如，如果f位的Hash值第i位的值為1，則V的第i個(gè)元素加上該特征的權(quán)重，否則V的第i個(gè)元素需要減去該特征值的權(quán)重。

（3）當(dāng)所有的特征碼處理完畢之后，向量V中有的元素為正，有的元素為負(fù)。

（4）建立一個(gè)f位的二進(jìn)制數(shù)S，并將其初始化為0。如果向量V的第i個(gè)元素大于0，則S的第i位為1，否則為0。

（5）輸出S作為文本的簽名。

（6）通過比較兩個(gè)文本簽名的Hamm ing Distance[27]（兩個(gè)二進(jìn)制向量中不相同位的個(gè)數(shù)），可以得出相似程度[28-29]，并通過預(yù)先設(shè)定的相似度閾值去除相似文本。

5 實(shí)驗(yàn)算例研究

5.1 Bloom Filter與Trie樹比較實(shí)驗(yàn)研究

5.1.1 對(duì)比速率研究實(shí)驗(yàn)

對(duì)圖3分析可知，隨著處理中文短文本數(shù)據(jù)量的增長(zhǎng)，Bloom Filter與Trie樹的消耗時(shí)間均有所增加。其中Trie樹較之于Bloom Filter而言，雖然有著精確度100%的優(yōu)勢(shì)，但在處理海量文本時(shí)，其速率表現(xiàn)差強(qiáng)人意。另外，隨著重復(fù)率r的增高，二者的速率均有所降低。

為了更加明顯地比較海量數(shù)據(jù)條件下，Trie樹的低效率性，本文比較了二者在處理1×106，2.5×106條r為1%的文本數(shù)據(jù)時(shí)的表現(xiàn)。在五組實(shí)驗(yàn)中，當(dāng)需要處理的中文短文本數(shù)據(jù)達(dá)到2.5×106條時(shí)，Bloom Filter所需的平均處理時(shí)間為3 526.8 ms（約3.5 s），而Trie樹所需的平均處理時(shí)間為14 429.8 m s（約14.3 s），并且由于二者的消耗時(shí)間與數(shù)據(jù)處理量成正比例關(guān)系，隨著處理量的增多，二者的消耗時(shí)間差不斷增大。

5.1.2 Bloom Filter準(zhǔn)確率研究實(shí)驗(yàn)

雖然Bloom Filter算法在處理中文短文本的去重問題時(shí)，時(shí)間與空間方面均有一定的優(yōu)勢(shì)。然而，如前文分析，隨著中文短文本數(shù)據(jù)量的增加，算法的準(zhǔn)確率k不斷下降。并且k在很大程度上也受到了待去重文本不重復(fù)率r的影響。r在待去重文本中所占比例越大，其準(zhǔn)確率k的水平越低。在10%不重復(fù)率的實(shí)驗(yàn)中，當(dāng)中文短文本數(shù)據(jù)量達(dá)到5×104條時(shí)，Bloom Filter算法的準(zhǔn)確率低至56%左右，去重的效果已經(jīng)受到極大的影響。

5.1.3 Bloom Filter內(nèi)存分配研究實(shí)驗(yàn)

但是，上述關(guān)于準(zhǔn)確率的實(shí)驗(yàn)是在分配內(nèi)存5×104bit（約6.1 KB）的條件下進(jìn)行的，不可否認(rèn)后期數(shù)據(jù)量較大時(shí)導(dǎo)致其準(zhǔn)確率較低是受到內(nèi)存的制約，即在內(nèi)存中開辟的位向量由于容量過低，使得非重復(fù)文本的Hash值映射到了位向量中的相同位置，進(jìn)而導(dǎo)致誤判而影響精度。為驗(yàn)證分析中關(guān)于準(zhǔn)確率與內(nèi)存之間的關(guān)系，又進(jìn)行了補(bǔ)充實(shí)驗(yàn)。

關(guān)于內(nèi)存分配與算法準(zhǔn)確率之間的關(guān)系，在不重復(fù)率r=10%的條件中，對(duì)5×105條中文短文本進(jìn)行處理實(shí)驗(yàn)，選取實(shí)驗(yàn)內(nèi)存區(qū)間在1×104bit（約1.2 KB）和2×107bit（約2.4 MB）。當(dāng)分配內(nèi)存在1.6×105bit左右時(shí)，準(zhǔn)確率升至90%，并隨著分配內(nèi)存量的增加不斷上升，趨向于100%。當(dāng)分配內(nèi)存在2×107bit時(shí)，算法的準(zhǔn)確率達(dá)到100%。由此可見，在準(zhǔn)確率要求并非很高的情況下，較小的內(nèi)存量便可以滿足去重的要求。在內(nèi)存受限之時(shí)，甚至可以考慮循環(huán)采用Bloom Filter算法進(jìn)行過濾。

圖3 不重復(fù)率去重效果比較

圖4 準(zhǔn)確率比較

圖5 Bloom Filter準(zhǔn)確率測(cè)試

綜上所述，Bloom Filter算法與Trie樹算法對(duì)于需要完全去重的文本，在時(shí)間速率方面表現(xiàn)良好。而對(duì)于不需要過分注重精度的海量文本，在極低的空間開銷的情況下，Bloom Filter算法完全可以勝任。Trie樹雖然可以保證100%的準(zhǔn)確率，但是在海量數(shù)據(jù)的處理方面，仍要稍遜一籌。對(duì)于中文短文本處理的第一階段，可以綜合考慮實(shí)際情況，對(duì)上述算法進(jìn)行選擇。

5.2 Sim Hash研究實(shí)驗(yàn)

在實(shí)驗(yàn)中，筆者將向量V的維數(shù)定為64維，由于采用了Shingling特征值的選取思想，同時(shí)為了簡(jiǎn)化實(shí)驗(yàn)過程，實(shí)驗(yàn)中并未加入涉及權(quán)重值以及語料庫的相關(guān)內(nèi)容。在實(shí)驗(yàn)中，分別對(duì)文本數(shù)據(jù)量為100，500，1 000，2 000的數(shù)據(jù)集進(jìn)行數(shù)據(jù)相似去重處理工作（相似度閾值取Hamming Distance＜5），所得實(shí)驗(yàn)結(jié)果如圖6所示。

圖6 SimHash算法的處理速率

在實(shí)驗(yàn)中，文本數(shù)據(jù)量在100條左右時(shí)，處理速率約為2 s左右，而文本數(shù)據(jù)量在1 000條左右時(shí)，處理速率約為1 m in左右，尚在可以接受的范圍之內(nèi)。隨著文本數(shù)據(jù)量的不斷增加，時(shí)間開銷將逐步增大。這是由于SimHash算法在進(jìn)行相似度的數(shù)值比較時(shí)需要進(jìn)行成對(duì)比較，因而時(shí)間復(fù)雜度為O(n2)。所以在數(shù)據(jù)量較低時(shí)，采用SimHash算法將比較有效，過高的數(shù)據(jù)量將嚴(yán)重影響算法的性能。在文本數(shù)據(jù)去重處理的第二階段，如果處理數(shù)據(jù)量過大，可以考慮采用分布式的方法進(jìn)行分?jǐn)偺幚?。?duì)于分布式的處理方法，不在本文討論范圍之內(nèi)，在此并不贅述。

6 結(jié)語

本文的研究重點(diǎn)主要針對(duì)目前日益冗余但極富研究?jī)r(jià)值的中文短文本的去重工作。在綜合文本去重領(lǐng)域現(xiàn)有的研究基礎(chǔ)之上，提出了針對(duì)于中文短文本重復(fù)檢測(cè)的解決算法，并對(duì)方案做了實(shí)例研究驗(yàn)證。實(shí)驗(yàn)證明，Bloom Filter在處理中文短文本數(shù)據(jù)時(shí)能夠在低內(nèi)存占用的情況下，以可以接受的出錯(cuò)率換取較快的速度，Trie與前者在速率上在同一數(shù)量級(jí)，但仍要遜色一些；SimHash并不適宜直接處理中文短文本去重工作，其成對(duì)比較的低效性需要第一階段的有力配合。然而，不容忽視的是，本文的實(shí)驗(yàn)研究在第二階段并未充分引入語料庫的因素，因而弱化了相似去重中語義的影響。關(guān)于中文短文本去重領(lǐng)域在SimHash算法中引入語料庫以強(qiáng)化權(quán)重的部分，還有待于后人繼續(xù)研究。

[1]耿崇，薛德軍.中文文檔復(fù)制檢測(cè)方法研究[J].現(xiàn)代圖書情報(bào)技術(shù)，2007（6）.

[2]曹玉娟，牛振東，趙堃，等.基于概念和語義網(wǎng)絡(luò)的近似網(wǎng)頁檢測(cè)算法[J].軟件學(xué)報(bào)，2011，22（8）.

[3]鮑軍鵬，沈鈞毅，劉曉東，等.自然語言復(fù)制檢測(cè)研究綜述[J].軟件學(xué)報(bào)，2003，14（10）.

[4]Manber U.Finding sim ilar files in a large file system[C]// Proceedings of the Winter USENIX Conference，1994：1-10.

[5]Heintze N.Scalable document fingerprinting[C]//Proceedings of the 2nd USENIX Workshop on Electronic Commerce. 1996.http：//www.cs.cmu.edu/afs/cs/user/nch/www/koala/main. htm l.

[6]Broder A Z，Glassman S C，Manasse M S.Syntactic clustering of the Web[C/OL]//Proceedings of the 6th International Web Conference.1997.http：//gatekeeper.research.compaq.com/pub/DEC/SRC/technical-notes/SRC-1997-015-htm l/.

[7]Brin S，Davis J，Garcia—Molina H.Copy detection mechanisms for digital documents[C]//Proceedings of the ACM SIGMOD Annual Conference，1995.

[8]Monostori K，Zaslavsky A，Schmidt H.Match Detect Reveal：finding overlapping and similar digital documents[C/OL]// Proceedings of the Information Resources Management Association International Conference（IRMA 2000），2000. http：//www.csse.monash.edu.au/projects/MDR/papers/.

[9]Monostori K，Zaslavsky A，Vajk I.Suffix vector：a spaceefficient representation of a suffix tree[R].2001.

[10]Wise M J.YAP3：Improved detection of similarities in computer programs and other texts[C/OL].Proceedings of the SIGCSE’96.1996：130-134.http：//citeseer.nj.nec. com/w ise96yap.htm l.

[11]Chow dury A，F(xiàn)rieder O，Grossman D，et al.Collection statistics for fast duplicate document detection[J].ACM Transactions on Information System s（TOIS），2002，20（2）：171-191.

[12]Kolcz A，Chowhury A.Lexicon randomization for nearduplicate detection with I-M atch[J].The Journal of Supercomputing，2008，45（3）：255-276.

[13]Shivakumar N，Garcia-Molina H.SCAM：A copy detection mechanism for digital documents[C/OL].Proceedings of the 2nd International Conference in Theory and Practice of Digital Libraries（DL’95）.1995.http：//www-db.stanford.edu/～shiva/publns.html.

[14]Shivakumar N，Garcia-Molina H.Building a scalable and accurate copy detection mechanism[C/OL].Proceedings of the 1st ACM Conference on Digital Libraries（DL’96）. 1996.http：//www-db.stanford.edu/～shiva/publns.htm l.

[15]Garcia-Molina H，Gravano L，Shivakumar N.dSCAM：Finding document copies across multiple databases[C/OL]. Proceedings of the 4th International Conference on Parallel and Distributed Systems（PDIS’96）.1996.http：// www-db.stanford.edu/～shiva/publns.htm l.

[16]Antonio Si，PHong Va Leong，PRynson W H Lau.CHECK：a document plagiarism detection system[C]//Proceedings of the 1997 ACM Symposium on Applied Computing，1997.

[17]Yang Jung-Sheng，Wu Chih-Hung.Plagiarism detection of text using know ledge-based techniques[C]//Design and Application of Hybrid Intelligent Systems，2003：973-982.

[18]Brin S，Davis J，Garcia-molina H.Copy detection mechanisms for digital documents[C/OL]//Proceedings of the ACM SICMOD Annual Conference，1995：398-409.[2007-05-10]. http：//www-db.stanford.edu/pub/brin/1995/copy.ps.

[19]Theobald M，Siddharth J，Paepcke A.SpotSigs：robust and efficient near duplicate detection in large Web collections[C]//Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval，2008：563-570.

[20]李志義，梁士金.國(guó)內(nèi)網(wǎng)頁去重技術(shù)研究：現(xiàn)狀與總結(jié)[J].圖書情報(bào)工作，2011，55（7）.

[21]楊虎，楊樹強(qiáng)，韓偉紅，等.基于關(guān)聯(lián)規(guī)則和特征碼的快速去重方法[C]//中國(guó)計(jì)算機(jī)大會(huì)，2007.

[22]王曰芬，章成志，張蓓蓓，等.數(shù)據(jù)清洗研究綜述[J].現(xiàn)代圖書情報(bào)技術(shù)，2007（6）.

[23]向培素.聚類算法綜述[J].西南民族大學(xué)學(xué)報(bào)：自然科學(xué)版，2011（5）.

[24]Bloom B.Space/time tradeoffs in Hash coding with allowable errors[J].Communication of the ACM，1970，13（7）：422-426.

[25]http：//zh.wikipedia.org/wiki/Trie#cite_note-DADS-0[OL] [2012-05-07].

[26]丁振國(guó)，吳寶貴，辛友強(qiáng).基于Bloom Filter的大規(guī)模網(wǎng)頁去重策略研究[J].現(xiàn)代圖書情報(bào)技術(shù)，2008（3）.

[27]李彬，汪天飛，劉才銘，等.基于相對(duì)Hamming距離的Web聚類算法[J].計(jì)算機(jī)應(yīng)用，2011，31（5）.

[28]韓冰，林鴻飛.基于語義結(jié)構(gòu)的科技論文抄襲檢測(cè)[J].情報(bào)學(xué)報(bào)，2010，29（3）.

[29]樊勇，鄭家恒.網(wǎng)頁去重方法研究[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（12）：41-44.

GAO Xiang1,LI Bing2

1.Peking University HSBC Business School,Shenzhen,Guangdong 518055,China
2.School of Information Technology&Management,University of International Business and Economics,Beijing 100029,China

The article presents an effective algorithm framework for text de-duplication,focusing on redundancy problem of Chinese short texts.In view of the brevity and huge volumes of short texts,Bloom Filter have been introduced,Trie tree and the Sim Hash algorithm have been introduced.In the first stage of the algorithm framework,Bloom Filter or Trie tree is designed to remove duplications completely；in the second stage,the Sim Hash algorithm is used to detect similar duplications.This text has designed the parameters used in the algorithm framework,and the feasibility and rationality is testified.

text de-duplication;Chinese short texts;Bloom Filter;Trie tree;SimHash algorithm

A

TP311

10.3778/j.issn.1002-8331.1309-0424

GAO Xiang,LI Bing.Research on method to detect reduplicative Chinese short texts.Computer Engineering and Applications,2014,50（16）：192-197.

教育部人文社會(huì)科學(xué)項(xiàng)目（No.11YJA 870017）。

高翔，男，碩士；李兵，男，博士，副教授。E-mail：gx8600@126.com

2013-09-27

2013-10-23

1002-8331（2014）16-0192-06

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-12-10,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1309-0424.htm l