李恒新，韓堅華

(廣東工業(yè)大學計算機學院，廣州510006)

隨著互聯(lián)網(wǎng)信息量的增加，處理海量數(shù)據(jù)成了迫切需要解決的問題. 但大量數(shù)據(jù)中存在數(shù)據(jù)相似或者重復的現(xiàn)象，如信訪數(shù)據(jù):某一熱門問題不同社會公眾的多次咨詢，以及他們對投訴的處理不滿或得不到答復的再投訴等等. 對這些信訪業(yè)務相似數(shù)據(jù)的判重能夠使政府工作人員及時發(fā)現(xiàn)信訪人重復咨詢、反復投訴的現(xiàn)象，為提高政府部門的服務效能發(fā)揮輔助作用.因此，有必要快速地檢測出相似(相同)數(shù)據(jù)以達到判重的目的. 判重算法更多應用于網(wǎng)頁檢測領域，極少涉及到關系型數(shù)據(jù)庫中的數(shù)據(jù).但是這些數(shù)據(jù)也存在相似甚至重復的現(xiàn)象，對這類數(shù)據(jù)的處理也同樣重要. 關系型數(shù)據(jù)庫中的數(shù)據(jù)獨具自己的特點:數(shù)據(jù)類型豐富，空值數(shù)據(jù)多，表模式不同等.因此，用什么方法快速地從關系型數(shù)據(jù)庫中檢測出相似數(shù)據(jù)成了本文研究的主要內(nèi)容.

數(shù)據(jù)相似性檢測可以用到以下幾種主要的判重算法:DSC 算法(Shingle 算法)、DSC-SS 算法、IMatch 算法、Simhash 算法、VSM 模型、SCAM 算法布爾模型和中文特有的特征碼索引方法等. 其中DSC算法全稱Digital Syntactic Clustering，也就是有名的Shingle 算法，最初由Broder 等［1］提出.算法內(nèi)容:一個長度為L 的文檔，每隔N個漢字取一個Shingle(瓦片)，一共截取了L－N +1個Shingle，一個很長的文檔，其Shingle 會很多. 因此對于大文檔來說運算量太大，可以考慮對Shingle 集合進行抽樣，以降低空間和時間計算復雜性［2－3］.

當不考慮Shingle 出現(xiàn)的位置和順序，就有了IMatch 算法［4］.I-Match 算法認為在文檔中頻繁出現(xiàn)的詞并不會增加文檔的語義信息，因此過濾掉這些重復次數(shù)較多的Shingle. 再計算出每個Shingle 的IDF(Inverse Document Frequency)值，根據(jù)IDF 值挑選比較重要的Shingle.累積這些Shingle 的hash 值，作為這篇文檔的指紋特征值. 如果指紋特征值發(fā)生了沖突，則表示文檔重復.

VSM 為常見的向量空間模型［5］，統(tǒng)計文檔中各個單詞出現(xiàn)的次數(shù). 然后按照倒排索引存儲法存儲文檔和詞頻信息.將文檔用關鍵詞的特征向量表示.VSM 直接計算2個文檔的特征向量的夾角余弦來度量相似性.

Shingle 算法的空間和計算復雜性高，相似性精度也高，適合數(shù)據(jù)量不大且對精度要求高的應用.而I-Match 算法依賴于語料庫，缺乏深層挖掘文檔本身的語義特征，不適合多領域內(nèi)容的數(shù)據(jù)檢測［6］.VSM模型算法的前提是假設詞與詞之間是不相關的，但這種假設不現(xiàn)實，詞與詞之間往往存在語義相關，可能影響了算法的可靠性.

