具有間隙約束的模式匹配研究發展

范金泉 張楠

摘?要：模式匹配應用于求解模式在序列中的支持度，是序列模式挖掘的基礎問題，也是多種領域的重點研究方向。具有間隙約束的模式匹配相對傳統的模式匹配更具靈活性和挑戰性，在生物學、信息檢索、網絡安全等領域都有著廣泛研究。本文總結了近幾年來帶間隙約束的模式匹配的研究進展與成果，分析了其中有代表性的算法，最后對帶間隙約束的模式匹配的未來發展趨勢進行了展望與總結。

關鍵詞：模式匹配;間隙約束;支持度

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

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

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

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

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

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

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

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

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

四、總結

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

參考文獻：

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

[2]武優西，吳信東，江賀，等.一種求解MPMGOOC問題的啟發式算法[J].計算機學報，2011，34（8）：14521462.

[3]柴欣，賈曉菲，武優西，等.一般間隙及一次性條件的嚴格模式匹配[J].軟件學報，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.

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