具有間隙約束的模式匹配研究發(fā)展

范金泉 張楠

摘?要：模式匹配應(yīng)用于求解模式在序列中的支持度，是序列模式挖掘的基礎(chǔ)問題，也是多種領(lǐng)域的重點(diǎn)研究方向。具有間隙約束的模式匹配相對(duì)傳統(tǒng)的模式匹配更具靈活性和挑戰(zhàn)性，在生物學(xué)、信息檢索、網(wǎng)絡(luò)安全等領(lǐng)域都有著廣泛研究。本文總結(jié)了近幾年來帶間隙約束的模式匹配的研究進(jìn)展與成果，分析了其中有代表性的算法，最后對(duì)帶間隙約束的模式匹配的未來發(fā)展趨勢(shì)進(jìn)行了展望與總結(jié)。

關(guān)鍵詞：模式匹配;間隙約束;支持度

模式匹配在數(shù)據(jù)搜索、音樂信息檢索和生物信息學(xué)等領(lǐng)域有著非常重要的作用。但隨著數(shù)據(jù)的不斷變化，傳統(tǒng)的通配符數(shù)量不變的模式匹配無法滿足用戶的需求，提出了具有間隙的模式匹配（通配符的數(shù)量有上下界）。具有間隙的模式匹配不僅更加靈活多樣，富有挑戰(zhàn)性[1]。根據(jù)出現(xiàn)的不同，常見的約束條件有三種：無特殊條件、一次性條件和無重疊條件。本文將從這三個(gè)方面，對(duì)帶有約束條件的間隙約束模式匹配進(jìn)行分析討論。

一、無特殊條件下的間隙模式匹配

例1 假設(shè)序列S=s1s2s3s4s5s6=ATATTA，模式P=A[0，1]T[0，1]A。

無特殊條件下序列中的任意字符可以被多次使用，因此可以找到三個(gè)出現(xiàn)<1，2，3>，<3，4，6>，<3，5，6>。無特殊條件對(duì)出現(xiàn)沒有限制，因此會(huì)得到大量的解，提高求解的速度將是無特殊條件最為關(guān)心的一點(diǎn)。PAIG算法采用三維數(shù)據(jù)表求解無特殊的間隙模式匹配，速度方面有很大提升，但隨著序列的增長(zhǎng)空間消耗會(huì)非常大。為了提高算法的空間利用率，提出了網(wǎng)樹結(jié)構(gòu)，該結(jié)構(gòu)與樹型結(jié)構(gòu)類似，不同點(diǎn)在于網(wǎng)樹中存在多個(gè)根結(jié)點(diǎn)并且相同結(jié)點(diǎn)可能會(huì)出現(xiàn)在不同層，基于此結(jié)構(gòu)提出的NAMIC算法在運(yùn)行空間消耗有著很大的提升。

二、一次性條件下的間隙模式匹配

一次性條件下要求序列中的字符只能被使用一次，在例1中，<1，2，3>是一個(gè)出現(xiàn)，則<3，4，6>就不是一個(gè)出現(xiàn)，因?yàn)閟3使用了兩次。一次性條件對(duì)結(jié)果集進(jìn)行了很大程度的縮減，但會(huì)出現(xiàn)丟解的現(xiàn)象，原因在于一次性約束的模式匹配算法是基于回溯搜索，在回溯點(diǎn)上的選擇至關(guān)重要，SAIL算法是代表性的一次性模式匹配算法，可以在線求解一次性問題，但在局部最優(yōu)方面處理較差。針對(duì)求解的質(zhì)量問題，武等人[2]利用網(wǎng)樹設(shè)計(jì)了SBO算法，采用局部全局最優(yōu)解，增加了一次性條件的解集。在此基礎(chǔ)上，柴等人[3]提出了IM_DCNP算法，通過深度優(yōu)先遍歷網(wǎng)樹，解決了一次性約束下的一般間隙的近似模式匹配，具有良好的優(yōu)越性。

三、無重疊條件下的間隙模式匹配

無重疊條件是指允許序列中的任意位置的字符重復(fù)使用，但不允許同一字符在相同位置多次使用[4]，所以例1中對(duì)應(yīng)的無重疊出現(xiàn)有<1，2，3>和<3，4，6>，雖然s3被使用了兩次但是是在不同的子序列中。文獻(xiàn)[4]通過網(wǎng)樹結(jié)構(gòu)解決了無重疊模式匹配中無法求得完備解的問題。在此基礎(chǔ)上，將網(wǎng)樹應(yīng)用到無重疊條件下序列模式挖掘中也取得優(yōu)異的效果[5]。

從上述研究可以看出，無特殊結(jié)果是一個(gè)全集，則無重疊條件和一次性結(jié)果屬于全集中的不同子集，網(wǎng)樹結(jié)構(gòu)用于求解這三種條件下的間隙模式匹配是非常有優(yōu)勢(shì)的。無重疊條件下的模式匹配問題屬于P問題，通過遍歷網(wǎng)樹便可以求得完備解，然而一次性條件的模式匹配屬于NPhard問題，采用迭代方式可以進(jìn)行簡(jiǎn)化，因此，使用啟發(fā)式策略求解一次性問題是關(guān)鍵。無特殊問題相對(duì)比較容易處理，是其他兩種約束條件的關(guān)鍵問題。

四、總結(jié)

將間隙約束引入到模式匹配中使得模式匹配問題更加靈活多變，更富有挑戰(zhàn)性。同時(shí)，不同的約束條件與模式匹配結(jié)合，能更好地滿足用戶需求。本文對(duì)帶間隙約束的無特殊、一次性、無重疊條件下的模式匹配進(jìn)行了分析介紹，對(duì)每種約束條件進(jìn)行了總結(jié)并分析討論幾種求解算法。目前，帶間隙約束的模式匹配發(fā)展迅速，但是在解的質(zhì)量和實(shí)際應(yīng)用方面仍存在不足之處，是未來進(jìn)一步的發(fā)展趨勢(shì)。

參考文獻(xiàn)：

[1]Shi Q，Shan J，Yan W，et al.NetNPG：Nonoverlapping pattern matching with general gap constraints[J].Applied Intelligence，2020.

[2]武優(yōu)西，吳信東，江賀，等.一種求解MPMGOOC問題的啟發(fā)式算法[J].計(jì)算機(jī)學(xué)報(bào)，2011，34（8）：14521462.

[3]柴欣，賈曉菲，武優(yōu)西，等.一般間隙及一次性條件的嚴(yán)格模式匹配[J].軟件學(xué)報(bào)，2015，26（5）：10961112.

[4]Wu Y，Shen C，Jiang H，Wu X.Strict pattern matching under nonoverlapping condition[J].Science China Information Sciences.2017，60（1）：012101.

[5]Wu Y，Tong Y，Zhu X，Wu X.NOSEP：Nonoverlapping sequence pattern mining with gap constraints[J].IEEE Transactions on Cybernetics.2018，48（10）：28092822.

作者簡(jiǎn)介：范金泉（1993—），男，漢族，山東臨沂人，碩士，學(xué)生，研究方向：序列模式與挖掘;張楠（1991—），女，漢族，山東濟(jì)寧人，碩士，學(xué)生，研究方向：鐵路信息技術(shù)。