文本指紋介紹

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

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

最簡單的指紋構(gòu)造方式就是計(jì)算文本的md5或者sha哈希值，但易發(fā)生“雪崩效應(yīng)”，極小的文本差異通過md5或者sha計(jì)算出來的指紋就會(huì)不同（沖撞的概率極低）。

因此，一個(gè)好的指紋應(yīng)該具備如下特點(diǎn)：

1. 指紋是確定性的，相同的文本的指紋是相同的；
2. 指紋越相似，文本相似性就越高；
3. 指紋生成和匹配效率高。

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

2. 常用的指紋算法
   • k-shingle算法

shingle在英文中表示相互覆蓋的瓦片。對(duì)于一段文本，分詞向量為[w1, w2, w3, w4, … wn]， 設(shè)k=3，那么該文本的shingle向量表示為[(w1,w2,w3), (w2,w3,w4), (w3,w4,w5), …… (wn-2,wn-1,wn)]，計(jì)算兩個(gè)文本的shingle向量的相似度（jarccard系數(shù)）來判斷文本是否重復(fù)。由于k-shingle算法的shingle向量空間巨大（特別是k特別大時(shí)），相比vsm更加耗費(fèi)資源，一般業(yè)界很少采用這類算法。

• Simhash算法

Simhash是google用來處理海量文本去重的算法，同時(shí)也是一種基于LSH(locality sensitive hashing)的算法。簡單來說，和md5和sha哈希算法所不同，局部敏感哈希可以將相似的字符串hash得到相似的hash值，使得相似項(xiàng)會(huì)比不相似項(xiàng)更可能的hash到一個(gè)桶中，hash到同一個(gè)桶中的文檔間成為候選對(duì)。這樣就可以以接近線性的時(shí)間去解決相似性判斷和去重問題。

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

圖1 simhash算法示意圖

Simhash指紋匹配過程

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

Simhash算法效率較高，比較適用于對(duì)于長文本，同時(shí)simhash算法沒有考慮去重的粒度以及詞的順序，面對(duì)高精度時(shí)可能會(huì)帶來準(zhǔn)確度問題。

• Minhash算法

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

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

Minhash算法采用最小哈希函數(shù)族（一組隨機(jī)的最小哈希函數(shù)）來構(gòu)建文檔的最小哈希簽名。文檔的最小哈希簽名矩陣是對(duì)原始特征矩陣降維的結(jié)果。應(yīng)用過程中，可以使用k個(gè)最小函數(shù)分別計(jì)算出集合的哈希最小值。設(shè)hi表示第i個(gè)最小hash函數(shù)，最小簽名矩陣中列向量為樣本si的最小簽名向量，其中wij表示第j個(gè)最小hash函數(shù)對(duì)樣本i的最小哈希值。

當(dāng)k小于原始集合的長度（k << n）時(shí)，就相當(dāng)于對(duì)數(shù)據(jù)降維。

關(guān)于minhash的原理和推導(dǎo)，以及在大量文本及高維特征下如何快速進(jìn)行最小簽名矩陣的構(gòu)建操作可以參考https://en.wikipedia.org/wiki/MinHash及《大數(shù)據(jù) 互聯(lián)網(wǎng)大規(guī)模數(shù)據(jù)挖掘與分布式處理》。

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

本節(jié)將給出我們?cè)趯?duì)內(nèi)容型網(wǎng)頁（小說、新聞等）去重任務(wù)中總結(jié)出來的算法和實(shí)踐經(jīng)驗(yàn)，特別在當(dāng)前內(nèi)容版權(quán)日益受到重視和保護(hù)的背景下，對(duì)于內(nèi)容版權(quán)方來說，如何從網(wǎng)絡(luò)上發(fā)現(xiàn)和追蹤侵權(quán)和盜版行為日益重要。

從前文可以看出，指紋識(shí)別算法是實(shí)現(xiàn)指紋識(shí)別的關(guān)鍵，它直接決定了識(shí)別率的高低，是指紋識(shí)別技術(shù)的核心。特別是類似新聞?lì)?、小說類網(wǎng)頁在轉(zhuǎn)載或者盜版過程中，文字的個(gè)數(shù)、順序上一般都保持一致，當(dāng)然不排除個(gè)別字錯(cuò)誤或者少一個(gè)字的情況。

指紋生成的過程主要包括將文本全部轉(zhuǎn)換成拼音、截取每個(gè)字拼音的首字母、統(tǒng)計(jì)該粒度內(nèi)字母的頻率分布、通過和參考系比較，將結(jié)果進(jìn)行歸一化、按字母序，將數(shù)字表征轉(zhuǎn)換成數(shù)字。

圖3 指紋生成算法

算法描述：

1. 轉(zhuǎn)拼音：可以解決字符集編碼不一致的問題，可以利用成熟的英文指紋算法，減小分布空間，同時(shí)可以解決同音字替代問題；
2. 截取拼音首字：減小存儲(chǔ)長度和分布空間（26個(gè)字母）；
3. 提取首字母頻率：選擇多少字來計(jì)算指紋，統(tǒng)計(jì)頻率分布。需要設(shè)置顆粒度的大?。ǚ侄未笮。┮约爸丿B率。

