周游，賈創(chuàng)輝

（四川大學計算機學院，成都610065）

0 引言

隨著大數(shù)據(jù)時代的到來，數(shù)據(jù)呈爆炸式的增長，數(shù)據(jù)信息冗余過載的問題也隨之而來，這也成為了個人以及企業(yè)比較頭疼的一個問題。對于相似重復數(shù)據(jù)的相關(guān)理論和技術(shù)的研究，已成為了各界學者研究的熱點話題，并取得了一定的成果。相似重復數(shù)據(jù)清洗的相關(guān)技術(shù)在論文抄襲檢測、垃圾郵件檢測、相似重復網(wǎng)頁檢測等領(lǐng)域都得到了一定程度的應用。而且，相似重復數(shù)據(jù)清洗技術(shù)對檢測出的相似重復數(shù)據(jù)進行清洗，不僅降低了存儲系統(tǒng)的消耗，而且優(yōu)化了存儲空間[1]。同時，也有效地減少了存儲系統(tǒng)的訪問量，提高了其性能。

本文針對相似重復數(shù)據(jù)檢測過程中出現(xiàn)的準確度不高問題，提出了一種相似重復數(shù)據(jù)的清洗方法，能夠提高相似重復數(shù)據(jù)檢測的正確率，可以有效地甄別出相似重復的數(shù)據(jù)。在對相似檢測算法Simhash算法進行了優(yōu)化的基礎(chǔ)上，計算出Simhash簽名值，提高了相似重復數(shù)據(jù)識別的準確率。在大規(guī)模數(shù)據(jù)下，為了使得相似重復數(shù)據(jù)檢測和清洗的效率得到提高，將提出的相似重復數(shù)據(jù)檢測算法和大數(shù)據(jù)處理平臺Spark相結(jié)合[2]。提高了數(shù)據(jù)清洗的速率，能夠高效、快速地對相似重復數(shù)據(jù)進行清洗，為用戶挖掘海量數(shù)據(jù)下的隱藏信息，做好了前期工作。

1 Simhash算法介紹

1.1 算法描述

Simhash算法是一種不同于傳統(tǒng)的哈希算法，具有局部敏感性，該算法被Google應用在重復網(wǎng)頁的去除工作上。Simhash算法于2007年第一次被三位Google的工程師提出，該算法可以把維度比較高的向量轉(zhuǎn)換為維度比較低的指紋值。

傳統(tǒng)的hash算法只是將內(nèi)容隨機的用一個hash值來表示，如果兩個hash值不相等，則兩個內(nèi)容是不相等的，但是沒有其他額外的信息，所以，無法通過傳統(tǒng)的hash算法來表示內(nèi)容的相似程度[3]。而Simhash算法則不同，該算法可以通過產(chǎn)生的指紋簽名值表示內(nèi)容之間的相似程度。

Simhash算法是用來檢測相似或重復數(shù)據(jù)的高效hash算法，它不僅能檢測出原數(shù)據(jù)的相似性，而且還能檢測出不一樣內(nèi)容所造成的bit位的不同。Simhash算法主要通過將維度較高的特征向量轉(zhuǎn)化為一個f位的指紋簽名（Fingerprint），通過比較兩個文件f位指紋簽名的漢明距離來判斷文章的相似性。本文對相似重復數(shù)據(jù)的研究中主要使用的方法就是以改進后的Simhash算法為基礎(chǔ)，結(jié)合其他相關(guān)技術(shù)實現(xiàn)相似重復數(shù)據(jù)的識別。

1.2 Simhash算法的流程

（1）文本獲取：通過相應的技術(shù)獲取文本內(nèi)容。

（2）分詞：通過特定的分詞技術(shù)對文本內(nèi)容進行分詞處理，過濾掉一些不重要的詞，這些不重要的詞指的是停用詞，并去一些標點和干擾符號。

（3）生成hash值：通過hash生成算法把每個詞變成一個個的哈希值，這樣字和詞語就變成了數(shù)字組成的序列串。

（4）加權(quán)：對上一步計算得到的hash值，根據(jù)每個詞的權(quán)重，對其進行加權(quán)處理。

（5）合并：把上一步計算出的每個詞的序列串進行相加，得到一個新的序列串。

（6）降維：把上一步計算出來的序列串轉(zhuǎn)轉(zhuǎn)變成只有01的串，最后生成Simhash指紋簽名。如果每一位大于0記為1，小于0記為0。

根據(jù)上述的6個步驟，文本內(nèi)容就會轉(zhuǎn)化為一個自定義維度大小的指紋值。通常情況下，維度的維數(shù)有32、64和128位三種。按照上述流程就將兩個文檔內(nèi)容的相似度判斷變成了對兩個指紋簽名值的相似度進行判斷。通過計算兩個Simhash指紋簽名海明距離，就可以判斷出兩個文檔是否相似。

