張 航，盛志偉，張仕斌，楊 敏

成都信息工程大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院，成都610225

1 引言

隨著計(jì)算機(jī)與信息技術(shù)的高速發(fā)展以及信息存儲(chǔ)技術(shù)[1]的廣泛應(yīng)用，人們已經(jīng)步入大數(shù)據(jù)時(shí)代[2]，數(shù)字化信息量呈現(xiàn)爆炸式增長(zhǎng)。數(shù)據(jù)量大、復(fù)雜度高以及冗余度高是當(dāng)前大數(shù)據(jù)信息的特點(diǎn)。研究表明，一些存儲(chǔ)系統(tǒng)中的冗余數(shù)據(jù)已經(jīng)達(dá)到了60%[3]，并且會(huì)隨著數(shù)據(jù)量的上升而增多。因此在有限的存儲(chǔ)空間和時(shí)間內(nèi)，如何存儲(chǔ)更多有效精煉的信息成為當(dāng)前研究的熱點(diǎn)。

在去除冗余數(shù)據(jù)方面，Simhash 算法是當(dāng)前公認(rèn)的最好的去重算法。該算法是一種局部敏感哈希算法[4]，它能夠?qū)⒏呔S數(shù)據(jù)進(jìn)行概率降維并映射為位數(shù)較少且固定的指紋，之后再對(duì)指紋進(jìn)行相似度比較來反應(yīng)數(shù)據(jù)之間的相似程度。其中比較算法通常使用海明距離[5]及編輯距離[6]。Simhash算法優(yōu)勢(shì)在于處理速度快，并且結(jié)果準(zhǔn)確度高。

如今，Simhash 算法被廣泛應(yīng)用在近似文本檢測(cè)、冗余數(shù)據(jù)去重、異常檢測(cè)[7]等領(lǐng)域。文獻(xiàn)[8]提出了一種基于多Simhash 指紋算法，利用多種指紋值經(jīng)過k 維多曲面進(jìn)行相似度計(jì)算，有效地解決了指紋單一、信息丟失嚴(yán)重的問題。文獻(xiàn)[9]在Simhash 算法中加入了減值運(yùn)算，對(duì)最后合并的結(jié)果序列串結(jié)果減去一個(gè)閾值T ，從而提升了Simhash算法的準(zhǔn)確性。文獻(xiàn)[10]將Simhash算法和CNN 進(jìn)行結(jié)合用于惡意軟件檢測(cè)，通過轉(zhuǎn)化為灰度圖像提高惡意軟件識(shí)別率和性能。

但是以上對(duì)Simhash 的應(yīng)用都存在一些問題，首先沒有突出關(guān)鍵項(xiàng)在Simhash 指紋中的比重，比如文獻(xiàn)[8]只是簡(jiǎn)單地進(jìn)行了術(shù)語長(zhǎng)度統(tǒng)計(jì)從而確定文章的信息，文獻(xiàn)[9]中設(shè)置關(guān)鍵詞權(quán)重為1，這樣造成嚴(yán)重的信息失真。其次沒有考慮到信息位置分布對(duì)指紋的影響。為了提升Simhash 算法的文本去重效果、準(zhǔn)確率，解決Simhash 算法無法體現(xiàn)分布信息的缺點(diǎn)，引入信息熵的概念，采用熵加權(quán)的方式給文檔中的關(guān)鍵詞進(jìn)行賦權(quán)，優(yōu)化權(quán)重計(jì)算公式，并在hash 計(jì)算中加入關(guān)鍵詞分布信息，從而達(dá)到對(duì)傳統(tǒng)Simhash 算法的優(yōu)化，最后通過仿真實(shí)驗(yàn)論證了該算法的可行性、合理性。

2 相關(guān)問題研究

2.1 Simhash算法的分析

定義1 Simhash 算法的原理是對(duì)于兩個(gè)給定的變量x,y，哈希函數(shù)h 總是滿足下式：

其中，Pr 表示h( x )=h( y )的可能性，sim( x,y )∈[0,1]是相似度函數(shù)，一般也用雅可比函數(shù)Jac(x,y)來表示變量x,y 的相似度，sim( x,y )表示如下：

