應用：
- 網頁地址去重
網頁地址有100個字符，存儲5000億個網址本身需要50T的容量，而Hash表的存儲效率只有50%，所有存儲爬蟲已經爬過的網址需要100T的內存
解決辦法：將網址隨機映射到128個bit上，即16個字節的整數空間上，每個網址只需要16個字節，而不是100個了，內存的需求量下降到原來的1/6不到，這16個字節的隨機數，就稱作該網址的信息指紋
步驟：a.現將網址轉為數值（每個字符對應的ascii）b.通過偉隨機數產生器，將得到的數值轉為16個字節的整數
在互聯網上加密要使用基於加密的偽隨機數產生器，常用MD5或者SHA-1等標準
- 判定集合是否相同
a.場景：
兩個查詢，如“北京 中關村 星巴克”和“星巴克 中關村 北京”是否相同；一個人是否用兩個不同的賬號對同一群人發垃圾郵件；網上的一首歌是否是盜版別人的
需要將查詢或者群體的郵件列表存儲在兩個集合裡，然後判斷兩個集合是否相同即可
b.算法選擇：
兩次變量對比：時間複雜度為O(N^2)
先排序，後遍歷對比：時間複雜度為O(NlogN)
先將一個集合放入HashSet，然後判斷另一個集合的元素是否都在HashSet裡，時間複雜度為O(N)，但是有額外的空間負責度O(N)
完美的方案：對單個集合的元素求其信息指紋，然後相加，與兩一個集合的信息指紋和比較，來判斷兩個集合元素是否相同，時間複雜度為O(N)；用加法的交換率，消除了元素次序對結果的影響
c.電子郵件的問題：
如果按照b的思路，兩次郵件列表裡只有一兩個用戶不同，則需要對步驟進行一個修改，即按照同樣的規則（如尾數為24的）對郵件列表進行過濾，如果他們的指紋相同，或者是否有80%以上的相同率，來判斷兩個郵件列表是否相同
d.兩篇網頁、文章是否相同
對兩篇文章先去掉常見詞、然後去掉出現一次的詞（噪音），在剩下的詞中對IDF最大的詞進行信息指紋的求和、比較，即可判斷是否是相同的文章；為了保證容錯性，採取了相似哈希的信息指紋（見後文）
- 視頻的反盜版
視頻匹配兩個核心技術：關鍵幀的提取和特徵的提取，MPEG視頻每秒有30幀圖像，但是隻有極少數的關鍵幀是完整的影像，其他幀存儲的是和關鍵幀相比的差異值
提取出視頻中的關鍵幀（類似於主題詞對新聞），然後對其最信息指紋的
2.指紋重複的可能性：
128位的偽隨機數，其k個指紋不重複的概率為
，Pk隨著k的增大而減小，當Pk<0.5時，k個指紋重複的期望超過1，此時k的最大值為：
在128bit時，N為2^128，所以k約等於2^64，即一千八百億億次才能重複一次，因此不同信息產生相同指紋的可能性幾乎為0
3.相似哈希（Simhash）
如果網頁中若干詞T1,T2,...,Tk，其權重（如TF-IDF）為W1,W2,...,Wk，先計算其信息指紋（這裡以8bit為例），在計算相似哈希：
i.擴展：
將8bit的信息指紋擴展為8個實數：對於每一個詞一個詞Tk，如果其第n位為1，則第一個實數Rn加Wn，如果為0，則Rn減Wn；最後得到8個實數，
ii.收縮：
然後將8個實數收縮，Rk>0?1:0，變為一個8位的二進制，即是其相似哈希指紋
iii.場景：
少數權重小的詞不同的情況下，相似哈希也會相同
用64位的相似哈希做對比，如果兩者相差一位，其網頁內容重複的可能性大於80%
閱讀更多 小猿圈兒 的文章
