高翔，李兵

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

2.對外經濟貿易大學信息學院，北京 100029

◎信號處理◎

中文短文本去重方法研究

高翔1，李兵2

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

2.對外經濟貿易大學信息學院，北京 100029

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

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

1 引言

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

2 國內外研究進展

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

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

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

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

3 研究模型

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

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

圖1 算法框架圖

4 基本算法設計

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

4.1 Bloom Filter設計

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

其中n為數據集中元素的個數，k為Hash函數個數，m為分配位向量的大小。

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

Bloom Filter算法的具體設計如下：

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

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

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

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

4.2 Trie樹的設計

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

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

英文全部由26個字母構成，Trie樹的思想源泉就來源于對英文字典的查詢。但是，考慮到常用中文有大約2 000多字，據此建立Trie樹則不切實際。基于此種考慮，筆者對Trie樹做出了改進。對于中文短文本集合A=(a1，a2，…，an)中的任意一個中文字符串ai，經過散列函數得到整型變量Val，并取NVal=Val2之后，針對一組的NVal構建數字Trie樹。

改進后的Trie樹具體設計如下：

（1）初始化根節(jié)點，構建Trie樹。

（2）對于中文短文本集合A=(a1，a2，…，an)中的任意一個中文字符串ai，經過散列函數（使用Visual Studio 2010 C#內置Hash函數）得到整型變量ki。

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

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

4.3 Sim Hash算法設計

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

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

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

（3）當所有的特征碼處理完畢之后，向量V中有的元素為正，有的元素為負。

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

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

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

5 實驗算例研究

5.1 Bloom Filter與Trie樹比較實驗研究

5.1.1 對比速率研究實驗

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

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

5.1.2 Bloom Filter準確率研究實驗

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

5.1.3 Bloom Filter內存分配研究實驗

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

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

圖3 不重復率去重效果比較

圖4 準確率比較

圖5 Bloom Filter準確率測試

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

5.2 Sim Hash研究實驗

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

圖6 SimHash算法的處理速率

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

6 結語

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

[1]耿崇，薛德軍.中文文檔復制檢測方法研究[J].現代圖書情報技術，2007（6）.

[2]曹玉娟，牛振東，趙堃，等.基于概念和語義網絡的近似網頁檢測算法[J].軟件學報，2011，22（8）.

[3]鮑軍鵬，沈鈞毅，劉曉東，等.自然語言復制檢測研究綜述[J].軟件學報，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，Frieder 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]李志義，梁士金.國內網頁去重技術研究：現狀與總結[J].圖書情報工作，2011，55（7）.

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

[22]王曰芬，章成志，張蓓蓓，等.數據清洗研究綜述[J].現代圖書情報技術，2007（6）.

[23]向培素.聚類算法綜述[J].西南民族大學學報：自然科學版，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]丁振國，吳寶貴，辛友強.基于Bloom Filter的大規(guī)模網頁去重策略研究[J].現代圖書情報技術，2008（3）.

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

[28]韓冰，林鴻飛.基于語義結構的科技論文抄襲檢測[J].情報學報，2010，29（3）.

[29]樊勇，鄭家恒.網頁去重方法研究[J].計算機工程與應用，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.

教育部人文社會科學項目（No.11YJA 870017）。

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

2013-09-27

2013-10-23

1002-8331（2014）16-0192-06

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