代理加盟 2019全新代理計劃 賺錢+省錢雙管齊下,獨立平臺,豐厚利潤!

您現在的位置: 秀站網 > 站長學院 > SEO資訊 >

什么是文本指紋和內容指紋系統

來源:未知 發布時間:2019-03-30熱度:我要評論
文本指紋算法是百度爬蟲系統中較讓采集內容的站長們頭疼的算法之一,但對于辛苦做白帽的站長卻是福利。 文本指紋算法 現在網上的小說、新聞、圖片盜版實在猖狂,需要對網頁或文本進行去重和過濾。最簡單的文本相似性計算文本中md5或者sha哈希值。但有可能造成極小的文...

織夢模板免費下載,無需注冊無需充值

文本指紋算法是百度爬蟲系統中較讓采集內容的站長們頭疼的算法之一,但對于辛苦做白帽的站長卻是福利。

文本指紋算法

現在網上的小說、新聞、圖片盜版實在猖狂,需要對網頁或文本進行去重和過濾。最簡單的文本相似性計算文本中md5或者sha哈希值。但有可能造成極小的文本差異通過md5或sha哈希值計算出來的指紋就會不同。

好的指紋應具備如下特點

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

②指紋越相似,文本相似性就越高;

③指紋生成和匹配效率高。

常用的指紋算法

k-shingle算法

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

Simhash算法

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

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

圖1 simhash算法示意圖

Simhash指紋匹配過程

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

Simhash算法效率較高,比較適用于對于長文本,同時simhash算法沒有考慮去重的粒度以及詞的順序,面對高精度時可能會帶來準確度問題。

Minhash算法

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

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

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

當k小于原始集合的長度(k << n)時,就相當于對數據降維。

內容型網頁文本指紋算法

本節將給出我們在對內容型網頁(小說、新聞等)去重任務中總結出來的算法和實踐經驗,特別在當前內容版權日益受到重視和保護的背景下,對于內容版權方來說,如何從網絡上發現和追蹤侵權和盜版行為日益重要。

從前文可以看出,指紋識別算法是實現指紋識別的關鍵,它直接決定了識別率的高低,是指紋識別技術的核心。特別是類似新聞類、小說類網頁在轉載或者盜版過程中,文字的個數、順序上一般都保持一致,當然不排除個別字錯誤或者少一個字的情況。

指紋生成的過程主要包括將文本全部轉換成拼音、截取每個字拼音的首字母、統計該粒度內字母的頻率分布、通過和參考系比較,將結果進行歸一化、按字母序,將數字表征轉換成數字。

圖3 指紋生成算法

算法描述:

1. 轉拼音:可以解決字符集編碼不一致的問題,可以利用成熟的英文指紋算法,減小分布空間,同時可以解決同音字替代問題;

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

3. 提取首字母頻率:選擇多少字來計算指紋,統計頻率分布。需要設置顆粒度的大小(分段大小)以及重疊率。

大粒度容錯性高,但是匹配率低;小粒度容錯性低,但是誤報率高且敏感度高。

重疊率是設置指紋計算片段移動的窗口大小:

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

4. 減去參考系:頻率減去參考系

5. 歸一化:將每個字母的數字特征歸一化到一個閉區間內,如[0,9],按照字母順序連接數字特征,變成一個數字,即指紋。

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

若空間為[0,7],可用一個20位的8進制數,8^20,需要 8 byte

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

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

歸一化過程的算法步驟如下,假設顆粒長度為m:

達觀指紋系統結構

基本架構

達觀指紋追蹤系統主要由爬蟲系統、指紋生成系統、指紋存儲、指紋查詢和比對、數據分析、后臺管理系統等幾個主要模塊構成,如圖4所示。其中存儲層包括匹配結果信息庫、網頁庫以及指紋庫。

圖4 指紋追蹤系統模塊圖

爬蟲系統

爬蟲系統從目的上看主要在于抓取互聯網上的特定領域的網頁(如新聞類網頁),爬蟲系統是原始數據的唯一來源,只有通過爬蟲系統才能從浩瀚的互聯網中抓取相似的網頁內容。爬蟲系統需要擁有較高的抓取能力和反爬取能力,為整個系統提供大量的待檢測頁面。

指紋存儲模塊

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

指紋生成模塊

指紋生成模塊的輸入是一行文本,其輸出為該文本的指紋表示,為了達到較高的對比準確率,一個好的指紋生成系統至關重要。

指紋查詢和比對模塊

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

數據分析

數據分析系統需要對大量的文本及其對比結果進行統計數據分析。

后臺管理平臺

提供數據分析的展示,并提供用戶使用查詢和輸出分析報告等。

數據存儲模塊

網頁庫

主要存放爬蟲系統抓取的網頁信息、站點信息,本系統網頁庫采用mongo DB。

指紋庫

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

匹配信息庫

存儲指紋匹配結果, 包括待匹配的兩個指紋, 原始網頁id, 匹配相似度等。

4.2 系統架構

圖5 系統架構圖

4.3 系統處理流程

本系統的處理流程如圖6所示,系統支持每天自動化從母體庫中調度新的任務進行去重操作。

圖6 系統流程圖

4.4 查詢和比對系統

查詢和比對的系統的目的就是快速和高效的找出與目標指紋相似性較高的母體指紋。針對指紋查詢的特點,對母體指紋庫建立索引,待查詢指紋通過查詢索引,即可發現最可能匹配的母體。

指紋查詢比對流程如下:

建立索引

每個母體指紋描述的是母體ID -> 特征的關系,可以通過以特征為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]。與其他算法一樣的是,也需要考慮索引的粒度,粒度的大小同時應考慮指紋算法選擇的粒度。

采樣

根據待匹配文本的特點(長度),選擇合適的粒度和片段,重要的是保證匹配的正確性的同時,減少生成指紋的運算量。

提取指紋

根據指紋生成算法生成待查詢指紋。

查詢指紋

將待查詢指紋進行索引查詢,統計命中母體和命中次數,并按照次數排序,選擇命中次數高的母體作為可疑對象,次數低于閾值,可忽略。

后處理

結合歷史統計模型,篩選結果。匹配結果不確定,可進行第二輪細致比對或人工驗證。

總結

對于網頁去重、內容盜版追蹤、內容聚類等應用來說,指紋模塊都是極其重要的模塊。本文介紹了一些比較常用的指紋算法,包括k-shingle、simhash、minhash;同時介紹了達觀數據自主開發的指紋追蹤系統及其關鍵算法,達觀數據在指紋系統構建和算法方面積累了豐富的經驗,沒有最好的算法,只有合適的算法,在實際的使用過程中,需要根據具體業務場景,確定架構和算法。

本文地址:http://www.alolpiu.com.cn/seo/1203.html

責任編輯:秀站網

    發表評論

    評論列表(條)

      新时时彩中奖怎么查