核心概念#
任何一段信息（文字、語音、視頻、圖片等），都可以對應一個不太長的隨機數，作為區別這段信息和其他信息的指紋（Fingerprint）。只要算法設計得好，任意兩段信息的指紋都很難重複，就如同人類的指紋一樣。
信息指紋#
- 互聯網上的網址平均長度超過 100 個字符，直接存儲在哈希表中既耗費空間又浪費查找時間
- 解決方法：用一個函數將網址隨機映射到 128 位二進制的整數空間（16 字節），作為該網址的信息指紋
- 這樣每個網址只占用 16 字節（而非原來的 100 字節），內存需求降至原來的 1/6 不到
- 信息指紋的計算分兩步：先將字符串轉為整數，再用偽隨機數產生器算法（PRNG）轉換成固定長度的偽隨機數
信息指紋的一個重要特徵是不可逆性——無法根據指紋推出原始信息。這正是網絡加密傳輸所需要的性質，例如網站的 cookie 就是一種信息指紋。
- 互聯網上加密常用的算法有 MD5 或 SHA-1 等標準（基於 CSPRNG），可將任意長度的信息變為 128 位或 160 位二進制隨機數
信息指紋的用途#
集合相同的判定#
- 判斷兩個查詢用詞集合是否相同：計算兩個集合的信息指紋（各元素指紋之和），若指紋相同則集合相同
- 時間複雜度為 $O(N)$，且不需要額外空間，是最佳方法
判定集合基本相同#
- 判斷兩個賬號的郵件收件人清單是否基本相同（如垃圾郵件偵測）：隨機抽取部分元素比較指紋
- Google 使用一種特殊的信息指紋——相似哈希（Simhash）來判斷網頁內容是否重複
判斷文章抄襲#
- 將文章切成小片段，計算各片段的指紋，比較指紋就能找出大段相同的文字
- Google 實驗室的 CopyCat 項目利用這個原理找到原文和抄襲的文章
YouTube 的反盜版#
- 視頻匹配的核心技術是關鍵幀的提取和特徵提取
- 用一組信息指紋表示關鍵幀，檢測盜版就類似於比較兩個集合元素是否相同
- Google 收購 YouTube 後，利用這套反盜版系統制定了廣告分成策略：廣告收益全部給原創視頻
延伸閱讀：信息指紋的重複性和相似哈希#
指紋重複的可能性#
- 假設指紋範圍為 $0 \sim N-1$，$k$ 個指紋不重複的概率為 $P_k = \frac{(N-1)(N-2)\cdots(N-k+1)}{N^{k-1}}$
- 使用 128 位二進制的 MD5 指紋（$N = 2^{64}$），$k > 2^{64} \approx 1.8 \times 10^{19}$ 時才可能重複，即每一千八百億億次才重複一次
相似哈希（Simhash）#
- 由 Moses Charikar 在 2002 年提出，Google 在網頁爬蟲中使用
- 計算分為擴展和收縮兩步：
- 擴展：將每個詞的指紋位元展開為實數（1 位加權重，0 位減權重），累加所有詞的貢獻
- 收縮：將累加結果的正數變為 1、負數變為 0，得到文章的 Simhash 值
- 特點：兩個網頁的 Simhash 相差越小，內容重複的可能性越高；64 位 Simhash 只差一兩位，內容重複可能性大於 80%
本章小結#
信息指紋可以簡單理解為將一段信息隨機地映射到多維二進制空間中的一個點。只要隨機函數做得好，不同信息的映射點就不會重合，這些二進制數字便成為信息獨一無二的指紋。