針對以上算法存在的缺點，目前的Simhash 算法對數(shù)據(jù)庫數(shù)據(jù)的相似性檢測是一種較好的去重算法.Simhash 算法能夠根據(jù)數(shù)據(jù)內(nèi)容的權重不同特征，轉(zhuǎn)化為特征值的同時，根據(jù)特征值累積起來的差別大小來判斷數(shù)據(jù)的差別程度.不過度依賴語料庫，對海量數(shù)據(jù)集的相似性計算速度也較快，在計算性能方面上具有很大優(yōu)勢，并且文檔特征值存儲空間小.該算法是對大量數(shù)據(jù)庫數(shù)據(jù)相似性檢測的最佳選擇.

本文采用的數(shù)據(jù)來自于廣州市某區(qū)政府的信訪業(yè)務綜合信息匯集與處理平臺，介紹并改進Simhash算法，提出一種高效處理指紋特征值的算法，并展示改進算法的時間效率和準確率.

1 Simhash 算法

1.1 Simhash 算法實現(xiàn)

Simhash 算法由Charikar［7］提出.算法的主要思想是降維，將高維的數(shù)據(jù)特征向量映射成一個f-bit的指紋(fingerprint)，通過比較數(shù)據(jù)的f-bit 指紋的海明距離(hamming distance)來確定數(shù)據(jù)是否重復或者高度近似.

從數(shù)據(jù)庫中提取出數(shù)據(jù)，作為Simhash 算法的輸入，通過該算法計算得出數(shù)據(jù)的語義指紋值.算法的整體流程圖見圖1.wn代表數(shù)據(jù)中的詞匯，經(jīng)過字符串Hash 函數(shù)分別計算出二進制特征值，再把這些特征值累加，正數(shù)取1，負數(shù)和零取0，重新構成了一個代表這整個數(shù)據(jù)的特征值，稱為指紋特征值.

圖1 Simhash 算法流程圖Figure 1 Flowchart of Simhash algorithm

Simhash 算法自身攜帶的字符串Hash 函數(shù)具有沖突高、速度慢的缺點. 另外，如果對數(shù)據(jù)庫不同字段值的數(shù)據(jù)同等對待處理，會造成相似性檢測精確度低的現(xiàn)象，所以提出采用改進的Simhash 算法.

1.2 改進的Simhash 算法

首先，不同的特征值賦予不同的權重.針對數(shù)據(jù)庫數(shù)據(jù)，小文本字段值賦予較大權重，大文本采用詞頻作為權重，以使產(chǎn)生的指紋值更能代表數(shù)據(jù)特征.

其次，Simhash 算法最后產(chǎn)生的代表數(shù)據(jù)特征的指紋值S，其維度可以有32 位、64 位和128 位等.一般維度越大，計算也就越復雜，好處就是數(shù)據(jù)差異性更能體現(xiàn)出來.為了在復雜性和高效性間做平衡，指紋值S 的維度設為64 位較合適.

最后，針對指紋值S 的維度為64 位，選擇一種字符串Hash 函數(shù)尤為重要. 算法中，對每個特征值的計算要用到字符串Hash 函數(shù)，可見，這個字符串Hash 函數(shù)是Simhash 算法的核心，選擇字符串Hash函數(shù)是使Simhash 算法高效最為關鍵的一步. 傳統(tǒng)的字符串Hash 函數(shù)有不少，比如BKDRHash、APHash、DJBHash、JSHash 和RSHash 等. 但是這些字符串Hash 函數(shù)都是運行在32 位系統(tǒng)上的算法，稍加改動，也能運行在64 位系統(tǒng)上，不過效率必定打了個折扣.為了更好地產(chǎn)生64 位Hash 值，Austin Appleby 創(chuàng)立了一種非加密 Hash 算法:MurmurHash［8］.MurmurHash 的最新版本是MurmurHash 3，支持32 位、64 位及128 位值的產(chǎn)生，并在多個開源項目中得到應用，包括Libstdc、Libmemcached、Nginx、Hadoop 等.受MurmurHash 的啟發(fā)，Google 發(fā)布了CityHash 字符串散列算法. 該算法比MurmurHash 略快，比傳統(tǒng)Hash 算法快30% 以上［9］.CityHash 計算的過程很繁雜，但是充分利用了64 位系統(tǒng)硬件的性能，因此能得到較快的速度［10］. 本文采用CityHash 算法研究Simhash 算法，在64 位計算機上計算每個特征值的Hash 值，同時和采用其他字符串Hash 函數(shù)的Simhash 算法做比較，驗證了改進后的Simhash 算法的快速性.

