1. 文本指紋介紹

互聯(lián)網(wǎng)網(wǎng)頁存在大量的重復(fù)內(nèi)容網(wǎng)頁，無論對于搜索引擎的網(wǎng)頁去重和過濾、新聞小說等內(nèi)容網(wǎng)站的內(nèi)容反盜版和追蹤、還是社交媒體等文本去重和聚類，都需要對網(wǎng)頁或者文本進(jìn)行去重和過濾。

最簡單的文本相似性計算方法可以利用空間向量模型，計算分詞后的文本的特征向量的相似性，這種方法存在效率的嚴(yán)重弊端，無法針對海量的文本進(jìn)行兩兩的相似性判斷。模仿生物學(xué)指紋的特點，對每個文本構(gòu)造一個指紋，來作為該文本的標(biāo)識，從形式上來看指紋一般為固定長度較短的字符串，相同指紋的文本可以認(rèn)為是相同文本。

最簡單的指紋構(gòu)造方式就是計算文本的md5或者sha哈希值，除非輸入相同的文本，否則會發(fā)生“雪崩效應(yīng)”，極小的文本差異通過md5或者sha計算出來的指紋就會不同(發(fā)生沖撞的概率極低)，那么對于稍加改動的文本，計算出來的指紋也是不一樣。因此，一個好的指紋應(yīng)該具備如下特點：

指紋是確定性的，相同的文本的指紋是相同的;

指紋越相似，文本相似性就越高;

指紋生成和匹配效率高。

業(yè)界關(guān)于文本指紋去重的算法眾多，如k-shingle算法、google提出的simhash算法、Minhash算法、top k最長句子簽名算法等等，本文接下來將簡單介紹各個算法以及達(dá)觀指紋系統(tǒng)的基本架構(gòu)和思路。

2. 常用的指紋算法

2.1 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è)界很少采用這類算法。

2.2 Simhash算法

Simhash是google用來處理海量文本去重的算法，同時也是一種基于LSH(locality sensitive hashing)的算法。簡單來說，和md5和sha哈希算法所不同，局部敏感哈?？梢詫⑾嗨频淖址甴ash得到相似的hash值，使得相似項會比不相似項更可能的hash到一個桶中，hash到同一個桶中的文檔間成為候選對。這樣就可以以接近線性的時間去解決相似性判斷和去重問題。

simhash算法通過計算每個特征(關(guān)鍵詞)的哈希值，并最終合并成一個特征值即指紋。

simhash算法流程：

1.首先基于傳統(tǒng)的IR方法，將文章轉(zhuǎn)換為一組加權(quán)的特征值構(gòu)成的向量。

2.初始化一個f維的向量V，其中每一個元素初始值為0。

3.對于文章的特征向量集中的每一個特征，做如下計算：

a) 利用傳統(tǒng)的hash算法映射到一個f-bit(一般設(shè)成32位或者64位)的簽名。對于這個f- bit的簽名，如果簽名的第i位上為1，則對向量V中第i維加上這個特征的權(quán)值，否則對向量的第i維減去該特征的權(quán)值;

b) 整個特征向量集合迭代上述運算后，根據(jù)V中每一維向量的符號來確定生成的f-bit指紋的值，如果V的第i維為正數(shù)，則生成f-bit指紋的第i維為1，否則為0。

圖1 simhash算法示意圖

Simhash指紋匹配過程經(jīng)過simhash指紋生成算法生成的指紋是一個f位的二進(jìn)制字符串，如一個32位的指紋，‘101001111100011010100011011011’。對于兩個文本的f位0-1字符串，simhash算法采用hamming distance來計算兩個指紋之間的相似度，但是對于海量文本，如何從千萬級別(甚至更多)的指紋集合中，找出最多只有k位不同的指紋呢?一個簡單的思想就是以空間換時間，對于一個32位的指紋來說，將該指紋劃分成4段，即4個區(qū)間，每個區(qū)間8位，如果兩個指紋至多存在3(設(shè)k=3)位差異，那么至少有一段的8位是完全相同的，因此可以考慮利用分段來建立索引，來減少需要匹配的候選指紋數(shù)量。

Simhash指紋匹配算法：

