湯建明 寇小強

(華北計算機系統(tǒng)工程研究所 北京 100083)

0 引 言

隨著互聯(lián)網(wǎng)的普及，每天有數(shù)以億計的新內(nèi)容在網(wǎng)絡(luò)上產(chǎn)生。這些內(nèi)容或者以新聞報道的形式，或者以公眾號和專欄文章的形式呈現(xiàn)在人們眼中?；谌绱撕Ａ康奈谋緮?shù)據(jù)，其中有著大量的冗余相似內(nèi)容。有研究表明，在應(yīng)用系統(tǒng)所保存的數(shù)據(jù)中，冗余數(shù)據(jù)約占60%左右[1]。因此，如何有效地來識別互聯(lián)網(wǎng)上的重復(fù)信息，對學(xué)術(shù)界和工業(yè)界來說都是一個很有意義的課題。

舉一個例子：對于基本所有的搜索引擎系統(tǒng)來說，它們底層的爬蟲系統(tǒng)會去大量抓取網(wǎng)絡(luò)上的文本等數(shù)據(jù)資源，顯然，抓取到重復(fù)和高度相似的網(wǎng)頁和文本進(jìn)行存儲和收錄是沒有意義的，這樣不僅浪費存儲資源，也會對后續(xù)的計算處理帶來不好的影響；同時，展示重復(fù)和高度相似的檢索結(jié)果對于用戶來說也是不好的使用體驗。對于像傳統(tǒng)的新聞門戶網(wǎng)站和推薦系統(tǒng)應(yīng)用來說，保證文章質(zhì)量是非常重要的。所以，有必要保證對于每天新產(chǎn)生的文本內(nèi)容進(jìn)行相似度判斷和去重處理。對于相似度過高的文章只保證唯一一份內(nèi)容入庫，這樣不僅節(jié)約了數(shù)據(jù)存儲的成本，也會提高用戶的檢索體驗。

本文基于simhash算法【2-3】設(shè)計和實現(xiàn)一個文本去重系統(tǒng)，采用Ansj開源分詞工具對原始文本內(nèi)容進(jìn)行分詞處理，數(shù)據(jù)存儲采用Rdis+Mysql+Hbase。

1 海量網(wǎng)絡(luò)文本去重系統(tǒng)設(shè)計

1.1 整體架構(gòu)

圖1是本文海量網(wǎng)絡(luò)文本去重系統(tǒng)的整體功能模塊設(shè)計圖。整個系統(tǒng)可以主要分成三個部分：一是分詞模塊對原始文本內(nèi)容進(jìn)行分詞處理；二是判重模塊對處理后的文章進(jìn)行相似度判斷；三是入庫模塊對經(jīng)過去重的文本數(shù)據(jù)進(jìn)行入庫處理。

1.2 工作流程

圖2是本文海量網(wǎng)絡(luò)文本去重系統(tǒng)的整體調(diào)用處理流程。整個系統(tǒng)會用Maven打成war包，最后部署在Tomcat服務(wù)器中。系統(tǒng)以HttpServlet接口的方式提供調(diào)用入口。每篇文章有一個唯一標(biāo)識，記為nid。經(jīng)過預(yù)處理的文本數(shù)據(jù)以JSON字符串的形式進(jìn)入系統(tǒng)，主要包含有文章來源url、文章標(biāo)題title和文章內(nèi)容content等屬性。最后會返回一個唯一標(biāo)識，以docId來表示，內(nèi)容相似的文章對應(yīng)同一個docId值。系統(tǒng)會依次根據(jù)文章的url、title和content去Redis中查找是否有相同的緩存值，有則直接返回對應(yīng)的docId值，沒有則會根據(jù)文章的url、title和content計算出一個新的docId值，并緩存在Redis中。數(shù)據(jù)庫Mysql中會保存所有nid和docId的對應(yīng)關(guān)系。Hbase中會保存文章的所有內(nèi)容信息，用docId來唯一標(biāo)識。

圖2 工作流程

2 關(guān)鍵實現(xiàn)技術(shù)

2.1 Ansj分詞

Ansj是一個分詞效果非常精準(zhǔn)的中文分詞器[4]，它完全開源，是ICTLAS的Java實現(xiàn)版本，同樣是構(gòu)建了Bigram[5]+HMM的模型來進(jìn)行分詞。雖然它的基本原理和ICTLAS一樣，但是Ansj在工程上做了一些優(yōu)化，比如：用DAT高效實現(xiàn)的檢索詞典、用鄰接表來實現(xiàn)分詞DAG、同時支持基于個人需求的自定義分詞詞典，以及支持消歧義規(guī)則的自定義等[8]特點。

