【摘要】：隨著互聯(lián)網(wǎng)的日益強大,互聯(lián)網(wǎng)上數(shù)據(jù)急劇增多,如何在海量的數(shù)據(jù)中快速準(zhǔn)確的找到所需信息,就顯得尤為重要,這就需要多模式串匹配算法。同時越來越多的人使用互聯(lián)網(wǎng)就會使互聯(lián)網(wǎng)的安全也變得越來越重要,如何盡可能早的識別出網(wǎng)絡(luò)攻擊行為,就需要對相關(guān)的行為進(jìn)行分析比對,同樣需要多模式匹配算法的應(yīng)用。而且隨著時代的發(fā)展,多模式串匹配算法在越來越廣闊的范圍里都有著相當(dāng)多的運用,比如:信息安全領(lǐng)域中:入侵偵測系統(tǒng)等;在醫(yī)學(xué)領(lǐng)域;數(shù)據(jù)挖掘,信息檢索,文本編輯器,計算生物學(xué)和對象識別等等領(lǐng)域中均有廣泛的應(yīng)用。本文通過對現(xiàn)今的幾種相對主流的多模式串匹配算法的闡述總結(jié),針對千萬規(guī)模級網(wǎng)絡(luò)上數(shù)據(jù)流的特點,在模式串集合較小的情況下選取了AC_QS(AhoCorasick_Quick Search)算法作為探究對象;當(dāng)模式串集合規(guī)模較大,達(dá)到上萬或者更大級別,或者機器實際的內(nèi)存開銷不足以運行AC_QS算法時,本文選取了KR(Karp Rabin)算法作為探究對象。AC(Aho Corasick)算法在這樣如此多的多模式串字符串匹配算法中是第一個時間消耗為線性的高效算法,其算法處理匹配時間短。AC_QS算法是使用AC算法的所有步驟,但在處理過程中利用QS(Quick Search)算法的思想進(jìn)一步增加字符跳轉(zhuǎn)距離而得到的算法,利用不出現(xiàn)字符的機制,進(jìn)一步增加了匹配時跳轉(zhuǎn)的字符數(shù),改善優(yōu)化了算法,提高了算法的運行效率,但其空間占用量也進(jìn)一步的變高。本文在AC_QS算法的基礎(chǔ)上主要針對其在模式串預(yù)處理過程,建立字典樹和與目標(biāo)文本的匹配過程三個方面進(jìn)行了優(yōu)化改善。對模式串預(yù)處理中的優(yōu)化主要表現(xiàn)在提前比較不在模式串中出現(xiàn)的字符,劃分目標(biāo)段更加方便并行處理,提高訪問模式串字符的訪問效率。對字典樹的優(yōu)化,主要表現(xiàn)在利用有序樹的方式對字典樹進(jìn)行存儲,減少字符的比較次數(shù)。匹配過程中的優(yōu)化,是在匹配過程中發(fā)現(xiàn)當(dāng)前匹配的部分字符不可能匹配某個模式串,則將該模式串置為當(dāng)前不可用狀態(tài),使得此模式串中字符變成無關(guān)字符,不進(jìn)行比較,達(dá)到減少部分比較次數(shù)的目的。本文針對大規(guī)模模式串集合提出的另一種基于KR算法的優(yōu)化算法,該算法是利用哈希函數(shù)的特性對字符串進(jìn)行哈希計算。本文首先設(shè)計了哈希函數(shù),然后將模式串進(jìn)行合適的分類,按照設(shè)計好的哈希函數(shù),求出模式串半段對應(yīng)的哈希值,然后對目標(biāo)文本串按照設(shè)定的基準(zhǔn)長度化分片段,每次比較目標(biāo)段是否含有模式串的半段。這樣算法每次處理目標(biāo)段的半段即可,這樣極大的減少了KR算法執(zhí)行過程里的字符匹配個數(shù),使得KR優(yōu)化算法的性能得到明顯提升。綜上,本文設(shè)計的多模式匹配算法AC_QS優(yōu)化算法和KR優(yōu)化算法,都是針對千萬級規(guī)模網(wǎng)絡(luò)的來設(shè)計。AC_QS優(yōu)化算法保證了算法的高效運行,但是需要消耗更多的內(nèi)存。KR優(yōu)化算法主要適用在無法為AC_QS優(yōu)化算法提供充足的內(nèi)存支持的情況下,能夠處理相當(dāng)大的模式串集合,因為算法的內(nèi)存占用相當(dāng)小。并通過實驗對兩個算法都與別的算法進(jìn)行了實驗比對,并分析了算法的時間復(fù)雜度和空間復(fù)雜度等相關(guān)性能指標(biāo),檢驗了算法,得出了最終結(jié)論。
[Abstract]:......
【學(xué)位授予單位】：哈爾濱工業(yè)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP391.1;TP393.08

【參考文獻(xiàn)】

相關(guān)期刊論文 前9條

1 王艷霞;江艷霞;王亞剛;李燁;;BMH2C單模匹配算法的研究與改進(jìn)[J];計算機工程;2014年03期

2 張元競;張偉哲;;一種基于位圖的多模式匹配算法[J];哈爾濱工業(yè)大學(xué)學(xué)報;2010年02期

3 高朝勤;陳元琰;黎蕓;;入侵檢測中一種節(jié)約內(nèi)存的多模式匹配算法[J];計算機工程與應(yīng)用;2009年11期

4 李志東;楊武;張汝波;王巍;;基于異構(gòu)隱式存儲的多模式匹配算法[J];通信學(xué)報;2009年03期

5 張麗霞;陳莉;;一種改進(jìn)的模式匹配算法[J];微計算機信息;2008年30期

6 張龍;吳文玲;溫巧燕;;mod 2~n加運算與F_2上異或運算差值的概率分布和遞推公式[J];北京郵電大學(xué)學(xué)報;2007年01期

7 張慶丹;戴正華;馮圣中;孫凝暉;;基于GPU的串匹配算法研究[J];計算機應(yīng)用;2006年07期

8 李曉明,鳳旺森;兩種對URL的散列效果很好的函數(shù)[J];軟件學(xué)報;2004年02期

9 張鑫,譚建龍,程學(xué)旗;一種改進(jìn)的Wu-Manber多關(guān)鍵詞匹配算法[J];計算機應(yīng)用;2003年07期

相關(guān)博士學(xué)位論文 前1條

1 李志敏;哈希函數(shù)設(shè)計與分析[D];北京郵電大學(xué);2009年

相關(guān)碩士學(xué)位論文 前5條

1 舒銀東;基于有限狀態(tài)自動機的多模式匹配算法研究[D];合肥工業(yè)大學(xué);2011年

2 唐定車;基于GPU并行串匹配算法的研究[D];湘潭大學(xué);2009年

3 李瑞林;Hash函數(shù)的分析與設(shè)計[D];國防科學(xué)技術(shù)大學(xué);2007年

4 劉燕兵;串匹配算法優(yōu)化技術(shù)研究[D];中國科學(xué)院研究生院（計算技術(shù)研究所）;2006年

5 劉萍;面向網(wǎng)絡(luò)內(nèi)容篩選的串匹配技術(shù)研究[D];中國科學(xué)院研究生院（計算技術(shù)研究所）;2005年

，

本文編號：2291532