本文關(guān)鍵詞：確定狀態(tài)自動機空間占用的優(yōu)化研究

  更多相關(guān)文章： 確定狀態(tài)自動機 完美哈希函數(shù) 存儲空間 壓縮算法

【摘要】：隨著互聯(lián)網(wǎng)時代的到來，計算機網(wǎng)絡(luò)已經(jīng)成為人們不可或缺的重要部分但網(wǎng)絡(luò)中的安全問題也日趨嚴重；網(wǎng)絡(luò)攻擊，網(wǎng)絡(luò)欺騙，以及盜用用戶賬號密碼的手段層出不窮通常情況下，所有的惡意代碼都被封裝到網(wǎng)絡(luò)數(shù)據(jù)包當中這樣計算機安全領(lǐng)域的重要問題就變成了如何高效的找出數(shù)據(jù)包中惡意代碼所以基于模糊查詢的正則表達式應(yīng)運而生，它通過自身的句法規(guī)則來描述特定字符串來提供數(shù)據(jù)集合中的查找結(jié)果，并且在模式匹配領(lǐng)域占據(jù)了極其重要地位，經(jīng)久不衰在基于文本的編輯器和搜索工具中，正則表達式的出現(xiàn)也使得數(shù)據(jù)處理變得更方便更高效正則表達式的匹配過程是由確定狀態(tài)自動機ξDFAο和非確定狀態(tài)自動機ξNFAο來完成的經(jīng)典的正則表達式自動機是Thompson自動機和Glushkov自動機，，但是經(jīng)典自動機的狀態(tài)轉(zhuǎn)移需要占用大量的存儲空間，并且狀態(tài)轉(zhuǎn)移的過程十分復(fù)雜，導(dǎo)致最終得到的實驗結(jié)果在時間復(fù)雜度和空間復(fù)雜度方面并不盡如人意近年來提出的基于比特并行的模式匹配方法使得模式匹配可以通過比特向量和位操作來完成，大大的降低了模式匹配占用的存儲空間利用比特并行方法實現(xiàn)的自動機可以進一步提高匹配速度并且減少存儲空間考慮到構(gòu)造Glushkov自動機的時間較快，本文以基于比特并行的Glushkov自動機作為研究對象，目的是縮小自動機占用的存儲空間狀態(tài)轉(zhuǎn)移表T表是Glushkov自動機的重要組成部分，也是占用存儲空間最多的數(shù)據(jù)表本文在原有的比特并行算法的基礎(chǔ)上，提出了壓縮T表空間兩種方法：一種是通過構(gòu)造移位函數(shù)和數(shù)組對T表的所有表項進行移位和壓縮處理，來減少T表所占用的存儲空間這種方法實現(xiàn)簡單，但在處理表項時還是會造成存儲空間的浪費另一種是使用MPHFξ最小完美哈希函數(shù)ο對T表中的表項進行優(yōu)化，最小完美哈希函數(shù)是基于無向圖實現(xiàn)的，本文中使用了比其他的完美哈希算法更快的RAM算法通過實驗發(fā)現(xiàn)T表的存儲空間要比實際占用的存儲空間縮小2到3倍左右，而且完美哈希函數(shù)的方法占據(jù)的存儲空間更小雖然完美哈希函數(shù)提供了完美的集合一對一映射方法，但實現(xiàn)的過程相對復(fù)雜當處理海量字符串生成對應(yīng)的哈希值問題時，我們的目標是使用盡可能簡單的算法，花費更短的處理時間，同時希望生成的哈希值是盡可能無重復(fù)的隨著計算機圖形處理器的更新?lián)Q代，基于GPU并行計算使得大規(guī)模數(shù)據(jù)的高速處理變得游刃有余，同時NVDIA公司提供的CUDA平臺也降低了并行計算編程的復(fù)雜性本文選取了八種高效哈希算法，在CUDA平臺上實現(xiàn)了這八種算法通過算法在CPU和GPU的執(zhí)行時間分析，我們發(fā)現(xiàn)基于多線程的GPU編程模型可以加速這八種哈希算法的執(zhí)行過程，同時GPU的高計算能力也極大程度上縮短了這八種哈希算法的處理時間
【關(guān)鍵詞】：確定狀態(tài)自動機 完美哈希函數(shù) 存儲空間 壓縮算法
【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：TP393.08
【目錄】：

