相似資料檢測算法

相似資料檢測算法對給定的一對資料序列計算兩者之間的相似度([0,1], 1表示完全相同)或距離([0, ), 0表示完全相同)，進而度量資料之間的相似程度。相似資料檢測在資訊科學領域具有非常重要的應用價值，比如搜尋引擎檢索結果的聚類與排序、資料聚類與分類、Spam檢測、論文剽竊檢測、重複資料删除、Delta資料編碼等應用。正是由于它的重要性，近年來成為了研究的重點，不斷有新檢測方法湧現并得到評估。其中，Broder提出的shingling算法和Charikar的simhash算法被認為是目前為止最好的算法。

對于相似資料檢測，最為簡單地可以采用類似Unix diff的方法。Unix diff對文檔進行逐行對比來檢測相似檔案，它采用經典的LCS(Longest Common Subsequence，最長公共子串)算法，運用動态規劃方法來計算相似性。LCS的含義是同時包含在字元串裡的一個最長字元序列，LCS的長度作為這兩個字元串相似性的度量。Diff算法以整行作為"字元"來計算最長公共子串，性能上比字元級的LCS算法快很多。這種方法效率很低，而且隻适用文本檔案的相似比較，不能直接适用于二進制檔案。為此，研究者們提出為每個文檔提取一組特征，這樣将檔案相似性問題轉換為集合相似性問題，如基于shingle的計算方法。這種方式的核心思想是為每個檔案提取組特征值，以特征值集合來計算相似性，進而降低空間和計算複雜性來提高性能。

經過對shingle算法和simhash算法以及筆者基于bloom filter實作算法的分析，相似資料檢測算法大緻流程如下：

(1) 将資料段分解成一組shingle(即子序列或資料塊)，可以采用定長、變長、單詞或段落(文本檔案)等分塊算法；

(2) 為了降低空間和時間計算複雜性，可以對shingle集合進行抽樣，比如Min-Wise，Modm，Mins方法；

(3) 基于標明的shingle集合為資料檔案抽取特征，通常是為每個shingle計算hash值組成的序列作為特征值；

(4) 為了降低空間和時間計算複雜性，可以對檔案特征進行降維處理，比如simhash和bloom filter；

(5) 基于檔案特征計算兩個資料對象之間的相似性，計算方法有Cosine、Overlap、Dice、Jaccard或Hamming距離。

Shingle算法

Shingle算法的核心思想是将檔案相似性問題轉換為集合的相似性問題，集合的相似性度量方法主要有resemblance 和containment兩種，其定義如下。

|shingle(f1, w) ∩ shingle(f2, w)|

　Rw(f1, f2) = ----------------------------------------------

|shingle(f1, w) ∪ shingle(f2, w)|

|shingle(f1, w) ∩ shingle(f2, w)|

　Cw(f1, f2) = ----------------------------------------------

|shingle(f1, w)|

數量較大時，如果對所有shingle進行相似性處理則系統開銷較大，包括記憶體和CPU資源。這時就可以考慮對shingle集合進行抽樣，以降低空間和時間計算複雜性，但同時由于樣本覆寫率有限，相似性精确度會有所降低。shingle取樣主要有三種方法，即Min-Wise，Modm，和Mins。Min-Wise技術是通過将shingle的長度w和整數值進行映射産生随機哈希的公共集，在此相同的模式下進行随機最小獨立置換的采樣，進而得到采樣集合；Modm 技術是通過在與Min-Wise同樣的公共映射集中選擇所有模m為0 的哈希值對應的shingle組成取樣集合；Mins技術同樣也是先将shingle和整數集進行映射，然後從中選擇最小s個元素組成取樣集合。此外，還可以使用shingle的hash值代表shingle進行相似性計算，能夠節省一定計算開銷。

Simhash算法

Shingle算法的空間和時間計算複雜性都比較高，對于大資料集的Simlarity Join問題将難以适用。Charikar的simhash算法的核心思想是用一個b位的hash值來表示檔案的特征值，然後使用simhash之間的Hamming距離來衡量相似性。Hamming距離的定義為，兩個二進制序列中對應位不同的個數。simhash的計算方法如下：

(1) 将一個b維的向量V初始化為0，b位的二進制數s初始化為0;

(2) 對每一個shingle，用hash函數(如MD5, SHA1)計算一個b位的簽名h。對i=1到b，如果h的第i位為1，則V的第i個元素加上該特征權重；否則，V的第i個元素減去該特征權重；

(3) 如果V的第i個元素大于0，則s的第i位為1，否則為0；

