靳超艷 劉靖宇

?

具有間隙約束的模式匹配的研究進(jìn)展

靳超艷 劉靖宇

河北工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津 300401

模式匹配（也稱為字符串匹配）是計(jì)算機(jī)科學(xué)的經(jīng)典問題之一，也是眾多交叉學(xué)科解決技術(shù)問題的關(guān)鍵。具有間隙約束的序列模式匹配已成為模式匹配問題中的研究熱點(diǎn)，在很多領(lǐng)域有著廣泛應(yīng)用，如生物學(xué)中DNA序列的研究、音樂領(lǐng)域音符信息的檢索以及目前研究火熱的大數(shù)據(jù)領(lǐng)域等，因此具有間隙約束的模式匹配問題是諸多領(lǐng)域的基礎(chǔ)，具有很高的研究價(jià)值和意義。因此，總結(jié)了近年來具有間隙約束的模式匹配的成果和進(jìn)展，對(duì)具有間隙約束的模式匹配的發(fā)展趨勢進(jìn)行了展望，以便對(duì)具有間隙約束的模式匹配問題做進(jìn)一步研究。

模式匹配；間隙約束；研究進(jìn)展

引言

近年來，隨著科學(xué)技術(shù)的迅猛發(fā)展，人類進(jìn)入了信息社會(huì)。人類社會(huì)產(chǎn)生的數(shù)據(jù)量與日俱增，在很多領(lǐng)域涌現(xiàn)出大量的序列數(shù)據(jù)。如何對(duì)這些序列數(shù)據(jù)進(jìn)行分析和挖掘以提取有價(jià)值的信息，是目前人們比較關(guān)注的問題。數(shù)據(jù)挖掘技術(shù)的基礎(chǔ)就是模式匹配問題。

模式匹配也稱為字符串匹配。此問題描述的是從序列串中找到與模式串P相匹配的出現(xiàn)的個(gè)數(shù)或者出現(xiàn)的位置。其中，序列串S和模式串來自同一個(gè)字符集。具有間隙的模式匹配問題的研究較早，所研究的模式串間隙都是單個(gè)可變間隙，例如Manber等人[1]為解決單個(gè)可變間隙的模式匹配問題提出了有效算法。然而隨著科技的快速發(fā)展，單一可變通配符的模式匹配已經(jīng)不能滿足現(xiàn)實(shí)應(yīng)用。因此，多個(gè)可變間隙的模式匹配問題成為研究熱點(diǎn)，近年來受到越來越多研究者的關(guān)注。

1 具有間隙約束的模式匹配

具有間隙約束的模式匹配問題主要可以從以下幾方面進(jìn)行分類：非負(fù)間隙約束或者一般間隙約束、寬松模式匹配或者嚴(yán)格模式匹配、精確匹配或者近似匹配、是否對(duì)出現(xiàn)有特殊約束條件。

1.1 間隙類型

具有間隙約束的模式匹配問題按照間隙的類型可以分為非負(fù)間隙約束模式匹配和一般間隙約束模式匹配。非負(fù)間隙模式匹配是指模式串中的最小間隙和最大間隙均為大于等于0的數(shù)，而一般間隙模式匹配是指模式串中的最小間隙和最大間隙至少有一個(gè)為小于0的數(shù)。例如模式串=1[1，1]2[2，2]3= a[0，1]b[0，1]c就是一個(gè)非負(fù)間隙模式串，而模式串=1[1，1]2[2，2]3=a[-1，1]b[-1，2]c則為一般間隙模式串。文獻(xiàn)[2]對(duì)非負(fù)間隙約束的模式匹配問題進(jìn)行了研究，并應(yīng)用于序列模式挖掘中；文獻(xiàn)[3]利用網(wǎng)樹結(jié)構(gòu)對(duì)一般間隙約束的模式匹配問題進(jìn)行了研究。

1.2 寬松模式匹配與嚴(yán)格模式匹配

