基于DRPKP算法的文本去重研究與應用

俞楓，王引娜

基于DRPKP算法的文本去重研究與應用

俞楓，王引娜

SimHash算法是目前主流的文本去重算法，但它對于特定行業的文本數據在主題方面的天然相似性特點并沒有特殊的考慮。基于多年在金融證券行業信息管理和數據整合的經驗，本文分析目前文本去重方法存在的問題，特別針對SimHash算法在特定行業文本去重中的不足，創新地提出一種基于段落主題的文本去重方法(簡稱DRPKP算法)，通過對去重準確率、覆蓋率和去重時間3個指標進行對比測試，DRPKP算法比SimHash算法準確率可提高24.5%、覆蓋率可提高16.34%，且去重時間更短。

文本去重；段落主題；SimHash；相似度；MapReduce

0 引言

SimHash算法由Charikar.M.S在2002年提出[1]，是目前主流的文本去重算法，它被包括Google在內的互聯網公司廣泛使用于開放領域的網頁文本去重，它具有計算速度快，存儲空間小等優點。然而，SimHash算法對于特定行業的文本數據在主題方面的天然相似性特點并沒有特殊的考慮。以金融證券行業為例，其文本信息包含的關鍵字雷同、文本結構相似，這種主題天然相似性是特定行業文本有別于開放領域網頁文本的特征，這會給通用型的去重算法帶來干擾。

基于多年來在金融證券行業信息管理和數據整合的經驗，本文針對SimHash算法在特定行業文本去重中的不足，提出了一種基于段落主題的文本去重方法(簡稱DRPKP算法)，并基于MapReduce框架進行了算法實現，以國泰君安金融資訊和統一檢索平臺中的實際數據為基礎，通過分組測試和交叉比較，驗證了DRPKP算法相比SimHash算法在去重準確率、覆蓋率和去重時間3個指標方面的性能，結果表明DRPKP算法比SimHash算法準確率可提高24.5%、覆蓋率可提高16.34%，且去重時間更短。

1 文本去重相關技術比較

目前，文本去重的主要方法有：

1）基于URL的去重。主要是檢測URL是否重復，文獻[2]采用布隆過濾器檢查一個URL是否已經被抓取過以判斷重復信息。然而，由于同一個網頁可以關聯給不同的URL，因此，基于URL的去重效果準確性較低。

2）基于特征碼的去重。它一般是從文章中提取出一些字符串（稱為“指紋”），把指紋映射到hash表中，通過統計hash表中相同的指紋數目或者比率，來計算網頁的相似性。代表算法有DSC和DSC-SS算法，DSC算法效率不高，而且文檔數量大時比較的次數過多，導致效率下降，DSC-SS算法處理短小文檔時效率較低。

3）基于文本復制檢測技術的去重。代表方法有COPS (copy protection system) 系統及其相應算法、SEAM ( Stanford copy analysis method)原型、dSCAM模型、KOALA系統、YAP3和MDR以及北大天網查重算法，這些方法的基礎是基于詞頻統計的方法來計算文件相似性，方法不夠準確而且計算量大，不適合大規模的文本去重。

4）基于局部敏感哈希的去重。經典代表如SimHash算法，它是從文本中抽取一些帶有權重的特征集，通過這些特征集的疊加計算得到該文本的指紋，通過計算兩個指紋之間的海明距離來判斷兩個文本的相似度。文獻[3]提出基于多SimHash指紋和k維超曲面的近似文本檢測，文獻[4]提出對SimHash存在的問題進行了改進。然而，SimHash算法及其改進的方法主要還是面向包含主題眾多，特征集差異度比較大的開放文本領域，而在特定行業中的文本之間的相似度天然就很高，使得通用去重算法判斷文檔重復的準確率降低。根據我們在金融證券領域的文本去重經驗，在券商的文本數據中重復數據約占50%，而SimHash算法只能去掉重復數據中的60%到70%，低于其用于開放領域網頁文本去重的平均水平（SimHash算法在開放領域網頁文本去重的平均水平在70%以上）。

通過以上分析，目前的各類去重方法均存在一定的不足。主流的通用型去重算法，如SimHash算法，由于特定行業文本具有關鍵詞集合小、關鍵詞重復率高、文本結構特征相似等特點，使判斷文本信息是否相似的難度加大，從而導致通用型去重方法在特定行業文本去重的表現反而比開放領域有所下降。

