無(wú)重疊條件下嚴(yán)格模式匹配的研究.pdf

1、序列模式挖掘是數(shù)據(jù)挖掘分支，而序列模式匹配是序列模式挖掘的重要基礎(chǔ)。將挖掘方法用于生物序列、顧客購(gòu)買序列、網(wǎng)絡(luò)日志的分析，我們可從大數(shù)據(jù)中獲取各種潛在的規(guī)律和感興趣的信息。在這些研究中，帶有通配符間隙約束的生物序列匹配和挖掘比傳統(tǒng)的串匹配方法更具有挑戰(zhàn)性，且衍生出諸多種類的條件和約束。有一種方法是建立在無(wú)重疊條件基礎(chǔ)上的模式匹配，該問(wèn)題是當(dāng)給定具有間隙約束的模式串時(shí)，在給定的序列中找到滿足無(wú)重疊約束的最多出現(xiàn)，而無(wú)重疊出現(xiàn)是指任何兩個(gè)出

2、現(xiàn)中不能在相同位置處使用相同字符。因此本文對(duì)無(wú)重疊約束的嚴(yán)格模式匹配問(wèn)題進(jìn)行研究。
　　本文的主要研究?jī)?nèi)容和相關(guān)工作如下：
　　（1）給出了無(wú)重疊約束模式匹配的嚴(yán)格形式化定義；
　?。?）理論證明了無(wú)重疊約束模式匹配的計(jì)算復(fù)雜性是P的，即無(wú)重疊約束模式匹配是具有多項(xiàng)式時(shí)間的確定性算法來(lái)求解的判定問(wèn)題；
　?。?）采用網(wǎng)樹結(jié)構(gòu)構(gòu)造了完備性求解算法NETLAP-Best算法；
　　（4）大量對(duì)比性實(shí)驗(yàn)驗(yàn)證了NE