張亞男，陳衛(wèi)衛(wèi)，付印金，徐 堃

(陸軍工程大學 指揮控制工程學院，江蘇 南京 210007)

0 引 言

進入大數(shù)據(jù)時代，數(shù)字化信息呈現(xiàn)爆炸式增長。伴隨著云計算、大數(shù)據(jù)、物聯(lián)網(wǎng)等信息技術的快速發(fā)展，數(shù)據(jù)量呈幾何級增長，據(jù)IDC最新發(fā)布的報告預測，全球數(shù)據(jù)總量將從2016年的16.1 ZB增長到2025年的175 ZB[1]。隨著全球生成和存儲的數(shù)據(jù)越來越多，對存儲容量的需求將繼續(xù)以穩(wěn)定的速度增長。但是無論是云存儲系統(tǒng)，還是傳統(tǒng)的數(shù)據(jù)存儲系統(tǒng)，都存在大量的冗余數(shù)據(jù)，有的系統(tǒng)中數(shù)據(jù)重復率高達70%～90%[2]。越來越多的研究者開始關注解決數(shù)據(jù)冗余問題以縮減存儲空間，重復數(shù)據(jù)刪除技術應運而生。重復數(shù)據(jù)刪除技術的核心思想是，只存儲唯一的數(shù)據(jù)對象，對于其他重復數(shù)據(jù)則通過存儲指針代替，指針指向該唯一數(shù)據(jù)對象。

當前流行的相似文本檢測和去重算法主要有k-shingle[3]、Minhash[4]和Simhash[5]算法。Simhash是Google工程師Charikar等人提出的一種局部敏感哈希算法，用來解決億萬級別網(wǎng)頁去重問題。Simhash算法較其他算法的優(yōu)勢是處理速度快，結(jié)果準確度高，被廣泛應用于相似文本檢測、冗余數(shù)據(jù)去重和數(shù)據(jù)異常檢測等領域[6]。該文主要對Simhash算法在文本去重上的應用進行研究和改進，以進一步提高其檢測重復文本的精確率。

1 相關研究

1.1 Simhash算法

傳統(tǒng)的哈希算法能夠?qū)θ我忾L度的輸入數(shù)據(jù)進行計算，輸出固定長度的哈希值。SHA-1、MD5等傳統(tǒng)哈希算法，對輸入數(shù)據(jù)非常敏感，只要有1 bit的差距都幾乎不可能產(chǎn)生相同的哈希值，因此無法衡量文本的相似度。重復數(shù)據(jù)刪除技術分為相同數(shù)據(jù)檢測技術和相似數(shù)據(jù)檢測技術兩大類，傳統(tǒng)的哈希算法對后者的效果并不理想[7]。Simhash的主要思想是降維，將高維的特征向量映射成低維的特征向量，通過這些向量的漢明距離(Hamming Distance)來判定文本的相似度。Simhash算法流程(如圖1所示)大致如下：

圖1 Simhash算法流程

(1)分詞。首先對文本進行分詞，將文本轉(zhuǎn)化為一組特征。然后，去除特殊符號、停用詞等無關字詞。

(2)哈希。使用同一哈希函數(shù)計算各個詞的哈希值，分別得到它們對應的f位簽名Sig。

(3)加權(quán)。為每個特征詞賦予權(quán)重，對每個詞的f位簽名進行加權(quán)計算。在計算每個比特位時，遇到1則加上其權(quán)重值，遇到0則減去其權(quán)重值，得到每個詞的加權(quán)特征值。

(4)合并。對文本內(nèi)的每個加權(quán)特征值進行累加，得到一個f位向量V。

(5)降維。對向量V降維，對于每個比特位，如果大于0則將該比特位置為1，否則置為0。得到的結(jié)果作為文本的簽名，記為S。

在計算文本間距離階段，對不同文本的簽名進行異或操作，逐位比較其簽名值。如果該比特位上的值不同則記為1，否則為0，得到1的個數(shù)即為漢明距離的大小。漢明距離越大，代表兩個文本相似度越低，反之則相似度越高。

1.2 當前研究現(xiàn)狀

