發(fā)布時間：2017-05-03 14:00

  本文關(guān)鍵詞：基于跳躍式匹配的多模式匹配算法研究，由筆耕文化傳播整理發(fā)布。

【摘要】：模式匹配技術(shù)廣泛應(yīng)用于生物信息學(xué)、網(wǎng)絡(luò)搜索引擎、內(nèi)容過濾防火墻、入侵檢測系統(tǒng)等領(lǐng)域,是信息科學(xué)領(lǐng)域中重要的研究方向之一。隨著計算機網(wǎng)絡(luò)技術(shù)的飛速發(fā)展,網(wǎng)絡(luò)中的信息量呈現(xiàn)爆炸式增長。如何提高模式匹配效率成為人們研究的熱點。本文介紹了模式匹配技術(shù)的國內(nèi)外研究現(xiàn)狀,探討了模式匹配及其應(yīng)用技術(shù),研究了幾種典型的模式匹配算法,包括單模式匹配BM算法、BMH算法、Sunday算法等及多模式匹配AC算法、AC_BM算法等,分析了他們的時間性能,并比較了各自的優(yōu)缺點。針對AC_BM等算法的不足之處,提出一種改進(jìn)的多模式匹配算法——AC TE,該算法具有以下特點：(1)基于跳躍式匹配思想,根據(jù)當(dāng)前匹配窗口前兩個字符確定模式樹跳躍距離,保證在不發(fā)生漏檢的情況下,使得模式樹最大移動距離達(dá)到最短模式串長度minlen加2,從而減少匹配次數(shù)。(2)構(gòu)建首字符表、minlen層字符表和字符串跳躍哈希表,分別存儲模式樹首層字符、minlen層字符和模式樹中兩兩相鄰字符組成的字符串的跳躍值,采用多層跳躍規(guī)則查找這三個表,快速獲取模式樹跳躍距離,提高算法的時間效率。分析了AC TE算法模式樹最大移動距離和時間復(fù)雜度。對算法進(jìn)行性能測試,測試結(jié)果表明,與AC_BMH、AC_SUNDAY算法相比,AC TE算法具有較好時間性能。
【關(guān)鍵詞】：跳躍式匹配 AC算法 移動距離 AC_TE算法 模式樹
【學(xué)位授予單位】：合肥工業(yè)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：TP301.6
【目錄】：

• 致謝7-8
• 摘要8-9
• ABSTRACT9-14
• 第一章 緒論14-17
• 1.1 研究背景與意義14
• 1.2 國內(nèi)外研究現(xiàn)狀14-15
• 1.3 研究內(nèi)容15
• 1.4 本文的組織結(jié)構(gòu)15-17
• 第二章 模式匹配技術(shù)17-21
• 2.1 概述17
• 2.2 模式匹配算法分類17-18
• 2.3 模式匹配技術(shù)應(yīng)用18-19
• 2.4 模式匹配技術(shù)研究面臨的問題19-20
• 2.5 本章小結(jié)20-21
• 第三章 模式匹配算法研究21-39
• 3.1 單模式匹配算法21-29
• 3.1.1 BF算法21
• 3.1.2 KMP算法21-22
• 3.1.3 BM算法22-25
• 3.1.4 BMH算法25-27
• 3.1.5 Sunday算法27-29
• 3.2 多模式匹配算法29-38
• 3.2.1 AC算法29-33
• 3.2.2 AC_BM算法33-35
• 3.2.3 Two-HT算法35-38
• 3.3 本章小結(jié)38-39
• 第四章 AC_TE多模式匹配算法39-47
• 4.1 AC改進(jìn)算法的不足39
• 4.1.1 AC_BM算法的不足39
• 4.1.2 AC_BMH算法的不足39
• 4.1.3 AC_SUNDAY算法的不足39
• 4.2 AC_TE算法39-42
• 4.2.1 基本思想39-40
• 4.2.2 AC_TE算法模式樹移動規(guī)則40
• 4.2.3 AC_TE算法預(yù)處理表40-42
• 4.3 AC_TE算法描述42-45
• 4.3.1 預(yù)處理階段42-43
• 4.3.2 匹配階段43-45
• 4.4 AC_TE算法匹配過程示例45-46
• 4.5 AC_TE算法分析46
• 4.5.1 模式樹最大移動距離46
• 4.5.2 匹配階段時間復(fù)雜度46
• 4.6 本章小結(jié)46-47
• 第五章 算法性能測試47-56
• 5.1 實驗環(huán)境與資源47
• 5.1.1 實驗環(huán)境47
• 5.1.2 文本串和模式串47
• 5.2 實驗?zāi)康呐c內(nèi)容47
• 5.3 實驗結(jié)果與分析47-55
• 5.3.1 模式樹移動次數(shù)47-49
• 5.3.2 模式樹平均移動距離49-51
• 5.3.3 字符比較次數(shù)51-53
• 5.3.4 匹配時間53-55
• 5.4 本章小結(jié)55-56
• 第六章 總結(jié)與展望56-57
• 6.1 總結(jié)56
• 6.2 展望56-57
• 參考文獻(xiàn)57-60
• 附錄：AC_TE算法源代碼60-73
• 攻讀碩士學(xué)位期間的學(xué)術(shù)活動及成果情況73-74

【相似文獻(xiàn)】

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

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

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

3 張峰;;一種改進(jìn)的多模式匹配算法[J];福建電腦;2010年08期

4 姚亞鋒;蔣毅;;模式匹配算法及其優(yōu)化[J];南通職業(yè)大學(xué)學(xué)報;2011年04期

5 萬姝伊;;關(guān)于快速高效的模式匹配算法的剖析與改進(jìn)[J];數(shù)字技術(shù)與應(yīng)用;2011年12期

6 何文華;;基于海量數(shù)據(jù)的多模式匹配算法研究[J];計算機應(yīng)用與軟件;2012年04期

7 王瑞瑩;邱亮;;一種新的應(yīng)用于數(shù)據(jù)流關(guān)聯(lián)分析的多模式匹配算法[J];東北電力大學(xué)學(xué)報;2012年04期

8 周慶勛;高效率的模式匹配算法[J];云南民族學(xué)院學(xué)報(自然科學(xué)版);2000年04期

9 劉建軍,武兵,寧玉富;一種新的模式匹配算法的設(shè)計與實現(xiàn)[J];德州學(xué)院學(xué)報(自然科學(xué)版);2003年06期

10 程圣宇,白英杰,肖瀛,蘆東昕;模式匹配算法性能測試[J];計算機應(yīng)用;2003年S2期

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

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

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

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

4 朱艷;許家s，

本文編號：343105