發(fā)布時間：2017-11-06 18:01

  本文關(guān)鍵詞：兩種高性能多模式匹配算法的設(shè)計與實現(xiàn)

  更多相關(guān)文章： 多模式匹配 高匹配性能 MASM算法 ELSM算法 SBT算法

【摘要】：作為計算機研究領(lǐng)域的核心技術(shù)之一,模式匹配算法被廣泛應(yīng)用于網(wǎng)絡(luò)安全,搜索引擎以及生物計算等領(lǐng)域,特別是針對網(wǎng)絡(luò)安全問題,模式匹配算法的性能更是直接影響了網(wǎng)絡(luò)安全系統(tǒng)的整體性能。隨著計算機網(wǎng)絡(luò)技術(shù)的飛速發(fā)展,互聯(lián)網(wǎng)產(chǎn)生的數(shù)據(jù)量也呈爆炸式增長,從而導(dǎo)致了模式匹配算法的研究面臨著諸多新的挑戰(zhàn),其中主要表現(xiàn)為隨著模式集的規(guī)模迅速增大,模式匹配算法的性能成為系統(tǒng)的瓶頸所在。因此絕大多數(shù)經(jīng)典的模式匹配算法無法直接有效的運用到大規(guī)模模式集環(huán)境下,所以研究適用于大規(guī)模模式集環(huán)境下具有高匹配性能的模式匹配算法是當(dāng)務(wù)之急,具有重要的學(xué)術(shù)研究意義和廣闊的應(yīng)用前景。論文的主要工作如下:1.提出了一種高匹配性能的較大規(guī)模多模式匹配算法,簡稱為ELSM算法。論文首先分析了一種適用于較大規(guī)模模式集而且空間復(fù)雜度低的多模式匹配算法:MASM算法,以及MASM算法在預(yù)處理階段用于模式串壓縮的Leaf-Attaching算法。雖然MASM算法空間復(fù)雜度低,但是算法的時間復(fù)雜度高,而且算法的時間復(fù)雜度和模式集的數(shù)量成正比。本論文提出的ELSM算法在保持MASM算法低空間復(fù)雜度性質(zhì)下又有著較低時間復(fù)雜度。ELSM算法在預(yù)處理階段使用改進的Leaf-Attaching算法,保證了算法在壓縮大規(guī)模模式集的時候不會出現(xiàn)內(nèi)存不足的情況。ELSM算法在模式匹配階段對MASM算法提出了如下三種改進策略:(1)使用數(shù)組的形式來實現(xiàn)完全二叉搜索樹,減少了算法的內(nèi)存占有量并且加快了訪問樹節(jié)點的速度。(2)采用AC算法作為初步匹配算法,過濾掉文本串中大量不會發(fā)生模式匹配的位置,減少了算法的匹配時間。(3)使用哈希表將完全二叉搜索樹分組,該策略減少了算法需要遍歷的完全二叉搜索樹的高度,從而減少了算法的匹配時間。最后通過實驗驗證ELSM算法在保留了MASM算法具有較低空間復(fù)雜度優(yōu)點的基礎(chǔ)上,有著更高的匹配性能。2.提出了一種帶失效跳轉(zhuǎn)機制的多模式匹配算法,簡稱為SBT算法。SBT算法主要基于Burst Tries數(shù)據(jù)結(jié)構(gòu)實現(xiàn),論文首先詳細分析Burst Tries的數(shù)據(jù)結(jié)構(gòu),以及Burst Tries的字符串查找以及字符串插入過程。然后提出將Burst Tries數(shù)據(jù)結(jié)構(gòu)應(yīng)用于多模式匹配領(lǐng)域的方法,并針對在應(yīng)用過程中會出現(xiàn)的空間復(fù)雜度過高和匹配效率低下的缺點提出了兩種改進策略即空間壓縮與失效跳轉(zhuǎn)策略,其具體內(nèi)容為:(1)SBT算法通過空間壓縮策略降低了Burst Tries中節(jié)點的內(nèi)存占用量,從而降低了算法的空間復(fù)雜度。(2)SBT算法的失效跳轉(zhuǎn)策略充分利用了模式匹配過程中已經(jīng)匹配的字符串信息,保證算法能跳過文本串中大量不會發(fā)生匹配的位置,從而提高了算法的匹配效率。最后通過設(shè)計一系列實驗驗證了SBT算法在匹配性能上的優(yōu)越性。
【學(xué)位授予單位】：西安電子科技大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：TP391.1;TP393.08

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 劉省賢;;模式匹配算法及其在農(nóng)作物嫁接中的作用[J];安徽農(nóng)業(yè)科學(xué);2009年19期

2 宋華,戴一奇;入侵檢測中一類允許誤差的多模式匹配算法[J];清華大學(xué)學(xué)報(自然科學(xué)版);2003年07期

3 伊靜,劉培玉;入侵檢測中模式匹配算法的研究[J];計算機應(yīng)用與軟件;2005年01期

4 彭詩力,譚漢松;基于特征值的多模式匹配算法及硬件實現(xiàn)[J];計算機工程與應(yīng)用;2005年01期

5 張春生;張曉英;王國忠;;字符串隨機探測模式匹配算法[J];內(nèi)蒙古民族大學(xué)學(xué)報(自然科學(xué)版);2007年06期

6 林南暉;張國軍;;對模式匹配算法的存儲優(yōu)化研究[J];中國海洋大學(xué)學(xué)報(自然科學(xué)版);2008年S1期

7 王杰;劉亞賓;孫珂珂;;一種快速高效的模式匹配算法的應(yīng)用研究[J];計算機工程與應(yīng)用;2008年32期

8 周延森;汪永好;;網(wǎng)絡(luò)入侵檢測系統(tǒng)模式匹配算法研究[J];計算機工程與設(shè)計;2008年07期

9 劉磊;;多模式匹配算法的研究與優(yōu)化[J];濰坊學(xué)院學(xué)報;2008年02期

10 任叢美;阮冬茹;郭彥穎;;入侵檢測模式匹配算法的研究與改進[J];中國新技術(shù)新產(chǎn)品;2008年16期

中國重要會議論文全文數(shù)據(jù)庫 前10條

1 張曉利;周榮輝;;多模式匹配算法在協(xié)議識別中的應(yīng)用[A];中國電子學(xué)會第十六屆信息論學(xué)術(shù)年會論文集[C];2009年

2 佟冰;張忠平;宋麗;;一種改進的多源模式匹配算法[A];2005年全國理論計算機科學(xué)學(xué)術(shù)年會論文集[C];2005年

3 王德正;;網(wǎng)絡(luò)入侵檢測系統(tǒng)中模式匹配算法的研究與改進[A];計算機技術(shù)與應(yīng)用進展·2007——全國第18屆計算機技術(shù)與應(yīng)用（CACIS）學(xué)術(shù)會議論文集[C];2007年

4 朱艷;許家s，

本文編號：1148752