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

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

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

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

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