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

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

【摘要】：隨著互聯(lián)網(wǎng)時(shí)代的到來(lái)，計(jì)算機(jī)網(wǎng)絡(luò)已經(jīng)成為人們不可或缺的重要部分但網(wǎng)絡(luò)中的安全問(wèn)題也日趨嚴(yán)重；網(wǎng)絡(luò)攻擊，網(wǎng)絡(luò)欺騙，以及盜用用戶賬號(hào)密碼的手段層出不窮通常情況下，所有的惡意代碼都被封裝到網(wǎng)絡(luò)數(shù)據(jù)包當(dāng)中這樣計(jì)算機(jī)安全領(lǐng)域的重要問(wèn)題就變成了如何高效的找出數(shù)據(jù)包中惡意代碼所以基于模糊查詢的正則表達(dá)式應(yīng)運(yùn)而生，它通過(guò)自身的句法規(guī)則來(lái)描述特定字符串來(lái)提供數(shù)據(jù)集合中的查找結(jié)果，并且在模式匹配領(lǐng)域占據(jù)了極其重要地位，經(jīng)久不衰在基于文本的編輯器和搜索工具中，正則表達(dá)式的出現(xiàn)也使得數(shù)據(jù)處理變得更方便更高效正則表達(dá)式的匹配過(guò)程是由確定狀態(tài)自動(dòng)機(jī)ξDFAο和非確定狀態(tài)自動(dòng)機(jī)ξNFAο來(lái)完成的經(jīng)典的正則表達(dá)式自動(dòng)機(jī)是Thompson自動(dòng)機(jī)和Glushkov自動(dòng)機(jī)，，但是經(jīng)典自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)移需要占用大量的存儲(chǔ)空間，并且狀態(tài)轉(zhuǎn)移的過(guò)程十分復(fù)雜，導(dǎo)致最終得到的實(shí)驗(yàn)結(jié)果在時(shí)間復(fù)雜度和空間復(fù)雜度方面并不盡如人意近年來(lái)提出的基于比特并行的模式匹配方法使得模式匹配可以通過(guò)比特向量和位操作來(lái)完成，大大的降低了模式匹配占用的存儲(chǔ)空間利用比特并行方法實(shí)現(xiàn)的自動(dòng)機(jī)可以進(jìn)一步提高匹配速度并且減少存儲(chǔ)空間考慮到構(gòu)造Glushkov自動(dòng)機(jī)的時(shí)間較快，本文以基于比特并行的Glushkov自動(dòng)機(jī)作為研究對(duì)象，目的是縮小自動(dòng)機(jī)占用的存儲(chǔ)空間狀態(tài)轉(zhuǎn)移表T表是Glushkov自動(dòng)機(jī)的重要組成部分，也是占用存儲(chǔ)空間最多的數(shù)據(jù)表本文在原有的比特并行算法的基礎(chǔ)上，提出了壓縮T表空間兩種方法：一種是通過(guò)構(gòu)造移位函數(shù)和數(shù)組對(duì)T表的所有表項(xiàng)進(jìn)行移位和壓縮處理，來(lái)減少T表所占用的存儲(chǔ)空間這種方法實(shí)現(xiàn)簡(jiǎn)單，但在處理表項(xiàng)時(shí)還是會(huì)造成存儲(chǔ)空間的浪費(fèi)另一種是使用MPHFξ最小完美哈希函數(shù)ο對(duì)T表中的表項(xiàng)進(jìn)行優(yōu)化，最小完美哈希函數(shù)是基于無(wú)向圖實(shí)現(xiàn)的，本文中使用了比其他的完美哈希算法更快的RAM算法通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)T表的存儲(chǔ)空間要比實(shí)際占用的存儲(chǔ)空間縮小2到3倍左右，而且完美哈希函數(shù)的方法占據(jù)的存儲(chǔ)空間更小雖然完美哈希函數(shù)提供了完美的集合一對(duì)一映射方法，但實(shí)現(xiàn)的過(guò)程相對(duì)復(fù)雜當(dāng)處理海量字符串生成對(duì)應(yīng)的哈希值問(wèn)題時(shí)，我們的目標(biāo)是使用盡可能簡(jiǎn)單的算法，花費(fèi)更短的處理時(shí)間，同時(shí)希望生成的哈希值是盡可能無(wú)重復(fù)的隨著計(jì)算機(jī)圖形處理器的更新?lián)Q代，基于GPU并行計(jì)算使得大規(guī)模數(shù)據(jù)的高速處理變得游刃有余，同時(shí)NVDIA公司提供的CUDA平臺(tái)也降低了并行計(jì)算編程的復(fù)雜性本文選取了八種高效哈希算法，在CUDA平臺(tái)上實(shí)現(xiàn)了這八種算法通過(guò)算法在CPU和GPU的執(zhí)行時(shí)間分析，我們發(fā)現(xiàn)基于多線程的GPU編程模型可以加速這八種哈希算法的執(zhí)行過(guò)程，同時(shí)GPU的高計(jì)算能力也極大程度上縮短了這八種哈希算法的處理時(shí)間
【關(guān)鍵詞】：確定狀態(tài)自動(dòng)機(jī) 完美哈希函數(shù) 存儲(chǔ)空間 壓縮算法
【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：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 正則表達(dá)式12-14
• 2.1.1 使用正則表達(dá)式描述模式集合12-13
• 2.1.2 正則表達(dá)式的定義13-14
• 2.2 正則表達(dá)式對(duì)應(yīng)的 NFA14-16
• 2.3 構(gòu)造模擬 NFA16-17
• 2.4 Thompson 自動(dòng)機(jī)17-19
• 2.5 確定有限狀態(tài)自動(dòng)機(jī)19-20
• 2.6 經(jīng)典自動(dòng)機(jī)構(gòu)造時(shí)間對(duì)比實(shí)驗(yàn)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 算法的詳細(xì)步驟24-28
• 3.2.2.1 RAM 算法過(guò)程的說(shuō)明24-25
• 3.2.2.2 RAM 算法的構(gòu)造過(guò)程25-28
• 3.3 確立哈希函數(shù)集合28-35
• 3.3.1 利用無(wú)相圖的算法29-31
• 3.3.2 算法時(shí)間復(fù)雜度的分析31-32
• 3.3.3 算法實(shí)例32-34
• 3.3.4 RAM 算法實(shí)驗(yàn)34-35
• 第4章 Glushkov 自動(dòng)機(jī)存儲(chǔ)空間的優(yōu)化方法35-42
• 4.1 Glushkov 自動(dòng)機(jī)簡(jiǎn)介35-36
• 4.2 Glushkov 自動(dòng)機(jī)的比特并行方法36-37
• 4.3 壓縮Td 表空間方法37-40
• 4.3.1 利用移位和數(shù)組實(shí)現(xiàn)空間壓縮38-39
• 4.3.2 通過(guò)二維數(shù)組查找數(shù)據(jù)39
• 4.3.3 使用完美哈希函數(shù)優(yōu)化存儲(chǔ)空間39-40
• 4.4 實(shí)驗(yàn)結(jié)果40-42
• 第5章 GPU 對(duì)哈希函數(shù)計(jì)算的研究42-51
• 5.1 圖像處理器簡(jiǎn)介42-43
• 5.2 CUDA 平臺(tái)介紹43-44
• 5.3 CUDA 特性44-46
• 5.4 處理字符串的高效哈希算法46-49
• 5.5 CPU 和 GPU 實(shí)現(xiàn)哈希算法的對(duì)比實(shí)驗(yàn)49-51
• 第6章 結(jié)論與下一步工作51-52
• 參考文獻(xiàn)52-55
• 作者簡(jiǎn)介及在學(xué)期間所取得的科研成果55-56
• 致謝56

【共引文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本文編號(hào)：636396