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

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

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

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

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