1、首先對于指紋集合Q構(gòu)建多個表T1，T2…Tt，每一個表都是采用對應(yīng)的置換函數(shù)π(i)將32-bit的fingerprint中的某p(i)位序列置換換到整個序列的最前面。即每個表存儲都是整個Q的fingerprint的復(fù)制置換;

2、對于給定的F，在每個Ti中進(jìn)行匹配，尋找所有前pi位與F經(jīng)過π(i)置換后的前pi位相同的fingerprint。

3、對于所有在上一步中匹配到的置換后的fingerprint，計算其是否與π(i)(F)至多有k-bit不同。

Simhash算法比較高效，比較適用于對于長文本。

2.3 Minhash算法

Minhash也是一種LSH算法，同時也是一種降維的方法。Minhash算法的基本思想是使用一個隨機(jī)的hash函數(shù)h(x)對集合A和B中的每個元素進(jìn)行hash，hmin(A)、hmin(B)分別表示hash后集合A和集合B的最小值，那么P(hmin(A) == hmin(B)) = Jaccard(A, B)。這是minhash算法的核心，其中hmin(A)為哈希函數(shù)h(x)對集合A的最小哈希值。

圖2： 最小簽名矩陣生成示意圖

Minhash算法采用最小哈希函數(shù)族(一組隨機(jī)的最小哈希函數(shù))來構(gòu)建文檔的最小哈希簽名。文檔的最小哈希簽名矩陣是對原始特征矩陣降維的結(jié)果。應(yīng)用過程中，可以使用k個最小函數(shù)分別計算出集合的哈希最小值。設(shè)hi表示第i個最小hash函數(shù)，最小簽名矩陣中列向量為樣本si的最小簽名向量，其中wij表示第j個最小hash函數(shù)對樣本i的最小哈希值。當(dāng)k小于原始集合的長度(k << n)時，就相當(dāng)于對數(shù)據(jù)降維，類比PCA等降維方法，minhash避免了復(fù)雜的矩陣運算。由于最小簽名矩陣中，樣本i，j的某一行或某幾行的子向量的相似度于樣本i，j的jarcarrd距離相等，因此可以對最小簽名矩陣運行行條化策略，經(jīng)矩陣平均分為b個行條，每個行條由r條組成，當(dāng)兩個樣本在任意一個行條中的向量相等，即是一個相似性候選對，并檢查文檔是否真正相似或者相等。

關(guān)于minhash的原理和推導(dǎo)，以及在大量文本及高維特征下如何快速進(jìn)行最小簽名矩陣的構(gòu)建操作可以參考https://en.wikipedia.org/wiki/MinHash及《大數(shù)據(jù) 互聯(lián)網(wǎng)大規(guī)模數(shù)據(jù)挖掘與分布式處理》，數(shù)學(xué)的奧妙就在于此。經(jīng)過minhash降維后的文本向量，從概率上保證了兩個向量的相似度和降維前是一樣的，結(jié)合LSH技術(shù)構(gòu)建候選對可以大大減少空間規(guī)模，加快查找速度。

3.內(nèi)容型網(wǎng)頁文本指紋算法

本節(jié)將給出我們在對內(nèi)容型網(wǎng)頁(小說、新聞等)去重任務(wù)中總結(jié)出來的算法和實踐經(jīng)驗，特別在當(dāng)前內(nèi)容版權(quán)日益受到重視和保護(hù)的背景下，對于內(nèi)容版權(quán)方來說，如何從網(wǎng)絡(luò)上發(fā)現(xiàn)和追蹤侵權(quán)和盜版行為日益重要。從前文可以看出，指紋識別算法是實現(xiàn)指紋識別的關(guān)鍵，它直接決定了識別率的高低，是指紋識別技術(shù)的核心。特別是類似新聞類、小說類網(wǎng)頁在轉(zhuǎn)載或者盜版過程中，文字的個數(shù)、順序上一般都保持一致，當(dāng)然不排除個別字錯誤或者少一個字的情況。指紋生成的過程主要包括將文本全部轉(zhuǎn)換成拼音、截取每個字拼音的首字母、統(tǒng)計該粒度內(nèi)字母的頻率分布、通過和參考系比較，將結(jié)果進(jìn)行歸一化、按字母序，將數(shù)字表征轉(zhuǎn)換成數(shù)字。

圖3 指紋生成算法

算法描述：