2 針對64 位指紋特征值的快速處理

指紋特征值的比較一般用海明距離來表示.所謂的海明距離，就是指2個二進制數(shù)對應比特位不同的個數(shù).對于2個指紋特征值x =(x1x2x3…xn)和y=(y1y2y3…yn)，海明距離計算公式為:

海明距離越小，說明數(shù)據(jù)內(nèi)容越相似. 對于64位指紋特征值相似性的檢測，閥值HD 一般設為3，也就是說海明距離小于等于3 的話，數(shù)據(jù)就相似.

對所有的數(shù)據(jù)都進行判重處理，稱為集中處理.在舊數(shù)據(jù)已處理過的前提下，單獨對新加入的數(shù)據(jù)判重處理，可稱之為增量處理.大數(shù)據(jù)下的集中處理耗時較長，非常有必要改進處理的方式，以提高處理的速度.本文根據(jù)特征指紋值的特點，采用索引歸類方法來提高全部數(shù)據(jù)集中處理的速度，大大縮短了處理的時間. 對于增量處理，采用MongoDB 數(shù)據(jù)庫來存儲指紋值，新加入的指紋值可以很快比對舊指紋值，從而判斷出是否為重復數(shù)據(jù). 在處理的速度上，比傳統(tǒng)關系型數(shù)據(jù)庫快.

2.1 集中處理

對所有指紋特征值的判重.傳統(tǒng)做法多采用聚類算法.文獻［11］所采用的Single-Pass 算法屬于聚類算法中的層次凝聚算法. 大體思想就是認為所有的個體都是一個單獨的類，類與類之間進行比較，相似的合并成一類，如此循環(huán)，直到滿足條件且都不能再合并為停止運行條件. 這個算法運用在指紋值的比較上，當設置低相似閥值或者所有指紋相似度高的時候，該算法能有較高性能.最好的時間復雜度為O(n).指紋相似度不高時，最差的時間復雜度能達到O(n2).

上述的算法如果用在大規(guī)模的數(shù)據(jù)處理上，性能將會非常低下.考慮到閥值HD 為3 即數(shù)據(jù)就相似的特點，采用索引歸類的方法，速度就會得到提升.

64 位二進制指紋值分為4 塊，每塊16 位.根據(jù)鴿巢原理，要海明距離為3，則一定有1 塊是相同的.把每一塊的值都作為索引值，按索引值進行歸類存儲.例如一個64 位指紋值Q1Q2Q3Q4，Qn代表第n類由16 位構成的索引值.那么這個指紋值就可以分別存入索引值為Q1的第1 類中，索引值為Q2的第2 類中……16 位二進制的索引值，能產(chǎn)生的索引為216個. 一個指紋值根據(jù)對應的索引值需要存儲4次，但只需找到對應索引，然后和索引里面的指紋做比較就可以了，比較次數(shù)大大減少.建立索引流程如圖2 所示.

假設數(shù)據(jù)量足夠大，有F個指紋值，當F=2n(n＞34)，那么F 就會超過10 億個. 按索引歸類進行存儲，需要存儲4F個指紋值，每個類中的每個索引平均需要存儲S =F/216=2n/216=2n－16個指紋值，新加入的指紋需要在4個類中都進行比較，大概需要比較4S 次.假如不采用這種算法的話，需要比較F 次(大于10 億).兩者對比，計算量減少到原來的當然，跟前面的算法比較，存儲空間多了4 倍，可是比較次數(shù)卻大大減少，是一種以空間換時間的策略.

圖2 索引建立圖Figure 2 Figure of indexing

2.2 增量處理

