国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

一種用于大數(shù)據(jù)內(nèi)容安全監(jiān)測(cè)的快速相似匹配并行算法

2022-11-25 04:38王曉霞孫德才
現(xiàn)代計(jì)算機(jī) 2022年17期
關(guān)鍵詞:節(jié)點(diǎn)階段算法

王曉霞,孫德才

(渤海大學(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ā)展起來(lái)的,是專(zhuān)注于海量信息采集、監(jiān)測(cè)和分析等技術(shù)的一個(gè)新的研究領(lǐng)域。

如何從巨大的數(shù)據(jù)集中快速找出滿(mǎn)足要求的信息,是信息安全監(jiān)測(cè)研究中需要解決的一個(gè)基本問(wèn)題。在大數(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)問(wèn)題,對(duì)應(yīng)出現(xiàn)了很多先進(jìn)的算法,MassJoin算法是一個(gè)支持多數(shù)據(jù)集的相似連接算法,能快速找出文本集間編輯距離[8]滿(mǎn)足要求的文本對(duì),算法分為四個(gè)階段:統(tǒng)計(jì)階段、過(guò)濾階段、驗(yàn)證階段1和驗(yàn)證階段2。然而該算法在匹配速度上稍顯不足。

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

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

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

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

定義1給定兩個(gè)文本s和d,稱(chēng)s為查詢(xún)串,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è)查詢(xún)集和一個(gè)大文本集,系統(tǒng)要在大文本集中快速發(fā)現(xiàn)與查詢(xún)集中匹配度達(dá)到要求的文本,這里查詢(xún)集通常是一個(gè)由關(guān)鍵詞(詞或句子)構(gòu)成的集合。設(shè)某個(gè)查詢(xún)總共有N個(gè)關(guān)鍵詞,則此時(shí)公式(1)中

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

如給定查詢(xún)集Q和文本集D如表1,在每個(gè)集合中“#”號(hào)前面的是查詢(xún)編號(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 查詢(xún)集和文本集例子

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

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

定理1給定查詢(xún)串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)度和不超過(guò)Sq(s),d+N(q-1),即Cq(s,d)≤Sq(s,d)+N(q-1),則即

2 MQSM相似匹配算法

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

2.1 配對(duì)階段

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

2.1.1 Map過(guò)程

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

生成匹配子串:如分片來(lái)源于查詢(xún)集Q,從內(nèi)容c中提取出查詢(xún)編號(hào)sid和查詢(xún)內(nèi)容s(“#”分隔)。因?yàn)椴樵?xún)s是一個(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è)匹配子串。

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

2.1.2 Reduce過(guò)程

每個(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ì)。通過(guò)該過(guò)濾條件,新算法能夠過(guò)濾掉大量不存在共享q-gram的串對(duì)。如DL和QS都不空,則為集合QS中每個(gè)sid都生成一個(gè)鍵/值對(duì)(鍵 為sid,值 為DL列 表)并 輸 出,即。處理完集合QS后,Reduce任務(wù)完成。

2.2 過(guò)濾階段

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

2.2.1 Map過(guò)程

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

2.2.2 Reduce過(guò)程

每個(gè)Reduce過(guò)程的輸入是Shuffle過(guò)程輸出的一個(gè)鍵/值對(duì),即其中sid鍵為查詢(xún)編號(hào)。新算法先遍歷值列表list(list(did)/(#s))內(nèi)的所有項(xiàng),如該項(xiàng)以‘#’開(kāi)頭,則該項(xiàng)是查詢(xún)的內(nèi)容,內(nèi)容保存到s中;否則,該項(xiàng)是與該查詢(xún)候選的文本編號(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))中無(wú)文本did,則該查詢(xún)無(wú)匹配;否則,先拆分查詢(xún)內(nèi)容s并統(tǒng)計(jì)關(guān)鍵詞總數(shù)tn、查詢(xún)總長(zhǎng)tl,然后檢查命中數(shù)組中每個(gè)H[did]。

2.3 驗(yàn)證階段

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

2.3.1 Map過(guò)程

每個(gè)map任務(wù)的輸入是鍵/值對(duì),這里根據(jù)鍵/值對(duì)的來(lái)源采用不同的處理方法。如鍵/值對(duì)來(lái)源于文本集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ì)是過(guò)濾階段的輸出結(jié)果,則c是,并直接輸出。

2.3.2 Reduce過(guò)程

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

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

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

本文采用Java語(yǔ)言在Hadoop平臺(tái)上實(shí)現(xiàn)了新算法MQSM。為對(duì)比集群分布式算法和單機(jī)算法的性能差別,實(shí)驗(yàn)中還實(shí)現(xiàn)了一個(gè)單機(jī)多線程算法,記為MTSM。本實(shí)驗(yàn)的數(shù)據(jù)來(lái)源于Sogou實(shí)驗(yàn)室的Sogou新聞?wù)Z料庫(kù)(http://www.sogou.com/labs/),處理后的文本集和查詢(xún)集詳情見(jiàn)表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,查詢(xún)集如表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ì)不斷提高,最后匹配速度超過(guò)了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ì)算法性能的影響稱(chēng)為算法的敏感度。為測(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ì)階段和過(guò)濾階段,而匹配的驗(yàn)證階段因結(jié)果較少而消耗時(shí)間較少。因MQSM算法中的配對(duì)階段和過(guò)濾階段受匹配度的影響較小,所以當(dāng)匹配度增大,過(guò)濾條件變嚴(yán),輸出候選對(duì)相對(duì)少些,只是稍微減少了一點(diǎn)驗(yàn)證時(shí)間。因此,MQSM算法對(duì)匹配度的變化敏感度較小,較適合匹配度變化范圍較大的應(yīng)用場(chǎng)景。

4 結(jié)語(yǔ)

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

猜你喜歡
節(jié)點(diǎn)階段算法
關(guān)于基礎(chǔ)教育階段實(shí)驗(yàn)教學(xué)的幾點(diǎn)看法
哪種算法簡(jiǎn)便
基于圖連通支配集的子圖匹配優(yōu)化算法
結(jié)合概率路由的機(jī)會(huì)網(wǎng)絡(luò)自私節(jié)點(diǎn)檢測(cè)算法
面向復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)相似性度量*
采用貪婪啟發(fā)式的異構(gòu)WSNs 部分覆蓋算法*
在學(xué)前教育階段,提前搶跑,只能跑得快一時(shí),卻跑不快一生。
Travellng thg World Full—time for Rree
進(jìn)位加法的兩種算法
根據(jù)問(wèn)題 確定算法
靖安县| 潼关县| 宜兰市| 霍林郭勒市| 崇义县| 潞西市| 古交市| 宾阳县| 张家川| 青州市| 嘉峪关市| 岑溪市| 泸西县| 毕节市| 海口市| 兴山县| 平顶山市| 兰坪| 瑞安市| 社会| 贡嘎县| 宁乡县| 祁门县| 抚顺县| 水富县| 江源县| 革吉县| 临海市| 白朗县| 惠安县| 渑池县| 祥云县| 平谷区| 临海市| 卫辉市| 景洪市| 临夏县| 古交市| 两当县| 仪陇县| 衡水市|