轉(zhuǎn)拼音：可以解決字符集編碼不一致的問題，可以利用成熟的英文指紋算法，減小分布空間，同時可以解決同音字替代問題;

截取拼音首字：減小存儲長度和分布空間(26個字母);

提取首字母頻率：選擇多少字來計算指紋，統(tǒng)計頻率分布。需要設(shè)置顆粒度的大小(分段大小)以及重疊率。大粒度容錯性高，但是匹配率低;小粒度容錯性低，但是誤報率高且敏感度高。重疊率是設(shè)置指紋計算片段移動的窗口大?。杭僭O(shè)拼音內(nèi)容長為2n，顆粒長度為n，重疊率為50%，則需要計算的指紋片段分別為[1-n]，[n/2,3*n/2]，[n,2n]

減去參考系：頻率減去參考系

歸一化：將每個字母的數(shù)字特征歸一化到一個閉區(qū)間內(nèi)，如[0,9],按照字母順序連接數(shù)字特征，變成一個數(shù)字，即指紋。

若空間為[0,9],即一個20位的整數(shù)，2^64，需要 8 byte

若空間為[0,7],可用一個20位的8進(jìn)制數(shù)，8^20,需要 8 byte

若空間為[0,3],只需要 4^20, 共40 bit, 5 byte

若空間為[0,1],需要2^20,20 bit,3 byte

歸一化過程的算法步驟如下，假設(shè)顆粒長度為m：

4. 達(dá)觀指紋系統(tǒng)結(jié)構(gòu)

4.1 基本架構(gòu)達(dá)觀指紋追蹤系統(tǒng)主要由爬蟲系統(tǒng)、指紋生成系統(tǒng)、指紋存儲、指紋查詢和比對、數(shù)據(jù)分析、后臺管理系統(tǒng)等幾個主要模塊構(gòu)成，如圖4所示。其中存儲層包括匹配結(jié)果信息庫、網(wǎng)頁庫以及指紋庫。

圖4 指紋追蹤系統(tǒng)模塊圖

A. 爬蟲系統(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)提供大量的待檢測頁面。

B. 指紋存儲模塊

指紋存儲模塊計算母體(海量文本)的指紋，指紋可以理解為一行文本的向量表示，本系統(tǒng)的指紋存儲系統(tǒng)采用mongo DB進(jìn)行存儲。

C. 指紋生成模塊

指紋生成模塊的輸入是一行文本，其輸出為該文本的指紋表示，為了達(dá)到較高的對比準(zhǔn)確率，一個好的指紋生成系統(tǒng)至關(guān)重要。

D. 指紋查詢和比對模塊

指紋庫中存儲著大量的母體指紋，對于某一文本，指紋查詢和比對模塊要快速的判斷該文本是否在母體庫中存在重復(fù)。

E. 數(shù)據(jù)分析

數(shù)據(jù)分析系統(tǒng)需要對大量的文本及其對比結(jié)果進(jìn)行統(tǒng)計數(shù)據(jù)分析。

F. 后臺管理平臺

提供數(shù)據(jù)分析的展示，并提供用戶使用查詢和輸出分析報告等。

數(shù)據(jù)存儲模塊

A. 網(wǎng)頁庫

主要存放爬蟲系統(tǒng)抓取的網(wǎng)頁信息、站點信息，本系統(tǒng)網(wǎng)頁庫采用mongo DB。

B. 指紋庫

主要存放母體指紋，本系統(tǒng)采用mongo DB存放指紋。為了加快指紋的查詢和比對，本系統(tǒng)采用redis來對指紋建立索引，加快匹配速度。

C. 匹配信息庫

存儲指紋匹配結(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ù)進(jìn)行去重操作。

圖6 系統(tǒng)流程圖

5 總結(jié)

對于網(wǎng)頁去重、內(nèi)容盜版追蹤、內(nèi)容聚類等應(yīng)用來說，指紋模塊都是極其重要的模塊。本文介紹了一些比較常用的指紋算法，包括k-shingle、simhash、minhash;同時介紹了達(dá)觀數(shù)據(jù)自主開發(fā)的指紋追蹤系統(tǒng)及其關(guān)鍵算法，沒有最好的算法，只有合適的算法，在實際的使用過程中，需要根據(jù)具體業(yè)務(wù)場景，確定架構(gòu)和算法。

來源：36大數(shù)據(jù)