武優(yōu)西,陳 彤,閆文杰,高雪冬

(河北工業(yè)大學(xué) 人工智能與數(shù)據(jù)科學(xué)學(xué)院,天津 300401) (河北省大數(shù)據(jù)重點(diǎn)實(shí)驗(yàn)室,天津 300401)

1 引 言

模式匹配(又稱字符串匹配)是計(jì)算機(jī)科學(xué)的基礎(chǔ)問(wèn)題之一[1],其在生物信息學(xué)[2]、網(wǎng)絡(luò)入侵[3]以及數(shù)據(jù)挖掘[4]等諸多領(lǐng)域具有重要應(yīng)用,其問(wèn)題實(shí)質(zhì)是在一個(gè)相對(duì)長(zhǎng)的序列串S上查找相對(duì)較短的模式P所有出現(xiàn)的位置及個(gè)數(shù),這里序列串S以及模式P必須采用相同的字母表中[5].

近年來(lái),為了滿足實(shí)際需要,在傳統(tǒng)通配符的基礎(chǔ)上,研究者們致力于間隙約束的模式匹配,其模式串P可以表示為:P=p1[a1,b1]p2…[aj,bj]pj+1…[am-1,bm-1]pm(1≤j≤m),其中aj和bj分別為pj和pj+1之間通配符之間最小和最大通配符的個(gè)數(shù).這種間隙約束的模式在序列模式挖掘中亦有深入探索,如Min等人[6]在間隙約束下探索了序列中字符作用不均等的模式挖掘方法;Wu等人[7]采用網(wǎng)樹(shù)結(jié)構(gòu)對(duì)周期性一般間隙的序列模式挖掘問(wèn)題進(jìn)行研究;Ding等人[8]在無(wú)重疊條件下探索了間隙約束的序列模式挖掘問(wèn)題;文獻(xiàn)[9]中提出免預(yù)設(shè)間隔約束的對(duì)比序列模式高效挖掘算法,解決了序列數(shù)據(jù)挖掘問(wèn)題;Dong等人[10]在挖掘重復(fù)模式問(wèn)題上,提出了e-RNSP算法;Tan等人[11]根據(jù)位置的頻繁模式檢測(cè),提出具有弱通配符間隙算法.在上述研究中,均需采用間隙約束模式匹配技術(shù)實(shí)現(xiàn)模式支持度的計(jì)算,從而判定模式的頻繁性,因此這種間隙約束模式匹配是序列模式挖掘的核心與基礎(chǔ)[12].

當(dāng)前研究主要在非負(fù)間隙下進(jìn)行研究,即aj≥0,但一般間隙約束能得到更多有價(jià)值的信息.因此,Fredriksson和Grabowski[13]對(duì)一般間隙約束下模式匹配問(wèn)題進(jìn)行研究,柴等[14]也提出一般間隙及一次性條件的模式匹配問(wèn)題,并提出了具有完備性的有效算法DNCP;文獻(xiàn)[15]中提到一種基于靈活間隙模式匹配的服務(wù)器,并提出RNAPattMatch算法.與其他多種間隙約束模式匹配相比,無(wú)重疊模式匹配具有獨(dú)特的計(jì)算性能[16],在序列模式挖掘中更容易發(fā)現(xiàn)有價(jià)值的頻繁模式[17].

然而精確匹配有時(shí)不能完全提供給我們更多有價(jià)值的信息.在實(shí)際應(yīng)用中大多數(shù)情況屬于近似模式匹配[18].近似模式匹配問(wèn)題是指在模式串中其中一個(gè)字符與序列串中某個(gè)字符進(jìn)行匹配時(shí),兩個(gè)字符位置相同,但字符可以不完全相同.按照距離計(jì)算公式,可將近似條件約束模式匹配分為Hamming距離[19]、δ距離[20,21]及編輯距離[22]等.Hu等人[23]運(yùn)用字符串相似搜索的通用Gram過(guò)濾器,提出了GFilter算法.