2.2 simhash文本去重算法

Simhash是locality sensitive hash(局部敏感哈希)的一種，最早是由Moses Charikar在《similarity estimation techniques from rounding algorithms》一文中提出來的。

該算法的主要思想就是降維，將高維的特征向量經(jīng)過一系列的處理后映射成低維的特征向量，然后通過比較兩個向量的Hamming Distance來判斷文本是否高度相似甚至完全重復(fù)。其中，Hamming Distance通常又稱為漢明距離[7]，這是信息論中的一個概念，指的是兩個長度相等的字符串之間對應(yīng)的各個位置上不同的字符的總個數(shù)。簡單來說就是，將其中一個字符串變?yōu)榱硪粋€字符串總共需要改變的字符總個數(shù)。這樣一來，通過對比文檔內(nèi)容的simhash值的漢明距離，就能夠得到它們之間的相似度是多少。

2.3 Redis+Mysql+HBase三級存儲系統(tǒng)

Redis是一個支持網(wǎng)絡(luò)的、基于內(nèi)存存儲、數(shù)據(jù)可持久化的開源Key-Value數(shù)據(jù)庫[9]。和傳統(tǒng)的關(guān)系型數(shù)據(jù)庫Mysql相比，Redis的查詢和存儲性能都要高得多。由于Redis可基于內(nèi)存存儲，所以非常適合用作緩存處理，這樣可以加快存儲和查詢速度，也能夠減輕數(shù)據(jù)庫的負(fù)載壓力。

在本文的海量網(wǎng)絡(luò)文本去重系統(tǒng)中，Redis用來存儲文章url、title和content經(jīng)過處理后的索引，這樣，即使是在高并發(fā)的網(wǎng)絡(luò)場景下，每次有新的請求進(jìn)入系統(tǒng)，也不會存在查詢瓶頸。這樣的緩存設(shè)計也將真正的文章內(nèi)容存儲解耦，使得判重模塊只關(guān)注于文章內(nèi)容去重，數(shù)據(jù)的存儲異步地載入庫模塊進(jìn)行，可以在很大程度上提高整個系統(tǒng)的處理性能。

在本系統(tǒng)的三級存儲系統(tǒng)設(shè)計中，Mysql只用來存儲每篇文章的唯一標(biāo)識nid和docId的映射關(guān)系，并不真正存儲文章的數(shù)據(jù)內(nèi)容。互聯(lián)網(wǎng)上的海量文本數(shù)據(jù)包含的屬性大不相同，Mysql不適合用來存儲這種數(shù)據(jù)，當(dāng)數(shù)據(jù)量大到一定級別后，Mysql的性能也會大打折扣。因此，文章的數(shù)據(jù)最后存儲在HBase中。

HBase是一種分布式的存儲系統(tǒng)，它構(gòu)建在HDFS之上、支持面向列的存儲[6]。HBase支持?jǐn)?shù)據(jù)實時地讀寫，同時，它對超大規(guī)模的數(shù)據(jù)集的隨機訪問也支持的非常好?；贖Base的這些特性，非常適合用來存儲海量的文本數(shù)據(jù)，其列存儲屬性極易擴展，不會因為文章內(nèi)容各不相同的屬性而帶來存儲困難。

3 海量網(wǎng)絡(luò)文本去重系統(tǒng)的實現(xiàn)

3.1 分詞模塊

對于請求的Json數(shù)據(jù)，其格式大致如下：

json=

{

″url″: ″http://www.help.com″,

″title″: ″測試″,

″content″: ″這是一個測試″,

″category″: ″0″,

″media″: ″sina″,

″imageCount″: ″4″

}

url表示文章的網(wǎng)絡(luò)地址，title表示文章的標(biāo)題，content表示文章的內(nèi)容，category表示文章的屬性，media表示文章所屬的媒體，imageCount表示文章中的插圖數(shù)量。在該系統(tǒng)中，我們只關(guān)注title和content兩個字段的內(nèi)容分詞。

分詞模塊將title和content的內(nèi)容切分成一個一個單獨的詞，采用Ansj提供的ToAnalysis分詞實現(xiàn)，對于分詞后的單詞，保存在Redis緩存中，過期時間設(shè)置為7天。

3.2 內(nèi)容判重模塊

該模塊是系統(tǒng)的核心模塊。主要依據(jù)文章的url、title和content三個屬性值來進(jìn)行判重處理。

經(jīng)過分詞處理的文章title和content，會首先經(jīng)過判重模塊提供的簽名方法生成一個唯一的64位簽名，該方法則基于simhash算法實現(xiàn)。simhash算法主要分為5個步驟來進(jìn)行：