用數(shù)據(jù)庫存儲集中處理后的特征指紋值.較為傳統(tǒng)的做法就是把這些值與值對應的數(shù)據(jù)信息存儲到關系型數(shù)據(jù)庫中的一張表中.根據(jù)上節(jié)理論分析，用象限值作為索引，可以加快查找速度.表模式見表1.

表1 特征指紋值表模式Table 1 Table mode of fingerprint feature value

可以預見，當數(shù)據(jù)量非常大時，表的規(guī)模也會很大，查找的時間將會延長，造成分析檢測用時過長，無法達到快速檢測的目的.

MongoDB 是一種面向文檔存儲的數(shù)據(jù)庫，具有強大、靈活和可擴展的功能［12］.文檔以類似JSON 格式來進行存儲，對某些字段建立索引，可以實現(xiàn)關系型數(shù)據(jù)的某些功能. 指紋特征值是先按象限值查找進而再作比較.因此，我們可以把一個象限值內(nèi)裝的所有指紋特征值作為一個“文檔”來存儲，這個“文檔”相當于一個索引，索引下的全部特征指紋值構成了一個集合.

MongoDB 是一種表模式自由的數(shù)據(jù)庫，因此不用設計表的結構.根據(jù)上面的設計，我們將以下面的方式來存儲特征指紋值:

"blockName" :"象限值";

"info" :［{"hashcode" :"指紋特征值1"，"textname" :"數(shù)據(jù)名稱1"}，{"hashcode" :"指紋特征值2"，"textname" :"數(shù)據(jù)名稱2"，…}］}.

類似JSON 的格式，很簡單就表示了所有象限值和對應的指紋特征值. 在查找的速度上優(yōu)于關系型數(shù)據(jù)庫.當不管檢測的結果是否有相似數(shù)據(jù)，都執(zhí)行插入新增數(shù)據(jù)操作時，MongoDB 所耗時間也少于傳統(tǒng)關系型數(shù)據(jù)庫，因差別不大，所以不再做實驗分析.

3 結果與分析

算法采用Java 語言實現(xiàn)，采用平臺中的數(shù)據(jù)庫信訪表作為分析對象.此表具有多個字段，有些字段值為空，其中信訪內(nèi)容為大文本，沒有空值.除了大文本，其他字段值都賦予2 的權重.大文本經(jīng)過分詞工具處理，詞頻作為權重.該分詞工具為IKAnalyzer 2012，該工具具有160 萬字/s 的高速處理能力，同時支持自定義的擴展詞匯表和停用詞匯表. 在擴展詞匯表里面加入了搜狗語料庫. 停用詞匯表加入一些語氣助詞等，以使分詞更為精確.

實驗軟硬件環(huán)境為Intel(R)Core(TM)i7－4500U CPU@2.4 GHz，內(nèi)存為8 G，操作系統(tǒng)為64位windows8.1，編程工具為IntelliJ IDEA 13.0.2，采用Java7.

為了評價改進后的Simhash 算法執(zhí)行效率和正確性，本文設計了一系列實驗，其中，實驗1、實驗2是對算法的時間效率和正確性進行驗證，實驗3 是關于特征指紋值的集中處理以及增量處理實驗.

3.1 算法的時間效率

指紋特征值是對數(shù)據(jù)中詞匯特征值總和的表現(xiàn).Simhash 算法采用不同的字符串Hash 函數(shù)對相等的數(shù)據(jù)量會有不同的時間效率. 時空性是衡量一種算法是否得到有效改進的重要指標之一.因此，分別對原有字符串Hash 函數(shù)的Simhash 算法和改進后的Simhash 算法進行了對比實驗.

其中，在官方提供的Simhash 算法實現(xiàn)中，包含有自帶生成64 位二進制值的字符串Hash 函數(shù). 另外，BKDRHash 字符串函數(shù)是32 位Hash 函數(shù)的優(yōu)秀代表，在字符串生成的過程中作了改進，使它能對字符串產(chǎn)生64 位Hash 值，并應用于Simhash 算法.最后我們用CityHash 字符串函數(shù)改進Simhash 算法，因為是運行在64 位計算機上，理論上時間效率應該是最高的.實驗數(shù)據(jù)為三萬條信訪記錄，數(shù)量從少到多都進行了測試.實驗結果如表2 所示.