有鑒于此,本文提出了一般間隙近似無(wú)重疊模式匹配問(wèn)題(Nonoverlapping Approximation Pattern Matching with General Gaps,簡(jiǎn)稱NOAPMGG).該問(wèn)題具有以下4個(gè)特點(diǎn):它是一種嚴(yán)格的近似模式匹配問(wèn)題,在匹配出現(xiàn)的過(guò)程中,不要求模式串上的字符與模式串上的字符完全相同;滿足了無(wú)重疊條件約束,允許同一字符在多個(gè)位置使用多次,但不允許在同一位置上同一字符使用多次;在模式串的設(shè)定中,允許間隙設(shè)置上出現(xiàn)多個(gè)負(fù)間隙.

2 NOAPMGG問(wèn)題

定義1(序列串).序列串記為S,S=s1…si…sn(1≤i≤n),由字符組成的長(zhǎng)度為n的信息源,其中,si∈∑,∑表示為一種符號(hào)的集合.在不同應(yīng)用當(dāng)中,∑的意義也會(huì)隨之不同.例如,在DNA基因序列中,∑由{A,C,G,T}組合而成.例如,S=s1s2s3s4s5=agcag,序列串S的長(zhǎng)度為5.

定義2(模式串).模式串記為P,P=p1[a1,b1]p2…pj[aj,bj]pj+1…[am-1,bm-1]pm(1≤j≤m),其中,m指模式串P的長(zhǎng)度,pj∈∑;aj、bj分別指間隙約束的下界與上界且取值必須是整數(shù),并滿足aj≤bj.若aj≥0且bj≥0,則稱此區(qū)間為非負(fù)間隙條件約束;若aj或bj至少有一個(gè)小于0,則稱此區(qū)間為一般間隙條件約束.

定義3(出現(xiàn)).出現(xiàn)記為L(zhǎng),如果一個(gè)位置索引L=,其中,0≤lj≤n,0≤j≤m,lj≠lj-1,且滿足si=pj且:

(1)

則稱L為模式串P在序列串S上的一個(gè)出現(xiàn).例如,模式串P=p1[a1,b1]p2[a2,b2]p3= A[0,3]T[0,2]C,則說(shuō)明模式串P的長(zhǎng)度為3;在字符A和字符T間根據(jù)間隙約束可知,兩個(gè)字符間可通配0到3個(gè)字符;而字符T和字符C間根據(jù)間隙約束可知,兩個(gè)字符間可通配0到2個(gè)字符.

定義5(Hamming距離).Hamming距離記為T(mén),即表示兩個(gè)(相同長(zhǎng)度)字對(duì)應(yīng)位不同的數(shù)量.例如:序列串S1=s1s2s3s4s5=abcab與序列串S2=s1s2s3s4s5=acbac,在兩個(gè)序列串中,第2、3、5位置字符不同,因此,Hamming距離為3.

3 網(wǎng)樹(shù)與NOPARLA算法

3.1 網(wǎng)樹(shù)的概念

網(wǎng)樹(shù)的數(shù)據(jù)結(jié)構(gòu)是一種樹(shù)型結(jié)構(gòu)的拓展,目前被應(yīng)用于解決多種模式匹配問(wèn)題[24]、序列模式挖掘問(wèn)題[25]和圖問(wèn)題[26],其定義如下:

定義6(網(wǎng)樹(shù)).網(wǎng)樹(shù)是一種非線性數(shù)據(jù)結(jié)構(gòu),是由根結(jié)點(diǎn)與子網(wǎng)樹(shù)組成,所有相連的路徑之間用來(lái)表示雙親與孩子關(guān)系.

性質(zhì)1.網(wǎng)樹(shù)具有樹(shù)結(jié)構(gòu)的一些特點(diǎn),如雙親、孩子、葉子結(jié)點(diǎn)、根結(jié)點(diǎn)、層等.此外,其具有如下獨(dú)特特點(diǎn):