h 屬于哈希函數(shù)簇F，需要滿足以下條件：

稱F 為(d1,d2,p1,p1)上的敏感哈希簇函數(shù)[11]。其中d( )

x,y 表示x,y 變量之間的距離，通俗而言，表示如果x,y 足夠相似時(shí)，那么它們映射為同一hash 函數(shù)的概率也就足夠大，反之哈希值相等的概率足夠小。

由于傳統(tǒng)hash函數(shù)[12]與Simhash函數(shù)最大的不同在于局部敏感性，如果針對(duì)輸入的數(shù)據(jù)做些局部修改，經(jīng)過傳統(tǒng)hash函數(shù)運(yùn)算后可能會(huì)得到完全不同的結(jié)果，而Simhash 計(jì)算的結(jié)果則很相似，因此可以使用Simhash函數(shù)產(chǎn)生的指紋相似程度來表示源數(shù)據(jù)之間的相似程度。

2.2 Simhash算法流程

Simhash 算法的流程是首先定義一個(gè)f 維度的空間，然后在這個(gè)空間中定義每一個(gè)特征所對(duì)應(yīng)的向量，接著將所有的向量結(jié)合自身的權(quán)重進(jìn)行加權(quán)、求和就得到了一個(gè)和向量作為結(jié)果。最后再對(duì)該結(jié)果進(jìn)一步地進(jìn)行壓縮轉(zhuǎn)化，其規(guī)則是：對(duì)每一個(gè)向量得出一個(gè)相對(duì)應(yīng)的f 位簽名信息，若向量維度的值大于0，則置其簽名所在的位置為1，否則置為0。通過這樣的轉(zhuǎn)化方式，得到的簽名信息表證了此向量在各個(gè)維度中的值的信息。Simhash的算法流程圖如圖1所示。

圖1 Simhash指紋生成

Simhash算法的具體步驟如下：

步驟1 初始化

針對(duì)數(shù)據(jù)集大小及存儲(chǔ)成本確定Simhash 位數(shù)以及f 維向量空間，同時(shí)初始化f 位二進(jìn)制數(shù)S 均置為0。

步驟2 文檔預(yù)處理

主要包含兩部分，第一部分是分詞，尋找文檔的特征詞匯以及去除文檔停用詞等。第二就是賦權(quán)，一般而言這里普遍忽略了權(quán)重的計(jì)算設(shè)置為1[13]。

步驟3 生成hash值

利用傳統(tǒng)的散列算法對(duì)步驟2 中的每個(gè)特征詞計(jì)算一個(gè)f 位hash值，并進(jìn)行下列運(yùn)算：

for k in V ：

for i in f ：

if（i==0）：

Vi=Vi+wki

else：

Vi=Vi-wki

步驟4 壓縮變換

針對(duì)最后生成的向量V ，對(duì)每一位進(jìn)行轉(zhuǎn)化處理。

if V[i]＞0：

S[i]=1

else：

S[i]=0

步驟5 指紋生成

輸出最終的簽名S 作為該文檔的指紋，之后再進(jìn)行海明距離或編輯距離計(jì)算相似度。

步驟6 距離計(jì)算

在Simhash 算法中通常使用海明距離進(jìn)行相似度計(jì)算。海明距離通過比較兩個(gè)文檔指紋中不相同的個(gè)數(shù)來度量?jī)蓚€(gè)文檔之間的相似度[14]。海明距離越大，代表兩個(gè)字符串的相似度越低，反之則兩個(gè)字符串相似度越高。對(duì)于二進(jìn)制字符串而言，可以使用異或運(yùn)算來計(jì)算兩個(gè)二進(jìn)制的海明距離。舉例說明如下：

例1 設(shè)a,b 為兩個(gè)二進(jìn)制數(shù)，其中：

則可知a,b 兩個(gè)二進(jìn)制數(shù)只有第二位不同，故Hamming(a,b)=1。