(1) 分詞 該步驟首先調(diào)用分詞模塊提供的方法，將待處理的語句先進(jìn)行初步的分詞，這樣就得到了語句有效的特征向量，接著為特征向量來設(shè)置權(quán)重，這里可以根據(jù)需求自定義n個級別的權(quán)重。比如將n設(shè)為5，則可以用1～5來表示每個向量的權(quán)重。在具體實現(xiàn)中，可以根據(jù)每個單詞在整段文本數(shù)據(jù)中出現(xiàn)的次數(shù)來定義它對應(yīng)的權(quán)重值大小。

(2) 計算hash值 通過hash函數(shù)來算出上一步中每個特征向量各自的hash值，hash值可以看成用二進(jìn)制數(shù)0和1所組成的n-bit位簽名。比如“去重”的hash值計算出來為110010，“系統(tǒng)”的hash值計算出來為101001。經(jīng)過這樣處理之后，字符串值就變成了一系列的二進(jìn)制數(shù)字組合。

(3) 加權(quán)處理 在算出了單詞hash值的基礎(chǔ)之上，對這些特征向量來進(jìn)行加權(quán)處理，具體實現(xiàn)方式即：W=hash×weight，weight代表該單詞在文本中的權(quán)重。對上一步算出來的每一個hash值，計算它二進(jìn)制數(shù)字每一位的加權(quán)結(jié)果。如果該位的值為1，那么就和權(quán)值進(jìn)行正相乘；如果該位的值為0，就和權(quán)值進(jìn)行負(fù)相乘。例如：假如上一步“去重”的權(quán)值為3，則加權(quán)后的值計算為W(去重)=3 3-3-3 3-3；同理，假設(shè)“系統(tǒng)”的權(quán)值為5，則加權(quán)后的值為W(系統(tǒng))=5-5 5-5-5 5。其余所有特征向量依此類推。

(4) 合并計算 將所有經(jīng)過加權(quán)計算的特征向量的加權(quán)結(jié)果累加，得到這段文本的總的加權(quán)值。例如：拿前面的“去重”和“系統(tǒng)”舉例，累加得到“3+5 3-5 -3+5 -3-5 3-5 -3+5”，最后結(jié)果為“8 -2 2 -8 -2 2”。

(5) 降維處理 對于以上處理后的n-bit的hash加權(quán)值，對每一位，如果該位的值大于0則置為1，否則置為0，從而得到該文本語句的simhash值。同樣以上面的例子來看，則降維處理后的值為101001，這就是最后這段文本的simhash簽名。

圖3體現(xiàn)了計算simhash簽名的過程。

圖3 計算simhash簽名

在得到每篇文檔對應(yīng)的simhash簽名值之后，通過計算兩個簽名值的漢明距離來判斷它們是否相似。判斷標(biāo)準(zhǔn)可以根據(jù)具體業(yè)務(wù)場景來定，本系統(tǒng)采用業(yè)界工程實踐較好的3作為判斷標(biāo)準(zhǔn)，即對于64位的simhash值，如果漢明距離相差在3以內(nèi)的話，就可以認(rèn)為兩篇文檔是高度相似的。

以上通過計算simhash值來判斷相似的過程是判重模塊所提供的一個方法，具體到本系統(tǒng)的業(yè)務(wù)邏輯處理中，判重流程如下：

(a) 根據(jù)url和固定前綴值URL_INDEX形成的字符串去Redis緩存中查找是否有相同的值，如果存在，則直接返回對應(yīng)的docId值；如果不存在，則進(jìn)行步驟(b)。

(b) 根據(jù)title生成的simhash簽名以及固定前綴值TITLE_INDEX形成的字符串去Redis中查找是否有相同的值，如果存在，則直接返回對應(yīng)的docId值；如果不存在，則進(jìn)行步驟(c)。

(c) 根據(jù)content生成的simhash簽名以及固定前綴值CONTENT_INDEX形成的字符串去Redis中查找是否有相同的值，如果存在，則直接返回對應(yīng)的docId值；如果不存在，則進(jìn)行步驟(d)。

(d) 經(jīng)過前面三步流程查找都沒找到，說明這一次請求的文章是一篇新的文章，則根據(jù)該文章的url、title和content值生成一個唯一的64位docId值，同時對title和content的simhash值建立索引并進(jìn)行緩存處理，以供下一次新的請求做查詢比對處理。

以上即為整個判重模塊的設(shè)計實現(xiàn)。

3.3 數(shù)據(jù)入庫模塊

數(shù)據(jù)入庫模塊異步地進(jìn)行數(shù)據(jù)的入庫存儲處理。