1)一棵網(wǎng)樹(shù)中可以存在一個(gè)或多個(gè)根結(jié)點(diǎn);

2)網(wǎng)樹(shù)中非樹(shù)根結(jié)點(diǎn)也會(huì)存在多個(gè)雙親結(jié)點(diǎn);

3)任何一個(gè)結(jié)點(diǎn)到它的祖先結(jié)點(diǎn)路徑可能不止一條;

4)給定序列中的結(jié)點(diǎn)可以在網(wǎng)樹(shù)的不同層上出現(xiàn);

5)一個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)一定在網(wǎng)樹(shù)的同一層上出現(xiàn).

定義7(樹(shù)根葉子路徑).在網(wǎng)樹(shù)中,能從樹(shù)根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的一條完整的路徑.

定義9(最右雙親策略).從最后一層的最大結(jié)點(diǎn)開(kāi)始查找,選擇最右雙親結(jié)點(diǎn)向樹(shù)根方向?qū)ふ覙?shù)根的過(guò)程.首先判斷最右雙親結(jié)點(diǎn)是否滿足間隙約束條件,若滿足則進(jìn)行匹配,若不滿足則判斷次右雙親結(jié)點(diǎn),直至找到相匹配的雙親結(jié)點(diǎn).

定義10(最左孩子策略).從第一層的最小樹(shù)根結(jié)點(diǎn)出發(fā),選擇最左孩子結(jié)點(diǎn)向葉子結(jié)點(diǎn)方向?qū)ふ衣窂降倪^(guò)程.首先判斷最左孩子結(jié)點(diǎn)是否滿足間隙約束,若滿足則進(jìn)行匹配,若不滿足則判斷次左孩子結(jié)點(diǎn),直至找到與之相匹配的葉子結(jié)點(diǎn).

3.2 NOPARLA算法的設(shè)計(jì)及分析

3.2.1 創(chuàng)建一般間隙近似網(wǎng)樹(shù)

在文獻(xiàn)[16]中,提出利用網(wǎng)樹(shù)的結(jié)構(gòu)特點(diǎn)可以有效地解決無(wú)重疊條件約束下的模式匹配問(wèn)題.由于本文研究的是近似距離下的模式匹配問(wèn)題,因此需要在文獻(xiàn)[16]的創(chuàng)建網(wǎng)樹(shù)問(wèn)題上進(jìn)行一些修改.在修改算法的過(guò)程中會(huì)存在兩個(gè)難點(diǎn):在處理結(jié)點(diǎn)關(guān)系時(shí),會(huì)出現(xiàn)Hamming距離的實(shí)時(shí)更新;在創(chuàng)建父子關(guān)系前,需要進(jìn)行預(yù)判斷處理.

在創(chuàng)建一般間隙近似網(wǎng)樹(shù)前,我們需提到一些與近似距離相關(guān)的定義如下.

1)計(jì)算該葉子結(jié)點(diǎn)到根結(jié)點(diǎn)之間的Hamming距離d時(shí)樹(shù)根到葉子的路徑數(shù);

(2)

1)計(jì)算該根結(jié)點(diǎn)到葉子結(jié)點(diǎn)之間的Hamming距離d的路徑數(shù).

(3)

算法1.CreateNetTree

輸入:長(zhǎng)度為m的模式串P,長(zhǎng)度為n的序列串S,Hamming距離閾值T

輸出:網(wǎng)樹(shù)NetTree

1.forj=1 tomstep 1do

2.fori=1 tonstep 1do

3. 依據(jù)定義11創(chuàng)建并計(jì)算結(jié)點(diǎn)的NHDRL值;

4.endfor

5.endfor

6.returnNetTree;

例1.給定序列串S=tgttagt,模式串P= t[-1,1]t[-1,2]a[-1,1]t,Hamming距離為1,根據(jù)CreateNetTree算法可以建立一棵近似網(wǎng)樹(shù),如圖1所示.

該網(wǎng)樹(shù)的創(chuàng)建步驟如下:

1)當(dāng)j=1時(shí),將序列串中所有字符一次掃描插入第一層nettree[1],根據(jù)定義13,對(duì)所有結(jié)點(diǎn)進(jìn)行初始值定義;

圖1 模式串P在序列串S對(duì)應(yīng)的網(wǎng)樹(shù)Fig.1 Nettree for pattern P in sequence S

3.2.2 最左孩子策略

為解決近似距離閾值問(wèn)題,在創(chuàng)建一般間隙近似網(wǎng)樹(shù)為每個(gè)結(jié)點(diǎn)都進(jìn)行了在不同Hamming距離下路徑數(shù)量的定義與計(jì)算.若滿足近似度閾值條件,則根據(jù)樹(shù)根葉子路徑數(shù)匹配該結(jié)點(diǎn)的孩子結(jié)點(diǎn).該方法可以有效提高匹配效率,具體過(guò)程如下:從最小根結(jié)點(diǎn)出發(fā),根據(jù)間隙約束條件與Hamming距離的設(shè)定,當(dāng)上一層結(jié)點(diǎn)與下一層結(jié)點(diǎn)建立關(guān)系時(shí),根據(jù)公式(2)選擇與之匹配的最小孩子結(jié)點(diǎn).其算法如算法2.

算法2.RootToLeaf

輸入:NetTree,模式串P長(zhǎng)度為m,序列串S長(zhǎng)度為n,閾值T,當(dāng)前結(jié)點(diǎn)F

輸出:occin,各層結(jié)點(diǎn)F[m]集合

1.occin.position[1]=t;

2.F[1]=nettree[1][t];

3.ifF[1].used=true orF[1].toleave=falsethen

4.ifp[1].start≠s[F[1]]thenapprox=1;

5.forj=1 tomstep 1do

6.fort=1 tonettree[j][i].children.size()step 1do

7.maxh=T-approx;

8.endfor

9.ifnettree[j][child].toleave=false thenapprox=

approx+1;

10.endfor

11.endif

12.returnoccinandF[m];

3.2.3 近似閾值監(jiān)測(cè)機(jī)制

根據(jù)文獻(xiàn)[17]可知,基于從最小根結(jié)點(diǎn)向下采用最左孩子結(jié)點(diǎn)找到較多的樹(shù)根葉子路徑,若模式串P的間隙約束略大或間隙條件過(guò)多時(shí),結(jié)點(diǎn)的孩子結(jié)點(diǎn)也會(huì)成倍增加,由于近似度閾值的約束會(huì)造成該結(jié)點(diǎn)選擇的孩子結(jié)點(diǎn)并不是最小孩子結(jié)點(diǎn),因此僅依靠最左孩子策略并不能找到更多的出現(xiàn),由此可見(jiàn)需要引入近似閾值檢測(cè)機(jī)制.具體過(guò)程如下:從網(wǎng)樹(shù)的第二層開(kāi)始,若第一次檢測(cè)到si=pj,且該結(jié)點(diǎn)在Hamming距離0～T-1時(shí)有路徑,則重新向上根據(jù)最左雙親策略尋找與之匹配的結(jié)點(diǎn).其算法如算法3.

算法3.RootToLeaf_Approx

輸入:NetTree,模式串P(長(zhǎng)度:m),序列串S(長(zhǎng)度:n),閾值T,當(dāng)前結(jié)點(diǎn)Q

輸出:occin,各層結(jié)點(diǎn)Q[t]集合

1.forj=1 tomstep 1do

2.if(j≤m)then

3. 采用算法2,從結(jié)點(diǎn)Q[t]出發(fā),采用最左孩子策略,獲得子路徑Q及對(duì)應(yīng)的Hamming距離為approx的子模式;

4.forx=jdownto 2 step-1do

5.fory=1 toNetTree[x][y].parents.size()step 1do

6.maxh=T-approx;

7.endfor

8.ifNetTree[x][child].toleave=falsethenapprox=approx+1;

9.endfor

10.endif

