基于Simhash的大規(guī)模文檔去重改進算法研究

王 誠，王宇成

(南京郵電大學 通信與信息工程學院，江蘇 南京 210003)

0 引 言

隨著大數(shù)據(jù)時代的到來[1]，數(shù)據(jù)化信息增長迅速，與此同時，數(shù)據(jù)占用空間越來越大，如此海量的數(shù)據(jù)帶來了巨大的存儲問題。研究發(fā)現(xiàn)，存儲的數(shù)據(jù)中冗余數(shù)據(jù)的比例大于六成，并且接下來有繼續(xù)增加的勢頭。冗余數(shù)據(jù)降低了用戶檢索和查詢數(shù)據(jù)的效率，并且大量的存儲資源浪費于存儲冗余數(shù)據(jù)。因此相似性文檔檢測和去重已經(jīng)逐漸成為國內(nèi)外重要的研究課題[2]。

目前關(guān)于相似性文檔檢測和去重的主要算法有Simhash、Minhash和Bitmap[3]。文中就Simhash算法進行研究和改進，以期提高原Simhash算法的效率和準確率。

1 Simhash算法簡介

傳統(tǒng)的哈希算法通過計算將輸入數(shù)據(jù)映射成特定長度的哈希值輸出，輸入數(shù)據(jù)的差異越大，映射出的簽名值差異也越大。但傳統(tǒng)的哈希算法，如SHA-1、MD5，對1比特差距的輸入數(shù)據(jù)都會產(chǎn)生完全不同的輸出哈希值[4]，因此無法檢測出相似文檔，需要對原哈希算法進行改進，使得相似文檔可以輸出相似的哈希值。

Simhash算法[5-6]是一種改進的哈希算法，旨在解決相似數(shù)據(jù)的去重，從而高效地識別出輸入數(shù)據(jù)是否相似。Simhash算法主要有兩個步驟：

第一步：hash值的計算。

首先初始化，每一篇文檔內(nèi)容對應一個初始化為0長度為f的簽名S，和一個初始化為0的f維向量V。然后通過分詞庫對文檔內(nèi)容進行分詞，過濾掉一些語氣詞、助詞，并去掉干擾符號后將文檔內(nèi)容轉(zhuǎn)換為一組特征詞，特征詞的權(quán)重為該特征詞在文檔中出現(xiàn)的次數(shù)。再將所有特征詞使用相同的哈希函數(shù)映射為長度為f的簽名h，遍歷h的每一位，若h的第i位為1(i介于1到f之間)，V的第i位加上該特征詞的權(quán)重，否則減去。最后遍歷V，如果V的第i位大于0，簽名S的第i位置為1，否則置為0。最終生成的簽名S就是文檔內(nèi)容對應的Simhash簽名。

第二步：對Simhash簽名值使用海明距離[7]對比檢索。

兩個Simhash簽名值的海明距離計算很容易，但當文檔規(guī)模非常大時，不可能采用逐個比較的方式。對此，Google提出了解決方法，使得效率大幅提升[8]，下面舉例進行闡述。

假設(shè)f為64位，如需找出海明距離小于等于3的Simhash簽名，通過抽屜原理可知，平分為4個部分的Simhash簽名，至少有一個部分是完全相同。因此將64位Simhash簽名平分為4個部分，每部分16位，將每部分16位作為key，包含16位key的簽名作為value存在Redis中。對于一個待比較的簽名，使用相同方式均分為4個部分，每個部分和Redis存在的對應部分key作比較，只有這部分key完全相同的情況，才會從Redis中取出key所對應的value，并進行海明距離的計算。這種方法能夠大量減少海明距離的計算量[9]。

現(xiàn)令k為3[10]，將64位簽名平分為4部分，每部分16位，key有216個。假設(shè)數(shù)據(jù)庫中已有233篇文檔，每個key下平均有131 072(233-16)個簽名，再來一篇新的文檔需要計算海明距離數(shù)目為524 288(4×131 072)個，大大減少了海明距離的計算量[11]。

需要綜合考慮空間和時間復雜度，key的位數(shù)越多空間占用越高，空間復雜度也就越高，不過，此時每個key對應下的簽名越少，時間花費越少，時間復雜度也就越低。