對每一次請求，如果進(jìn)過判重模塊處理后為相似的文章，則在Mysql中添加一條記錄，保存該文章nid和已經(jīng)存在的相似文章的docId的映射關(guān)系；如果判重處理后為新的文章，則在Mysql中添加一條記錄，保存該文章nid和新生成的docId值的映射關(guān)系。對每一個docId值，只在HBase中保存一份熱度最高的文章內(nèi)容。

我們在其他的系統(tǒng)中需要檢索或者推薦文章時，就不會出現(xiàn)重復(fù)相似的文章，因為入庫模塊最后數(shù)據(jù)入HBase的過程中保證了一個docId值在HBase中只保存有唯一一篇文章。

3.4 實驗結(jié)果展示

本系統(tǒng)采用Java開發(fā)實現(xiàn)，采用Maven作為項目構(gòu)建工具，最后部署在Linux服務(wù)器上，以war包形式部署在tomcat容器中，提供一個訪問接口供外部調(diào)用，具體調(diào)用形式如下：

127.0.0.1:8080/docId/getDocId?json={ }

其中,127.0.0.1為系統(tǒng)部署的服務(wù)器網(wǎng)絡(luò)地址，8080為訪問的端口號，docId為服務(wù)名稱，getDocId為訪問接口，json={}為請求數(shù)據(jù)，以Json形式傳輸，具體字段可見3.1中所描述。利用Postman來模擬請求，先自定義一個測試數(shù)據(jù)如下：

json=

{

″url″:″http://www.simhash.com″,

″title″: ″計算機應(yīng)用與軟件″,

″content″: ″海量網(wǎng)絡(luò)文本去重系統(tǒng)實驗測試，這是一段測試文本的內(nèi)容?！?

″category″: ″0″,

″media″: ″test1″,

″imageCount″: ″4″

}

系統(tǒng)運行過程如圖4所示。

可以看到，如果是一篇新的文章請求系統(tǒng)，則系統(tǒng)內(nèi)部會經(jīng)過url、title和content三次查找判重操作，最后會在Redis中緩存新的索引，并返回計算生成的新的docId值。最后結(jié)果以Json字符串形式返回，如下所示：

{

″filterReason″: ″docId_filter good news″,

″docId″: ″cdd71f57317390e7-ad7b2a053b6e4176″,

″filterStatus″: ″good″,

″status″: ″success″

}

接下來我們再定義一個和上面相似的文本內(nèi)容作為請求數(shù)據(jù)去請求該去重系統(tǒng)，自定義數(shù)據(jù)如下：

json=

{

″url″: ″http://www.simhash1.com″,

″title″: ″計算機應(yīng)用和軟件2″,

″content″: ″海量網(wǎng)絡(luò)文本去重系統(tǒng)實驗檢測，這是一段相似的測試文本的內(nèi)容?！?

″category″: ″0″,

″media″: ″test2″,

″imageCount″: ″3″

}

可以和上面的請求數(shù)據(jù)對比，兩者高度相似，這次系統(tǒng)運行過程如圖5。

從圖中紅線圈可以看到，系統(tǒng)最后判斷content排重成功，也就是成功判定出這篇請求的文章和上一篇文章相似。在查詢Redis判重的過程中，由于標(biāo)題和內(nèi)容都相似，系統(tǒng)也沒有重新計算新的索引去緩存。最后返回的docId值也和上一篇相同，也就是沒有重新計算生成新的docId。

4 結(jié) 語

海量網(wǎng)絡(luò)文本去重系統(tǒng)用于對互聯(lián)網(wǎng)上充斥著的大量重復(fù)網(wǎng)頁內(nèi)容和文章進(jìn)行去重處理。由于采用多模塊的解耦設(shè)計，可以保證系統(tǒng)在高并發(fā)的訪問情況下做到快速響應(yīng)。整個系統(tǒng)采用Maven作為項目構(gòu)建工具，易于移植和擴展。同時，本系統(tǒng)提供標(biāo)準(zhǔn)的HttpServlet接口，采用Json作為通用的網(wǎng)絡(luò)數(shù)據(jù)傳輸格式，可以很方便地接入到其他需要進(jìn)行文本去重處理的工程項目中。未來，該系統(tǒng)將添加圖片判重處理模塊，這樣使得系統(tǒng)的適用范圍更廣，可以識別出相似的圖片，這樣對包含有插圖的文本內(nèi)容可以進(jìn)行更為精確地去重判斷和處理。在系統(tǒng)的并發(fā)處理和存儲性能方面也將展開進(jìn)一步的研究工作，從而提高系統(tǒng)的性能水平。