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

1、本文研究的對(duì)象是在傳統(tǒng)的模式匹配問(wèn)題中引入通配符和長(zhǎng)度約束,并將之定義為PMWL問(wèn)題。相比于傳統(tǒng)的匹配問(wèn)題,PMWL更適合于生物信息學(xué)、信息檢索等領(lǐng)域的需求以及在數(shù)據(jù)壓縮、網(wǎng)絡(luò)入侵檢測(cè)等諸多學(xué)科上的交叉應(yīng)用。
　　 然而,PMWL較為靈活的定義也造成了問(wèn)題求解的困難。這種困難性往往表現(xiàn)在問(wèn)題完備性分析和算法設(shè)計(jì)上。目前已有的關(guān)于PMWL問(wèn)題的研究中,一方面缺少足夠的理論分析;另一方面一些代表性的算法在完備性和時(shí)間復(fù)雜度上都有改進(jìn)

2、的余地,而且上述算法的實(shí)驗(yàn)大多基于個(gè)別模式,缺少統(tǒng)計(jì)意義上的實(shí)驗(yàn)分析,特別是完備性的分析。本文針對(duì)上述問(wèn)題,借助模式特征,主要貢獻(xiàn)如下:
　　 (1)本文面向PMWL問(wèn)題,在研究影響完備性的模式長(zhǎng)度、通配符跨度、字母表大小和模式中字符的重復(fù)度等相關(guān)因素的基礎(chǔ)上,以目前最具代表性的SAIL算法為研究載體,一方面得到了基于模式特征的有條件完備性證明;另一方面得到了PMWL問(wèn)題基于實(shí)驗(yàn)分析的數(shù)學(xué)模型,描述了PMWL問(wèn)題的完備性與模式特