基于通配符和長度約束的近似模式匹配問題研究.pdf

1、近年來,隨著生物信息計(jì)算、網(wǎng)絡(luò)入侵檢測、文本檢索等領(lǐng)域數(shù)據(jù)量的激增,如何從中快速地提取用戶感興趣的信息成為了一項(xiàng)重要的研究課題,而模式匹配與挖掘是其中的重要組成部分,引起了國內(nèi)外研究學(xué)者的廣泛關(guān)注。
　　為了增加用戶模式查詢的靈活性,通配符和長度約束的概念先后被引入模式匹配問題中。本文首先針對帶有通配符和長度約束的近似模式匹配問題進(jìn)行研究,用戶可以自行定義模式字符間通配符的范圍、模式的最短長度和最大長度以及允許出現(xiàn)的編輯誤差。對該

2、問題的研究,不僅完善了近似模式匹配中通配符的引入問題,而且在許多實(shí)際領(lǐng)域同樣具備應(yīng)用價值。隨后,本文將該問題擴(kuò)展至帶有通配符和One-off條件的近似模式挖掘,解決了帶間隔約束和誤差的頻繁模式挖掘問題。
　　本文的研究工作主要包括以下三個方面:
　　(1)根據(jù)文本字符是否滿足One-off條件,針對帶有通配符和長度約束的近似模式匹配問題分別提出了APM算法和APM-OF算法,并與同類算法Sail-Approx進(jìn)行實(shí)驗(yàn)對比,結(jié)

3、果表明APM和APM-OF算法解的平均增長率分別達(dá)到了12.37％和8.34%。同時,對影響算法性能的三個主要參數(shù)進(jìn)行了實(shí)驗(yàn)與分析,發(fā)現(xiàn)當(dāng)編輯誤差k較大,模式P中字符(非通配符)的個數(shù)m適中,局部長度約束下限N很小或很大時解的增長率最為明顯,可分別達(dá)到31.43%和18.78%。
　　(2)將APM-OF算法擴(kuò)展至帶有通配符和長度約束的近似模式挖掘,提出了MAP算法。在與OneoffMining算法的實(shí)驗(yàn)對比中,結(jié)果顯示MAP算法