網頁查重算法Shingling和Simhash和bloom filter研究

在網頁查重算法中 shingling 和 simhash 被認為是當前最好的兩個算法。

shingling算法

shingling算法用于計算兩個文檔的相似度，例如，用于網頁去重。

"a rose is a rose is a rose"

分詞后的詞匯(token，語匯單元)集合是

(a,rose,is,a,rose,is, a, rose)

那么w=4的4-shingling就是集合:

{ (a,rose,is,a), (rose,is,a,rose), (is,a,rose,is), (a,rose,is,a), (rose,is,a,rose) }

去掉重復的子集合：

{ (a,rose,is,a), (rose,is,a,rose), (is,a,rose,is) }

給定shingle的大小,兩個文檔A和B的相似度 r 定義為:

r(A,B)=|S(A)∩S(B)| / |S(A)∪S(B)|

simhash算法

原文：https://wizardforcel.gitbooks.io/the-art-of-programming-by-july/content/06.03.html

其主要思想是降維，將高維的特征向量映射成低維的特征向量，通過兩個向量的Hamming Distance來確定文章是否重復或者高度近似。

• 其中，Hamming Distance，又稱漢明距離，在信息論中，兩個等長字符串之間的漢明距離是兩個字符串對應位置的不同字符的個數。也就是說，它就是將一個字符串變換成另外一個字符串所需要替換的字符個數。例如：1011101 與 1001001 之間的漢明距離是 2。至于我們常說的字符串編輯距離則是一般形式的漢明距離。

如此，通過比較多個文檔的simHash值的Hamming 距離，可以獲取它們的相似度。

流程

simhash算法分為5個步驟：分詞、hash、加權、合并、降維，具體過程如下所述：

分詞

給定一段語句，進行分詞，得到有效的特征向量，然后為每一個特征向量設置1-5等5個級別的權重（如果是給定一個文本，那么特征向量可以是文本中的詞，其權重可以是這個詞出現的次數）。

例如給定一段語句：“CSDN博客結構之法算法之道的作者July”，分詞后為：“CSDN 博客 結構 之 法 算法 之 道 的 作者 July”，然后為每個特征向量賦予權值：CSDN(4) 博客(5) 結構(3) 之(1) 法(2) 算法(3) 之(1) 道(2) 的(1) 作者(5) July(5)，其中括號里的數字代表這個單詞在整條語句中的重要程度，數字越大代表越重要。

hash

通過hash函數計算各個特征向量的hash值，hash值為二進制數01組成的n-bit簽名。比如“CSDN”的hash值Hash(CSDN)為100101，“博客”的hash值Hash(博客)為“101011”。就這樣，字符串就變成了一系列數字。

加權

在hash值的基礎上，給所有特征向量進行加權，即W = Hash weight，且遇到1則hash值和權值正相乘，遇到0則hash值和權值負相乘。例如給“CSDN”的hash值“100101”加權得到：W(CSDN) = 1001014 = 4 -4 -4 4 -4 4，給“博客”的hash值“101011”加權得到：W(博客)=101011*5 = 5 -5 5 -5 5 5，其余特征向量類似此般操作。

合并

將上述各個特征向量的加權結果累加，變成只有一個序列串。拿前兩個特征向量舉例，例如“CSDN”的“4 -4 -4 4 -4 4”和“博客”的“5 -5 5 -5 5 5”進行累加，得到“4+5 -4±5 -4+5 4±5 -4+5 4+5”，得到“9 -9 1 -1 1”。
降維

對于n-bit簽名的累加結果，如果大于0則置1，否則置0，從而得到該語句的simhash值，最后我們便可以根據不同語句simhash的海明距離來判斷它們的相似度。例如把上面計算出來的“9 -9 1 -1 1 9”降維（某位大于0記為1，小于0記為0），得到的01串為：“1 0 1 0 1 1”，從而形成它們的simhash簽名。
其流程如下圖所示：

應用

每篇文檔得到SimHash簽名值后，接著計算兩個簽名的海明距離即可。根據經驗值，對64位的 SimHash值，海明距離在3以內的可認為相似度比較高。

• 海明距離的求法：異或時，只有在兩個比較的位不同時其結果是1 ，否則結果為0，兩個二進制“異或”后得到1的個數即為海明距離的大小。

舉個例子，上面我們計算到的“CSDN博客”的simhash簽名值為“1 0 1 0 1 1”，假定我們計算出另外一個短語的簽名值為“1 0 1 0 0 0”，那么根據異或規則，我們可以計算出這兩個簽名的海明距離為2，從而判定這兩個短語的相似度是比較高的。