11.endfor

12.returnoccinandQ[t];

3.2.4 剪枝策略

定理1.若同一網(wǎng)樹(shù)中有互不相交的兩條路徑分別為A、B,則A、B經(jīng)過(guò)的路徑上所有結(jié)點(diǎn)可構(gòu)成兩個(gè)無(wú)重疊出現(xiàn).

由定理1可知,同一棵網(wǎng)樹(shù)中有兩條互不相交的兩條路徑,可構(gòu)成兩個(gè)無(wú)重疊出現(xiàn).因此,根據(jù)最左孩子策略,在網(wǎng)樹(shù)上剪掉一條樹(shù)根葉子路徑后,并不會(huì)影響尋找其他的無(wú)重疊出現(xiàn).但在進(jìn)行剪枝后會(huì)出現(xiàn)一些不能到達(dá)葉子結(jié)點(diǎn)的結(jié)點(diǎn),只需從葉子到樹(shù)根逐層檢測(cè),將不可抵達(dá)葉子結(jié)點(diǎn)的結(jié)點(diǎn)進(jìn)行剪枝,這樣可避免回溯過(guò)程.其算法如算法4.

算法4.Pruning

輸入:NetTree,模式串P的長(zhǎng)度m,occin

輸出:NetTree

1.fori=mdownto 1 step-1do

2.position=occin.position[i];

3.ifi

4.pos=occin.position[i+1];

5.position_b=NetTree[m+1][pos].parent[0];

6.ifposition_b

7.endif

8.forposition=1 toNetTree[i].size()step 1do

9.current=NetTree[i][position];

10.ifcurrent.used=false ¤t.child=false

thenbreak;

11. updatecurrent.used;

12.ifcurrent.used=truethenupdate NHDRL;

13.endif

14.endfor

15.endfor

16.returnNetTree;

3.2.5 求解算法NOPARLA算法

根據(jù)本文提出的問(wèn)題,NOPARLA算法將作為求解算法.該算法原理:

1)根據(jù)算法1將問(wèn)題轉(zhuǎn)化成一棵網(wǎng)樹(shù)并根據(jù)性質(zhì)11和公式(2)對(duì)結(jié)點(diǎn)進(jìn)行NHDRL值定義;

2)從下往上根據(jù)性質(zhì)12和公式(3)對(duì)結(jié)點(diǎn)進(jìn)行NHDLR值定義;

3)采用算法3進(jìn)行最左孩子策略和近似監(jiān)測(cè)機(jī)制;

4)當(dāng)找到一個(gè)無(wú)重疊出現(xiàn)時(shí),采用算法4將網(wǎng)樹(shù)進(jìn)行剪枝;

5)重復(fù)第3、4步,直至找到所有無(wú)重疊出現(xiàn).

其算法如算法5:

算法5.NOPARLA

輸入:長(zhǎng)度為m的模式串P,長(zhǎng)度為n的序列串S,閾值T

輸出:符合條件的無(wú)重疊出現(xiàn)集合C

1. 采用算法1創(chuàng)建一棵近似網(wǎng)樹(shù)NetTree;

2.forj=m-1 downto 1 step-1do

3.fori=1 tonstep 1do

4. update NHDLR;

5.endfor

6.endfor

7.fort=1 toNetTree[1].size()step 1do

8. 采用算法3 RootToLeaf_Approx(N,Q[t]),從結(jié)點(diǎn)Q出發(fā),采用最左孩子策略;

9. 采用算法4 Pruning更新NetTree;

10.C=Q∪occin;

11.endfor

12.returnC;

例2.給定序列串S=tgttagt和模式串P= t[-1,1]t[-1,1]a[-1,2]t,Hamming距離為1.

計(jì)算過(guò)程如下:

1)模式串P在序列串S中所建立的對(duì)應(yīng)網(wǎng)樹(shù),如圖1所示.

2)根據(jù)公式(3)對(duì)網(wǎng)樹(shù)重新定義NHDLR值.

