多模型下的近似字符串匹配算法研究.pdf

1、近似字符串匹配是模式匹配研究領(lǐng)域中的一個重要問題。近年來,隨著各學(xué)科的迅速發(fā)展,在許多不同背景下對于近似串匹配問題的研究逐漸受到人們的關(guān)注。特別是在計(jì)算生物學(xué)等新興學(xué)科中,有許多近似串匹配的新模型被陸續(xù)提出。一方面,這些模型在各學(xué)科中均有非常重要的應(yīng)用;另一方面,由于這些模型被提出的時間大多不長,因此對它們的研究并不充分。因此,對不同模型下的近似串匹配問題進(jìn)行研究就成為了在模式匹配和諸多相關(guān)領(lǐng)域中的研究重點(diǎn)和難點(diǎn)。針對這一現(xiàn)狀,研究的主

2、要內(nèi)容就是三種近年被提出的模型下的近似串匹配問題。這三種模型分別是:屬性匹配模型,交換匹配模型以及塊匹配模型。
　　針對屬性匹配,提出了一種新的索引結(jié)構(gòu)CIDS-PIP(compressedindexeddatastructureforpropertyindexingproblem)及相應(yīng)的匹配算法。在該算法中采用了壓縮后綴數(shù)組作為核心的索引結(jié)構(gòu)。為了進(jìn)一步降低索引的空間開銷,針對不同的屬性規(guī)模,提出了兩種解決方案。針對這兩種方案

3、設(shè)計(jì)了不同的輔助索引結(jié)構(gòu),以同時滿足較高的查詢效率和較低的空間開銷。與現(xiàn)有的支持屬性匹配的索引相比,CIDS-PIP的空間開銷更低。
　　針對交換匹配,提出了一種新的離線匹配算法,并證明了更精確的模式交換版本的個數(shù)上限。該交換匹配離線算法是建立在已有的全文索引的基礎(chǔ)上,而非設(shè)計(jì)全新的索引數(shù)據(jù)結(jié)構(gòu)。在該算法中,采用后綴數(shù)組或壓縮后綴數(shù)組作為索引結(jié)構(gòu)。當(dāng)模式長度較小時,該算法可以達(dá)到良好的時間效率,并明顯優(yōu)于現(xiàn)有的屬性匹配在線算法。此

4、外,還解決了近似交換匹配問題。實(shí)驗(yàn)證明,相對于已有的在線交換匹配算法,該算法的時間效率大幅提高。
　　塊模式匹配模型是JulioN.等人在2011年提出的一種匹配模型,現(xiàn)在在此基礎(chǔ)上進(jìn)行的研究并不多見。針對在線和離線兩種情況下的塊模式匹配問題進(jìn)行了研究,并且分別給出了新的算法。相對于現(xiàn)有的在線匹配算法,新的在線算法需要更低的空間開銷,而時間開銷并沒有增加。相對于現(xiàn)有的離線匹配算法,新的離線算法的時間效率更高。與此同時,還指出了在J