王曉霞，孫德才

（渤海大學(xué)信息科學(xué)與技術(shù)學(xué)院，錦州 121013）

0 引言

隨著互聯(lián)網(wǎng)的高速發(fā)展，人們可以利用各種新媒體工具在網(wǎng)絡(luò)上發(fā)表自己的觀點(diǎn)，由此也使一些話題迅速成為網(wǎng)絡(luò)焦點(diǎn)話題。面對(duì)數(shù)量龐大的網(wǎng)絡(luò)言論，網(wǎng)絡(luò)信息安全監(jiān)測(cè)領(lǐng)域的研究需要引入海量大數(shù)據(jù)分析技術(shù)［1］。大數(shù)據(jù)信息安全是為適應(yīng)大數(shù)據(jù)時(shí)代的輿情和服務(wù)而發(fā)展起來的，是專注于海量信息采集、監(jiān)測(cè)和分析等技術(shù)的一個(gè)新的研究領(lǐng)域。

如何從巨大的數(shù)據(jù)集中快速找出滿足要求的信息，是信息安全監(jiān)測(cè)研究中需要解決的一個(gè)基本問題。在大數(shù)據(jù)清洗中，為去除相似信息，常采用相似連接［2-6］技術(shù)。當(dāng)前的相似連接算法主要有單機(jī)算法和并行算法。單機(jī)算法因單節(jié)點(diǎn)計(jì)算能力有限導(dǎo)致其橫向擴(kuò)展能力不強(qiáng)，并行算法因其運(yùn)行在分布式集群的多節(jié)點(diǎn)上，橫向擴(kuò)展能力較強(qiáng)，漸漸成為一種主流技術(shù)。MapReduce框架是一種高效的分布式編程框架，基于MapReduce框架的相似連接并行算法［4-10］在大數(shù)據(jù)處理中被廣泛采用。它的主要研究?jī)?nèi)容包括V-SMART-Join［7］、PassJoinKMR［8］、Mass-Join［9］、SAX［10］和FS-Join［11］等。

大數(shù)據(jù)內(nèi)容安全監(jiān)測(cè)的快速相似匹配并行算法是大數(shù)據(jù)處理中的熱點(diǎn)問題，對(duì)應(yīng)出現(xiàn)了很多先進(jìn)的算法，MassJoin算法是一個(gè)支持多數(shù)據(jù)集的相似連接算法，能快速找出文本集間編輯距離［8］滿足要求的文本對(duì)，算法分為四個(gè)階段：統(tǒng)計(jì)階段、過濾階段、驗(yàn)證階段1和驗(yàn)證階段2。然而該算法在匹配速度上稍顯不足。

本文將改進(jìn)MassJoin算法［9］中的過濾和匹配技術(shù)，并提出一種新的基于MapReduce框架的并行算法MQSM（MapReduce and Q-gram based Similarity Match），擬解決信息安全監(jiān)測(cè)中的快速相似匹配問題。

1 內(nèi)容相似匹配及新過濾方案

1.1 基于內(nèi)容的相似匹配的問題定義

基于內(nèi)容的相似匹配是從一個(gè)已知的文本集中找出與給定查詢集中匹配度達(dá)到要求的所有文本，匹配度定義如下：

定義1給定兩個(gè)文本s和d，稱s為查詢串，d為文本串，兩串間的q元匹配度定義為

式（1）中，simq(s,d)為兩串間的q元匹配度，|s|為串長(zhǎng)，[s]q為文本s拆分得到的連續(xù)且重疊q-1個(gè)字符的q-gram［12］的總數(shù)目（q-gram是一個(gè)長(zhǎng)度為q的子串），即[s]q=|s|-q+1,Sq(s,d)為文本s拆分得到的[s]q個(gè)q-gram在文本d中出現(xiàn)的個(gè)數(shù)，Cq(s,d)為s的[s]q個(gè)q-gram構(gòu) 成 的 子串在d中匹配到的最長(zhǎng)子串長(zhǎng)度。當(dāng)q=1時(shí)為字符級(jí)別的匹配度，當(dāng)q＞1時(shí)為多元匹配度。在該匹配度公式中，前半部分描述的是q-gram的覆蓋情況，后半部分描述的是q-gram的連續(xù)情況。如：s為“thirty”，d為“thirsty”和q=2，則|s|=6，[s]2=5，Sq(s,d)=4，Cq(s,d)=4（th，hi，ir三個(gè)連續(xù)且重疊q-gram構(gòu)成的子串為最長(zhǎng)匹配子串），最終sim（2“thirty”“,thirsty”）=0.73。這里的匹配度不同于編輯距離［7］，編輯距離描述的是兩個(gè)串間的近似情況，而本文的匹配度描述的是一個(gè)串在另外一個(gè)串中匹配的情況。