2 改進Simhash算法

2.1 文檔相似度的改進

傳統(tǒng)的兩篇文檔相似度定義為，兩篇文檔內(nèi)容對應Simhash簽名值之間的海明距離。不過單一考慮文檔內(nèi)容比較片面，存在誤差。為了減少誤差，文中將兩篇文檔的相似度定義為文檔內(nèi)容的相似度和文檔其他信息的相似度權(quán)重加。文檔內(nèi)容的相似度使用改進Simhash算法計算，文檔其他信息的相似度使用最小哈希算法計算。下面給出文檔其他信息相似度的計算方法。

文檔其他信息包括文檔關(guān)鍵字、文檔標簽、文檔引用文獻等，用集合的形式表示?，F(xiàn)假設(shè)文檔中所有其他信息集合為{a,b,c,d,e},文檔s1含有其他信息集合為{a,b},文檔s2含有的其他信息集合為{b,c,d},文檔s3的集合為{a,d,e},文檔s4的集合為{d,e}，將這一系列集合組成特征矩陣，如圖1所示。

圖1 特征矩陣

圖1表示的特征矩陣的行表示文檔其他信息組成的集合，列表示文檔集合。計算文檔其他信息的相似度，就是計算特征矩陣對應列之間的jaccard相似度。因為特征矩陣十分稀疏，使用最小哈希的方法來計算。

先對矩陣進行隨機打亂，文檔其他信息(即為矩陣中的對應列)的最小哈希值，為矩陣對應列第一個值為1的行號。最小哈希函數(shù)設(shè)為h，最小哈希函數(shù)用于模擬對矩陣所進行的隨機打亂，特征矩陣兩列之間的jaccard相似度為對應列打亂后最小哈希值相同的概率。

當特征矩陣規(guī)模很大時，對其進行隨機打亂是非常耗時的，而且還要進行多次。為此使用多個哈希函數(shù)來模擬隨機打亂，具體做法為：假設(shè)要進行n次隨機打亂，選用n個隨機函數(shù)h1,h2,…,hn來模擬這一效果，步驟如下：

SIG(i,c)表示簽名矩陣第i個哈希函數(shù)在第c列上的值。SIG(i,c)初始化為Inf(無窮大)，再對r行進行以下步驟：

(1)計算h1(r),h2(r),…,hn(r)；

(2)對特征矩陣的每一列c。如果c所在的第r行為0，不做任何操作；如果c所在的第r行為1，則對于每個i=1,2,…,n，SIG(i,c)和hi(r)中的較小值設(shè)為SIG(i,c)。

計算圖1特征矩陣，a,b,c,d,e對應0，1，2，3，4，5行，選用哈希函數(shù)h1(x)=(x+1)mod5，h2(x)=(2×x+1)mod5，函數(shù)中的x表示行號，遍歷完所有行，最終的簽名矩陣如圖2所示。

圖2 最終簽名矩陣

文檔其他信息組成的特征矩陣轉(zhuǎn)化為簽名矩陣，通過簽名矩陣來估計特征矩陣對應列之間的jaccard相似度，也就是估計文檔其他信息的相似度。最終通過文檔內(nèi)容的相似度和文檔其他信息的相似度計算文檔的相似度，將A,B兩篇文檔間的相似度定義為：

(1-μ)minHash(A,B)

(1)

其中，Haming(A,B)表示A,B兩篇文檔內(nèi)容的海明距離，通過改進的Simhash計算得到，加一是為了保證當A,B兩篇文檔內(nèi)容的海明距離為0時，分數(shù)不會為無窮大；minHash(A,B)表示A,B兩篇文檔其他信息的相似度，通過最小哈希算法計算得到；μ的取值一般為0.8～0.9，兩篇文檔的相似度還是以內(nèi)容的相似度為主。

2.2 文檔特征權(quán)值的改進

傳統(tǒng)Simhash算法以文檔分詞識別出的關(guān)鍵詞為特征值，權(quán)重為該關(guān)鍵詞出現(xiàn)的次數(shù)。由于權(quán)重僅由單詞出現(xiàn)的次數(shù)來決定，部分重要信息會丟失，導致最終計算出的Simhash簽名值的準確性降低。為解決這一問題，綜合使用TF-IDF[12]技術(shù)和單詞的主題相關(guān)性計算關(guān)鍵詞權(quán)重。