(4) 輸出s作為simhash。

與傳統hash函數相比，simhash具有一個這樣的顯著特征，即越相似的檔案具有越相似的simhash值，也就是說Hamming距離越小。顯而易見，Simhash僅使用b位的hash值來表示檔案 的特征，節省了大量的存儲開銷；Hamming距離計算簡單高效，Simhash使用Hamming距離來衡量相似性，計算複雜性得到大大降低。簡而言之，simhash算法通過對檔案特征的降維，有效解決了Shingle算法的高空間和時間計算複雜性問題。然而，simhash算法的精确度也會有所損耗，并且與simhash的位數b有關，b越大精确度越高。

Bloom filter算法

與Simhash算法本質相似，Bloom filter算法的核心思想也是着眼于檔案特征的降維，它使用Bloom filter資料結構來表示特征值。Bloom filter是一個空間效率很高的資料結構，它由一個位數組和一組hash映射函數組成。Bloom filter可以用于檢索一個元素是否在一個集合中，它的優點是空間效率和查詢時間都遠遠超過一般的算法，缺點是有一定的誤識别率和删除困難。使用Bloom filter進行相似資料檢測，可以彌補shingle中應用特征集交集計算檔案相似性所導緻的高計算和存儲空間開銷，在性能與相似性比對精度之間取得平衡。Bloom filter構造方法如下：

(1) 構造一個m位的bloom filter資料結構bf，并将所有位初始為0；

(2) 標明兩個hash函數作為映射函數，分别為hash1，hash2；

(3) 對每一個shingle，分别應用hash1和hash2，并對bf相應比特位置1；

(4) 輸出bf作為檔案特征值。

這樣，兩個檔案相似性計算就轉換成兩個bloom filter的相似性計算，越相似的檔案在它們的bloom filter中有更多共同的1。由于Bloom filter具有有限的誤識别率的特性，相似性算法精确度取決于Bloom filter的大小，越大則精确度越高，同時存儲空間消耗也越大。Bloom filter同樣可以使用Hamming距離衡量相似性，也可以使用Cosine、Overlap、Dice、Jaccard等方法來度量。Hamming距離前面已有定義，這裡介紹一下後四種方法的計算公式。

dot(x, y)

Cosine_sim(x, y) = -----------------

sqrt(|x|.|y|)

dot(x, y)

Overlap_sim(x, y) = -----------------

min(|x|, |y|)

2.dot(x, y)

Dice_sim(x, y) = -----------------

|x| + |y|

dot(x, y)

Jaccard_sim(x, y) = ------------------------

|x| + |y| - dot(x, y)

其中，dot(x, y) = Σx[i].y[i]，在這裡相當于兩個Bloom filter資料結構中同時為1的位數；|x|表示bloom filter資料結構中為1的位數。相似性計算函數如下：

static double bloom_sim(BLOOM *bloom1, BLOOM *bloom2) { int i, r1, r2; int c1 = 0, c2 = 0, comm = 0; double sim; for (i = 0; i < BLOOM_ARRAY_SZ; i++) { r1 = bloom_check(bloom1, 1, i); r2 = bloom_check(bloom2, 1, i); if (r1 && r2) { comm++; c1++; c2++; } else { if (r1) { c1++; } if (r2) { c2++; } } } //sim = comm/(sqrt(c1) * sqrt(c2)); //sim = comm/1.0/(c1 + c2 - comm); //sim = comm*2.0/(c1 + c2); sim = comm*1.0/(c1<c2?c1:c2); return sim; }

三種算法對比

Shingle算法的空間和計算複雜性高，相似性精度也高，适合資料量不大且對精度要求高的應用。Simhash和bloom filter算法在空間消耗和計算複雜性方面都優于Shingle算法，但是精度有所損耗，取決于simhash的長度和bloom filter的大小。simhash的長度通常為64位或128位，這個基本可以滿足應用的需求，可以根據實際需求增大位數。bloom filter要大于simhash長度，可以根據最大shingle數的兩倍來估算，精度方面也要優于simhash。由于hash函數的碰撞問題，simhash和bloom filter算法可能出現誤判現象，即不相似的檔案可能會判定為相似的。總結一下，通常情況下，檔案特征值存儲空間消耗方面，Shingle > bloom filter > simhash；相似性計算精度方面，Shingle < bloom filter < simhash。Bloom filter算法往往是比較折中的相似資料檢測方法選擇，但海量資料集的相似性計算往往采用simhash算法，在計算性能方面具有很大優勢，而且更加适合MapReduce計算模型。