串匹配算法優(yōu)化技術(shù)研究.pdf

1、串匹配是計(jì)算機(jī)研究領(lǐng)域的一個(gè)經(jīng)典問(wèn)題，是眾多網(wǎng)絡(luò)安全系統(tǒng)中的關(guān)鍵技術(shù)之一。隨著互聯(lián)網(wǎng)的普及和發(fā)展，海量信息的處理和新的應(yīng)用需求對(duì)串匹配技術(shù)提出了新的挑戰(zhàn)。 本文主要對(duì)大規(guī)模精確串匹配技術(shù)和動(dòng)態(tài)串匹配技術(shù)進(jìn)行研究。在大規(guī)模精確串匹配方面，本文分別從壓縮存儲(chǔ)空間和改善數(shù)據(jù)結(jié)構(gòu)局部性這兩方面出發(fā)，提出了基于存儲(chǔ)壓縮的串匹配算法和對(duì)串匹配自動(dòng)機(jī)進(jìn)行內(nèi)存稚局優(yōu)化的策略。在動(dòng)態(tài)串匹配方面，本文對(duì)經(jīng)典的串匹配算法進(jìn)行了擴(kuò)展，提供動(dòng)態(tài)增刪關(guān)鍵詞

2、的能力。 具體來(lái)說(shuō)，本文取得的主要成果如下： 1.串匹配算法性能分析：通過(guò)實(shí)驗(yàn)和理論分析，本文得出串匹配算法的執(zhí)行時(shí)間和二級(jí)cache miss之間的線性關(guān)系，并對(duì)經(jīng)典算法的時(shí)間復(fù)雜度進(jìn)行了分析，提出了從爪縮存儲(chǔ)空間和改善數(shù)據(jù)結(jié)構(gòu)局部性這兩方面來(lái)優(yōu)化串匹配算法的途徑。 2.基于存儲(chǔ)壓縮的串匹配算法：從壓縮存儲(chǔ)空間以改善cache命中率的思想出發(fā)，本文提出了一種對(duì)經(jīng)典SBOM算法進(jìn)行空間壓縮的策略，并從理論上證明了

3、該方法具有線性的空間復(fù)雜度。這種改進(jìn)策略有效地壓縮了自動(dòng)機(jī)的存儲(chǔ)空間，大幅度地提高了算法的匹配速度。 3.串匹配算法的內(nèi)存布局優(yōu)化：從改善數(shù)據(jù)結(jié)構(gòu)局部性的思想出發(fā)，本文 對(duì)內(nèi)存布局優(yōu)化問(wèn)題進(jìn)行了形式化和建模，并提出了利用線性規(guī)劃方法進(jìn) 行求解的策略。該方法在理論和實(shí)際中都具有一定的指導(dǎo)意義。 4.經(jīng)典算法在動(dòng)態(tài)匹配上的擴(kuò)展：本文對(duì)經(jīng)典的串匹配算法進(jìn)行了擴(kuò)展， 動(dòng)態(tài)地維護(hù)和更新已經(jīng)建立的數(shù)據(jù)結(jié)構(gòu)，提供增加和刪除關(guān)鍵詞