TF-IDF技術(shù)用于計算一個關(guān)鍵詞在一個文檔集中的一篇文檔的重要性，TF表示關(guān)鍵詞在這篇文檔出現(xiàn)的頻率，關(guān)鍵詞ti的TF定義為:

(2)

逆向文檔頻率IDF，表示關(guān)鍵詞所在文檔在文檔集所有文檔中的比重，定義為：

(3)

其中，|D|表示ti文檔集中的文檔總數(shù)；|{j:ti∈dj}|表示含有關(guān)鍵詞的文檔的數(shù)量(ni,j不為0的文檔)。

關(guān)鍵詞i在文檔j的TD-IDF定義為：tf-idfi,j=tfi,j×idfi。TD-IDF的局限是在文檔集出現(xiàn)次數(shù)越多，重要性就一定越小，這對于部分文檔來說存在誤差，有些重要單詞在文檔集中的出現(xiàn)次數(shù)也很大，需要給這些單詞更大的權(quán)重。

文中使用單詞的主題相關(guān)性作為附加權(quán)重，將專業(yè)術(shù)語詞匯的長度作為判斷單詞主題相關(guān)性的依據(jù)。選用CSSCI關(guān)鍵詞庫中的關(guān)鍵詞作為數(shù)據(jù)集，統(tǒng)計數(shù)據(jù)集中10 000個中文術(shù)語的長度，并進行正態(tài)擬合，如圖3所示。

圖3 中文術(shù)語長度擬合

圖3所示的擬合正態(tài)分布函數(shù)為：

(4)

擬合得到的正態(tài)分布函數(shù)均值μ=4.51，標準差σ=2.207，μ的置信度為95%的置信區(qū)間[4.214,4.806],σ的置信度為95%的置信區(qū)間[1.787,2.627]。擬合得到的R square為擬合函數(shù)的確定系數(shù)，越接近1，表示擬合函數(shù)對實際數(shù)據(jù)的解釋能力越好。此次擬合得到的R square為0.949 9，較接近1，說明擬合方程具有較好的解釋能力。將正態(tài)分布函數(shù)歸一化得到：

將歸一化得到的中文術(shù)語長度函數(shù)len(x)作為單詞的主題相關(guān)性函數(shù)。其中x表示單詞的長度，可以看出長度越接近4.5，函數(shù)值越高，單詞的主題相關(guān)性也越高。使用單詞主題相關(guān)性函數(shù)作為附加的權(quán)重，可以提高TF-IDF技術(shù)判斷單詞權(quán)重的準確性。最終得出關(guān)鍵詞x的權(quán)重計算公式為：

w(x)=tfx,j×idfx×(1+len(x))

(6)

其中，tfx,j×idfx為關(guān)鍵詞x在文檔j的TF-IDF值；len(x)為單詞x的主題相關(guān)性函數(shù)。

2.3 Simhash簽名值檢索階段的改進

Simhash簽名值檢索階段使用哈希到桶的方法選出候選對，具體做法為將簽名值分塊，對同塊的簽名值使用相同的哈希函數(shù)，映射到桶，哈希到同一個桶中元素為候選對。此時可能會出現(xiàn)分布不均勻的情況，大量元素被哈希到了同一個桶，這個桶中的所有元素都是候選對，需要進行大量海明距離計算。

文中通過設(shè)定閾值的方法解決這個問題。當一個桶中元素超過此閾值，對桶中元素所屬簽名值除去桶中元素后再次分塊，對同塊的簽名值使用相同的哈希函數(shù)，二次哈希映射仍被映射到同一個桶中元素為候選對，可以減少候選對數(shù)量，使分布更加均勻。

具體步驟為：

(1)檢查每一個桶中的元素，判斷元素數(shù)量是否超過閾值，閾值定義為(1+μ)×AVEn，其中AVEn為桶中元素的平均值，μ為權(quán)重。

(2)當一個桶中的元素超過這個閾值時，對桶中元素所屬的簽名值除去桶中元素塊后，再次分塊，將同一塊的簽名值使用相同的哈希函數(shù)，進行二次哈希，二次哈希映射到相同桶中的元素作為候選對。