也可利用異或操作，統(tǒng)計(jì)異或結(jié)果中1 的個(gè)數(shù)。a⊕b=01000，共有1個(gè)1，故海明距離為1。

2.3 Simhash存在的一些問題

傳統(tǒng)Simhash算法在權(quán)重計(jì)算方面通常設(shè)置為1或特征詞出現(xiàn)的次數(shù)，這很容易造成信息丟失，導(dǎo)致最終的Simhash 指紋準(zhǔn)確性降低，并且根據(jù)Simhash 算法可知它不表現(xiàn)出詞匯分布信息，關(guān)鍵特征詞調(diào)整順后，不會(huì)影響最終生成的Simhash指紋。

如圖2所示，兩個(gè)關(guān)鍵詞的位置調(diào)整下就可能導(dǎo)致最終的意義大不相同，但是傳統(tǒng)的Simhash算法生成的指紋卻是一樣的。

3 改進(jìn)的Simhash算法

本文提出了一種新的基于信息熵的Simhash 算法，考慮到傳統(tǒng)Simhash算法中針對(duì)權(quán)重的計(jì)算不充分，以及不能更好地反應(yīng)文檔中詞匯的分布特征，本文中引入信息熵理論來解決上述問題，并且在hash計(jì)算中加入位置關(guān)系特征，從而提升Simhash算法的準(zhǔn)確度。

3.1 熵加權(quán)權(quán)重計(jì)算方法

（1）詞頻-逆向文件頻率

詞頻-逆向文件頻率（TF-IDF）[15]算法是一種常用的文本特征權(quán)重計(jì)算方法，特征詞tk在文檔dj中的TF-IDF值記為tfidf(tk,dj)，有如下定義：

定義2 特征項(xiàng)tk在文檔dj中出現(xiàn)的頻率tf(tk,dj)為：

式中，nj,k表示特征詞tk在文檔dj中出現(xiàn)的次數(shù)，表示文檔dj中的所有特征詞的個(gè)數(shù)。

定義3 反文檔頻率idf(tk,dj)是權(quán)衡特征詞重要性的系數(shù)，其定義為：

式中，{ j:tk∈dj} 為含有特征詞tk的文檔綜述，|D|為語料庫中的文件總數(shù)。

定義4 TF-IDF函數(shù)，特征詞的詞頻權(quán)重定義為：

（2）信息熵

信息熵[16]是由香農(nóng)在1948 年提出的一個(gè)概念，用它來表示在隨機(jī)事件發(fā)生之前的結(jié)果不確定性的量度，以及在隨機(jī)事件發(fā)生之后，人們從該事件中得到的信息量。

根據(jù)信息熵的定義：

其中，X 表示信息概率空間X=(x1:P(x1),x2:P(x2),…,xn:P(xn))，H( )X 表示隨機(jī)變量X 不確定性的量度。（3）左右信息熵

左右熵[17]是指多字詞表達(dá)的左邊界的熵和右邊界的熵。左右熵的公式如下：

式中，W 表示某個(gè)單詞，El(W)表示該單詞的左熵，P( a W|W )表示該單詞左側(cè)出現(xiàn)不同詞的概率，a 變量是一個(gè)變化值，表示與W 相結(jié)合的詞匯。Er(W)右熵同理。

（4）熵加權(quán)計(jì)算法

本文采用熵加權(quán)計(jì)算方法這里對(duì)特征詞左右信息熵取平均。用Hk(w)來表示該單詞的熵信息量。把熵因子Hk加入權(quán)值計(jì)算公式中，取兩者的平方平均數(shù)作為詞權(quán)重，如下所示：上式的物理意義為：特征項(xiàng)tk在文檔dj中出現(xiàn)的次數(shù)越多，在訓(xùn)練集中出現(xiàn)該特征項(xiàng)的文檔越少，并且其信息量越大，則其權(quán)重越高。

3.2 基于熵加權(quán)的Simhash算法