表2 不同Hash 函數(shù)下的Simhash 算法時間性能Table 2 Time performance of the Simhash algorithm in different Hash function

從表格數(shù)據(jù)可以看出，改進后的Simhash 算法對同樣數(shù)量的數(shù)據(jù)生成指紋值耗時更少.采用32 位BKDRHash 函數(shù)改進的Simhash 算法比自帶的快，而采用CityHash 字符串函數(shù)的Simhash 算法在時間效率上最優(yōu). 可見改進過的Simhash 算法都提高了處理的速度，具有更快的性能.以下實驗所說的改進Simhash 算法都是指采用CityHash 字符串函數(shù)的Simhash 算法.

3.2 算法評估

采用經(jīng)典的信息檢索度量標準來評估算法:召回率和準確率，定義如下:

選擇“教育”、“城市管理”和“城鄉(xiāng)建設”三個主題.評估改進后的Simhash 算法，每個主題分別在數(shù)據(jù)庫的信訪表里找出多組相似數(shù)據(jù)，共計300 條，作為測試之前已知相似數(shù)據(jù)量. 然后混合到5 000條不相似混雜內(nèi)容數(shù)據(jù)中. 分別運行I-Match 算法、官方提供的Simhash 算法和改進后的Simhash 算法進行相似數(shù)據(jù)檢測. 檢測結果為測試找出的相似數(shù)據(jù)量，在這些數(shù)據(jù)量中與已知的300 條相似數(shù)據(jù)吻合的就為測試正確的相似數(shù)據(jù)量.結果見表3.

表3 各算法的評估結果Table 3 Evaluation results of the algorithms

改進后的Simhash 算法在各類數(shù)據(jù)的判重中具有較高的召回率(約90%)和準確率(95%左右)，都源自于攜帶的低沖突率CityHash 函數(shù)算法.I-Match 算法在城市管理版塊表現(xiàn)出較高的召回率.這主要是因為本實驗采用的搜狗語料庫中有不少日常詞匯，所以在該版塊中，I-Match 算法表現(xiàn)出了較好性能.但在其他2個版塊，召回率都有所下降. 這說明了I-Match 算法具有領域相關的缺點. Simhash算法基于所有詞匯來構建指紋特征值，因此與語料庫的關系沒有I-Match 算法的大，召回率相對穩(wěn)定.

3.3 指紋特征值的處理分析

指紋特征值的匹配是找出相似文檔的最后一步驟.先做集中處理的實驗，也就是一次性處理所有的數(shù)據(jù).用Single-Pass 聚類算法來找出相似數(shù)據(jù)，再針對64 位指紋值和海明距離小于等于3 就歸為相似的特點，用了索引歸類的方法，理論上效果應該大大提高.實驗在不同數(shù)據(jù)量下分別運行這2 種算法.

從表4 的結果看，在少量數(shù)據(jù)的前提下，Single-Pass 聚類算法所耗費的時間和索引歸類相比就已經(jīng)有差距了，這種差距隨著數(shù)據(jù)量的增加呈幾何級地增長.當需一次性處理大量數(shù)據(jù)時.索引歸類算法無疑是最好的選擇.

索引歸類處理后的特征指紋值可以存儲到數(shù)據(jù)庫中.實驗中分別存儲到了關系型數(shù)據(jù)庫MySQL 和NoSQL 數(shù)據(jù)庫MongoDB.增量處理又可分為2 種:一種只是判斷與歷史數(shù)據(jù)是否有相似的情況，一種就是判斷有相似數(shù)據(jù)的前提下返回所有的相似特征指紋值，以便進一步的分析需要.在大量不同的新增數(shù)據(jù)處理前提下對處理時間做了平均值，以使實驗結果更趨于準確(表5).