在大數(shù)據(jù)高性能存儲應用領域，傳統(tǒng)的Simhash算法已無法滿足其需求。首先，特征詞選取的精度不高，不能很好地體現(xiàn)文本特征。其次，對特征詞權(quán)重的計算比較片面，導致準確率下降。針對上述問題，國內(nèi)外研究者進行了進一步的研究與改進。

文獻[8]針對特征詞權(quán)重影響因素考慮不足的問題，在Simhash權(quán)重計算階段，從詞性、詞長、標志詞以及文檔標題中是否含有特征詞等幾大方面對TF-IDF算法的權(quán)重計算進行改進，缺點是僅僅根據(jù)特征詞的詞性、長度和是否處于標題摘要等位置對權(quán)重進行優(yōu)化，會導致部分權(quán)重過大。文獻[9]將Simhash算法和GAN(Generative Adversarial Networks)網(wǎng)絡進行結(jié)合用于惡意軟件檢測，通過轉(zhuǎn)化為灰度圖像提高惡意軟件識別率和性能。文獻[10]引入文檔標簽、摘要、關鍵詞和參考文獻等其他信息，從多個維度計算文本相似度，但是沒有考慮詞匯位置分布的影響因素。文獻[11]提出的E-Simhash算法采用詞頻和熵加權(quán)的方式優(yōu)化特征詞權(quán)重計算，并針對Simhash算法無法體現(xiàn)特征詞位置信息的問題，在特征詞哈希時與其位置進行異或運算。但是在計算特征詞簽名時簡單地將其哈希與所在位置進行異或運算，容易造成文本簽名失真。例如在文本頭僅僅添加一個文字就可能會導致所有特征詞位置發(fā)生改變，造成文本簽名值的顯著改變。

以上對Simhash算法的改進主要存在兩個問題。第一個問題是，在對特征詞哈希加權(quán)時沒有考慮特征詞之間的關聯(lián)性，例如待去重文本中可能存在幾個大類，而屬于某一類文本中的特征詞具有很強的關聯(lián)性，可能會同時出現(xiàn)。如果這些詞同時占有較高權(quán)重，對于分類性能很好，但是卻為差異檢測帶來了干擾。第二個問題是，不能很好地體現(xiàn)特征詞位置分布信息。

2 改進的Simhash算法

針對以上提到的問題，對Simhash算法進行改進。傳統(tǒng)的Simhash算法基于詞袋模型，無法表征語序信息。但是僅考慮特征詞出現(xiàn)的頻率而不考慮語序特征，會影響結(jié)果的準確性。為了減少誤判，該文將特征詞的位置分布信息融入Simhash計算簽名。為提高運算效率，選取權(quán)重前m的詞語而非全部詞語作為特征詞。針對特征詞的共現(xiàn)現(xiàn)象，根據(jù)Jaccard相似度對權(quán)重進行優(yōu)化，降低相關度較高的特征詞的權(quán)重，以提高檢測精度。改進BDR算法用于反映特征詞位置分布，使用隨機函數(shù)將特征詞所在位置映射到f維向量空間，對得到的特征向量累加得到均差向量，然后做降維處理作為位置特征值。取特征詞哈希與位置特征值加權(quán)求和作為其特征向量，與優(yōu)化后的特征詞權(quán)重相乘，經(jīng)合并降維后生成新的文本簽名。最后，通過計算文本間的漢明距離來判斷文本相似度，將A,B兩個文本之間的相似度定義為：

(1)

其中，Ham(A,B)表示A,B兩個文本的漢明距離，f表示文本簽名值的比特位數(shù)。兩個文本的距離越小，相似度越大。文獻[12]的實驗結(jié)果表明，對于64位的長文本簽名，可以將漢明距離不大于3的兩個文本判定為相似文本，同時保證較高的準確性。

2.1 特征詞權(quán)重的改進