寬松模式匹配是指僅考慮模式串中最后一個(gè)字符在序列串中的位置，不考慮其他位置的字符，因此寬松模式匹配通常對(duì)出現(xiàn)沒有特殊的約束要求。Fredriksson和Grabowski[4]對(duì)一般間隙的寬松模式匹配問題進(jìn)行了研究，并應(yīng)用于音樂信息檢索及蛋白質(zhì)序列分析等方面。

嚴(yán)格模式匹配要考慮模式串中每個(gè)字符在序列串中的位置，并由此構(gòu)成一個(gè)出現(xiàn)。文獻(xiàn)[2]及文獻(xiàn)[5]均是對(duì)嚴(yán)格模式匹配問題進(jìn)行研究。嚴(yán)格模式匹配更廣泛的應(yīng)用于生物信息等領(lǐng)域。

以下舉例說明了寬松模式匹配與嚴(yán)格模式匹配的區(qū)別。

例1：給定序列串=1234567=gaccgac，模式串=1[1，1]2[2，2]3=g[0，4]a[0，1]c。

寬松模式匹配只考慮模式串中最后一個(gè)字符3=c在序列串中的位置，例1中模式串在序列串中有3個(gè)出現(xiàn)，分別是3、4、7。

嚴(yán)格模式匹配考慮模式串中所有字符在序列串中的位置，例1中模式串在序列串中的出現(xiàn)有4個(gè)，分別為<1，2，3>、<1，2，4>、<1，6，7>以及<5，6，7>。

1.3 精確模式匹配與近似模式匹配

精確模式匹配要求所有位置的字符都要與模式串P中的字符相對(duì)應(yīng)，而近似模式匹配允許一定程度的不對(duì)應(yīng)，如基于Hamming距離的近似模式匹配。文獻(xiàn)[6]對(duì)基于Hamming距離的一般間隙的近似模式匹配問題進(jìn)行研究，并提出SETA算法對(duì)該匹配問題進(jìn)行求解。

1.4 對(duì)出現(xiàn)的特殊約束條件

對(duì)出現(xiàn)的特殊約束條件只存在于嚴(yán)格模式匹配問題中。其中包括三種對(duì)出現(xiàn)的統(tǒng)計(jì)方式：無條件約束、一次性條件約束和無重疊條件約束。此外，還有無長度約束。

1.4.1 無條件約束

無條件約束指對(duì)出現(xiàn)沒有任何約束，即找到模式串在序列串中的所有出現(xiàn)。

例2：給定序列串=123456=gagaag，模式串=1[1，1]2[2，2]3=g[0，1]a[0，1]g。

無約束條件下模式串在序列串中的3個(gè)出現(xiàn)為：<1，2，3>、<3，4，6>以及<3，5，6>。文獻(xiàn)[2]所研究的即為無條件約束的模式匹配問題。

1.4.2 一次性條件約束

一次性條件約束要求序列串中任意位置對(duì)應(yīng)的字符在匹配過程中最多被使用一次。在一次性條件約束下，例2中模式串在序列串中的出現(xiàn)只有1個(gè)，為<1，2，3>（或<3，4，6>或<3，5，6>）。文獻(xiàn)[5]提出了DCNP算法，該算法利用網(wǎng)樹結(jié)構(gòu)，通過動(dòng)態(tài)更新網(wǎng)樹的策略，解決了一般間隙及一次性條件的模式匹配問題，并在很大程度上提高了解的質(zhì)量。

1.4.3 無重疊條件約束

Ding 等人[7]提出了無重疊序列模式挖掘問題。無重疊條件約束要求序列串中任意位置的字符不能在兩個(gè)出現(xiàn)的同一位置使用。在例2中，模式串在序列串中的無重疊出現(xiàn)有兩個(gè)，為<1，2，3>和<3，4，6>（或<1，2，3>和<3，5，6>亦可）。盡管位置3的字符“g”被使用了兩次，但是分別是模式子串3和子串1使用。