根據(jù)NOPARLA算法,可以找到三個(gè)無(wú)重疊出現(xiàn),即<1,3,2,1>、<3,4,3,4>、<4,6,5,7>.

3.3 算法分析

由于網(wǎng)樹(shù)最多只有m層,每一層結(jié)點(diǎn)數(shù)最多只有n個(gè)結(jié)點(diǎn),由此可見(jiàn),每一個(gè)孩子結(jié)點(diǎn)最多會(huì)有W個(gè)雙親結(jié)點(diǎn),即W=max(bj-aj+1),且aj為間隙約束的下界,bj為間隙約束的上界,近似閾值為T(mén).因此,NOPARLA算法的空間復(fù)雜度為O(m*n*W*T).其中,m為模式串的長(zhǎng)度,n為序列串的長(zhǎng)度,W為模式串的最大間隙長(zhǎng)度W=max(bj-aj+1),T為近似閾值.

在分析本文算法時(shí)間復(fù)雜度之前,先分析CreateNetTree算法、RootToLeaf算法、RootToLeaf_Approx算法以及Pruning算法的時(shí)間復(fù)雜度.易知CreateNetTree算法創(chuàng)建一棵一般間隙近似網(wǎng)樹(shù)的時(shí)間復(fù)雜度為O(m*n*W*T);在RootToLeaf算法中,每個(gè)結(jié)點(diǎn)最多有W個(gè)孩子結(jié)點(diǎn),網(wǎng)樹(shù)共有m層,近似閾值為T(mén),所以RootToLeaf算法的時(shí)間復(fù)雜度為O(m*W*T);RootToLeaf_Approx算法的時(shí)間復(fù)雜度為O(m2*W*T);根據(jù)Pruning算法可知,該算法的時(shí)間復(fù)雜度為O(m3*W*T).由于NOPARLA算法最多運(yùn)行n-m次剪枝算法,由此本文算法的時(shí)間復(fù)雜度為O(m3*n*W*T).

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

4.1 實(shí)驗(yàn)環(huán)境及實(shí)驗(yàn)數(shù)據(jù)

本文中實(shí)驗(yàn)運(yùn)行的軟、硬件環(huán)境為:Inter(R)Core(TM)i5-3210處理器、2.50GHz主頻、4.00GB內(nèi)存、Windows8.1 專業(yè)版操作系統(tǒng)的計(jì)算機(jī).完成實(shí)驗(yàn)工具為Microsoft Visual C++6.0.本文所使用的測(cè)試序列串均為真實(shí)的生物數(shù)據(jù),DNA序列均來(lái)自美國(guó)國(guó)家生物計(jì)算信息中心網(wǎng)站1.為體現(xiàn)模式串的間隙約束具有一般性規(guī)律,在本文中設(shè)計(jì)了九個(gè)具有一般性的模式串. 表1和表2分別給出了實(shí)驗(yàn)中使用的序列串和模式串的特征.

表1 真實(shí)生物序列
Table 1 Sequences of real biological data

序號(hào)片段名稱位點(diǎn)片段長(zhǎng)度S1Segment 1CY0585632286S2Segment 2CY0585622299S3Segment 3CY0585612169S4Segment 4CY0585561720S5Segment 5CY0585591516S6Segment 6CY0585581418S7Segment 7CY058557982S8Segment 8CY058560844

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

為了測(cè)試本文NOPARLA算法的性能,我們又提出了三種對(duì)比算法,即NOPALR算法、NOPARL算法和NOPALRA算法.這三種對(duì)比算法均采用網(wǎng)樹(shù)結(jié)構(gòu)進(jìn)行求解,其中NOPALR算法采用最右雙親策略,當(dāng)找到一個(gè)無(wú)重疊出現(xiàn)時(shí)將網(wǎng)樹(shù)進(jìn)行剪枝;NOPARL算法采用最左孩子策略,當(dāng)找到一個(gè)無(wú)重疊出現(xiàn)時(shí)將網(wǎng)樹(shù)進(jìn)行剪枝;NOPALRA算法采用最右雙親策略,再采用近似閾值檢測(cè),當(dāng)找到一個(gè)無(wú)重疊出現(xiàn)時(shí)將網(wǎng)樹(shù)進(jìn)行剪枝.