基于信息熵的Simhash 算法主要是在權(quán)重方面進(jìn)行優(yōu)化，首先利用基于TF-IDF 算法與信息熵進(jìn)行加權(quán)得到權(quán)重，并按照其在文檔中的分布進(jìn)行排序，針對(duì)每個(gè)特征詞匯生成的hash再與其所在位置進(jìn)行異或。

但是經(jīng)過改進(jìn)的權(quán)重計(jì)算后，由于訓(xùn)練集的不完整等因素，會(huì)導(dǎo)致部分特征次權(quán)重過大，最終引起查準(zhǔn)率下降，為了解決這一問題，引入權(quán)重閾值Wt。下面就權(quán)重不均導(dǎo)致的問題進(jìn)行證明。

設(shè)一個(gè)文檔中提取出n 個(gè)關(guān)鍵詞分別為{p1,p2,…,pn}，各關(guān)鍵詞的權(quán)重為W={w1,w2,…,wn}。對(duì)n 個(gè)關(guān)鍵詞生成hash 值，其結(jié)果為H={h1,h2,…,hn}，經(jīng)過疊加后生成二級(jí)指紋F={f1,f2,…,fm} ，m 為指紋位數(shù)，最后根據(jù)F 中fi是否大于0生成Simhash指紋為S。

若存在某一特征詞pk，其權(quán)重：

則S 主要由pk決定。證明如下：

設(shè)hi={ai1,ai2,…,aim},aij是一個(gè)二進(jìn)制變量，則：

提取出wk，則有：

因wk?wj，故：

所以此時(shí)：

最終有F 主要與pk相關(guān)，證明完成。

以上證明同時(shí)也反映出權(quán)重對(duì)Simhash 指紋的影響。

引入權(quán)重閾值后，此時(shí)的權(quán)重計(jì)算如式（13）所示。

綜上所述，E-Simhash算法流程如圖3所示。

圖3 E-Simhash算法過程

E-Simhash 算法與傳統(tǒng)的Simhash 算法有三點(diǎn)不同，這里主要在TF-IDF 的基礎(chǔ)上引入信息熵進(jìn)行特征詞權(quán)重計(jì)算，并使用兩者的平方平均數(shù)作為最后的特征詞權(quán)重，同時(shí)為了避免權(quán)重過高的情況導(dǎo)致指紋失真，引入權(quán)重閾值，計(jì)算方式如式（16）所示。最后在生成特征詞hash 時(shí)與特征詞位置進(jìn)行異或，使其hash 包含文檔的位置分布信息。

4 仿真實(shí)驗(yàn)與分析

本章主要模擬真實(shí)的應(yīng)用場(chǎng)景，驗(yàn)證E-Simhash 算法的性能是否比傳統(tǒng)Simhash算法優(yōu)越。

4.1 實(shí)驗(yàn)環(huán)境及數(shù)據(jù)集

實(shí)驗(yàn)環(huán)境部署在一臺(tái)臺(tái)式機(jī)上，機(jī)器參數(shù)如表1所示。

數(shù)據(jù)集來自搜狗實(shí)驗(yàn)室中的全網(wǎng)新聞數(shù)據(jù)2012版，它是來自多家新聞?wù)军c(diǎn)近20個(gè)欄目的分類新聞，剔除低于800 字符的數(shù)據(jù)，并從中隨機(jī)選取1 565 篇進(jìn)行后續(xù)實(shí)驗(yàn)。

首先從1 565篇新聞中，根據(jù)修改比例，隨機(jī)選取若干篇新聞進(jìn)行修改、刪除、移位、替換等隨機(jī)操作，并控制修改后的文章與原始文章有一定閾值T 的相似度，生成待測(cè)樣本集，之后使用傳統(tǒng)Simhash與本文中的算法進(jìn)行比較，統(tǒng)計(jì)實(shí)驗(yàn)的相關(guān)指標(biāo)。

表1 實(shí)驗(yàn)環(huán)境參數(shù)

4.2 實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)結(jié)果中常用四種指標(biāo)進(jìn)行評(píng)估，分別是去重率、查準(zhǔn)率、召回率以及F 值[18]，其中去重率是指分類正確的樣本數(shù)與總樣本的比值，就本實(shí)驗(yàn)而言即預(yù)測(cè)為同源文章集數(shù)與總文章數(shù)的比值。