2 基于DRPKP的文本去重算法

2.1 DRPKP算法

針對SimHash算法在特定行業領域應用的不足，本文提出基于DRPKP算法的文本去重方法，相比于SimHash算法，DRPKP算法充分考慮了文本的結構以及特性的分布情況：SimHash算法是一個文本產生一個指紋，而DRPKP算法是文本中的每個段落產生一個指紋，因而一個文本可以表達為其包含段落的指紋集合。對于同一個文本而言，基于段落主題的指紋集合比單一指紋包含更多的信息，從而提高對文本相似度判斷的準確率。

DRPKP算法的流程如圖1所示：

圖1 基于DRPKP算法的去重流程圖

以下為基于DRPKP算法的去重步驟：

Step1：利用中科院的ICTCLAS系統對文本進行分詞和詞性標注，為了減少計算的復雜度，去掉除名詞和動詞以外的詞。

Step2：對文本按照段落提取主題詞，并為每一個提取的主題詞設定權重，這些帶有權重的特征構成一個多維向量。

其中主題詞提取的實現方式是：統計出段落文本中的實詞的出現概率，其中代表實詞wi在段落中出現的次數，n(si)代表段落si中出現的實詞個數，然后選取概率最高的10個主題詞作為段落主題。

每個主題詞的權重計算為詞頻權重、上下文權重和位置權重之和，其中上下文權重是指在一個詞匯窗口（20個字）出現的多個主題詞的上下文權重，若一個詞匯窗口同時出現n個主題詞，則每個主題詞的權重為0.1n，位置權重考慮的位置包括標題、首段、尾段、第x段，計算公式如公式（1）：

Step3：初始化一個64維的向量，且各維初始化為0。采用Rabin的隨機多項式生成指紋算法將每個段落主題計算出一個

64-bit的指紋，Rabin的指紋算法是基于系數屬于二進制整數空間的不可約多項式的模運算。

Step4：對于每個段落的64-bit指紋，如果第i位為0，則64維向量的第i維的值被減去該段落主題的權重；反之，如果第i位為1，則加上該段落主題的權重。

Step5：當所有的段落主題特征都這樣處理完之后，64維向量的各維的值則有正有負，如果該維的值的符號為正則取1，為負取0，從而得到了該段落的指紋。如果該文本有m個段落，則文本d的指紋集合為。

Step6：計算兩個文本的海明距離得出兩個文本的相似度。

2.2 DRPKP算法實現

為了進一步提高去重過程的效率，本文采用MapReduce框架對DRPKP算法進行實現。MapReduce是一種并行運算的編程模型，它通過定義Map函數（映射）和Reduce函數（規約）實現并行計算。DRPKP算法基于MapReduce的去重流程如圖2所示：

圖2 基于MapReduce的去重流程

其中fileId代表文本的ID，n代表文本的段落數。

DRPKP算法實現包含兩個MapReduce過程。

第一個MapReduce過程，以提取段落指紋為Map函數，輸入為段落主題及權重，輸出為根據3.1中的Step4得出的段落指紋；以生成文本指紋集合為Reduce函數。第二個MapReduce過程為計算海明距離做準備，把第一個MapRduce過程的結果做倒排，產生段落指紋與包含該段落文本的對應關系，結果用于計算海明距離，根據海明距離來判斷兩個文本是否重復。

在實際實驗中，判定兩個文本是否重復的海明距離閾值設定為3，這個數字是與文本所包含的平均段落數有關的經驗數字，文本包含的段落數越多，相應的閾值也會越大。

3 DRPKP算法對金融證券類文本去重結果驗證

為了驗證DRPKP算法在特定行業文本去重中的效果，我們在國泰君安的金融資訊和統一檢索平臺上進行了實驗。該平臺是一個基于主題域的資訊整合平臺，包含文本數據的總量超過300GB。基于隨機采樣，我們得到大小分別為10G、20G、50G、100G、200G的5組文本數據，通過分組測試，對比SimHash和DRPKP算法在去重準確率、覆蓋率和去重時間3個方面的去重效果。

通過對5個文本集合進行去重操作，得出兩種算法各自的準確率和覆蓋率的如表1所示：

表1 兩種算法的準確率和覆蓋率比較

DRPKP算法的平均準確率和平均覆蓋率比SimHash算法分別提升24.5%和16.34%。這意味著在實際去重中，可以準確發現并消除90%以上的重復數據。