本文選取表2中P1～P9中的9個(gè)模式串與表1中S1～S8中的8個(gè)序列串作為本文的對(duì)比實(shí)驗(yàn)數(shù)據(jù),在選取近似閾值T=1與T=2進(jìn)行對(duì)比實(shí)驗(yàn),并對(duì)這四種算法的求解質(zhì)量與求解速度進(jìn)行對(duì)比.表3和表4分別給出了近似閾值T=1與T=2情況下,模式串P1～P9在序列串S1～S8上的出現(xiàn)總數(shù).

表2 模式串
Table 2 Patterns

表3T=1時(shí),序列S1～S8在模式P1～P9上的出現(xiàn)總數(shù)
Table 3 Total results ofS1～S8 inP1～P9 whenT=1

出現(xiàn)數(shù)P1P2P3P4P5P6P7P8P9NOPALR341045303193255514581725123027493199NOPARL353244143452268818821905161629303218NOPARLA351843573382273016791882140030943450NOPARLA360345563445265819722016169331473508

表4T=2時(shí),序列S1～S8在模式P1～P9上的出現(xiàn)總數(shù)
Table 4 Total results ofS1～S8 inP1～P9 whenT=2

出現(xiàn)數(shù)P1P2P3P4P5P6P7P8P9NOPALR6468100866216499126192500211843604469NOPARL6575101236389533826012524227143604445NOPARLA6438101126220520427662713226846684828NOPARLA6664101976442508727882753240548044971

為了能更清晰的反映出四種算法分別在近似閾值T=1與T=2情況下,模式串P1～P9在序列串S1～S8上的時(shí)間性能,四種算法的平均運(yùn)行時(shí)間見(jiàn)表5和表6.

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

1)在求解性能方面,NOPARLA算法整體比NOPARL算法、NOPALR算法與NOPALRA算法較好.

通過(guò)表3～表4,即T=1和T=2時(shí),序列串S1～S8在模式P1～P9上的出現(xiàn)總數(shù).從兩張表中,清晰看出NOPARLA算法從總體來(lái)說(shuō),求解性能優(yōu)于其他三種算法.在模式串P3上,NOPARL算法求解性能優(yōu)于NOPARLA算法;在模式串P4上,NOPALRA算法與NOPARLA算法均沒(méi)有NOPARL算法的求解性能好;產(chǎn)生這樣的原因一是由于序列串的長(zhǎng)短會(huì)造成這樣的原因,由于在NOPARL算法與NOPALR算法并沒(méi)有判斷近似監(jiān)測(cè)機(jī)制,因此,對(duì)網(wǎng)樹(shù)造成較小的影響;二是因?yàn)楫?dāng)序列串足夠長(zhǎng)的時(shí)候,為了能找到能多有價(jià)值的出現(xiàn),算法對(duì)近似距離做檢測(cè),當(dāng)滿足一定條件時(shí),會(huì)觸發(fā)近似監(jiān)測(cè)機(jī)制,使得產(chǎn)生的新無(wú)重疊出現(xiàn)比原有無(wú)重疊出現(xiàn)對(duì)網(wǎng)樹(shù)的影響減小,因而提高了算法的求解性能.

表5T=1時(shí),序列S1～S8在模式P1～P9上的平均運(yùn)行時(shí)間
Table 5 Average running time ofS1～S8 inP1～P9 whenT=1

平均時(shí)間P1P2P3P4P5P6P7P8P9NOPALR4392844394141164171714579301424NOPARL52235052548814332145176711331660NOPARLA50634052548613522029168410781625NOPARLA53937354351014812271183411491735

表6T=2時(shí),序列S1～S8在模式P1～P9上的平均運(yùn)行時(shí)間
Table 6 Average running time ofS1～S8 inP1～P9 whenT=2

