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

【參考文獻】

相關期刊論文 前10條

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

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

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

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

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

6 關超;蔣建中;郭軍利;;一種基于反向有限自動機的多模式匹配算法[J];計算機工程;2010年01期

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

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

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

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

相關碩士學位論文 前3條

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

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

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

，

本文編號：2251777