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

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

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

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