基于位并行技術(shù)的帶通配符約束的模式匹配問題研究.pdf

1、模式串匹配是計(jì)算機(jī)科學(xué)中一個(gè)基本、重要的研究問題。隨著信息技術(shù)的高速發(fā)展，它在Internet網(wǎng)絡(luò)信息搜索、數(shù)據(jù)流挖掘、網(wǎng)絡(luò)入侵檢測(cè)、計(jì)算生物學(xué)等領(lǐng)域中的應(yīng)用越來越廣泛。
　　 近年來，帶通配符約束的模式匹配問題作為模式匹配領(lǐng)域的一項(xiàng)新穎的研究方向已經(jīng)越來越引起廣泛的關(guān)注。在傳統(tǒng)的模式中加入通配符約束，雖然使問題變得更復(fù)雜，但更能滿足用戶對(duì)模式的靈活定義的需求。這使得帶通配符約束的模式匹配問題不僅具有理論研究價(jià)值，而且有著實(shí)際應(yīng)

2、用價(jià)值：如在生物信息學(xué)中，很多蛋白質(zhì)模式便含有通配符約束。當(dāng)前對(duì)帶通配符的模式匹配存在的很多現(xiàn)有的工作，但仍然有一些問題需要進(jìn)一步的研究，如在模式中通配符約束的定義，匹配結(jié)果的表達(dá)，時(shí)間效率的提高。為此，本文針對(duì)以上關(guān)鍵問題進(jìn)行研究，主要工作如下：
　　 (1)本文在已有的工作基礎(chǔ)上，介紹同時(shí)包括全局長度約束及局部通配符約束模式匹配問題的形式化定義，證明在One-Off條件下帶通配符約束的模式匹配問題是一個(gè)NP-hard問題。<

3、br>　　 (2)提出一種基于位并行技術(shù)的提出的BPBM算法。算法基于“最左最優(yōu)”的啟發(fā)式策略，返回One-Off條件下的所有匹配序列。該算法的基本思想是采用了BM算法的基于后綴搜索的方法，使用兩個(gè)非確定性自動(dòng)機(jī)NFA對(duì)掃描文本的過程進(jìn)行模擬，并利用位并行技術(shù)解決了NFA當(dāng)前活動(dòng)狀態(tài)比較多，對(duì)于每次讀入的新字符更新活動(dòng)狀態(tài)集慢的缺陷。理論分析及實(shí)驗(yàn)證明BPBM算法較解決同類或類似問題的其他算法無論在時(shí)間上或匹配結(jié)果上更具競(jìng)爭(zhēng)力。