現(xiàn)有的基于Simhash改進算法主要使用TF-IDF算法為特征詞賦權(quán)，在計算文本間相似性時沒有考慮特征詞之間的共現(xiàn)現(xiàn)象，而這與基于選擇的特征降維模型前提條件“特征項之間相互獨立”相矛盾[13]。文本集中的特征詞可以分為三類[14]：第1類特征詞在某一類文本中大量出現(xiàn)而在其他類文本里很少出現(xiàn)，第2類特征詞常常在幾個文本類別中出現(xiàn)而在其他類文本里很少出現(xiàn)，第3類特征詞卻在幾乎所有文本類別中都出現(xiàn)。使用TF-IDF算法會對第3類特征詞賦予極低的權(quán)重，對于前兩類特征詞通常會賦予較高權(quán)重。但是當前兩類特征詞出現(xiàn)共現(xiàn)現(xiàn)象時，由于都占據(jù)較高的權(quán)重，導致文本簽名模糊，反而不利于文本去重。例如有以下文本：

①李白是唐代詩人

簽名值：010011000101000100101101

②李白不是唐代詩人

簽名值：010011000101000100111101

其中，詞語“是”、“不是”就屬于第3類，在幾乎哪一類文本中都有出現(xiàn)，根據(jù)TF-IDF計算得到的權(quán)重很低。而“李白”、“唐代”、“詩人”這些詞屬于前兩類，根據(jù)TF-IDF算法計算得到的權(quán)重較高。如果取權(quán)重前3的詞語作為特征詞，通過傳統(tǒng)Simhash計算兩個文本簽名值距離為1，即使兩個文本內(nèi)容和含義有很大差異也會被判定為重復。而“李白”、“唐代”、“詩人”共現(xiàn)頻率很高，由“李白”一詞幾乎可以代替其他詞語，這樣一來“是”、“不是”就成為影響文本簽名值的特征詞。

(1)TF-IDF算法。

在大數(shù)據(jù)高性能存儲中，文本數(shù)量巨大，將每個文本分詞后所得的詞語數(shù)量會大大增加，為降低計算機運行的時空間復雜度，需要對分詞結(jié)果進行篩選。TF-IDF算法是一種特征提取的方法，可以在盡量保證文本特征信息的同時縮減特征詞的數(shù)量，達到降維目的。其一般表達形式為：

ωdt=tfdt×idf(Nnt)

(2)

其中，ωdt表示特征詞t在文本d中的權(quán)重，tfdt表示特征詞t在文本d中出現(xiàn)的頻率，N表示文本集中文本的總數(shù)，idf(Nnt)表示逆文檔頻率，是對文本集中文本總數(shù)N和特征詞t出現(xiàn)的文本數(shù)目n的比值取對數(shù)，用于權(quán)衡特征詞重要性。在實際應用中，為減少文本長度影響，需要對特征詞權(quán)重進行歸一化處理。在改進的算法中，TFC[15]的應用最為廣泛，其表達式可寫作：

(3)

其中，mdt表示特征詞t在文本d中出現(xiàn)的次數(shù)，Md表示文本d中的特征詞總數(shù)，nt表示文本集中出現(xiàn)特征詞t的文本數(shù)。

(2)Jaccard相似度。

Jaccard系數(shù)是一種二元數(shù)據(jù)對象的相似性度量方法，常用于比較有限樣本集之間的相似性。其表達式為：

(4)

其中，J(x,y)表示二元對象x,y的相似度，f11表示x取1并且y取1的樣本個數(shù)，f01表示x取0并且y取1的樣本個數(shù)，f10表示x取1并且y取0的樣本個數(shù)。在上式中，x取1表示樣本中包含特征詞x，反之則不包含，y同理。在實際應用中，特征詞x,y即使同時出現(xiàn)在多個樣本中，它們出現(xiàn)的次數(shù)也會呈現(xiàn)隨機性。為了消除量綱的影響，對其做了以下改進：

(5)

其中，n表示同時包含特征詞x,y的樣本總數(shù)，xk表示第k個樣本中特征詞x出現(xiàn)的次數(shù)，yk表示第k個樣本中特征詞y出現(xiàn)的次數(shù)。

(3)相似度加權(quán)算法。

在計算特征詞權(quán)重時，在TF-IDF基礎上，根據(jù)Jaccard相似度對權(quán)重進行優(yōu)化。算法簡記為J-Tidf，由其計算得到的權(quán)重表達式為：

(6)

2.2 體現(xiàn)特征詞位置信息的哈希簽名

