【摘要】：字符串匹配是計(jì)算機(jī)科學(xué)與工程中的基本問題之一,應(yīng)用范圍極為廣泛,尤其是在計(jì)算生物學(xué),網(wǎng)絡(luò)安全,信息過濾等重要領(lǐng)域中是性能瓶頸�，F(xiàn)如今隨著信息化的高速發(fā)展,網(wǎng)絡(luò)流量增速已超出摩爾定律的約定范圍,僅通過硬件改進(jìn)的方式進(jìn)行以上領(lǐng)域的性能的提高并不現(xiàn)實(shí),所以必須研究方法更新、速度更快、性能更好的字符串匹配算法,以提高多領(lǐng)域中實(shí)時(shí)信息處理的速度。單模式和多模式串匹配,是字符串領(lǐng)域研究的基礎(chǔ),本文對(duì)此展開研究。單模式字符串匹配是模式匹配領(lǐng)域中的基礎(chǔ)研究課題,并擁有著悠久的歷史,其中著名的單模式字符串匹配算法,包括:KMP算法(Knuth-Morris-Pratt算法)和BM算法(Boyer和Moore算法)等,二者的最壞時(shí)間復(fù)雜度分別為:O(n)和O(mn)。多模式字符串匹配算法相對(duì)于單模式字符串匹配算法,不單單增多了匹配模式的個(gè)數(shù),也增多了應(yīng)用的范圍,尤其在實(shí)時(shí)信息處理的領(lǐng)域中受到非常多的關(guān)注,最為經(jīng)典的算法為AC算法(Aho-Corasick算法)。本文主要工作總結(jié)為以下幾個(gè)方面:第一,對(duì)字符串匹配算法的研究課題進(jìn)行了總結(jié)和分析,總結(jié)出了傳統(tǒng)模式串匹配算法的優(yōu)缺點(diǎn),包括:精確串匹配,正則表達(dá)式匹配,近似串匹配等,對(duì)字符串匹配的關(guān)鍵性能參數(shù)即時(shí)空復(fù)雜度進(jìn)行總結(jié)分析。第二,提出以整數(shù)為單位的比較方法,對(duì)后綴類字符串匹配算法進(jìn)行方法改進(jìn),結(jié)合幾種方法機(jī)制,其中,第一種機(jī)制是多窗口機(jī)制,并給出雙窗口和多窗口機(jī)制的示意圖,對(duì)其提高性能的原因進(jìn)行了詳細(xì)的分析和總結(jié);第二種機(jī)制是非對(duì)齊整數(shù)讀機(jī)制,分析該機(jī)制的工作原理以及具體的操作方式;第三種機(jī)制是q-grams方法機(jī)制,并總結(jié)了該機(jī)制應(yīng)用于模式匹配的優(yōu)勢。根據(jù)以上提出的方法,首先,提出了基于多窗口和非對(duì)齊整數(shù)讀機(jī)制的QSMI系列算法和TBMMI系列算法,然后,提出基于q-grams機(jī)制的改進(jìn)的BMHq算法,通過實(shí)驗(yàn)均證實(shí)了以上的改進(jìn)算法在時(shí)空復(fù)雜性方面達(dá)到最優(yōu)。第三,提出基于整數(shù)比較的改進(jìn)型BOM類算法,其中提到了基于后綴的FO自動(dòng)機(jī)以及UnrollingFO自動(dòng)機(jī)的構(gòu)建方法,在改進(jìn)方法中融合了 q-grams方法機(jī)制和非對(duì)齊整數(shù)讀方法機(jī)制,其中,利用q-grams機(jī)制增加算法的跳躍距離,利用非對(duì)齊整數(shù)讀方法機(jī)制簡化查表操縱,分別提出了q= 的BOMq算法,EBOM_sb系列算法和BOMq_sb系列算法,并給出自動(dòng)機(jī)構(gòu)建代碼和BOM3算法以及BOM3__2sb算法的實(shí)現(xiàn)偽代碼,并給出相應(yīng)的實(shí)驗(yàn)結(jié)果數(shù)據(jù)以便后續(xù)分析總結(jié)。第四,對(duì)經(jīng)典多模式串匹配AAC算法進(jìn)行詳細(xì)介紹,由于其匹配時(shí)消耗較大空間,且在發(fā)生失配時(shí),查找output表的操作過于復(fù)雜,本文基于AAC算法的基礎(chǔ)上,提出 AACA(Advanced AC with Additive State)算法和 AACN(Advanced AC with Negtive State)算法,二者雖然與AAC算法在構(gòu)建自動(dòng)機(jī)的方式上是一致,但是,AACA算法和AACN算法分別通過轉(zhuǎn)移和改變相應(yīng)狀態(tài),達(dá)到省略查找output表的操作,最后通過實(shí)驗(yàn)證實(shí),兩種改進(jìn)后的多模式串匹配算法,在小規(guī)模模式集合中進(jìn)行匹配時(shí),能得到很好的性能。最后,在提出的改進(jìn)算法的各章節(jié)的最后,給出了所做的相關(guān)實(shí)驗(yàn),實(shí)驗(yàn)分析和實(shí)驗(yàn)數(shù)據(jù)的結(jié)果展示,充分證實(shí)改進(jìn)算法的性能最優(yōu),并進(jìn)行工作總結(jié)。
[Abstract]:......
【學(xué)位授予單位】：昆明理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：TP391.1

【參考文獻(xiàn)】

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

1 許家銘;李曉東;金鍵;馬盈;;一種高效的多模式字符串匹配算法[J];計(jì)算機(jī)工程;2014年03期

2 范洪博;姚念民;;高級(jí)AC自動(dòng)機(jī)的快速構(gòu)建方法[J];計(jì)算機(jī)研究與發(fā)展;2013年12期

3 張建;范洪博;黃青松;劉利軍;;基于非對(duì)齊雙字節(jié)讀機(jī)制的單模式串匹配算法[J];計(jì)算機(jī)工程;2013年12期

4 巫喜紅;曾鋒;;AC多模式匹配算法研究[J];計(jì)算機(jī)工程;2012年06期

5 孫友倉;;多模式匹配算法的性能分析[J];電子設(shè)計(jì)工程;2010年01期

6 關(guān)超;蔣建中;郭軍利;;一種基于反向有限自動(dòng)機(jī)的多模式匹配算法[J];計(jì)算機(jī)工程;2010年01期

7 范洪博;姚念民;;一種高速精確單模式串匹配算法[J];計(jì)算機(jī)研究與發(fā)展;2009年08期

8 萬曉榆;楊波;樊自甫;;改進(jìn)的Sunday模式匹配算法[J];計(jì)算機(jī)工程;2009年07期

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

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

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

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

2 李雪;大規(guī)模特征串匹配技術(shù)的研究[D];北京郵電大學(xué);2008年

3 鄧惠俊;多模式匹配算法的研究[D];合肥工業(yè)大學(xué);2009年

，

本文編號(hào)：2251777