大粒度容錯(cuò)性高，但是匹配率低；小粒度容錯(cuò)性低，但是誤報(bào)率高且敏感度高。

重疊率是設(shè)置指紋計(jì)算片段移動(dòng)的窗口大?。?/p>

假設(shè)拼音內(nèi)容長為2n，顆粒長度為n，重疊率為50%，則需要計(jì)算的指紋片段分別為[1-n]，[n/2,3*n/2]，[n,2n]

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

• 若空間為[0,9],即一個(gè)20位的整數(shù)，2^64，需要 8 byte
• 若空間為[0,7],可用一個(gè)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)、指紋存儲(chǔ)、指紋查詢和比對(duì)、數(shù)據(jù)分析、后臺(tái)管理系統(tǒng)等幾個(gè)主要模塊構(gòu)成，如圖4所示。其中存儲(chǔ)層包括匹配結(jié)果信息庫、網(wǎng)頁庫以及指紋庫。

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

1. 爬蟲系統(tǒng)

爬蟲系統(tǒng)從目的上看主要在于抓取互聯(lián)網(wǎng)上的特定領(lǐng)域的網(wǎng)頁（如新聞?lì)惥W(wǎng)頁），爬蟲系統(tǒng)是原始數(shù)據(jù)的唯一來源，只有通過爬蟲系統(tǒng)才能從浩瀚的互聯(lián)網(wǎng)中抓取相似的網(wǎng)頁內(nèi)容。爬蟲系統(tǒng)需要擁有較高的抓取能力和反爬取能力，為整個(gè)系統(tǒng)提供大量的待檢測頁面。

1. 指紋存儲(chǔ)模塊

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

1. 指紋生成模塊

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

1. 指紋查詢和比對(duì)模塊

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

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

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

1. 后臺(tái)管理平臺(tái)

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

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

1. 網(wǎng)頁庫

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

1. 指紋庫

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

1. 匹配信息庫

存儲(chǔ)指紋匹配結(jié)果， 包括待匹配的兩個(gè)指紋， 原始網(wǎng)頁id， 匹配相似度等。

4.2 系統(tǒng)架構(gòu)

圖5 系統(tǒng)架構(gòu)圖

4.3 系統(tǒng)處理流程

本系統(tǒng)的處理流程如圖6所示，系統(tǒng)支持每天自動(dòng)化從母體庫中調(diào)度新的任務(wù)進(jìn)行去重操作。

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

4.4 查詢和比對(duì)系統(tǒng)

查詢和比對(duì)的系統(tǒng)的目的就是快速和高效的找出與目標(biāo)指紋相似性較高的母體指紋。針對(duì)指紋查詢的特點(diǎn)，對(duì)母體指紋庫建立索引，待查詢指紋通過查詢索引，即可發(fā)現(xiàn)最可能匹配的母體。

指紋查詢比對(duì)流程如下：

1. 建立索引

每個(gè)母體指紋描述的是母體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]。與其他算法一樣的是，也需要考慮索引的粒度，粒度的大小同時(shí)應(yīng)考慮指紋算法選擇的粒度。

2. 采樣

根據(jù)待匹配文本的特點(diǎn)（長度），選擇合適的粒度和片段，重要的是保證匹配的正確性的同時(shí)，減少生成指紋的運(yùn)算量。

3. 提取指紋

根據(jù)指紋生成算法生成待查詢指紋。

4. 查詢指紋

將待查詢指紋進(jìn)行索引查詢，統(tǒng)計(jì)命中母體和命中次數(shù)，并按照次數(shù)排序，選擇命中次數(shù)高的母體作為可疑對(duì)象，次數(shù)低于閾值，可忽略。

5. 后處理

結(jié)合歷史統(tǒng)計(jì)模型，篩選結(jié)果。匹配結(jié)果不確定，可進(jìn)行第二輪細(xì)致比對(duì)或人工驗(yàn)證。

5. 總結(jié)

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

作者簡介

文輝，同濟(jì)大學(xué)計(jì)算機(jī)應(yīng)用技術(shù)專業(yè)碩士，現(xiàn)任達(dá)觀數(shù)據(jù)聯(lián)合創(chuàng)始人，主要負(fù)責(zé)據(jù)推薦系統(tǒng)、數(shù)據(jù)采集系統(tǒng)、大數(shù)據(jù)平臺(tái)架構(gòu)等主要系統(tǒng)的研究和開發(fā)。曾就職于盛大文學(xué)數(shù)據(jù)中心部門，負(fù)責(zé)推薦系統(tǒng)、爬蟲系統(tǒng)、數(shù)據(jù)挖掘和分析等大數(shù)據(jù)系統(tǒng)的研發(fā)工作，在數(shù)據(jù)挖掘和采集、Hadoop/Hive、Spark等方面具備充足的研發(fā)和實(shí)踐經(jīng)驗(yàn)。