2 基于spark相似重復檢測實現(xiàn)

在為了提高相似重復處理的速度，本文將基于Simhash相似重復檢測算法于大數(shù)據(jù)處理平臺相結(jié)合。在基于Spark的相似檢測的實現(xiàn)過程中，主要分為兩步，首先是對Simhash指紋簽名分塊并建立索引，其次是相似重復的計算。

2.1 建立Simhash順序指紋索引

對于給定的文本，通過Simhash算法計算出文本的Simhash簽名值，并以鍵值對的形式存入到Spark數(shù)據(jù)庫中，為了方便在Spark平臺上進行計算。為了提高相似檢測的速度，本文對Simhash簽名值進行分塊操作，并建立索引。在本文中，需要將64位的Simhash簽名值分成相等的4份，用字母ABCD、BACD、CABD、DABC表示，每份16位。分塊之后的鍵值對數(shù)據(jù)如下為：

>

>

>

>

其中，fileId表示文件編號，ABCD表示按照A部分排序的指紋值，BACD表示按照B部分排序好的指紋值，以此類推。

對于以上描述的優(yōu)化方法，存在一個問題。如果該指紋索引在指紋簽名值F1中的分塊的位置與指紋簽名值F中的分塊位置不相同，例如F的第1個指紋索引與F1的第2個指紋索引相同，但是分塊的位置是不用的。所以，這次漢明距離的比較沒有意義，會額外增加了比較時間和計算成本。

基于此本文采用在分段后的指紋值增加前綴編號，同時將原有的指紋值作為后綴，共同組成全新的指紋值。例如，將64位的Simhash簽名值分成相等的4份，用字母 ABCD、BACD、CABD、DABC表示，則分段后的新的指紋值可以表示為00ABCD、01BACD、10CABD和11DABC，最后可以通過簡單的計算將指紋值還原。新的指紋值數(shù)據(jù)格式為：

>

>

>

>

通過全新的指紋值按照00A、01B建立索引，將數(shù)據(jù)輸入計算模型，在第一階段對每個指紋記錄進行遍歷，輸出組合的二元組key-value對，其中二元組為指紋值，表示為，其中 f為指紋集合，即BCD、ACD等?；赟park計算模型下的Map階段數(shù)據(jù)有以下兩種：

輸入階段：

>

>

>

>

輸出階段：

<00A,>

<01B,>

<10C,>

<11D>

在模型計算的第二步的操作過程中，對第一步產(chǎn)生的結(jié)果做歸并處理，并將得到的結(jié)果進行分組，輸出的形式例如：)>。

在基于Spark并行計算模型下，對文本內(nèi)容的指紋簽名按照建立的順序索引進行指紋簽名的分類操作，通過Spark并行計算模型中的相應的Map函數(shù)，把相同的順序指紋索引所對應的文本的編號和后續(xù)的指紋值添加入順序指紋索引中；通過Spark并行計算模型中的相應的Reduce函數(shù)，對相同的順序指紋索引的文本編號和指紋值的鍵值對內(nèi)容進行處理歸并處理。

在進行歸并的時候，將歸并的步驟拆分為兩步，第一步是局部的歸并，對每一個鍵都添加一個隨機數(shù)，例如10以內(nèi)的隨機數(shù)，此時原來的鍵就變成了新的鍵。例如（hello,1）（hello,1）（hello,1）（hello,1），就會變成（1_hello,1）（1_hello,1）（2_hello,1）（2_hello,1）。接著對新的鍵值對按照鍵進行歸并操作，進行局部的歸并操作，那么聚合后的結(jié)果就變成了（1_hello,2）（2_hello,2）。第二步是將各個鍵的前綴去掉，就變成了（hello,2）（hello,2），再次進行全局的歸并操作，就得到了最終的結(jié)果了，例如（hello,4）。

通過采用二段聚合的方式，可以避免在shuffle階段出現(xiàn)數(shù)據(jù)傾斜現(xiàn)象，提高Spark處理數(shù)據(jù)的速度和性能。

2.2 相似度檢測計算

在數(shù)據(jù)規(guī)模非常大的情況下，數(shù)據(jù)相似度檢測計算的任務量也是相當大的。所以本文在進行相似度檢測計算時，充分利用了Spark在大規(guī)模數(shù)據(jù)處理下的優(yōu)勢，完成大規(guī)模數(shù)據(jù)下的相似度檢測計算任務。

