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

靳超艷 劉靖宇

?

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

靳超艷 劉靖宇

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

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

模式匹配；間隙約束；研究進展

引言

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

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

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

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

1.1 間隙類型

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

1.2 寬松模式匹配與嚴格模式匹配

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

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

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

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

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

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

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

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

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

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

1.4.1 無條件約束

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

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

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

1.4.2 一次性條件約束

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

1.4.3 無重疊條件約束

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

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

1.4.4 是否存在長度約束

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

2 總結(jié)

本文介紹了具有間隙約束的模式匹配問題的研究現(xiàn)狀，具體介紹了具有間隙約束的模式匹配問題的分類以及近幾年各種模式匹配問題的研究進展，并對其中經(jīng)典算法進行了簡單的介紹。目前具有間隙約束的模式匹配問題的研究越來越多，如何更好地提高解的質(zhì)量，并將其應(yīng)用到現(xià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)樹求解一般間隙和長度約束嚴格模式匹配[J].軟件學(xué)報，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)西，等.一般間隙及一次性條件的嚴格模式匹配[J].軟件學(xué)報，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ù)研究項目資助（QN2014192）；河北省科技計劃項目（15210325）；河北省自然科學(xué)基金（F2016202145）。