一次性序列模式匹配研究進展

摘?要：帶通配符的模式匹配問題具有更廣闊的應用前景。間隙約束是將通配符的數量設置為一個可變范圍，具有更高的靈活性。一次性模式匹配作為帶間隙約束模式匹配的一種，能夠對匹配結果進行有效的縮減，有著重要的實際應用意義。本文主要綜述了目前一次性序列模式匹配相關研究，并對將來的研究工作進行了展望。

關鍵詞：一次性;間隙約束;模式匹配

模式匹配是計算機科學中的一個重要研究方向。帶通配符的模式匹配不僅具有理論研究意義，而且在生物基因檢測、序列模式挖掘、文本信息搜索等領域具有重要的應用。然而，傳統通配符的數目通常是單個或固定值，在間隔不確定字符數時無法適用。而更靈活的間隙約束采用了指定范圍來描述模式中的通配符數量，可以表示為P=p1[a1，b1]p2…pj[aj，bj]pj+1…pm1[am1，bm1]pm，其中，[aj，bj]就是間隙約束，aj和bj分別指pj和pj+1之間通配符個數的最小值和最大值[1]。

一次性模式匹配作為帶間隙約束模式匹配中的一種，不僅能夠對結果集進行有效縮減，而且在序列模式挖掘中具有重要應用[2]。由于間隙約束的存在，每當子模式出現不同的位置，都會產生一個新的出現，從而導致解的空間大小達到指數級。設序列長度為n，模式長度為m，最大間隙為w，則解的空間大小為O（nwm），當模式長度m較大時，所有出現的數量將無法估計。為了解決該問題，武等人[3]研究了一次性條件的模式匹配，一次性條件規定序列中的字符最多只能被匹配一次，解的空間大小降低到O（n/m）。在此基礎上，一系列的一次性匹配算法被相繼提出，如SBO算法[3]、DCNP算法[4]等。按照間隙類型的不同，一次性模式匹配可分為非負間隙的匹配和一般間隙的匹配。本文將從這兩個方面，對目前的一次性匹配算法進行綜述。

一、非負間隙的匹配

一次性模式匹配已被證明為NPHard問題，現有的研究無法得到完備解。因此，研究者們均從解的完備性和時間效率兩方面進行不斷平衡。目前一次性模式匹配的求解方法可大致分為三類：二維表結構、位并行方法、樹或圖結構。

非負間隙約束滿足0≤ai≤bi，在求解這類模式匹配問題時，最直接的方法是用二維表結構進行求解，通過對二維表的構建和回溯來搜索一次性出現。這類算法的特點是能夠在線求解，具有較快的求解速度，但是容易陷入局部最優而丟解。而位并行的方法則是利用計算機字位運算的內在并行性，能夠進一步提高匹配效率，但在求解數量上相比二維表結構的方法并未提高。為了提高算法的求解質量，有研究者將模式匹配轉換為樹或圖中的路徑搜索問題，得到了較好的結果。例如，武等人[3]利用網樹結構提出一種離線求解算法SBO，該算法通過計算局部最優和全局最優，提高了一次性條件下解的個數。這類算法能夠得到更多的解，但由于存在大量的耗時計算，導致算法的求解效率不高。

二、一般間隙的匹配

非負間隙忽略了字符顛倒的情況，在某些領域中使用受到限制。例如，在實際的購買序列中，<鼠標，鍵盤>和<鍵盤，鼠標>可以認為是同一購買行為。為了提高間隙約束的靈活性，有研究者開展了一般間隙下的模式匹配研究。一般間隙允許存在ai<0或者bi<0的情況，如P=a[1，2]g[2，1]t就是一般間隙下的模式，這樣的模式能夠發現更多隱藏的信息，但是求解難度更大。武等人[5]對一般間隙轉化為非負間隙的模式進行了理論研究，并利用子網樹結構提出一種SETS算法，能夠對一般間隙下的模式匹配進行快速求解。然而該算法只能計算完全匹配數，出現數量巨大，并且不能輸出具體的出現位置。為解決該問題，柴等人[4]在一般間隙的模式匹配問題中引入一次性條件，由于一次性條件限制了字符的使用次數，導致在一般間隙下存在形如<1，2，1>的內部重復問題。于是，引入一種Checking檢測機制對該問題進行有效的解決，并提出一種基于結點動態更新的DCNP算法。該算法不僅能夠對出現集進行有效縮減，而且能夠計算出一般間隙模式的具體出現位置，具有更廣闊的應用前景。

三、總結與展望

本文主要對一次性序列模式匹配進行了詳細綜述。首先對帶間隙約束的模式匹配進行了介紹，然后從非負間隙和一般間隙兩個角度，對一次性模式匹配的相關研究進行了詳細分析。最終我們發現，目前的一次性模式匹配都是在力求找到更多解的同時，提高求解效率，但均未實現完備性求解。如何更加高效地處理一次性模式匹配問題，仍然需要進一步的研究。同時，現有的研究大多都將字符的效用視為均等，而基于高效用的一次性模式匹配工作則更加具有實際意義，這也需要進一步的研究探討。

參考文獻：

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

[2]Wu Y，Wang L，Ren J，et al.Mining sequential patterns with periodic wildcard gaps[J].Applied Intelligence，2014，41（1）：99116.

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

[4]柴欣，賈曉菲，武優西，等.一般間隙及一次性條件的嚴格模式匹配[J].軟件學報，2015，26（5）：10961112.

[5]武優西，劉亞偉，郭磊，等.子網樹求解一般間隙和長度約束嚴格模式匹配[J].軟件學報，2013，24（5）：915932.

作者簡介：于磊（1994—），男，漢族，河北深州人，碩士，學生，研究方向：模式挖掘。