例如一共有233(將近10億篇文檔)，每篇文檔每部分簽名為16位，則桶數(shù)組數(shù)目為65 536(216)個，每個桶的平均元素個數(shù)為131 072(233-16)個，則AVEn=131 072，現(xiàn)取μ為2，則當某個桶中的元素超過(1+2)×131 072=393 216時進行二次哈希，二次哈希的桶數(shù)組數(shù)目為4 096(212)個，此時依舊被哈希到同一個桶的元素作為候選對進行海明距離計算。

3 實驗結(jié)果及分析

3.1 實驗參數(shù)選取

仿真環(huán)境采用聯(lián)想Lenovo U41電腦，處理器為Intel CORE i7，系統(tǒng)為64位Windows10，分詞系統(tǒng)選用NLPIR，算法采用Java語言實現(xiàn)。

選擇當下較為熱門的互聯(lián)網(wǎng)、醫(yī)療、教育、AI、住房五大主題作為實驗數(shù)據(jù)，對原Simhash算法和改進后的Simhash算法進行對比試驗。每個主題從數(shù)據(jù)庫中選取1 000條相似數(shù)據(jù)，并混入5 000條不相關(guān)數(shù)據(jù)。

選用準確率和召回率來評估算法，定義如下:

(7)

(8)

3.2 實驗步驟

文檔集為互聯(lián)網(wǎng)、醫(yī)療、教育、AI、住房五大主題中的1 000條相似數(shù)據(jù)和混入的5 000條不相關(guān)混雜數(shù)據(jù)。

(1)計算文檔集中文檔其他信息組成的特征矩陣，并使用最小哈希算法將特征矩陣轉(zhuǎn)化為簽名矩陣，對特征矩陣進行100次隨機打亂，選用的隨機哈希函數(shù)為hi(x)=(x+i)mod100(i=1,2,…,100)。

其中μ取0.9，當兩篇文檔間的相似度小于0.25時為相似文檔。

(4)使用原Simhash算法和改進Simhash算法(第三步的文檔間相似度計算方法)計算文檔集的召回率和準確率。以AI主題為例，準確率的計算方法為找出的相似文檔數(shù)目為分母，找出的相似文檔中屬于AI主題中的1 000條相似數(shù)據(jù)的數(shù)目為分子，召回率的計算方法為1 000為分母，找出的相似文檔中屬于AI主題中的1 000條相似數(shù)據(jù)的數(shù)目為分子。

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

通過圖4與圖5可以發(fā)現(xiàn)，改進的Simhash算法具有較高的準確率(約94%)和較高的召回率(約92%)。

改進的Simhash算法從多個維度，包括文檔內(nèi)容、文檔關(guān)鍵字、文檔標簽、文檔引用文獻等綜合計算文檔的相似度，所以準確率較高。該算法綜合使用TF-IDF技術(shù)和單詞的主題相關(guān)性計算關(guān)鍵詞權(quán)重，所以召回率較高且波動很小。

為研究算法效率，每秒的數(shù)據(jù)訪問量不斷增加，比較原Simhash算法和改進的Simhash算法的執(zhí)行時間，如圖6所示。

圖4 準確率對比

圖5 召回率對比

圖6 執(zhí)行時間對比

可以看出，改進Simhash算法由于在檢索步驟中，在哈希到桶的時候應對分布不均勻的情況進行了二次哈希，減少了候選對的數(shù)量并且使分布更加均勻，可以在較短的時間內(nèi)完成相同的數(shù)據(jù)量，因此執(zhí)行效率較高。

4 結(jié)束語

基于Simhash算法的思想，提出了一種改進的Simhash算法，優(yōu)化了文檔的相似度和關(guān)鍵詞權(quán)重的計算方法，并且在哈希到桶的時候應對分布不均勻的情況，進行二次哈希，減少候選對的數(shù)量并且使分布更加均勻。實驗結(jié)果證明，改進Simhash算法提高了原Simhash算法的準確率和召回率，并且執(zhí)行效率較高。改進Simhash算法具有一定的可行性，可以給相關(guān)應用提供參考，可以提高相似性文檔檢測和去重的效率和準確率。