一般間隙及一次性條件的嚴(yán)格模式匹配.pdf

1、模式匹配問題在計算機(jī)科學(xué)的基本問題之一。隨著科技的發(fā)展，帶有通配符的模式匹配技術(shù)在諸多領(lǐng)域都有重要的應(yīng)用，如在信息檢索、計算生物學(xué)和序列模式挖掘等領(lǐng)域。帶通配符的模式匹配具有更高的靈活性，允許各個子模式串之間間隔若干個字符，更具有實際意義。
　　傳統(tǒng)的具有間隙約束的模式匹配都是間隙為非負(fù)的模式匹配。嚴(yán)格限定了字符的出現(xiàn)次序，一定程度上限定了匹配的靈活性。一次性條件約束是要求序列中每個位置的字符最多只能使用一次,在序列模式挖掘中采用

2、一次性條件約束更加合理?；谏鲜鲈?，提出了一般間隙及一次性條件的嚴(yán)格模式匹配。為了更好的解決這個問題，提出了一種基于網(wǎng)樹結(jié)構(gòu)的算法。
　　本文理論證明了該問題的計算復(fù)雜性為NP-Hard問題，之后提出了網(wǎng)樹的概念，并且在網(wǎng)樹基礎(chǔ)上構(gòu)造了動態(tài)更新結(jié)點屬性的算法(Dynamically Changing Node Property,DCNP)。該算法的主要思想是動態(tài)的更新共同祖先集的樹根路徑數(shù)、樹葉路徑數(shù)以及位置相關(guān)數(shù)，從而可以獲得