文本指紋算法是百度爬蟲系統(tǒng)中較讓采集內(nèi)容的站長們頭疼的算法之一，但對于辛苦做白帽的站長卻是福利。
文本指紋算法
現(xiàn)在網(wǎng)上的小說、新聞、圖片盜版實在猖狂，需要對網(wǎng)頁或文本進行去重和過濾。最簡單的文本相似性計算文本中md5或者sha哈希值。但有可能造成極小的文本差異通過md5或sha哈希值計算出來的指紋就會不同。
好的指紋應(yīng)具備如下特點
①指紋是確定性的，相同的文本的指紋是相同的；
②指紋越相似，文本相似性就越高；
③指紋生成和匹配效率高。
常用的指紋算法
k-shingle算法
shingle在英文中表示相互覆蓋的瓦片。對于一段文本，分詞向量為[w1, w2, w3, w4, … wn]， 設(shè)k=3，那么該文本的shingle向量表示為[(w1,w2,w3), (w2,w3,w4), (w3,w4,w5), …… (wn-2,wn-1,wn)]，計算兩個文本的shingle向量的相似度(jarccard系數(shù))來判斷文本是否重復(fù)。由于k-shingle算法的shingle向量空間巨大(特別是k特別大時)，相比vsm更加耗費資源，一般業(yè)界很少采用這類算法。
Simhash算法
Simhash是google用來處理海量文本去重的算法，同時也是一種基于LSH(locality sensitive hashing)的算法。簡單來說，和md5和sha哈希算法所不同，局部敏感哈�？梢詫⑾嗨频淖址甴ash得到相似的hash值，使得相似項會比不相似項更可能的hash到一個桶中，hash到同一個桶中的文檔間成為候選對。這樣就可以以接近線性的時間去解決相似性判斷和去重問題。
simhash算法通過計算每個特征(關(guān)鍵詞)的哈希值，并最終合并成一個特征值即指紋。
圖1 simhash算法示意圖
Simhash指紋匹配過程
經(jīng)過simhash指紋生成算法生成的指紋是一個f位的二進制字符串，如一個32位的指紋，‘101001111100011010100011011011’。對于兩個文本的f位0-1字符串，simhash算法采用hamming distance來計算兩個指紋之間的相似度。當面對海量指紋集合時，一個簡單的思想就是以空間換時間，對于一個32位的指紋來說，將該指紋劃分成4段，即4個區(qū)間，每個區(qū)間8位，如果兩個指紋至多存在3(設(shè)k=3)位差異，那么至少有一段的8位是完全相同的，因此可以考慮利用分段來建立索引，來減少需要匹配的候選指紋數(shù)量。
Simhash算法效率較高，比較適用于對于長文本，同時simhash算法沒有考慮去重的粒度以及詞的順序，面對高精度時可能會帶來準確度問題。
Minhash算法
Minhash也是一種LSH算法，同時也是一種降維的方法。Minhash算法的基本思想是使用一個隨機的hash函數(shù)h(x)對集合A和B中的每個元素進行hash，hmin(A)、hmin(B)分別表示hash后集合A和集合B的最小值，那么P(hmin(A) == hmin(B)) = Jaccard(A, B)。這是minhash算法的核心，其中hmin(A)為哈希函數(shù)h(x)對集合A的最小哈希值。(達觀數(shù)據(jù) 文輝)
圖2： 最小簽名矩陣生成示意圖
Minhash算法采用最小哈希函數(shù)族(一組隨機的最小哈希函數(shù))來構(gòu)建文檔的最小哈希簽名。文檔的最小哈希簽名矩陣是對原始特征矩陣降維的結(jié)果。應(yīng)用過程中，可以使用k個最小函數(shù)分別計算出集合的哈希最小值。設(shè)hi表示第i個最小hash函數(shù)，最小簽名矩陣中列向量為樣本si的最小簽名向量，其中wij表示第j個最小hash函數(shù)對樣本i的最小哈希值。
當k小于原始集合的長度(k << n)時，就相當于對數(shù)據(jù)降維。
內(nèi)容型網(wǎng)頁文本指紋算法
本節(jié)將給出我們在對內(nèi)容型網(wǎng)頁(小說、新聞等)去重任務(wù)中總結(jié)出來的算法和實踐經(jīng)驗，特別在當前內(nèi)容版權(quán)日益受到重視和保護的背景下，對于內(nèi)容版權(quán)方來說，如何從網(wǎng)絡(luò)上發(fā)現(xiàn)和追蹤侵權(quán)和盜版行為日益重要。
從前文可以看出，指紋識別算法是實現(xiàn)指紋識別的關(guān)鍵，它直接決定了識別率的高低，是指紋識別技術(shù)的核心。特別是類似新聞類、小說類網(wǎng)頁在轉(zhuǎn)載或者盜版過程中，文字的個數(shù)、順序上一般都保持一致，當然不排除個別字錯誤或者少一個字的情況。
指紋生成的過程主要包括將文本全部轉(zhuǎn)換成拼音、截取每個字拼音的首字母、統(tǒng)計該粒度內(nèi)字母的頻率分布、通過和參考系比較，將結(jié)果進行歸一化、按字母序，將數(shù)字表征轉(zhuǎn)換成數(shù)字。
圖3 指紋生成算法
算法描述：
1. 轉(zhuǎn)拼音：可以解決字符集編碼不一致的問題，可以利用成熟的英文指紋算法，減小分布空間，同時可以解決同音字替代問題;
2. 截取拼音首字：減小存儲長度和分布空間(26個字母);
3. 提取首字母頻率：選擇多少字來計算指紋，統(tǒng)計頻率分布。需要設(shè)置顆粒度的大小(分段大小)以及重疊率。
大粒度容錯性高，但是匹配率低;小粒度容錯性低，但是誤報率高且敏感度高。
重疊率是設(shè)置指紋計算片段移動的窗口大�。�
假設(shè)拼音內(nèi)容長為2n，顆粒長度為n，重疊率為50%，則需要計算的指紋片段分別為[1-n]，[n/2,3*n/2]，[n,2n]
4. 減去參考系：頻率減去參考系
5. 歸一化：將每個字母的數(shù)字特征歸一化到一個閉區(qū)間內(nèi)，如[0,9],按照字母順序連接數(shù)字特征，變成一個數(shù)字，即指紋。
若空間為[0,9],即一個20位的整數(shù)，2^64，需要 8 byte
若空間為[0,7],可用一個20位的8進制數(shù)，8^20,需要 8 byte
若空間為[0,3],只需要 4^20, 共40 bit, 5 byte
若空間為[0,1],需要2^20,20 bit,3 byte
歸一化過程的算法步驟如下，假設(shè)顆粒長度為m：
達觀指紋系統(tǒng)結(jié)構(gòu)
基本架構(gòu)
達觀指紋追蹤系統(tǒng)主要由爬蟲系統(tǒng)、指紋生成系統(tǒng)、指紋存儲、指紋查詢和比對、數(shù)據(jù)分析、后臺管理系統(tǒng)等幾個主要模塊構(gòu)成，如圖4所示。其中存儲層包括匹配結(jié)果信息庫、網(wǎng)頁庫以及指紋庫。
圖4 指紋追蹤系統(tǒng)模塊圖
爬蟲系統(tǒng)
爬蟲系統(tǒng)從目的上看主要在于抓取互聯(lián)網(wǎng)上的特定領(lǐng)域的網(wǎng)頁(如新聞類網(wǎng)頁)，爬蟲系統(tǒng)是原始數(shù)據(jù)的唯一來源，只有通過爬蟲系統(tǒng)才能從浩瀚的互聯(lián)網(wǎng)中抓取相似的網(wǎng)頁內(nèi)容。爬蟲系統(tǒng)需要擁有較高的抓取能力和反爬取能力，為整個系統(tǒng)提供大量的待檢測頁面。
指紋存儲模塊
指紋存儲模塊計算母體(海量文本)的指紋，指紋可以理解為一行文本的向量表示，本系統(tǒng)的指紋存儲系統(tǒng)采用mongo DB進行存儲。
指紋生成模塊
指紋生成模塊的輸入是一行文本，其輸出為該文本的指紋表示，為了達到較高的對比準確率，一個好的指紋生成系統(tǒng)至關(guān)重要。
指紋查詢和比對模塊
指紋庫中存儲著大量的母體指紋，對于某一文本，指紋查詢和比對模塊要快速的判斷該文本是否在母體庫中存在重復(fù)。
數(shù)據(jù)分析
數(shù)據(jù)分析系統(tǒng)需要對大量的文本及其對比結(jié)果進行統(tǒng)計數(shù)據(jù)分析。
后臺管理平臺
提供數(shù)據(jù)分析的展示，并提供用戶使用查詢和輸出分析報告等。
數(shù)據(jù)存儲模塊
網(wǎng)頁庫
主要存放爬蟲系統(tǒng)抓取的網(wǎng)頁信息、站點信息，本系統(tǒng)網(wǎng)頁庫采用mongo DB。
指紋庫
主要存放母體指紋，本系統(tǒng)采用mongo DB存放指紋。為了加快指紋的查詢和比對，本系統(tǒng)采用redis來對指紋建立索引，加快匹配速度。
匹配信息庫
存儲指紋匹配結(jié)果， 包括待匹配的兩個指紋， 原始網(wǎng)頁id， 匹配相似度等。
4.2 系統(tǒng)架構(gòu)
圖5 系統(tǒng)架構(gòu)圖
4.3 系統(tǒng)處理流程
本系統(tǒng)的處理流程如圖6所示，系統(tǒng)支持每天自動化從母體庫中調(diào)度新的任務(wù)進行去重操作。
圖6 系統(tǒng)流程圖
4.4 查詢和比對系統(tǒng)
查詢和比對的系統(tǒng)的目的就是快速和高效的找出與目標指紋相似性較高的母體指紋。針對指紋查詢的特點，對母體指紋庫建立索引，待查詢指紋通過查詢索引，即可發(fā)現(xiàn)最可能匹配的母體。
指紋查詢比對流程如下：
建立索引
每個母體指紋描述的是母體ID -> 特征的關(guān)系，可以通過以特征為key，母體ID為value建立倒排索引。如母體為: 1->[a,b,c,d], 2->[b,e,f], 3->[a,c,g]，則索引為：a->[1,3], b->[1,2], c->[1,3], d->[1], e->[2], f->[2], g->[3]。與其他算法一樣的是，也需要考慮索引的粒度，粒度的大小同時應(yīng)考慮指紋算法選擇的粒度。
采樣
根據(jù)待匹配文本的特點(長度)，選擇合適的粒度和片段，重要的是保證匹配的正確性的同時，減少生成指紋的運算量。
提取指紋
根據(jù)指紋生成算法生成待查詢指紋。
查詢指紋
將待查詢指紋進行索引查詢，統(tǒng)計命中母體和命中次數(shù)，并按照次數(shù)排序，選擇命中次數(shù)高的母體作為可疑對象，次數(shù)低于閾值，可忽略。
后處理
結(jié)合歷史統(tǒng)計模型，篩選結(jié)果。匹配結(jié)果不確定，可進行第二輪細致比對或人工驗證。
總結(jié)
對于網(wǎng)頁去重、內(nèi)容盜版追蹤、內(nèi)容聚類等應(yīng)用來說，指紋模塊都是極其重要的模塊。本文介紹了一些比較常用的指紋算法，包括k-shingle、simhash、minhash;同時介紹了達觀數(shù)據(jù)自主開發(fā)的指紋追蹤系統(tǒng)及其關(guān)鍵算法，達觀數(shù)據(jù)在指紋系統(tǒng)構(gòu)建和算法方面積累了豐富的經(jīng)驗，沒有最好的算法，只有合適的算法，在實際的使用過程中，需要根據(jù)具體業(yè)務(wù)場景，確定架構(gòu)和算法。
