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

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

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

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 朱艷;許家s，

本文編號(hào)：1148752