基于連續(xù)r位匹配規(guī)則的并行串匹配研究.pdf

1、隨著互聯(lián)網(wǎng)的發(fā)展和普及，海量信息的處理和新的應(yīng)用需求，對于串匹配這個(gè)計(jì)算機(jī)領(lǐng)域中一個(gè)基本的而又是重要的問題，提出了新的挑戰(zhàn)。串匹配問題在Internet網(wǎng)絡(luò)信息搜索、信息過濾、生物信息學(xué)、網(wǎng)絡(luò)入侵檢測、網(wǎng)絡(luò)遠(yuǎn)程教育、電子商務(wù)等領(lǐng)域具有廣泛的應(yīng)用。 關(guān)于串匹配的問題很早就有相關(guān)的研究，提出了許多單模式匹配算法和多模式匹配算法。人們逐漸發(fā)現(xiàn)在實(shí)際應(yīng)用中根據(jù)實(shí)際需要進(jìn)行串匹配的研究具有重要的應(yīng)用價(jià)值。因此，研究高效、快速的字符串匹配算

2、法具有重要的理論價(jià)值和實(shí)際意義。 應(yīng)該說，本文所提出的連續(xù)r位匹配規(guī)則是從精確串匹配規(guī)則中演變和發(fā)展而來的。這種演變思想的來源是，作者通過查閱醫(yī)學(xué)領(lǐng)域以及計(jì)算機(jī)領(lǐng)域中關(guān)于免疫學(xué)、人工免疫系統(tǒng)和免疫算法的相關(guān)資料，從中了解到免疫系統(tǒng)已經(jīng)應(yīng)用到計(jì)算機(jī)領(lǐng)域來解決許多難題，并得到了滿意的效果。但在這其中將免疫系統(tǒng)中的連續(xù)r位匹配規(guī)則應(yīng)用到字符串匹配這個(gè)問題上的先例并不多。然而，作者卻發(fā)現(xiàn)該免疫匹配規(guī)則有很多良好特性，如果能夠?qū)⑵鋺?yīng)用到我

3、們所討論的串匹配問題上，那么將會得到比較好的效果。例如，其分布性、并行性的特點(diǎn)，如果應(yīng)用到串匹配的問題上，那么當(dāng)數(shù)據(jù)量劇增的時(shí)候，運(yùn)行時(shí)間急劇下降的問題將會得到解決。在人類的免疫系統(tǒng)中，抗體的種類大概有10<'6>個(gè)，然而到目前為止，人們所發(fā)現(xiàn)的病毒性抗原的種類大概有10<'16>個(gè)，那么我們的肌體為什么能夠在如此龐大的病毒性抗原面前還能安然無恙呢? 這里面，抗原與抗體的不完全匹配起著非常重要的作用。連續(xù)r位匹配規(guī)則正是從免疫系統(tǒng)中抗原

4、與抗體不完全匹配性引出的，所以應(yīng)用其特點(diǎn)來解決串匹配問題也是值得研究的。作者正是基于以上的一些想法，開始了本論文的撰寫工作。 首先，本文簡單的介紹了一下免疫學(xué)的一些基本知識以及免疫匹配規(guī)則，給出了本文所應(yīng)用的生物學(xué)基礎(chǔ)。 其次，通過對KMP算法的分析，向其中引入了連續(xù)r位匹配規(guī)則因子，這樣就可以通過預(yù)先控制匹配閾值r的大小來滿足我們所需要的模式串與文本串相匹配的程度，從而得到我們滿意的答案。 最后，作者通過實(shí)際