在內(nèi)容信息安全監(jiān)測(cè)系統(tǒng)中，給定一個(gè)查詢集和一個(gè)大文本集，系統(tǒng)要在大文本集中快速發(fā)現(xiàn)與查詢集中匹配度達(dá)到要求的文本，這里查詢集通常是一個(gè)由關(guān)鍵詞（詞或句子）構(gòu)成的集合。設(shè)某個(gè)查詢總共有N個(gè)關(guān)鍵詞，則此時(shí)公式（1）中

定義2基于內(nèi)容的相似匹配問題：給定查詢集Q、大文本集D和q元匹配度參數(shù)τ，基于內(nèi)容的相似匹配問題是在Q和D間找出所有滿足simq(si,dj)≥τ,si∈Q,dj∈D的所有匹配對(duì)。

如給定查詢集Q和文本集D如表1，在每個(gè)集合中“#”號(hào)前面的是查詢編號(hào)或文本編號(hào)，后 面 的 是 內(nèi) 容。如τ=0.9,q=2，則sim2(s1,d1)=1≥0.9是 一 個(gè) 匹 配 對(duì)；而sim2(s2,d2)=0.85＜0.9，則不是匹配對(duì)。

表1 查詢集和文本集例子

1.2 基于內(nèi)容的相似匹配過濾方案

因給定的大文本集D中含有大量的文本串，查詢集Q中也有一定數(shù)量的查詢串，因此潛在串對(duì)是海量的。而計(jì)算所有可能串對(duì)的匹配度需要花費(fèi)大量的時(shí)間，因此本文擬采用過濾器先過濾掉那些不滿足要求的串對(duì)，然后再對(duì)通過過濾的候選對(duì)進(jìn)行計(jì)算。為實(shí)現(xiàn)快速過濾，新算法提出了一種基于分割子串的過濾方案。

定理1給定查詢串s、文本串d和q元匹配度參數(shù)τ。設(shè)串s中共有N個(gè)關(guān)鍵詞，把每個(gè)關(guān)鍵詞si都分割成||si-q+1個(gè)連續(xù)且重疊的長(zhǎng)度為q的q-gram，設(shè)文本d中含有這[s]q個(gè)q-gram中 的Sq(s,d)個(gè)，此時(shí)如則一定有simq(s,d)＜τ，即s,d一定不是匹配對(duì)。

證明：設(shè)因N≥1,q-1≥0則因文本d共享了Sq(s,d)個(gè)q-gram，則能構(gòu)成的最長(zhǎng)匹配子串長(zhǎng)度和不超過Sq(s),d+N(q-1)，即Cq(s,d)≤Sq(s,d)+N(q-1)，則即

2 MQSM相似匹配算法

給定查詢集Q、大文本集D和匹配度參數(shù)τ，相似匹配算法需要快速找出滿足匹配度要求的查詢/文本對(duì)。本文提出的新算法MQSM采用MapReduce框架來實(shí)現(xiàn)相似匹配的并行計(jì)算，算法包括三個(gè)階段：配對(duì)階段、過濾階段和驗(yàn)證階段。每個(gè)階段又包括Map過程、Shuffle過程和Reduce過程。其中Shuffle過程會(huì)將Map過程中生成的所有鍵/值對(duì)按鍵值進(jìn)行混淆、排序，并把具有相同鍵的鍵/值對(duì)送到同一個(gè)Reduce節(jié)點(diǎn)，作為Reduce過程的輸入，以后各階段中的Shuffle過程因原理相同不再描述。MapReduce是一個(gè)分布式編程框，因此程序在集群中運(yùn)行時(shí)各數(shù)據(jù)節(jié)點(diǎn)會(huì)開啟眾多的Map任務(wù)和Reduce任務(wù)進(jìn)行并行計(jì)算。

2.1 配對(duì)階段

由1.2節(jié)可知，定理1是一個(gè)無關(guān)對(duì)過濾條件，使用定理1能拋棄那些共享q-gram數(shù)目達(dá)不到要求的查詢/文本對(duì)。為方便地使用定理1進(jìn)行快速過濾，需要對(duì)輸入的查詢和文本進(jìn)行字符串分隔，然后才能根據(jù)查詢串和文本串間共享子串的情況進(jìn)行過濾。

