一般間隙及一次性條件的嚴格模式匹配.pdf

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

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