根據(jù)第一階段的操作，對指紋值進行分塊并建立索引后，并將鍵值相同的索引進行歸并，得到的中間結(jié)果為)>。并將該鍵值對作為第二階段的輸入值，進行下一階段的操作，進行指紋值相似度檢測計算。將產(chǎn)生的結(jié)果以鍵值對的形式存儲，形式如下所示：

在第二個Map計算階段，通過計算出兩個文件之間的相似度，將相似度與閾值進行比較，來判斷文件是否相似。利用如下公式計算相似度：

其中，A、B表示兩個文本數(shù)據(jù)，h(A ,B)表示A和B的漢明距離。計算出sim（A,B）的值，即為文本A和文本B的指紋簽名相似度。若sim（A,B）大于閾值，則證明文本A和文本B是相似重復的。具體流程示意圖如圖1所示。

圖1

在計算的第二階段，主要是為了查找和待檢測文本B相似度最接近的文本。所以，會根據(jù)文本之間的指紋簽名值進行相似度大小的比較，找到相似度的文本。獲取sim（A,B）的最大值的中間值，輸出以A為key，B和sim（A,B）組 成 的 二 元 組 為value，即，其中，網(wǎng)頁B代表這在文本集中已經(jīng)存在的某個文本。找到文本A與文本集中的某個文本的最大相似值，也就是最相似的某個文本，為了以后的指紋庫的更新也提供了方便。

3 算法實現(xiàn)效果

本文通過進行一系列對比實驗的方方法，對本文優(yōu)化后的Simhash相似檢測算法的算法性能從準確率、召回率、F值以及執(zhí)行時間等方面進行度量。將本文的Simhash算法分別和原有的Simhash算法、優(yōu)化的Simhash算法以及Shingle算法做對比實驗。

實驗針對五類新聞數(shù)據(jù)，每一類隨機選取2000條數(shù)據(jù)，其中包含500條相似重復數(shù)據(jù)。這500條相似重復數(shù)據(jù)作為實驗之前已經(jīng)知道的相似重復數(shù)據(jù)。分別用Shingle算法、原有的Simhash算法、優(yōu)化后的Simhash算法和本文提出的Simhash算法在這些數(shù)據(jù)集上對比實驗，分別對不同算法所得到的實驗結(jié)果進行分析。如果算法檢測出來的正確的相似重復數(shù)據(jù)的數(shù)量和原先設置的500條相似重復數(shù)據(jù)越接近，就說明算法本文的算法是切實可行的。

表1 算法準確度對比表

4 結(jié)語

本文提出的基于Spark的大規(guī)模相似重復數(shù)據(jù)清洗模型，通過對Simhash算法進行相應的優(yōu)化，提高了相似重復數(shù)據(jù)檢測的準確度和速度；將優(yōu)化的Simhash算法和Spark相結(jié)合，有效地解決了單機環(huán)境下處理海量文本數(shù)據(jù)存在的效率低下、存儲受限等問題。在此，對本文所研究的相關(guān)內(nèi)容進行了如下小結(jié)：

（1）對相似檢測技術(shù)和數(shù)據(jù)清洗的概念作了簡要的介紹，并介紹了Simhash相似檢測算法相關(guān)的技術(shù)，例如漢明距離以及Simhash算法的概念和算法思想。并基于傳統(tǒng)的Simhash算法在計算權(quán)重的基礎(chǔ)上做了相應的優(yōu)化，以提高相似重復數(shù)據(jù)檢測的準確度和匹配的速度。

（2）在針對Simhash算法權(quán)重計算的過程中，對Simhash算法進行了相應的優(yōu)化。在指紋值匹配過程中，通過對指紋值進行分塊并建立指紋值索引，使用了一種索引順序匹配的方式，提高指紋值匹配的速度和效率。

（3）結(jié)合優(yōu)化的Simhash算法，在深入研究了大數(shù)據(jù)處理平臺Spark之后，提出了基于Spark的大數(shù)據(jù)相似重復數(shù)據(jù)清洗模型。首先，通過使用改進的Simhash算法進行指紋值的計算，對指紋值進行分塊并建立順序索引，然后通過計算海明距離判斷是否相似。結(jié)合大數(shù)據(jù)處理平臺Spark中的并行計算框架，對每一步計算產(chǎn)生的中間數(shù)據(jù)進行適當?shù)淖冃巍Ｗ詈?，在基于Spark大數(shù)據(jù)處理平臺進行了相似重復數(shù)據(jù)的檢測和清洗，將清洗之后的干凈數(shù)據(jù)存入存儲系統(tǒng)中。通過相關(guān)實驗進行證明并對實驗結(jié)果進行分析，證明了將優(yōu)化的Simhash算法和Spark大數(shù)據(jù)處理平臺相結(jié)合，提高了相似重復數(shù)據(jù)檢測和清洗的準確度以及速度。