2.1.1 Map過程

每個(gè)Map任務(wù)處理的數(shù)據(jù)是一個(gè)鍵/值對(duì)n,c，其中n是數(shù)據(jù)分片號(hào)（內(nèi)容的偏移量），而數(shù)值c則是查詢集Q或文本集D中的一行內(nèi)容。此時(shí)需根據(jù)內(nèi)容來源不同進(jìn)行分別處理。為進(jìn)行相似匹配，新算法針對(duì)內(nèi)容c生成索引子串或匹配子串，具體過程如下。

生成匹配子串：如分片來源于查詢集Q，從內(nèi)容c中提取出查詢編號(hào)sid和查詢內(nèi)容s（“#”分隔）。因?yàn)椴樵僺是一個(gè)關(guān)鍵詞（詞或句子）集合，首先提取出所有關(guān)鍵詞。為使每個(gè)關(guān)鍵詞都能在容忍一定量錯(cuò)誤的情況下匹配到文本集中的文本，需把每個(gè)關(guān)鍵詞都拆分成連續(xù)且重疊q-1個(gè)字符的q-gram。設(shè)sji表示關(guān)鍵詞si第j個(gè)q-gram，0≤j＜|si|-q+1，則輸出一個(gè)作為匹配子串的鍵/值對(duì)，即，其中‘Q’符號(hào)代表該項(xiàng)是一個(gè)匹配子串。

生成索引子串：如分片來源于文本集D，則提取c中文本編號(hào)did和文本內(nèi)容d。為使查詢中拆分得到的q-gram能夠匹配到該文本，新算法把d也拆分成連續(xù)且重疊的q-gram，設(shè)dk表示d的第k個(gè)q-gram，0≤k＜|d|-q+1，則輸出一個(gè)索引子串的鍵/值對(duì)，即。

2.1.2 Reduce過程

每個(gè)Reduce任務(wù)將處理Shuffle結(jié)果中的一個(gè)鍵/值對(duì)，即，其中sg是子串（索引子串或匹配子串），后面列表是該子串下的索引子串項(xiàng)和匹配子串項(xiàng)。此時(shí)依次處理列表中每項(xiàng)，如是索引子串項(xiàng)did則加入到列表DL中；如是匹配子串項(xiàng)‘Q’sid則提取出sid，并把sid加入到集合QS中。處理完畢后，如此時(shí)DL或QS為空，則該子串中一定不存在候選串對(duì)。通過該過濾條件，新算法能夠過濾掉大量不存在共享q-gram的串對(duì)。如DL和QS都不空，則為集合QS中每個(gè)sid都生成一個(gè)鍵/值對(duì)（鍵 為sid，值 為DL列 表）并 輸 出，即。處理完集合QS后，Reduce任務(wù)完成。

2.2 過濾階段

配對(duì)階段的輸出結(jié)果是所有候選對(duì)的集合，由大量的鍵/值對(duì)組成，集合中每個(gè)鍵/值對(duì)都是文本集D與一個(gè)查詢的候選對(duì)情況。過濾階段的主要任務(wù)是采用定理1快速去除那些q-gram命中數(shù)達(dá)不到要求的候選對(duì)。而定理1中過濾條件需要在候選對(duì)中查詢串的信息，因此過濾階段除需要讀取配對(duì)階段的輸出結(jié)果外，還需要讀入查詢集Q。

2.2.1 Map過程

因該階段的輸入來源是配對(duì)階段的輸出結(jié)果和文本集Q，這里根據(jù)來源分別進(jìn)行處理。如鍵/值對(duì)來源于文本集Q，則是一個(gè)查詢；先定位‘#’在內(nèi)容c中的位置，從‘#’前面提取出查詢編號(hào)sid，從‘#’后面提取出查詢內(nèi)容s，對(duì)于查詢串輸出的鍵/值對(duì)中鍵為sid，值為#s（前添加‘#’標(biāo)識(shí)該項(xiàng)為查詢內(nèi)容項(xiàng)），即。如鍵/值對(duì)是配對(duì)階段的輸出結(jié) 果，則c是，并 直 接 輸 出。

2.2.2 Reduce過程

