基于通配符和長(zhǎng)度約束的近似模式匹配問(wèn)題研究.pdf

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

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

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