平均時(shí)間P1P2P3P4P5P6P7P8P9NOPALR74041277955128116184369120244986NOPARL83846790877731316840409422405250NOPARLA77143880361130686908410222425521NOPARLA86449493477232747387429523855855

2)在求解性能方面,通常情況下NOPARLA算法比NOPALRA算法可以發(fā)現(xiàn)更多的出現(xiàn).

從表3～表4可以看出,在模式串P1～P9上,當(dāng)T=1時(shí),NOPARLA算法有七次獲得了最多出現(xiàn)數(shù),當(dāng)T=2時(shí),NOPARLA算法有八次獲得了最多出現(xiàn)數(shù).

3)在時(shí)間運(yùn)行方面,改進(jìn)后的NOPARLA算法與NOPALRA算法運(yùn)行時(shí)間總體比未改進(jìn)的NOPARL算法與NOPALR算法較長(zhǎng).

從表5～表6可以看出,即T=1和T=2時(shí),序列串S1～S8在模式P1～P9上的平均運(yùn)行時(shí)間下,NOPARLA算法在運(yùn)行時(shí)間上總體來(lái)說(shuō)消耗最多,NOPALR算法消耗的時(shí)間最少,并且可以看出NOPARLA算法與NOPALRA算法消耗的時(shí)間,從整體來(lái)說(shuō)均比NOPARL算法與NOPALR算法時(shí)間長(zhǎng),造成這種現(xiàn)象別的主要原因是在處理無(wú)重疊出現(xiàn)時(shí),對(duì)近似距離做檢測(cè),通過(guò)檢測(cè)可以找到更多有價(jià)值的出現(xiàn),因此會(huì)增加時(shí)間的運(yùn)行.

4)隨著近似閾值T的增加,找到的出現(xiàn)數(shù)與運(yùn)行時(shí)間也會(huì)隨之增加.

通過(guò)表3～表4,即T=1和T=2時(shí),序列串S1～S8在模式P1～P9上的出現(xiàn)總數(shù).換言之,當(dāng)T從0到2逐漸增大時(shí),出現(xiàn)數(shù)也會(huì)隨之增加,產(chǎn)生這樣現(xiàn)象的原因是由于近似閾值T可轉(zhuǎn)換為近似距離為T(mén)-approx及近似距離為approx問(wèn)題.從表5～表6可以看出,即T=1、T=2時(shí),序列串S1～S8在模式串P1～P9上的平均運(yùn)行時(shí)間也會(huì)隨之增加,這與上一章中提高的算法時(shí)間復(fù)雜度與空間復(fù)雜度分析一致.

通過(guò)本章做的大量實(shí)驗(yàn)進(jìn)行分析可知,與其他3種算法相比,NOPARLA算法從整體來(lái)說(shuō)性能最好.

5 結(jié) 論

本文提出了一般間隙近似無(wú)重疊模式匹配問(wèn)題,即NOAPMGG問(wèn)題.該問(wèn)題需要滿足無(wú)重疊模式的條件約束,為增加模式串的一般性而提出近似模式匹配,為進(jìn)一步增加模式串的靈活性而提出一般間隙模式匹配問(wèn)題,來(lái)解決NOAPMGG問(wèn)題.本文提出NOPARLA算法,該算法根據(jù)網(wǎng)樹(shù)的結(jié)構(gòu)特點(diǎn),采用最左孩子策略,使用近似閾值機(jī)制找到一個(gè)無(wú)重疊出現(xiàn).該算法的空間復(fù)雜度與時(shí)間復(fù)雜度分別為O(m*n*W*T)和O(m3*n*W*T),其中m為模式串的長(zhǎng)度,n為序列串的長(zhǎng)度,W為模式串的最大間隙長(zhǎng)度,T為近似閾值.通過(guò)大量實(shí)驗(yàn)證明了,NOPARLA算法具有較高的可行性與高效性.