傳統(tǒng)的Simhash算法基于詞袋模型，無法表征特征詞在文本中出現(xiàn)的位置。例如有以下文本：

①太陽隊總決賽贏了雄鹿隊

簽名值：101110010101000100001100

②雄鹿隊總決賽贏了太陽隊

簽名值：101110010101000100001100

即使兩個文本的內(nèi)容和含義大不相同，使用傳統(tǒng)的Simhash算法也會得到完全相同的簽名值。因此，該文針對文本詞匯位置信息設計一套簽名方案，以量化文本間的特征詞分布差異。

2.2.1 BDR算法

BDR(Binary Dimension Reduction)是Rameshwar等人提出的一種稀疏二進制向量降維算法[16]，旨在通過維度壓縮降低存儲空間和提高計算效率，同時盡可能保留原始向量的特征。在詞袋模型中，大多數(shù)單詞很少出現(xiàn)在文本中。以Twitter為例，每條推文限制為140個字符，如果只考慮英文推文，由于英文詞匯量為171 476個，每條推文都可以表示為171 476維度的稀疏二進制向量，其中1表示存在單詞，0表示不存在。在BDR算法中，這種稀疏性是實現(xiàn)降維的前提[17]。BDR算法(如圖2所示)分為以下幾步：

圖2 BDR算法示例

①映射。對于由01組成的d維二進制向量u和N維向量v，選擇一個隨機函數(shù)，將向量u中的每個比特位映射到向量v上的每個位置。

②奇偶校驗。對于映射到向量v上的每個比特位上的01求和，如果和是奇數(shù)則記為1，否則記為0。

壓縮維度N的邊界為ψ2log2n，與原始向量維度d無關。其中ψ表示數(shù)據(jù)稀疏性，即原始向量集合中出現(xiàn)1的數(shù)量最多的向量中1的個數(shù)，n表示待比較二進制向量個數(shù)。壓縮后的數(shù)據(jù)繼承了原始數(shù)據(jù)的內(nèi)積，其漢明距離總是小于或等于原始數(shù)據(jù)的漢明距離，同時在Jaccard相似性計算上與Minhash保持幾乎相同的準確性。

2.2.2 改進BDR算法用于表示特征詞位置差異

BDR算法在保留數(shù)據(jù)對象內(nèi)積的前提下有效實現(xiàn)了數(shù)據(jù)降維，但是隨著待比較向量數(shù)目n的增加，文本長度增加導致稀疏性系數(shù)ψ變大，這使得壓縮維度N不斷增大。該文對BDR算法進行了改進，將其應用到特征詞位置信息的降維表達上，在損失一定精度的情況下，可以大大降低壓縮維度。改進后的算法簡稱PBDR，流程(如圖3所示)如下：

圖3 改進的BDR算法流程

①生成原始向量。對于每個特征詞，統(tǒng)計其在文本中的位置，生成對應的d維二進制向量u，d表示文本詞匯總數(shù)。對于每個比特位，如果該特征詞在文本第p個位置出現(xiàn)，則向量u的第p位置為1，否則置為0。

②映射。選擇一個隨機函數(shù)，將向量u中的每個比特位映射到f維向量v。在計算向量v的每個位置時，將映射到該位的01值進行求和。

③求均差。對向量v每個位置，先求所有位置上數(shù)值的均值，然后將每個位置上的數(shù)值減去均值，得到該特征詞的均差向量。

④降維。對特征詞的均差向量降維，對于每個比特位，如果大于0則將該比特位置為1，否則置為0。得到反映特征詞位置特征的簽名，記為Sig'。

2.3 融合特征詞詞匯和位置信息的Simhash算法

改進后的算法(P-Simhash算法)主要針對傳統(tǒng)Simhash算法為特征詞賦權(quán)不夠合理、沒有體現(xiàn)文本特征詞分布位置差異的缺點，在哈希、加權(quán)兩個過程中做出改進。算法流程(如圖4所示)如下：

(1)分詞。使用Jieba分詞工具對文本進行分詞，去除特殊符號、停用詞等無關字詞。

(2)哈希。計算權(quán)重并按照權(quán)重大小選取前m個分詞結(jié)果作為特征詞，使用同一哈希函數(shù)計算各個詞的哈希值，得到它們分別對應的f位簽名Sig。

