王曉霞，孫德才

(渤海大學 信息科學與技術學院，遼寧 錦州 121013)

0 引 言

隨著各行各業(yè)數(shù)據(jù)量的飛速增長，大數(shù)據(jù)的存儲、處理、管理和分析等領域已成為當前研究的熱點。在大數(shù)據(jù)處理中，數(shù)據(jù)清洗的目的是刪除冗余信息、糾正存在的錯誤等。相似連接(similarity join)[1-4]能在給定的數(shù)據(jù)集中快速找出所有滿足相似要求的記錄對，是數(shù)據(jù)清洗中去除相似信息的常用方法。相似連接在基因序列比對、剽竊檢測和信息檢索等領域也有廣泛的應用。

相似連接分為全局連接和局部連接。全局連接要求記錄對的整體相似，而局部連接則要求記錄對滿足局部相似要求即可。相似連接又根據(jù)參與連接的數(shù)據(jù)源數(shù)分為自連接和多源連接。當數(shù)據(jù)源為單個時稱為自連接，自連接找出的相似記錄對都來源于同一個數(shù)據(jù)集。而當數(shù)據(jù)源為兩個及以上時稱為多源連接，多源連接的相似記錄對分別來源于不同的數(shù)據(jù)集。在相似連接中，衡量一個記錄對的相似程度的方法主要包括編輯距離[5-6]、海明距離、Jaccard、Cosine和Dice等。編輯距離是指把一個字符串經(jīng)過插入、修改或刪除三種編輯操作轉變成另一個字符串所要進行的最小操作次數(shù)。文中用編輯距離衡量字符串對的相似度，因為編輯距離不僅對噪聲魯棒性強，還能體現(xiàn)出兩個字符串間字符順序的差別[6]。

研究相似連接算法的主要目的是加快相似連接的速度，尤其是基于大數(shù)據(jù)集的相似連接。當前的相似連接算法主要有內(nèi)存算法和并行算法。內(nèi)存算法由于運行過程中允許共享大量信息(如索引等)，所以只能運行在單臺機器上，如PassJoin[7]、K-Join[8]和LS-Join[9]等。并行算法的設計目的是實現(xiàn)集群多任務并行計算，但并行算法也有共享信息困難的問題。MapReduce框架是Google提出的一種高效的分布式編程框架，在大數(shù)據(jù)處理中應用廣泛。近年來，基于MapReduce框架的相似連接并行算法[6,10-15]的研究也得到了眾多學者的關注，如V-SMART-Join[10]、PassJoinKMR[6]、MassJoin[11]、SAX[14]、FS-Join[15]等。

文中研究的主要內(nèi)容是基于單個字符串集的局部相似自連接并行算法。目前，LS-Join算法是首個基于兩個數(shù)據(jù)集的局部相似連接內(nèi)存算法，雖然文中也提出了改進的多線程算法，但仍無法實現(xiàn)集群多節(jié)點的并行計算。另外，在當前的相關文獻中也尚未發(fā)現(xiàn)局部相似自連接算法的相關研究。對此，文中提出一種新的基于MapReduce框架的并行連接算法，并擬解決局部相似自連接的定位問題。

1 局部相似自連接及新過濾方案

1.1 局部相似自連接的問題定義

給定一個數(shù)據(jù)集，局部相似自連接將找出集合中所有存在局部相似的記錄對。這里先給出相關問題的定義：

定義2(局部相似自連接的定位問題)：給定一個窗口長度l、一個編輯距離參數(shù)τ和一個字符串集S。局部相似自連接的定位問題是從字符串集S中找出所有存在l-τ局部相似的串對,si∈S,sj∈S,i≠j，并同時找出該串對中最長的局部相似子串位置。

表1 例子字符串集

如給定一個字符串集S，如表1所示。數(shù)據(jù)集中每行是一個字符串的信息，其中‘#’號前面的是字符串編號，而后面的是字符串內(nèi)容。如l=7,τ=1，則是一個l-τ局部相似對，它們間如最長子串對為ed(s1[4,12],s3[1,9])=1。

1.2 局部相似自連接過濾方案

局部相似自連接的輸入包括一個給定的數(shù)據(jù)集、一個窗口長度和一個編輯距離參數(shù)。LS-Join算法[9]是一種基于兩個數(shù)據(jù)集的多源局部相似連接算法。LS-Join算法先讀取第一個字符串集并建立一個倒排索引。然后把第二個字符串集中的字符串拆分子串，并在倒排索引中檢索子串并生成候選串對。最后，提出了一種基于雙向擴展的局部驗證方法來驗證候選對。該算法也能進行自連接運算，只需輸入的兩數(shù)據(jù)集相同即可。但如此連接后，結果集中存在兩種冗余記錄對，即自身冗余對和正反冗余對。自身冗余對為字符串和本身組成的串對，該串對中因兩字符串完全一樣，所以一定存在于結果集中，即,si∈S,sj∈S,i=j。正反冗余串對是兩個不同編號的字符串組成的串對，但因分先后順序而形成的冗余，如,si∈S,sj∈S,i≠j和,si∈S,sj∈S,i≠j。這些冗余串對不僅增加了連接算法計算的時間，還增加了結果集的數(shù)量。

