• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      大數(shù)據(jù)處理中MapReduce框架的Q-sample算法設(shè)計

      2021-03-14 00:50:46王曉霞孫德才
      現(xiàn)代計算機(jī) 2021年36期
      關(guān)鍵詞:字符串列表過濾器

      王曉霞,孫德才

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

      0 引言

      隨著互聯(lián)網(wǎng)的飛速發(fā)展,各行各業(yè)數(shù)據(jù)量也急速增長,傳統(tǒng)的數(shù)據(jù)處理方式已不能滿足要求,大數(shù)據(jù)以其在存儲、處理、管理和分析等方面的優(yōu)勢漸漸成為解決海量數(shù)據(jù)處理的有效工具[1-2]。而基于MapReduce 框架的相似連接技術(shù)在海量大數(shù)據(jù)分析中取得了重大進(jìn)展,已成為主流的大數(shù)據(jù)分析技術(shù)[3]。近年來,大量的重復(fù)數(shù)據(jù)導(dǎo)致MapReduce 的混淆消耗過大[4],同時也導(dǎo)致網(wǎng)絡(luò)傳輸?shù)膿矶?。為提高基于編輯距離的相似連接算法速度,本文提出了一種基于MapReduce 的雙集合全局相似連接算法Q-sample,力圖通過減少MapReduce 框架的混淆消耗和網(wǎng)絡(luò)傳輸來提高連接效率。通過真實數(shù)據(jù)集的實驗,結(jié)果顯示本算法獲得了較高的連接效率。

      1 基于Q-sample和統(tǒng)計特征的相似連接算法

      Q-sample 算法的定義是:給定二個字符串集R,S和一個編輯距離閾值τ,相似連接算法的主要目的是在集合R和集合S間找出所有滿足相似要求的字符串對。為實現(xiàn)相似連接,設(shè)計了四個MapReduce 階段,即統(tǒng)計階段、過濾階段、驗證階段1和驗證階段2。

      1.1 統(tǒng)計階段

      統(tǒng)計階段是統(tǒng)計集合中各個q-gram 的頻率和對q-gram 進(jìn)行m集合分類,輸入是一個樣例集合和q-gram 過濾器參數(shù)Q和統(tǒng)計向量長度限值m。統(tǒng)計階段包含map、shuffle和reduce三個過程。

      Map 過程的任務(wù)是輸入一個key-value 對,key 是片段的編號sn,value 是片段的內(nèi)容。首先將value 拆分出字符串的內(nèi)容s,再把s從0到 |s|-Q拆分成固定長度為Q的連續(xù)且重疊Q-1 的q-gram,并輸出一個key-value對。

      在shuffle 過程中,把map 過程中產(chǎn)生的所有具有相同key 的key-value 對傳輸?shù)酵粋€reduce結(jié)點上。

      Reduce 過程中首先遍歷鏈表并統(tǒng)計列表中1的數(shù)目c。最后輸出一個key-value 對。

      當(dāng)reduce 過程結(jié)束后,則統(tǒng)計出了樣例集合中所有q-gram 的頻率。為把所有q-gram 分散到m個集合中,即G[i],0 ≤i≤m- 1。本文采用文獻(xiàn)[5]的貪婪算法實現(xiàn)q-gram 的分配,得出各個分組的頻率總和接近。最后,輸出這m個q-gram 分組到DFS中以備后用。

      1.2 過濾階段

      過濾階段的主要任務(wù)是生成子串和得出候選對集,同樣包含map、shuffle 和reduce 三個過程。在一個map 任務(wù)內(nèi)根據(jù)數(shù)據(jù)的來源不同進(jìn)行不同的處理。對于輸入的兩個集合R,S,如果輸入的key-value 對來源于集合R,將為集合生成索引子串。如果輸入的key-value 對來源于集合S,將為集合生成匹配子串。首先字符串的編號sid和內(nèi)容s先從key-value 對的value 中抽取出來。如果字符串s與字符串r相似,即ed(r,s) ≤τ,則字符串s中一定包含至少一個字符串的索引子串。如果字符串s有多個子串。則字符串r和字符串s滿足 |r|<|s|-t或 |r|> |s|+t,則這二個字符串一定不是相似對。因此,為字符串s匹配子串時,只需考慮為那些滿足 |s|-τ≤|r|≤|s|+τ的r生成匹配子串。為生成字符串s的匹配串,我們先讓q從循 環(huán)到。在每次循環(huán)中,邏輯上把字符串s用q分割成連續(xù)但不重疊的qsample,而此時只需為第i個q-sample生成匹配子串的位置psj限制在范圍[max(0,(i-1)q-t),min((i-1)q+t,s-q)]內(nèi),如圖1所示。

      圖1 一個固定q值下q-gram有效開始位置的范圍

      而當(dāng)q≤2τ+ 1時,此時所有q-gram都是有效的,所以不必為每個q-sample 計算生成q-gram。此時,map:< sn,split>→在shuffle 過程中具有相同key 的key-value 對被傳輸?shù)酵粋€reduce 結(jié)點上。在reduce 過程中,輸入是一個key-value對,即。首先遍歷列表中的每個value,根據(jù)value 中的值可以區(qū)分出來是索引子串還是匹配子串,索引子串被加入到Ilist 列表中,而匹配子串被加入到Slist 中。處理完成后,如果這二個列表中某個為空,則代表該子串無候選對。否則,對于Ilist 中的每個索引子串和Slist 中的每個匹配子串形成的對就是一個潛在的匹配對,如 ,Ilist[i]=(rid, ||r,pri),Slist[j]=(sid, ||s,psj)。 此 時, 如 果 滿足>τ(Standard-Match 過濾器),則它一定不是一個τ匹配,直接拋棄即可。否則是一個候選對,把rid加到列表list(rid)中。最后,針對每個Slist[j]生成一個key-value對,即

      1.3 驗證階段1

      在過濾階段,產(chǎn)生了包含R和S間所有潛在匹配對的候選集。但候選集中只有串的ID 號而沒有內(nèi)容,所以不能進(jìn)行驗證。采用文獻(xiàn)[6]中提出的二階段讀取方法實現(xiàn)R和S集合字符串內(nèi)容的讀取。驗證階段分為證階段1 和驗證階段2 兩個階段。

      驗證階段1 的主要任務(wù)是讀取候選集中涉及到集S的串內(nèi)容、消除冗余串對和生成集S中串的統(tǒng)計向量。驗證階段1 包含map、shuffle 和re?duce 三個過程。在setup(執(zhí)行map 任務(wù)前)中,統(tǒng)計階段的輸出的m個q-gram集G[i],0 ≤i≤m- 1被讀入并構(gòu)建。

      驗證階段1 的輸入包括集合S和過濾階段輸出的候選集。在一個map 任務(wù)中,首先區(qū)分輸入的來源。如果是候選集,則無需處理直接原樣輸出,即;如果是集S中的一個串,則先構(gòu)建一個長度為的全零向量v,然后從0開始到 |s|-Q處理每個q-gram。當(dāng)G[i]包含當(dāng)前q-gram 時,對v[i]增1;而當(dāng)某個q-gram 沒有出現(xiàn)在G中任何集中時,該q-gram 屬于樣例集中不存在的q-gram,則對G[m- 1]增1(認(rèn)為在最后一個集)。最后為當(dāng)前字符串s構(gòu)建了一個統(tǒng)計向量v,最后輸出一個key-value 對,即。這里‘#’是統(tǒng)計向量和串內(nèi)容的分隔。

      map:

      map:< sn,split> →

      在shuffle 過程中,具有相同sid的key-value對被傳送到同一個reduce 結(jié)點上。在reduce 過程中,輸入也是一個key-value對,該key-value 對包含了所有字符串s和集合R間是所有候選對。首先,構(gòu)造一個非重復(fù)集合L。然后依次處理列表list(list(rid)/(v#s))中的值,如果是v#s則存儲備用;否則是list(rid),則遍歷每個rid并加入到L中。處理完成時,用L構(gòu)建一個列表list(rid)。當(dāng)列表list(rid)非空時輸出key-value 對<(sid,v#s),list(rid) >,否則什么也不輸出。

      reduce: →<(sid,v#s),list(rid) >

      1.4 驗證階段2

      在驗證階段1結(jié)束后,候選集中屬于集合S的串內(nèi)容被保留,此時,因為缺少候選對中屬于集合R串的內(nèi)容,所以仍然無法進(jìn)行驗證。過濾階段2的主要任務(wù)是讀取候選集對屬于集合R中串的內(nèi)容、為集合R中串生成統(tǒng)計向量和驗證候選對。在輸出的m個q-gram 集G[i],0 ≤i≤m- 1 被讀入并構(gòu)建。驗證階段2 的map 過程的輸入包括集合R和驗證階段1 的輸出。在每個map 任務(wù)中,首先判斷輸入key-value 對的來源。如果來源是集R中的字符串r,則按驗證階段1 中方法為其生成統(tǒng) 計 向 量u, 并 輸 出 key-value 對。如果輸入是驗證階段1 的輸出key-value對<(sid,v#s),list(rid) >,則為列表中的每一個rid生成一個key-value對,即

      map:<(sid,v#s),list(rid) > →

      map:< sn,split> →

      在reduce 中將通過驗證每個候選對的方法找出真正相似對。在一個reduce 任務(wù)中,輸入是一個key-value 對。首先,列表list((sid,v#s)/('R',u#r))中的項被依次處理,如項是'R',u#r,則取出u和r。否則處理的項是sid,v#s,則把sid,v#s直接加入到一個列表slist中。所有項處理完成后,如slist 為空時,則該re?duce 任務(wù)無候選對;否則,循環(huán)處理slist 中的每個sid,v#s。對于每個sid,v#s,首先從中取出sid、v和s。然后計算如δ(u,v) >qτ,如果一不是一個候選對,直接拋棄,如果是一個候選對,則采用文獻(xiàn)[6]中的驗證方法進(jìn)行驗證,以確定是否是滿足要求的相似對。

      2 實驗

      2.1 實驗環(huán)境

      實驗中用Java 基于Hadoop 1.2.1 平臺實現(xiàn)了算法Q-sample。本文實驗數(shù)據(jù)來源于DBLP au?thor+title(http://dblp.uni-trier.de/xml/)、GenBank EST(ftp://ftp.ncbi.nlm.nih.gov/genbank/)和PubMed abstract(ftp://ftp.ncbi.nlm.nih.gov/pubmed/baseline/)三個數(shù)據(jù)集。三個數(shù)據(jù)集的詳情對比如表1。

      表1 數(shù)據(jù)集信息

      實驗集群中的總節(jié)點數(shù)為5個(1個主節(jié)點,4個從節(jié)點),每個節(jié)點的硬件配置為:CPU i5 4590 3.7 GHZ,內(nèi)存16 G,硬盤1 TB。集群軟件配置:操作系統(tǒng)Ubuntu 15.10 64 位,Java 1.7,Hadoop 平臺版本1.2.1。為進(jìn)行雙集合相似連接實驗,先把數(shù)據(jù)集分割成2 個字符串?dāng)?shù)目相等的集合(R和S),然后在上述集群環(huán)境中采用算法對2個集合進(jìn)行相似連接。實驗中以編輯距離作為默認(rèn)的相似連接度量標(biāo)準(zhǔn)。

      2.2 實驗結(jié)果

      實驗中使用Q-sample 算法分別在DBLP(τ= 4)、GenBank EST(τ= 8)和PubMed abstract(τ= 20)數(shù)據(jù)集上進(jìn)行相似連接運算。采用不同q-gram 過濾器及組合時算法的驗證時間統(tǒng)計如圖2到圖4。

      圖2 不同q-gram過濾器及組合DBLP

      圖3 不同q-gram過濾器及組合GenBank EST

      圖4 不同q-gram過濾器及組合PubMed

      圖2 到圖4 展示了在三個不同數(shù)據(jù)集上Qsample 算法使用不同q-gram 過濾器和向量長度的驗證時間。如圖2—圖4 所示,過濾器(Q= 1)的驗證時間要一直少于其他q-gram 過濾器(Q= 2或Q= 3)。

      從實驗結(jié)果可以看出,在所采用的三種數(shù)據(jù)集中,Q-sample 算法的時間都是最低的,使得在MapReduce處理中提高處理速度。

      3 結(jié)語

      本文主要研究大數(shù)據(jù)處理框架下基于MapRe?duce 框架的相似連接并行算法Q-sample。因為Q-sample 的子串生成方案減少了子串?dāng)?shù)量,所以算法的map 過程輸出量要降低,從而減少混淆時間和數(shù)據(jù)傳輸時間,因此過濾時間也減少了,而過濾時間的快慢大體上決定了從DFS 上讀取數(shù)據(jù)的時間消耗。 reduce 過程的輸出數(shù)據(jù)是候選集,采用了過濾驗證二階段模式。在驗證過程中,采用了多維的統(tǒng)計向量進(jìn)一步過濾掉了無效候選對,然后采用驗證算法對候選對進(jìn)行驗證,這樣則提高了過濾效率。實驗結(jié)果顯示算法可以解決大數(shù)據(jù)處理中的處理速度緩慢問題,在大數(shù)據(jù)應(yīng)用中有實際意義。

      猜你喜歡
      字符串列表過濾器
      巧用列表來推理
      學(xué)習(xí)運用列表法
      擴(kuò)列吧
      支持過濾器的REST模型研究與實現(xiàn)
      電子測試(2018年9期)2018-06-26 06:45:56
      聲音過濾器
      趣味(語文)(2018年2期)2018-05-26 09:17:55
      不含3-圈的1-平面圖的列表邊染色與列表全染色
      一種新的基于對稱性的字符串相似性處理算法
      基于LOGO!的空氣過濾器自潔控制系統(tǒng)
      自動化博覽(2014年6期)2014-02-28 22:32:20
      HVM膜過濾器管板改造總結(jié)
      中國氯堿(2014年11期)2014-02-28 01:05:07
      依據(jù)字符串匹配的中文分詞模型研究
      平阳县| 麦盖提县| 扎赉特旗| 巴彦淖尔市| 梨树县| 吉木乃县| 襄城县| 凉城县| 奉节县| 衡阳县| 郴州市| 澄江县| 承德市| 五华县| 金沙县| 盐山县| 涟源市| 汉川市| 获嘉县| 鄄城县| 池州市| 毕节市| 上杭县| 平原县| 托克托县| 木兰县| 恩平市| 绩溪县| 上犹县| 安阳县| 乌拉特后旗| 榆林市| 恭城| 屏边| 疏附县| 延川县| 秦皇岛市| 杭锦旗| 宜宾市| 安庆市| 海伦市|