換言之，現在問題轉換為：對于64位的SimHash值，我們只要找到海明距離在3以內的所有簽名，即可找出所有相似的短語。
但關鍵是，如何將其擴展到海量數據呢？譬如如何在海量的樣本庫中查詢與其海明距離在3以內的記錄呢？

• 一種方案是查找待查詢文本的64位simhash code的所有3位以內變化的組合, 大約需要四萬多次的查詢。
• 另一種方案是預生成庫中所有樣本simhash code的3位變化以內的組合, 大約需要占據4萬多倍的原始空間。

這兩種方案，要么時間復雜度高，要么空間復雜度復雜，能否有一種方案可以達到時空復雜度的絕佳平衡呢？答案是肯定的：

• 我們可以把 64 位的二進制simhash簽名均分成4塊，每塊16位。根據鴿巢原理（也稱抽屜原理），如果兩個簽名的海明距離在 3 以內，它們必有一塊完全相同。如下圖所示：
  
• 然后把分成的4 塊中的每一個塊分別作為前16位來進行查找，建倒排索引。
  
  如此，如果樣本庫中存有$2^{34}$ （差不多10億）的simhash簽名，則每個table返回$2^{(34?16)}=262144$個候選結果，大大減少了海明距離的計算成本。
• 假設數據是均勻分布，16位的數據，產生的像限為2^16個 ，則平均每個像限分布的文檔數則為$2^{34}/2^{16}=2^{(34?16)}$ ，四個塊返回的總結果數為 4* 262144 （大概 100 萬）。
  這樣，原本需要比較10億次，經過索引后，大概只需要處理100萬次。

Bloom Filter

參考：https://juejin.im/post/5de1e37c5188256e8e43adfc
應用：如網頁 URL 去重、垃圾郵件識別、大集合中重復元素的判斷和緩存穿透等問題。
它的優點是空間效率和查詢時間都比一般的算法要好的多，缺點是有一定的誤識別率和刪除困難。

布隆過濾器可以檢查值是 “可能在集合中” 還是 “絕對不在集合中”。“可能” 表示有一定的概率，也就是說可能存在一定為誤判率。
布隆過濾器（Bloom Filter）本質上是由長度為 m 的位向量或位列表（僅包含 0 或 1 位值的列表）組成，最初所有的值均設置為 0，如下圖所示。

為了將數據項添加到布隆過濾器中，我們會提供 K 個不同的哈希函數，并將結果位置上對應位的值置為 “1”。在前面所提到的哈希表中，我們使用的是單個哈希函數，因此只能輸出單個索引值。而對于布隆過濾器來說，我們將使用多個哈希函數，這將會產生多個索引值。

如上圖所示，當輸入 “semlinker” 時，預設的 3 個哈希函數將輸出 2、4、6，我們把相應位置 1。假設另一個輸入 ”kakuqo“，哈希函數輸出 3、4 和 7。你可能已經注意到，索引位 4 已經被先前的 “semlinker” 標記了。此時，我們已經使用 “semlinker” 和 ”kakuqo“ 兩個輸入值，填充了位向量。當前位向量的標記狀態為：

當對值進行搜索時，與哈希表類似，我們將使用 3 個哈希函數對 ”搜索的值“ 進行哈希運算，并查看其生成的索引值。假設，當我們搜索 ”fullstack“ 時，3 個哈希函數輸出的 3 個索引值分別是 2、3 和 7：

從上圖可以看出，相應的索引位都被置為 1，這意味著我們可以說 ”fullstack“ 可能已經插入到集合中。事實上這是誤報的情形，產生的原因是由于哈希碰撞導致的巧合而將不同的元素存儲在相同的比特位上。幸運的是，布隆過濾器有一個可預測的誤判率（FPP）：

• n 是已經添加元素的數量；
• k 哈希的次數；
• m 布隆過濾器的長度（如比特數組的大小）；

極端情況下，當布隆過濾器沒有空閑空間時（滿），每一次查詢都會返回 true 。這也就意味著 m 的選擇取決于期望預計添加元素的數量 n ，并且 m 需要遠遠大于 n 。
實際情況中，布隆過濾器的長度 m 可以根據給定的誤判率（FFP）的和期望添加的元素個數 n 的通過如下公式計算：

了解完上述的內容之后，我們可以得出一個結論，當我們搜索一個值的時候，若該值經過 K 個哈希函數運算后的任何一個索引位為 ”0“，那么該值肯定不在集合中。但如果所有哈希索引值均為 ”1“，則只能說該搜索的值可能存在集合中。

三種算法對比

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計算模型。

總結

以上是生活随笔為你收集整理的网页查重算法Shingling和Simhash和bloom filter研究的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。