網(wǎng)樹求解具有間隙和一次性條件約束的近似匹配.pdf

1、模式匹配是一個計算機學(xué)科中非?；A(chǔ)性和經(jīng)典性的問題，在諸多領(lǐng)域具有十分廣泛地應(yīng)用，如在文本檢索，生物序列分析，數(shù)據(jù)挖掘以及傳感器網(wǎng)絡(luò)中均有十分重要的應(yīng)用。
　　在模式匹配的研究過程中，通常需要引入通配符，以方便用戶的查詢與檢索。傳統(tǒng)的通配符僅有“?”和“*”分別用來通配單個字符或任意多個字符。但近年來，一種具有間隙約束的模式匹配問題在音樂信息檢索、數(shù)據(jù)挖掘和分類或聚類問題的特征抽取中均具有重要的應(yīng)用。新的模式匹配問題中模式串P可以

2、描述為p0[min0, max0]p1…[minj-1, maxj-1]pj…[minm-2, maxm-2]pm-1的形式，這里minj-1和maxj-1分別描述字符pj-1和pj可以通配的最小和最大字符的數(shù)量。在具有間隙約束模式匹配問題的研究中，一種被稱為一次性條件約束的模式匹配具有很大的挑戰(zhàn)意義，其是指不允許序列串中某一結(jié)點在結(jié)果中多次出現(xiàn)。但目前的研究主要是針對精確模式匹配的研究。近似模式匹配是更具實際意義的一項研究。
　

3、　本課題對目前具有間隙約束和一次條件的近似模式匹配問題進行研究，針對目前該問題的求解算法 SAIL-APPROX求解的精度不高問題進行研究，論文首先給出了問題的形式化定義；在此基礎(chǔ)上，將該問題轉(zhuǎn)化為一棵網(wǎng)樹；之后在網(wǎng)樹上建立了一種啟發(fā)式算法SBO-APP算法，該算法采用兩種策略，分別是優(yōu)化地選取近似出現(xiàn)策略和最右雙親近似出現(xiàn)策略，并從這兩個近似出現(xiàn)中，選取對問題影響最小的近似出現(xiàn)作為本次選擇的結(jié)果，迭代此過程，直到發(fā)現(xiàn)所有近似出現(xiàn)后停止