每個(gè)Reduce過程的輸入是Shuffle過程輸出的一個(gè)鍵/值對(duì)，即其中sid鍵為查詢編號(hào)。新算法先遍歷值列表list(list(did)/(#s))內(nèi)的所有項(xiàng)，如該項(xiàng)以‘#’開頭，則該項(xiàng)是查詢的內(nèi)容，內(nèi)容保存到s中；否則，該項(xiàng)是與該查詢候選的文本編號(hào)列表list(did)，則循環(huán)list(did)中的每個(gè)did，并把各文本的q-gram命中數(shù)組H[did]增1，直到list(list(did)/(#s))處理完畢。此時(shí)發(fā)現(xiàn)如list(list(did)/(#s))中無文本did，則該查詢無匹配；否則，先拆分查詢內(nèi)容s并統(tǒng)計(jì)關(guān)鍵詞總數(shù)tn、查詢總長(zhǎng)tl，然后檢查命中數(shù)組中每個(gè)H[did]。

2.3 驗(yàn)證階段

驗(yàn)證階段的主要任務(wù)是計(jì)算每個(gè)候選對(duì)的真實(shí)匹配度，并輸出達(dá)到要求的真實(shí)匹配對(duì)。過濾階段結(jié)束后輸出了所有候選對(duì)，此時(shí)候選對(duì)已有查詢串內(nèi)容但缺少文本串的內(nèi)容。因此驗(yàn)證階段除需要讀取過濾階段的輸出結(jié)果外，還需要讀取文本集D。

2.3.1 Map過程

每個(gè)map任務(wù)的輸入是鍵/值對(duì)，這里根據(jù)鍵/值對(duì)的來源采用不同的處理方法。如鍵/值對(duì)來源于文本集D，則是一個(gè)文本串，首先從內(nèi)容c中根據(jù)‘#’的位置截取出文本編號(hào)did和文本內(nèi)容d，此時(shí)輸出的鍵/值對(duì)中選用did為鍵，而值為#d，在前加‘#’是為標(biāo)識(shí)該項(xiàng)是一個(gè)文本內(nèi)容項(xiàng)，即輸出。如鍵/值對(duì)是過濾階段的輸出結(jié)果，則c是，并直接輸出。

2.3.2 Reduce過程

每個(gè)Reduce任務(wù)處理的是一個(gè)鍵/值對(duì)，即，其中did鍵為文本編號(hào)。算法先遍歷值列表list((sid#s)/(#d))內(nèi)的所有項(xiàng)，如處理的項(xiàng)是#d，則是當(dāng)前文本did的內(nèi)容（首字符是‘#’），并保存到d中備用；否則，處理的項(xiàng)是匹配的查詢信息，即sid#s，直接添加到集合QM中。當(dāng)值列表處理完成時(shí)，獲得了文本did的內(nèi)容d和該文本匹配到的所有查詢集QM。此時(shí)，如集QM為空，則代表該文本與所有查詢不匹配，直接拋棄；否則，依次處理集QM每個(gè)查詢sid#s，并用驗(yàn)證算法計(jì)算查詢sid與文本did的真實(shí)q元匹配度simq(sid,did)。驗(yàn)證算法的輸入包括查詢s、文本d和q值。算法中將計(jì)算出查詢所有關(guān)鍵詞長(zhǎng)度之和查詢拆分得到的連續(xù)且重疊的q-gram總數(shù)查詢和文本間共享的q-gram總數(shù)Sq(s,d)=和所有關(guān)鍵詞在文本中連續(xù)qgram匹配到的最長(zhǎng)子串長(zhǎng)度總和Cq(s,d)=最后，根據(jù)公式（1）即可計(jì)算出查詢s和文本d間q元匹配度。如simq(sid,did)≥τ，則該候選對(duì)是真實(shí)匹配，輸出一個(gè)鍵/值對(duì)，即。直到處理完集QM，Reduce過程結(jié)束。

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)配置及環(huán)境

本文采用Java語言在Hadoop平臺(tái)上實(shí)現(xiàn)了新算法MQSM。為對(duì)比集群分布式算法和單機(jī)算法的性能差別，實(shí)驗(yàn)中還實(shí)現(xiàn)了一個(gè)單機(jī)多線程算法，記為MTSM。本實(shí)驗(yàn)的數(shù)據(jù)來源于Sogou實(shí)驗(yàn)室的Sogou新聞?wù)Z料庫（http://www.sogou.com/labs/），處理后的文本集和查詢集詳情見表2。本次實(shí)驗(yàn)中配置的Hadoop集群環(huán)境共包括5個(gè)節(jié)點(diǎn)，其中主節(jié)點(diǎn)1個(gè)；節(jié)點(diǎn)硬件條件為8 G內(nèi)存+處理器i5 4590。MTSM算法設(shè)置線程數(shù)為4，運(yùn)行在單一節(jié)點(diǎn)上。因中文的特殊性，一般單字不具含義，而兩字以上的詞才有意義，因此后面實(shí)驗(yàn)中都設(shè)置q=2。

表2 實(shí)驗(yàn)數(shù)據(jù)集信息

3.2 實(shí)驗(yàn)結(jié)果分析

評(píng)價(jià)一個(gè)算法的優(yōu)劣主要有兩方面指標(biāo)，一是時(shí)間消耗，二是空間消耗，顯然在相似匹配算法中匹配速度更重要。給定不同大小的文本集，算法的匹配速度則不同。為衡量文本集大小對(duì)算法匹配速度的影響，本次實(shí)驗(yàn)中使用參數(shù)配置q=2,τ=0.7，查詢集如表2所示，文本集中字符串?dāng)?shù)目分別為40000、80000、120000和160000。參與實(shí)驗(yàn)的算法包括分布式集群算法MQSM和單節(jié)點(diǎn)多線程算法MTSM。實(shí)驗(yàn)結(jié)果對(duì)比如圖1所示。