實(shí)驗(yàn)1 去重率對(duì)比

在1 565 篇新聞中隨機(jī)選取1 162 篇進(jìn)行任意修改，選取不同的海明距離，對(duì)比兩種算法中的準(zhǔn)確率，實(shí)驗(yàn)中T =15%，即每篇新聞保持不超過15%修改，指紋長(zhǎng)度為128 位，詞權(quán)重閾值Wt=90，實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 不同海明距離下去重率對(duì)比

實(shí)驗(yàn)結(jié)果表明在海明距離大于2 時(shí)，E-Simhash 算法均具有很高的去重率。在實(shí)際應(yīng)用中海明距離一般取10左右，所以E-Simhash算法的去重效果更好。

實(shí)驗(yàn)2 修改T 閾值對(duì)比

本次實(shí)驗(yàn)修改文本的相似度閾值T ，分別對(duì)5%、10%、15%、20%的修改下，海明距離選為10，即低于10 則認(rèn)為相似，比較兩種算法的去重率，結(jié)果如圖5所示。

圖5 不同閾值下去重率對(duì)比

從實(shí)驗(yàn)結(jié)果中可知，E-Simhash 算法去重率分別以0.833∶0.679、0.751∶0.529，0.687∶0.476、0.661∶0.451優(yōu)于傳統(tǒng)的Simhash 算法，并且隨著文章變動(dòng)的增加，其去重率都呈現(xiàn)下降趨勢(shì)。實(shí)驗(yàn)結(jié)果表明在不同修改閾值T 下，E-Simhash算法均優(yōu)于傳統(tǒng)的Simhash算法。

實(shí)驗(yàn)3 查準(zhǔn)率、召回率以及F 值對(duì)比

在實(shí)驗(yàn)中，從新聞集中隨機(jī)選取一篇文章進(jìn)行隨機(jī)修改，并保證與原文有90%的相似度，對(duì)比基于Simhash指紋與E-Simhash 算法的查準(zhǔn)率、查全率以及F1 值。其中海明距離選取10；實(shí)驗(yàn)進(jìn)行100 次，并取它們的平均值，作為最終結(jié)果，結(jié)果如圖6所示。

圖6 綜合性能比較

通過實(shí)驗(yàn)數(shù)據(jù)可知，E-Simhash 算法在查準(zhǔn)率0.963∶0.818，召回率0.867∶0.621，F(xiàn)1 值0.912∶0.706 優(yōu)于傳統(tǒng)的Simhash算法。結(jié)果表明E-Simhash算法在查準(zhǔn)率、召回率以及F 值方面均比普通的Simhash算法有很大的提升，也足以證明E-Simhash算法的優(yōu)越性。

5 總結(jié)與展望

針對(duì)傳統(tǒng)Simhash 算法在權(quán)重計(jì)算方面的欠缺，以及算法中不能考慮到文檔特征詞匯的分布信息，本文通過優(yōu)化權(quán)重計(jì)算，使用TF-IDF 和信息熵的平方平均數(shù)作為特征詞的權(quán)重值，考慮到部分權(quán)重過大導(dǎo)致信息失真，引入權(quán)重閾值，并在此基礎(chǔ)上將特征詞的位置信息引入到hash 計(jì)算中去，從而提升Simhash 算法的去重率、查準(zhǔn)率，并通過仿真實(shí)驗(yàn)論證了E-Simhash算法在各方面均優(yōu)于傳統(tǒng)的Simhash 算法，但是E-Simhash 算法依然存在一些不足，在短文本相似度檢測(cè)方面準(zhǔn)確度不高，而且本文中的權(quán)重計(jì)算方法仍有可改進(jìn)之處，計(jì)算中的關(guān)鍵詞權(quán)重未必非常準(zhǔn)確，未來可通過優(yōu)化權(quán)重計(jì)算，如引入LDA主題模型[19]可提升Simhash算法的適應(yīng)范圍。