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

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

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

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