子網(wǎng)樹(shù)求解一般間隙和長(zhǎng)度約束嚴(yán)格模式匹配.pdf

1、模式匹配Pattern matching（也稱(chēng)串匹配String matching)是復(fù)雜性理論中研究最廣泛的問(wèn)題之一，它是網(wǎng)絡(luò)安全、信息檢索與過(guò)濾、文字處理、數(shù)據(jù)庫(kù)查詢(xún)、音樂(lè)檢索、計(jì)算生物學(xué)等重要領(lǐng)域的核心問(wèn)題，同時(shí)也是序列模式挖掘技術(shù)的核心與基礎(chǔ)。
　　目前學(xué)術(shù)界又重新對(duì)字符串匹配提起了興趣，尤其是人類(lèi)基因組計(jì)劃的實(shí)施，計(jì)算生物學(xué)的興起，又將字符串匹配推到了高潮。為了更好地滿(mǎn)足用戶(hù)對(duì)模式靈活設(shè)置，在傳統(tǒng)的模式中加入通配符約束，

2、使問(wèn)題變得更復(fù)雜。雖然目前允許對(duì)通配符進(jìn)行約束，但研究方向主要側(cè)重于對(duì)間隙值為正的有序模式匹配，然而間隙值為負(fù)的更為一般的模式匹配問(wèn)題更具普遍意義，且求解難度更大，本文針對(duì)以上研究現(xiàn)狀進(jìn)行分析，做了如下工作：
　　(1)基于前人的研究工作，提出了更具一般性的模式匹配，即一般間隙和長(zhǎng)度約束的嚴(yán)格模式匹配(Strict Pattern Matching with General Gaps and Length Constrains,簡(jiǎn)

3、稱(chēng)SPANGLO)：此匹配強(qiáng)調(diào)嚴(yán)格精確；文本串中的字符可以使用多次；模式串中可以含有多個(gè)負(fù)間隙；對(duì)匹配結(jié)果的長(zhǎng)度進(jìn)行了約束。
　　(2)深入分析了一般間隙和正間隙之間的關(guān)系，并給出了轉(zhuǎn)換方法，并實(shí)驗(yàn)驗(yàn)證了這種轉(zhuǎn)換方法的正確性。盡管這種轉(zhuǎn)換方法可以將SPANGLO問(wèn)題轉(zhuǎn)換為多個(gè)已解決的正間隙模式匹配問(wèn)題，但是這樣的轉(zhuǎn)換方法過(guò)于復(fù)雜，最壞情況下，一個(gè)SPANGLO問(wèn)題可以產(chǎn)生出指數(shù)個(gè)正間隙模式匹配問(wèn)題。
　　(3)在借鑒網(wǎng)樹(shù)概念