王曉霞，孫德才

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

0 引言

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

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

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

1.1 統(tǒng)計(jì)階段

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

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

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

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

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

1.2 過濾階段

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

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

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

1.3 驗(yàn)證階段1

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

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

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

map: →

map:< sn,split> →

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

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

1.4 驗(yàn)證階段2

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

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

map:< sn,split> →

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

2 實(shí)驗(yàn)

2.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)中用Java 基于Hadoop 1.2.1 平臺(tái)實(shí)現(xiàn)了算法Q-sample。本文實(shí)驗(yàn)數(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/）三個(gè)數(shù)據(jù)集。三個(gè)數(shù)據(jù)集的詳情對(duì)比如表1。

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

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

2.2 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

3 結(jié)語

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