1、相似數據檢測算法分類：計算機理論數據結構與算法2011-10-22 22:21 4893人閱讀評論(20)收藏舉報 相似數據檢測算法對給定的一對數據序列計算兩者之間的相似度(0,1, 1表示完全相同)或距離(0, ), 0表示 完全相同)，從而度量數據之間的相似程度。相似數據檢測在信息科學領域具有非常重要的應用價值，比如 搜索引擎檢索結果的聚類與排序、數據聚類與分類、Spam檢測、論文剽竊檢測、重復數據刪除、Delta數 據編碼等應用。正是由于它的重要性，近年來成為了研究的重點，不斷有新檢測方法涌現并得到評估。其 中，Broder提出的shingling算法和Charikar的simhash算

2、法被認為是目前為止最好的算法。對于相似數據檢測，最為簡單地可以采用類似Unix diff的方法。Unix diff對文檔進行逐行對比來檢測相似 文件，它采用經典的LCS(Longest Common Subsequence，最長公共子串)算法，運用動態規劃方法來計 算相似性。LCS的含義是同時包含在字符串里的一個最長字符序列，LCS的長度作為這兩個字符串相似性 的度量。Diff算法以整行作為字符來計算最長公共子串，性能上比字符級的LCS算法快很多。這種方法 效率很低，而且只適用文本文件的相似比較，不能直接適用于二進制文件。為此，研究者們提出為每個文 檔提取一組特征，這樣將文件相似性問題轉換為集

3、合相似性問題，如基于shingle的計算方法。這種方式 的核心思想是為每個文件提取組特征值，以特征值集合來計算相似性，從而降低空間和計算復雜性來提高 性能。經過對shingle算法和simhash算法以及筆者基于bloom filter實現算法的分析，相似數據檢測算法大致流 程如下：(1)將數據段分解成一組shingle(即子序列或數據塊)，可以采用定長、變長、單詞或段落文本文件)等分塊 算法； 為了降低空間和時間計算復雜性，可以對shingle集合進行抽樣，比如Min-Wise，Modm，Mins方法；基于選定的shingle集合為數據文件抽取特征，通常是為每個shingle計算hash值組

4、成的序列作為特 征值；為了降低空間和時間計算復雜性，可以對文件特征進行降維處理，比如simhash和bloom filter；基于文件特征計算兩個數據對象之間的相似性，計算方法有Cosine、Overlap、Dice、Jaccard或 Hamming 距離。Shingle 算法Shingle算法的核心思想是將文件相似性問題轉換為集合的相似性問題，集合的相似性度量方法主要有 resemblance 和containment兩種，其定義如下。|shingle(f1, w) n shingle(f2, w)|Rw(f1, f2)=|shingle(f1, w) u shingle(f2, w)|sh

5、ingle(f1, w) n shingle(f2, w)|Cw(f1, f2)=|shingle(f1, w)|數量較大時，如果對所有shingle進行相似性處理則系統開銷較大，包括內存和CPU資源。這時就可以考 慮對shingle集合進行抽樣，以降低空間和時間計算復雜性，但同時由于樣本覆蓋率有限，相似性精確度 會有所降低。shingle取樣主要有三種方法，即Min-Wise，Modm，和Mins。Min-Wise技術是通過將shingle 的長度w和整數值進行映射產生隨機哈希的公共集，在此相同的模式下進行隨機最小獨立置換的采樣，從 而得到采樣集合；Modm技術是通過在與Min-Wise同樣

6、的公共映射集中選擇所有模m為0的哈希值對應 的shingle組成取樣集合；Mins技術同樣也是先將shingle和整數集進行映射，然后從中選擇最小s個元 素組成取樣集合。此外，還可以使用shingle的hash值代表shingle進行相似性計算，能夠節省一定計算 開銷。Simhash 算法Shingle算法的空間和時間計算復雜性都比較高，對于大數據集的Simlarity Join問題將難以適用。Charikar 的simhash算法的核心思想是用一個b位的hash值來表示文件的特征值，然后使用simhash之間的 Hamming距離來衡量相似性。Hamming距離的定義為，兩個二進制序列中對應

7、位不同的個數。simhash 的計算方法如下：(1)將一個b維的向量V初始化為0，b位的二進制數s初始化為0; 對每一個shingle，用hash函數(如MD5, SHA1)計算一個b位的簽名h。對i=1到b，如果h的第i位 為1,則V的第i個元素加上該特征權重；否則，V的第i個元素減去該特征權重；(3)如果V的第i個元素大于0，則s的第i位為1，否則為0； 輸出s作為simhasho與傳統hash函數相比，simhash具有一個這樣的顯著特征，即越相似的文件具有越相似的simhash值， 也就是說Hamming距離越小。顯而易見，Simhash僅使用b位的hash值來表示文件 的特征，節省了

8、大 量的存儲開銷；Hamming距離計算簡單高效，Simhash使用Hamming距離來衡量相似性，計算復雜性得 到大大降低。簡而言之，simhash算法通過對文件特征的降維，有效解決了 Shingle算法的高空間和時間 計算復雜性問題。然而，simhash算法的精確度也會有所損耗，并且與simhash的位數b有關，b越大精 確度越高。Bloom filter 算法與Simhash算法本質相似，Bloom filter算法的核心思想也是著眼于文件特征的降維，它使用Bloom filter 數據結構來表示特征值。Bloom filter是一個空間效率很高的數據結構，它由一個位數組和一組hash映

9、射 函數組成。Bloom filter可以用于檢索一個元素是否在一個集合中，它的優點是空間效率和查詢時間都遠遠 超過一般的算法，缺點是有一定的誤識別率和刪除困難。使用Bloom filter進行相似數據檢測，可以彌補 shingle中應用特征集交集計算文件相似性所導致的高計算和存儲空間開銷，在性能與相似性匹配精度之間 取得平衡。Bloom filter構造方法如下：(1)構造一個m位的bloom filter數據結構bf，并將所有位初始為0； 選定兩個hash函數作為映射函數，分別為hash1，hash2；對每一個shingle，分別應用hash1和hash2，并對bf相應比特位置1 ；輸出b

10、f作為文件特征值。這樣，兩個文件相似性計算就轉換成兩個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|)

11、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) = Zxi履里相當于兩個Bloom filter數據結構中同時為1的位數;|x|表示bloom filter 數據結構中為1的位數。相似性計算函數如下： cpp view plaincopyprint?static double bloom_sim(BLOOM *bloom1, BLOOM *bloom2)(int i,

12、 r1, r2;int cl = 0, c2 = 0, comm = 0;double sim;6.for (i = 0; i BLOOM_ARRAY_SZ; i+) ( TOC o 1-5 h z r1= bloom_check(bloom1,1,i);r2= bloom_check(bloom2,1,i);if(r1 & r2) (comm+;c1+;c2+; else (if (r1) (c1+;18.if (r2) (c2+;24.25.26./* similarity measures */27./sim = comm/(sqrt(c1) * sqrt(c2); /* Cosine */28./sim = comm/1.0/(c1 + c2 - comm); /* Jaccard */29./sim = comm*2.0/(c1 +