• 摘要4-6
• Abstract6-11
• 第1章 緒論11-12
• 1.1 引言11
• 1.2 兩種構(gòu)造方法比較11
• 1.3 本文工作11
• 1.4 組織結(jié)構(gòu)11-12
• 第2章 研究背景12-22
• 2.1 正則表達式12-14
• 2.1.1 使用正則表達式描述模式集合12-13
• 2.1.2 正則表達式的定義13-14
• 2.2 正則表達式對應(yīng)的 NFA14-16
• 2.3 構(gòu)造模擬 NFA16-17
• 2.4 Thompson 自動機17-19
• 2.5 確定有限狀態(tài)自動機19-20
• 2.6 經(jīng)典自動機構(gòu)造時間對比實驗20-22
• 第3章 完美哈希函數(shù)22-35
• 3.1 最小完美哈希函數(shù)22
• 3.2 RAM 算法22-28
• 3.2.1 RAM 算法的基本組成23-24
• 3.2.2 RAM 算法的詳細步驟24-28
• 3.2.2.1 RAM 算法過程的說明24-25
• 3.2.2.2 RAM 算法的構(gòu)造過程25-28
• 3.3 確立哈希函數(shù)集合28-35
• 3.3.1 利用無相圖的算法29-31
• 3.3.2 算法時間復(fù)雜度的分析31-32
• 3.3.3 算法實例32-34
• 3.3.4 RAM 算法實驗34-35
• 第4章 Glushkov 自動機存儲空間的優(yōu)化方法35-42
• 4.1 Glushkov 自動機簡介35-36
• 4.2 Glushkov 自動機的比特并行方法36-37
• 4.3 壓縮Td 表空間方法37-40
• 4.3.1 利用移位和數(shù)組實現(xiàn)空間壓縮38-39
• 4.3.2 通過二維數(shù)組查找數(shù)據(jù)39
• 4.3.3 使用完美哈希函數(shù)優(yōu)化存儲空間39-40
• 4.4 實驗結(jié)果40-42
• 第5章 GPU 對哈希函數(shù)計算的研究42-51
• 5.1 圖像處理器簡介42-43
• 5.2 CUDA 平臺介紹43-44
• 5.3 CUDA 特性44-46
• 5.4 處理字符串的高效哈希算法46-49
• 5.5 CPU 和 GPU 實現(xiàn)哈希算法的對比實驗49-51
• 第6章 結(jié)論與下一步工作51-52
• 參考文獻52-55
• 作者簡介及在學(xué)期間所取得的科研成果55-56
• 致謝56

【共引文獻】

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

1 呂匯新;一個基于模式匹配入侵檢測技術(shù)的防信息泄露系統(tǒng)的設(shè)計與實現(xiàn)[J];哈爾濱師范大學(xué)自然科學(xué)學(xué)報;2004年03期

2 何畏;汪榮貴;查全民;;一種新的快速移動單模式匹配算法[J];合肥工業(yè)大學(xué)學(xué)報(自然科學(xué)版);2010年05期

3 徐克付;齊德昱;鄭偉平;錢正平;;一種基于Bloom Filter的正則表達式集合快速搜索算法[J];華南理工大學(xué)學(xué)報(自然科學(xué)版);2009年04期

4 錢立進,吳澤俊,董紅斌;基于Horspool算法的模糊匹配[J];計算機工程;2004年01期

5 向永紅,李u&,袁勇,林毓材,趙景秀;串的最大匹配算法[J];計算機工程與科學(xué);2003年04期

6 曹京;譚建龍;劉萍;郭莉;;布爾表達式匹配問題研究[J];計算機應(yīng)用研究;2007年09期

7 劉萍,譚建龍;XML內(nèi)容篩選中的快速串匹配算法[J];中文信息學(xué)報;2005年02期

8 朱小棟;高春昌;王恒山;;引入資源即服務(wù)的云計算架構(gòu)及其應(yīng)用[J];上海理工大學(xué)學(xué)報;2013年03期

9 周飛菲;趙雪梅;;基于爬蟲的用戶遷徙網(wǎng)絡(luò)的設(shè)計與實現(xiàn)[J];科技通報;2013年09期

10 楊子江;聶瑞華;;一種快速的單模式匹配算法[J];華南師范大學(xué)學(xué)報(自然科學(xué)版);2013年05期

中國博士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 代六玲;互聯(lián)網(wǎng)內(nèi)容監(jiān)管系統(tǒng)關(guān)鍵技術(shù)的研究[D];南京理工大學(xué);2005年

2 王小鳳;基于內(nèi)容的音樂檢索關(guān)鍵技術(shù)研究[D];西北大學(xué);2008年

3 王潔;基于FPGA的硬件防火墻內(nèi)容過濾技術(shù)研究[D];哈爾濱工業(yè)大學(xué);2009年

4 范洪博;快速精確字符串匹配算法研究[D];哈爾濱工程大學(xué);2011年

5 郭磊;面向高速網(wǎng)絡(luò)管控的多業(yè)務(wù)識別關(guān)鍵技術(shù)研究[D];解放軍信息工程大學(xué);2012年

6 劉瑤;社會網(wǎng)絡(luò)特征分析與社團結(jié)構(gòu)挖掘[D];電子科技大學(xué);2013年

7 李丹;基于流聚類的網(wǎng)絡(luò)業(yè)務(wù)識別關(guān)鍵技術(shù)研究[D];北京郵電大學(xué);2013年

8 李朋;異構(gòu)信息網(wǎng)絡(luò)分析模型及其應(yīng)用研究[D];重慶大學(xué);2013年

9 程輝;網(wǎng)絡(luò)用戶偏好分析及話題趨勢預(yù)測方法研究[D];北京交通大學(xué);2013年

10 楊婧;大型工程項目網(wǎng)絡(luò)化建模及關(guān)鍵節(jié)點分析方法研究[D];國防科學(xué)技術(shù)大學(xué);2012年

本文編號：636396