由于Ding 等人提出的無重疊模式匹配算法INSgrow不能找到完備解，因此Wu等人[8]針對(duì)INSgrow算法存在的問題，提出了NETGAP-Best算法，該算法利用網(wǎng)樹結(jié)構(gòu)通過尋找最右雙親結(jié)點(diǎn)來找到一個(gè)出現(xiàn)，在找到出現(xiàn)后對(duì)網(wǎng)樹進(jìn)行剪枝，該算法有效的解決了無重疊模式匹配所找解不完備的問題。

1.4.4 是否存在長度約束

具有長度約束的模式匹配要求找到的出現(xiàn)中的最小位置與最大位置的差要滿足給定的最大長度和最小長度。若例2中規(guī)定最小長度為4、最大長度為5，則由于出現(xiàn)<1，2，3>的長度為3-1+1=3，因此不滿足長度約束。對(duì)于出現(xiàn)<3，4，6>和出現(xiàn)<3，5，6>，因?yàn)?-3+1=4，所以滿足長度約束。文獻(xiàn)[3]對(duì)有長度約束的模式匹配進(jìn)行了研究。

2 總結(jié)

本文介紹了具有間隙約束的模式匹配問題的研究現(xiàn)狀，具體介紹了具有間隙約束的模式匹配問題的分類以及近幾年各種模式匹配問題的研究進(jìn)展，并對(duì)其中經(jīng)典算法進(jìn)行了簡單的介紹。目前具有間隙約束的模式匹配問題的研究越來越多，如何更好地提高解的質(zhì)量，并將其應(yīng)用到現(xiàn)實(shí)生活中，值得研究者們做進(jìn)一步的探索。

[1]Manber U，Baeza-Yates R. An algorithm for string matching with a sequence of don’t cares[J].Information Processing Letters，1991，37（3）：133-136.

[2]Wu Y X, Wang L L，Ren J D, et al. Mining Sequential Patterns with Periodic Wildcard Gaps[J]. ApplIntell，2014，41（1）：99-116.

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

[4]Fredriksson K，Grabowski S. Efficient algorithms for pattern matching with general gaps, character classes and transposition invari- ance[J]. Information Retrieval，2008，11（4）：335-357.

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

[6] Wu Y X，F(xiàn)u S，Jiang H， Wu X D.Strict approximate pattern matching with general gaps[J].ApplIntell, 2015，42：566-580.

[7]Ding B，Lo D， Han J， Khoo S C. Efficient mining of closed repetitive gapped subsequences from a sequence database[C]//In: Ioannidis Y E, Lee D L, Ng R T，eds. IEEE 25th International Conference on Data Engineering（ICDE），Shanghai，China: IEEE, 2009：1024-1035.

[8]Wu Y X，Shen C，Jiang H，Wu X D. Strict pattern matching under non-over lapping condition[J]. Science China Information Sciences，2017，60（1）：1-16.

Progress on Pattern Matching with Gap Constraints

Jin Chaoyan Liu Jingyu

School of Computer Science and Engineering, Hebei University of Technology, Tianjin 300401

Pattern matching (also known as string matching) is one of the classic computer science problems, and is also the key to solving technical problems many interdisciplinary. Sequence pattern matching with gap constraint has become a research hotspot in pattern matching. It has been widely used in many fields, such as the research of DNA sequence in biology, the retrieval of note information in music field, and the hot field of big data nowadays. Therefore, the problem of pattern matching with gap constraints is the foundation of many fields and has high research value and significance. The paper summarizes the achievements and progress of pattern matching with gap constraint in recent years, and forecasts the trend of pattern matching with gap constraint in order to further study the pattern matching with gap constraint.

pattern matching; gap conditions; research progress

TP391.1

A

河北省高等學(xué)校科學(xué)技術(shù)研究項(xiàng)目資助（QN2014192）；河北省科技計(jì)劃項(xiàng)目（15210325）；河北省自然科學(xué)基金（F2016202145）。