表4 指紋特征值處理所耗時間表Table 4 Characteristic value of fingerprint processing cost schedule ms

表5 不同數(shù)據(jù)庫下增量處理所耗費的時間Table 5 The cost processing time in the different database by incremental processing ms

MongoDB 數(shù)據(jù)庫處理的速度比MySQL 數(shù)據(jù)庫快，主要是因為MongoDB 本身的高性能和面對文檔存儲的特性非常符合指紋特征值按象限存儲的要求，提高了對增量數(shù)據(jù)的處理速度.

4 結論

針對傳統(tǒng)關系型數(shù)據(jù)庫數(shù)據(jù)的特點，應用改進后的Simhash 算法來計算出每行數(shù)據(jù)的指紋特征值，再用設計好的索引歸類方法一次性找出所有的相似數(shù)據(jù)，即使是新增數(shù)據(jù)，也能得到快速的處理.縱觀整個過程，時間效率和準確率都高于其他算法.在后續(xù)的研究中還需進一步優(yōu)化分詞效果，減少數(shù)據(jù)的噪聲，以提高Simhash 算法的召回率. 此外，可進一步探索在分布式環(huán)境下應用該算法，在大數(shù)據(jù)的前提下，使速度再一次得到提升.

［1］Broder A Z，Glassman S C，Manasse M S，et al. Syntactic clustering of the web［J］. Computer Networks and ISDN Systems，1997，29(8－13):1157－1166.

［2］Broder A Z. On the resemblance and containment of documents［C］∥The compression and complexity of sequences. New York:IEEE Computer Society，1997:21－29.

［3］Han B，Keleher P. Implementation and performance evaluation of fuzzy file block matching［C］∥Proceeding of the 2007 usenix annual technical conference. Berkeley:Usenix Association，2007:199－204.

［4］Chowdhury A，F(xiàn)rieder O，Grossman D，et al. Collection statistics for fast duplicate document detection［J］. ACM Transactions on Information Systems，2002，20(2):171－191.

［5］Salton G，Wong A，Yang C. A vector space model for automatic indexing［J］. Communications of the ACM，1975，11:613－620.

［6］曹玉娟，牛振東，趙堃，等. 基于概念和語義網(wǎng)絡的近似網(wǎng)頁檢測算法［J］. 軟件學報，2011，22(8):1816－1826.Cao Y J，Niu Z D，Zhao K，et al. Near duplicated web pages detection based on concept and semantic network［J］. Journal of Software. 2011，22(8):1816－1826.

［7］Charikar M S. Similarity estimation techniques from rounding algorithms［C］∥Proceedings of the 34th annual ACM symposium on the theory of computing. New York:ACM，2002:380－388.

［8］Tanjent. MurmurHash，final version［EB/OL］. (2008－03－03)［2014－08－13］. http:∥tanjent. livejournal.com/756623.html.

［9］Josh Haberman. State of the hash functions［EB/OL］.(2012－01－29)［2014－08－13］. http:∥blog. reverberate.org/2012/01/state-of-hash-functions-2012.html.

［10］陸陽，高寶. 基于CityHash 的政務網(wǎng)站完整性檢查方法研究［J］. 計算機工程與應用，2014(6):1－6.Lu Y，Gao B. Research on file integrity checking based on CityHash for e-government websites［J］. Computer Engineering and Applications，2014(6):1－6.

［11］李綱，毛進，陳璟浩. 基于語義指紋的中文文本快速去重［J］. 現(xiàn)代圖書情報技術，2013(9):41－47.Li G，Mao J，Chen J H. Fast duplicate detection for chinese texts based on semantic fingerprint［J］. New Technology of Library and Information Service，2013(9):41－47.

［12］Chodorow K，Dirolf M. MongoDB:The definitive guide［M］. 2nd Ed. Sebastopol:O'Reilly Media，Inc，2013:1－3.