圖4 P-Simhash算法流程

(3)位置特征轉(zhuǎn)換。使用同一映射函數(shù)通過PBDR算法計算各個詞對應的f位位置特征簽名Sig'。

(4)簽名加權(quán)合并。對于上兩步得到的特征詞的兩種特征簽名加權(quán)求和，得到其對應的特征向量SigFnl，計算公式為SigFnl=μ×Sig+(1-μ)×Sig'。在計算每一位時，如果遇到0則先將其置為-1然后再進行運算。

(5)二次加權(quán)。使用J-Tidf算法計算詞的權(quán)重，對每個詞的特征向量SigFnl進行加權(quán)計算。將特征向量對應的每一位上的數(shù)值乘以權(quán)重值，得到每個詞的加權(quán)特征值。

(6)合并。對文本內(nèi)的每個加權(quán)特征值進行累加，得到一個f位向量V。

(7)降維。對向量V降維，對于每個比特位，如果大于0則將該比特位置為1，否則置為0。得到的結(jié)果作為文本的簽名，記為S。

3 實驗及分析

為了檢驗提出的改進算法對重復文本的檢測性能，選擇搜狗新聞數(shù)據(jù)集作為實驗數(shù)據(jù)，對原Simhash算法和改進后的Simhash算法進行對比。主要評估去重率、精確率、召回率和F1值[18]等指標，各指標的表達式如下：

(7)

精確率(Precision)=

(8)

(9)

(10)

3.1 實驗環(huán)境

實驗代碼采用Python語言編寫，測試環(huán)境部署在Windows10操作系統(tǒng)上，硬件環(huán)境為Intel(R) Core(TM) i5-10200HCPU @2.40 GHz 處理器，8 GB內(nèi)存容量，分詞工具采用 Jieba3.0。

3.2 實驗數(shù)據(jù)

數(shù)據(jù)集采用搜狗實驗室中的全網(wǎng)新聞數(shù)據(jù)2012版，收錄了來自若干新聞站點2012年6至7月期間國內(nèi)、國際、體育、社會和娛樂等18個頻道的新聞數(shù)據(jù)，有近10萬條。首先剔除少于100個內(nèi)容的新聞類別，然后再剔除其中字數(shù)小于800的新聞，隨機選取4 246篇新聞進行后續(xù)實驗。前文提及的E-Simhash算法在計算文本簽名時也融入了特征詞分布信息，因此該文也將重點與其進行實驗比較。隨機選取其中的2 831個樣本作為訓練集，用作計算特征詞之間的Jaccard相似度，以優(yōu)化其權(quán)重。在E-Simhash算法對比實驗中，用作計算特征詞的左右信息熵。將剩余的1 515個樣本作為測試集，比較不同算法性能。

3.3 實驗結(jié)果與分析

使用64位二進制01向量作為文本簽名值，在計算簽名值時μ值的選取待實驗后給出。E-Simhash算法選取漢明距離為10并以此為基礎開展實驗，為了保證實驗的客觀性，漢明距離取10。

3.3.1μ的取值對去重率的影響

如2.3中所述，P-Simhash算法在第(4)步計算特征詞對應的向量時，采用加權(quán)合并的方法得到融合位置分布信息的特征向量。對于任意比特位，若Sig和Sig'在該位上相同時μ值大小對結(jié)果無任何影響；當Sig和Sig'在該比特位上不同時，經(jīng)加權(quán)計算得到的值域為|2μ-1|，μ值表征了特征詞位置分布對簽名的影響程度。μ取值越大，特征詞位置分布不同帶來的影響就越大，但是對于自然文本來說，大多數(shù)時候特征詞位置的改變并不影響整個文本的語義。因此，當μ取值超過一定范圍后，算法的去重率反而會下降。圖5顯示了μ在不同取值情況下，運行P-Simhash算法得到對應的去重率。實驗結(jié)果表明，對于實驗選取的搜狗新聞數(shù)據(jù)集，當μ取值在1.4到1.9之間時，P-Simhash的去重率達到比較高的程度。因此，進行后續(xù)的算法性能比較實驗時，參數(shù)選擇μ=1.5。

