大規(guī)模文本去重研究

周游，賈創(chuàng)輝

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065）

0 引言

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

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

1 Simhash算法介紹

1.1 算法描述

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

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

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

1.2 Simhash算法的流程

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

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

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

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

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

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

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

2 基于spark相似重復(fù)檢測(cè)實(shí)現(xiàn)

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

2.1 建立Simhash順序指紋索引

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

>

>

>

>

其中，fileId表示文件編號(hào)，ABCD表示按照A部分排序的指紋值，BACD表示按照B部分排序好的指紋值，以此類(lèi)推。

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

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

>

>

>

>

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

輸入階段：

>

>

>

>

輸出階段：

<00A,>

<01B,>

<10C,>

<11D>

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

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

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

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

2.2 相似度檢測(cè)計(jì)算

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

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

在第二個(gè)Map計(jì)算階段，通過(guò)計(jì)算出兩個(gè)文件之間的相似度，將相似度與閾值進(jìn)行比較，來(lái)判斷文件是否相似。利用如下公式計(jì)算相似度：

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

圖1

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

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

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

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

表1 算法準(zhǔn)確度對(duì)比表

4 結(jié)語(yǔ)

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

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

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

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