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

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

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

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

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