因給定的數(shù)據(jù)集中含有大量的字符串，因此也存在著海量的字符串對。為避免枚舉所有串對，文中算法采用了過濾驗證二階段模式。為進行快速過濾和去除冗余對，該算法采用了基于分割子串的過濾方案。

定理1(無關對過濾定理)：給定兩個字符串si,sj，一個編輯距離參數(shù)τ和一個窗口長度l。把串si分割成?|si|/q」個連續(xù)但不重疊的長度為q的子串(稱為Q-sample)，其中q=?(l+1)/(τ+2)」,q≥1。此時如字符串對為l-τ局部相似對，則串sj中包含至少一個串si的Q-sample。

定理2(冗余對過濾定理)：給定一個字符串集S，一個編輯距離參數(shù)τ和一個窗口長度l。字符串集S中有兩個字符串si,sj，其中i為字符串si在集合S中的編號和j為sj的編號，則字符串對集G={,i

證明：在局部相似自連接中，有兩種冗余串對，即自身串對和正反串對。條件i

2 基于MapReduce框架的局部相似自連接算法

局部相似自連接的輸入包括：一個字符串集S，一個編輯距離參數(shù)τ和一個窗口長度l。為實現(xiàn)并行計算，文中的MLSSJ算法采用了分布式編程框架MapReduce，共設計了三個階段，即過濾階段、驗證階段1和驗證階段2。

2.1 過濾階段

為避免枚舉所有可能的字符串對，該算法設計了一個MapReduce任務實現(xiàn)無關對和冗余對的快速過濾方案。定理1是一個無關對過濾條件，使用定理1能拋棄那些不共享Q-sample的字符串對。定理2是一個冗余對過濾條件，使用定理2能拋棄影響連接性能的冗余對。為使用定理1和定理2進行快速過濾，MLSSJ算法在過濾階段先對輸入的字符串集S中所有字符串進行子串分割，然后再進行過濾。過濾階段的MapReduce任務包括三個過程，即Map、Shuffle和Reduce。

(1)Map過程：基于MapReduce框架設計的程序執(zhí)行中并行交替運行著眾多的map任務，每次map任務的輸入是一個key-value對，其中sn是分片的編號，而split是輸入字符串集S的一行內(nèi)容。例如表1中的例子集合，一次map的split就是一行內(nèi)容，即一個字符串的編號和內(nèi)容。為進行局部相似自連接的前期處理，該算法先提取字符串的編號(記為sid)和字符串內(nèi)容(記為s)，然后針對字符串s分別生成索引子串和匹配子串，具體過程如下：

(2)Shuffle過程：在MapReduce框架中，shuffle過程將map過程產(chǎn)生的所有key-value對按key值(索引子串和匹配子串)進行混淆、排序，并把具有相同key的key-value對送到同一reduce節(jié)點上。

2.2 驗證階段1

過濾階段輸出結果由大量的key-value對構成，其中每個key-value對都是一個候選對集，即一個key-value對包含了某個字符串與集S中所有編號小于該串的候選對。而驗證階段的任務是從這些候選對集中找出真正含有局部相似的串對，并定位最長相似子串的位置。但現(xiàn)在因候選對集只有串編號而沒有串內(nèi)容，所以算法無法驗證。為實現(xiàn)候選對集字符串內(nèi)容的快速讀取配對和驗證候選對，該算法把驗證階段設計成了兩個階段，即驗證階段1和驗證階段2。

驗證階段1的主要目的是讀取集S的字符串內(nèi)容，并初步進行字符串編號和串內(nèi)容的配對。它的輸入包括集S和過濾階段的輸出結果。驗證階段1的MapReduce任務也包含Map、Shuffle和Reduce三個過程。

2.3 驗證階段2

驗證階段1結束后實現(xiàn)了大編號串編號和串內(nèi)容的匹配，也給出了每個大編號串對應的候選對集，還輸出了需要保留的小編號串內(nèi)容。但此時仍無法進行候選對的驗證工作，因為還缺少小編號串的串內(nèi)容。驗證階段2的任務是實現(xiàn)小編號串編號和串內(nèi)容的配對，同時進行最終的驗證定位工作。驗證階段2的輸入是驗證階段1輸出結果。驗證階段2依然包含Map、Shuffle和Reduce三個過程。

3 實 驗

3.1 實驗環(huán)境

為驗證文中算法和相關技術的有效性，實驗中基于MapReduce框架用Java實現(xiàn)了文中的MLSSJ算法。算法運行環(huán)境為Hadoop集群，集群中主節(jié)點1個，從節(jié)點4個；硬件配置均為CPU i5 4590 四核心、16 G內(nèi)存和1 TB硬盤。實驗中還實現(xiàn)了文獻[9]中的LS-Join算法，這里記LSJ-S為單線程算法，記LSJ-M為多線程算法(線程數(shù)為4)。實驗的數(shù)據(jù)主要來源于兩個數(shù)據(jù)集，見表2。DBLP集是一個計算機類英文文獻的集成數(shù)據(jù)庫，實驗中只保留了記錄中作者和標題兩個字段。GBEST集為NCBI GenBank的表達序列標簽(Expressed Sequence Tags, ftp://ftp.ncbi.nlm.nih.gov/)，實驗中只保留了序列本身。

表2 實驗數(shù)據(jù)集信息

3.2 算法性能對比及結果分析

評價相似連接算法時，時間性能最為重要。LS-Join算法實驗中的最優(yōu)配置參數(shù)DBLP集為l=50,τ=5,q=7，GBEST集為l=100,τ=7,q=9。MLSSJ算法的配置參數(shù)除不需要q值外其他與LS-Join算法相同。首先在實驗中對比不同大小數(shù)據(jù)集對各算法性能的影響。實驗中分別采用LSJ-S、LSJ-M和MLSSJ算法在不同大小的字符串集分別進行局部相似自連接運算，并統(tǒng)計了各個算法自連接的時間消耗。隨著字符串集字符串數(shù)量的逐漸增大，各算法的總連接時間變化如圖1和圖2所示。

圖1 DBLP集大小與連接時間

由圖1和圖2可知，隨著數(shù)據(jù)集中字符串數(shù)量的不斷增大，LSJ-M算法的連接速度一直快于LSJ-S算法，由此可見多線程并發(fā)技術加快了LS-Join算法的連接速度。MLSSJ算法的連接速度要明顯快于LS-Join的LSJ-S算法和LSJ-M算法，尤其在小字母表且長字符串的數(shù)據(jù)集(如GBEST)上新算法性能表現(xiàn)更優(yōu)。這主要是因為LS-Join算法是一個內(nèi)存算法，雖然采用了多線程技術但也只能運行在一臺機器上。而MLSSJ算法是一個運行在多節(jié)點集群上的并行算法，基于MapReduce框架的設計使得它更適合大數(shù)據(jù)集的局部相似自連接。從圖中還可以看出，隨著數(shù)據(jù)集的增大，MLSSJ算法的連接時間基本呈線性增加。

圖2 GBEST集大小與連接時間

在相似連接中，編輯距離參數(shù)是一個非常重要的參數(shù)。為對比各個算法對編輯距離參數(shù)的敏感度，實驗中還分別采用不同的編輯距離參數(shù)對LSJ-M算法和MLSSJ算法在各數(shù)據(jù)集上進行了局部相似自連接操作。在DBLP集上配置參數(shù)為l=50,τ=0,1,3,5(LSJ-M中q=7)， GBEST集上為l=100,τ=0,1,3,5,7(LSJ-M中q=9)。隨著編輯距離參數(shù)的逐漸增大，各算法的性能表現(xiàn)對比如圖3和圖4所示。

圖3 DBLP集編輯距離與連接時間

圖4 GBEST集編輯距離與連接時間

由圖3和圖4可知，在不同編輯距離參數(shù)下MLSSJ算法的速度一直快于LSJ-M算法。該實驗主要分析各個算法對編輯距離參數(shù)的敏感度。由圖3和圖4可知，LSJ-M算法隨著編輯距離參數(shù)不斷增大而連接時間變化較小，因此該算法對編輯距離參數(shù)的敏感度較小。這主要是因為實驗中LSJ-M算法的索引子串長度q值對不同編輯距離參數(shù)影響較大，而這里q值固定。實際使用中需要對不同數(shù)據(jù)集進行q值實驗測優(yōu)，因此該算法也不夠靈活。而MLSSJ算法隨著編輯距離參數(shù)的不斷增大，其連接時間也不斷增加，因此該算法對編輯距離參數(shù)的敏感度較大。這主要是因為MLSSJ算法中切分子串長度是根據(jù)編輯距離參數(shù)動態(tài)計算的，即τ值越小，q值越大，分割得到的子串數(shù)目越少，處理所需的時間就越短。因此，MLSSJ算法在編輯距離參數(shù)動態(tài)變化的局部相似自連接中比LSJ-M算法更具優(yōu)勢。

4 結束語

文中主要研究了基于單個字符串集的局部相似自連接算法。先給出了局部相似自連接定位問題的定義，然后通過分析相似自連接中的無關串對和冗余串對問題，總結出了無關串對過濾定理和冗余串對過濾定理。最后提出了一種基于MapReduce框架的局部相似自連接并行算法。實驗結果表明，該算法有效地提高了局部相似自連接的速度。該算法雖然通過MapReduce框架的并行技術加快了局部相似自連接的速度，但仍存在并行節(jié)點間數(shù)據(jù)傳輸量大和過濾階段生成的候選對多等問題。下一步將研究更加苛刻的過濾條件，擬通過降低過濾階段生成的候選對數(shù)量來減少驗證時間。