俞楓，王引娜

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

俞楓，王引娜

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

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

0 引言

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

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

1 文本去重相關(guān)技術(shù)比較

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

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

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

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

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

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

2 基于DRPKP的文本去重算法

2.1 DRPKP算法

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 DRPKP算法實現(xiàn)

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

圖2 基于MapReduce的去重流程

其中fileId代表文本的ID，n代表文本的段落數(shù)。

DRPKP算法實現(xiàn)包含兩個MapReduce過程。

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

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

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

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

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

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

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

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

圖3 算法的去重時間對比

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

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

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

4 總結(jié)

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

[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] 黃濤．布隆過濾器在網(wǎng)頁去重中的研究與應用[D]．大連：大連海事大學，2013.

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

[4] 馬成前，毛許光．網(wǎng)頁查重算法Shingling和Simhash研究[J]．計算機與數(shù)字工程，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)

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

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