3.3.2 不同算法性能比較

P-Simhash在計算文本簽名時融入了位置信息，計算的文本簽名能夠體現(xiàn)特征詞位置分布差異的影響；同時在特征詞哈希加權(quán)時降低了共現(xiàn)詞的權(quán)重，避免了關聯(lián)特征詞具有較高權(quán)重導致簽名模糊，因此相比其他算法擁有較高的精確率和召回率。如圖6所示，P-Simhash算法在精確率上以0.946：0.803：0.909分別高于傳統(tǒng)Simhash算法和E-Simhash算法，在召回率上以0.879：0.674：0.813分別高于傳統(tǒng)Simhash算法和E-Simhash算法。F1值是評價去重算法性能的重要指標，在該指標上P-Simhash算法以0.911：0.732：0.858優(yōu)于傳統(tǒng)Simhash算法和E-Simhash算法。

圖5 μ在不同取值下的去重率

圖6 算法性能對比

3.3.3 算法執(zhí)行時間比較

P-Simhash算法在生成文本簽名時加入了詞匯位置特征計算，帶來了一定的時間開銷。為解決這一問題，該文采用前m個特征詞而非全部特征詞計算文本簽名，因此可以節(jié)省大量的哈希運算時間。由圖7可以看出，特征詞權(quán)重幾乎呈指數(shù)下降，當m大于20時，特征詞的權(quán)重值很小，對生成簽名值的影響也有限。因此，選擇權(quán)重前20的特征詞計算文本簽名。

圖7 前m個特征詞的權(quán)重

為了比較不同算法的運行時間，將測試樣本集通過裁剪拼接，調(diào)整每條新聞樣本長度為1 000、2 000、3 000、4 000字，然后分別進行測試。實驗結(jié)果如圖8所示，隨著文本長度不斷增加，算法的執(zhí)行時間也越來越長。P-Simhash算法由于在生成文本簽名時加入了詞匯位置特征計算，有一定的時間開銷，但由于僅使用前20個特征詞計算文本簽名，節(jié)省了特征詞哈希時間，因此P-Simhash算法執(zhí)行時間與Simhash算法幾乎相同。同時，由于無論文本長度變化始終選取前20個特征詞計算文本簽名，因此算法穩(wěn)定性更好。而E-Simhash算法將全部特征詞哈希與其每個位置分別進行異或操作，因此耗費時間更多。

圖8 算法執(zhí)行時間對比

總結(jié)以上實驗結(jié)果可以得出，P-Simhash以0.911：0.732將傳統(tǒng)Simhash的去重效果提高了24.4%，而算法執(zhí)行時間幾乎相等。同時，在時間開銷和去重性能上均明顯優(yōu)于E-Simhash算法。綜合去重性能和算法執(zhí)行效率，提出的P-Simhash算法較其他算法性能更好。

4 結(jié)束語

針對傳統(tǒng)Simhash算法對重復文本檢測精確度不高的問題，采用改進的Jaccard相似度計算方法計算特征詞的關聯(lián)度，適當降低共現(xiàn)詞的權(quán)重，從而將注意力放在可能造成文本差異的部分。對于其無法體現(xiàn)特征詞在文中分布的缺點，引入了二進制維度縮減算法，并在此基礎上進行了改進，以便將特征詞在文本中的位置分布信息映射到低維向量空間。設計了新的特征詞簽名，將詞哈希與其位置信息結(jié)合在一起作為新的特征詞簽名。實驗結(jié)果表明，提出的P-Simhash算法的去重性能較傳統(tǒng)Simhash算法有明顯提高?；赟imhash改進的中文文本去重算法普遍依賴ICTCLAS、Jieba等分詞工具，如不能識別新詞、分詞不準確等會給相似度計算帶來較大影響，在算法的分詞階段還有較大的改進空間。此外，上述算法直接將特征詞進行哈希計算，缺乏衡量近似詞的手段，兩個同義詞的哈希值很可能完全不同，可能導致兩個相似文本相似度很低。下一步將針對詞義的相似程度設計一套獨特的詞簽名方案，以便更好地應用于相似文本檢測工程。