一次性序列模式匹配研究進(jìn)展

摘?要：帶通配符的模式匹配問題具有更廣闊的應(yīng)用前景。間隙約束是將通配符的數(shù)量設(shè)置為一個(gè)可變范圍，具有更高的靈活性。一次性模式匹配作為帶間隙約束模式匹配的一種，能夠?qū)ζヅ浣Y(jié)果進(jìn)行有效的縮減，有著重要的實(shí)際應(yīng)用意義。本文主要綜述了目前一次性序列模式匹配相關(guān)研究，并對將來的研究工作進(jìn)行了展望。

關(guān)鍵詞：一次性;間隙約束;模式匹配

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

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

一、非負(fù)間隙的匹配

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

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

二、一般間隙的匹配

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

三、總結(jié)與展望

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

參考文獻(xiàn)：

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

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

[5]武優(yōu)西，劉亞偉，郭磊，等.子網(wǎng)樹求解一般間隙和長度約束嚴(yán)格模式匹配[J].軟件學(xué)報(bào)，2013，24（5）：915932.

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