由圖1可知，MTSM算法在文本集較小時(shí)的匹配速度要快于MQSM算法。但隨著文本集的不斷增大，MQSM算法的并行優(yōu)勢(shì)不斷提高，最后匹配速度超過了MTSM算法。這主要是因?yàn)镸TSM算法是一個(gè)單機(jī)內(nèi)存多線程算法，隨著文本集的增大處理能力逐漸不足，而新算法MQSM是一個(gè)基于MapReduce框架設(shè)計(jì)并運(yùn)行在多節(jié)點(diǎn)集群上的并行算法，更適合大數(shù)據(jù)集的處理。從圖1中曲線的變化趨勢(shì)可知，MQSM算法和MTSM算法的匹配時(shí)間與測(cè)試文本集的大小總體上呈線性關(guān)系。

匹配度參數(shù)變化對(duì)算法性能的影響稱為算法的敏感度。為測(cè)得新算法MQSM對(duì)匹配度的敏感度，在文本集（160000條）上分別采用不同的匹配度參數(shù)（τ=0.7,0.8,0.9,1.0和q=2）進(jìn)行了相關(guān)實(shí)驗(yàn)，隨著匹配度參數(shù)的變化，新算法的性能表現(xiàn)如圖2所示。

由圖2可知，匹配度參數(shù)的變化對(duì)MQSM算法的影響不大。隨著匹配度的增大，算法的匹配速度稍有提高。這是因?yàn)樗惴ǖ闹饕獣r(shí)間花費(fèi)在配對(duì)階段和過濾階段，而匹配的驗(yàn)證階段因結(jié)果較少而消耗時(shí)間較少。因MQSM算法中的配對(duì)階段和過濾階段受匹配度的影響較小，所以當(dāng)匹配度增大，過濾條件變嚴(yán)，輸出候選對(duì)相對(duì)少些，只是稍微減少了一點(diǎn)驗(yàn)證時(shí)間。因此，MQSM算法對(duì)匹配度的變化敏感度較小，較適合匹配度變化范圍較大的應(yīng)用場(chǎng)景。

4 結(jié)語

本文研究的主要內(nèi)容是用于大數(shù)據(jù)內(nèi)容安全監(jiān)測(cè)的相似匹配技術(shù)。文中先給出了相似匹配相關(guān)問題的定義。為能在算法中快速過濾掉那些一定不存在真實(shí)匹配的無關(guān)對(duì)，文中總結(jié)出了基于q-gram命中數(shù)特征的候選對(duì)過濾定理。最后提出并實(shí)現(xiàn)了一種用于大數(shù)據(jù)內(nèi)容安全監(jiān)測(cè)的快速相似匹配并行算法。文中通過實(shí)驗(yàn)證明本文提出的新算法，利用字符串分割和過濾技術(shù)加快了相似匹配的速度。作者將繼續(xù)研究更加苛刻的過濾條件和非連續(xù)的q-gram拆分等技術(shù)，擬通過減少配對(duì)階段子串的輸出量來降低算法的配對(duì)時(shí)間和過濾時(shí)間。