為了比較DRPKP算法與SimHash算法的處理速度，將SimHash算法也采用MapReduce方式進行了實現。實驗中，我們構建了10節點規模的MapReduce環境，8個Map節點，2個Reduce節點。兩種算法的去重時間的對比如圖3所示：

圖3 算法的去重時間對比

可見DRPKP算法所需時間短于并行化的SimHash算法。

圖3的結果的意義在于，雖然DRPKP算法基于指紋集合進行比較，理論上比SimHash要復雜一些，然而在分布式并行運算的框架下，文本數量和中間結果均被并行化處理，使SimHash在理論上的速度優勢被削弱。由于特定行業文本數據的天然相似性，使得文本數量增大時，主題關鍵詞、文本結構特征均出現收斂特性，即文本數量越多，段落指紋集合的歸約效果越明顯。因此，在特定行業文本去重中，隨著文本數量的增多，DRPKP算法的速度優勢就越發明顯。

通過以上的對比測試驗證了DRPKP算法在去重準確率、覆蓋率和去重時間3方面均優于SimHash算法，其中DRPKP算法比SimHash算法平均準確率可提高24.5%、平均覆蓋率可提高16.34%，而且在特定行業文本去重方面，DRPKP算法在處理速度上也具備明顯優勢，這種優勢隨文本數量的增加而愈發明顯。文本去重作為平臺的重要組成部分，提高了國泰君安客戶與員工的資訊使用效率和使用體驗。

4 總結

本文針對文本去重算法SimHash算法在特定行業文本去重方面的不足，提出一種基于DRPKP算法的文本去重方法，并將其在國泰君安的金融資訊和統一檢索平臺的生產環境中做了對比測試，通過對比DRPKP算法與SimHash算法在去重準確率、覆蓋率和去重時間3方面的指標，發現DRPKP算法在準確率和覆蓋率方面平均提升24.5%和16.34%，而且去重處理速度更快，結果表明DRPKP算法更加適用于特定行業的文本去重。未來，我們將把基于DRPKP算法的文本去重方法應用于醫療信息檢索、網絡安全監控等領域，從而進一步驗證本文方法的適用性和測試結論。

[1] Charikar M S．Similarity Estimation Techniques from Rounding Algorithms[A].In: Proceedings of the Thirty-fourth Annual ACM Symposium on Theory of Computing[C]．New York：ACM，2002：380-388．

[2] 黃濤．布隆過濾器在網頁去重中的研究與應用[D]．大連：大連海事大學，2013.

[3] 董博，鄭慶華，宋凱磊，田鋒，馬瑞．基于多SimHash指紋的近似文本檢測[J] ．小型微型計算機系統，2011,11(11):2152-2157.

[4] 馬成前，毛許光．網頁查重算法Shingling和Simhash研究[J]．計算機與數字工程，2009,1:15-17.

Research and Application on Text Duplication Removal Based on DRPKP Algorithm

Yu Feng1,Wang Yinna2
(1.Guotai Junan Securities Co., Ltd., Shanghai200120,China; 2.China Information Technology Co., Ltd. Stored Data,Shanghai200120,China))

SimHash algorithm is one of the best algorithm for text duplication detection and removal. However,it has less consideration on the naturalsimilarity of text in specific fields. Based on our experience in information management and data integration in financing and securities industry, we analyzemost text duplication removal algorithms today, especially focus onSimHash algorithm,and propose an newalgorithm for text duplication detection and removal which is based on paragraph key phrase(DRPKP). We appliedour algorithm to detect and remove text duplication in real data set onGuo Tai Jun An’s Financial Information and Unified Information Retrieval Platform. In comparison withSimHash algorithm,our DRPKPalgorithm performs better with the precision ofduplication removal increased by 24.5%, andthe recallincreased by 16.34%; meanwhile, our DRPKPalgorithm also shows an advantage in operating time.

Image Retrieval; Gaussian Pyramid; Color Histogram.

TP311

A

1007-757X(2014)01-0058-03

2013.12.20)

項目資助：國家科技支撐計劃課題“證券與金融產品交易綜合服務示范”資助（編號：2012BAH13F03）

俞 楓（1969-），男，博士，國泰君安證券股份有限公司，高級工程師，主研方向：系統構架設計、IT規劃，上海，200120王引娜（1986-），女，華存數據信息技術有限公司，碩士，研究方向：大數據、云計算、數據挖掘、機器學習，上海，200120