網(wǎng)絡(luò)數(shù)據(jù)流的正則表達式匹配技術(shù)研究.pdf

1、正則表達式是一種包含普通字符和通配符的模式串，它具有很靈活的的表達能力，其豐富的語義和強大的表達能力賦予了它對各種特征有效的描述能力，也就是具有這樣的能力使得正則表達式匹配技術(shù)占據(jù)了網(wǎng)絡(luò)內(nèi)容過濾分析系統(tǒng)和網(wǎng)絡(luò)入侵監(jiān)測系統(tǒng)中的核心地位。隨著互聯(lián)網(wǎng)的快速發(fā)展，尤其是移動互聯(lián)網(wǎng)的崛起，新型網(wǎng)絡(luò)應(yīng)用的井噴，網(wǎng)絡(luò)信息量呈指數(shù)級增長，帶來了待檢測數(shù)據(jù)量以及正則表達式的規(guī)則數(shù)目的急增，這對正則表達式匹配技術(shù)的匹配性能提出了巨大的挑戰(zhàn)。國內(nèi)外的研究者目

2、前對正則表達式匹配技術(shù)的研究工作主要集中在將其轉(zhuǎn)化為自動機進行匹配時的匹配效率和空間存儲兩方面。本文選擇正則表達式匹配算法的匹配效率作為研究方向進行了一系列的研究，主要的研究工作可以分為以下的兩個部分：
　　研究了空間高效，時間低效的非確定型自動機（NFA）匹配算法，對基于Glushkov構(gòu)造方法的NFA進行改進，提出了基于激活狀態(tài)過濾的正則表達式匹配算法，通過多加載一個待匹配字符進入自動機從而降低激活狀態(tài)集的大小，減少驗證次數(shù)的

3、方式來提升基于Glushkov NFA的正則表達式匹配算法的匹配效率。
　　研究了正則表達式的結(jié)構(gòu)以及實際互聯(lián)網(wǎng)中目標數(shù)據(jù)的分布情況和基于后綴搜索的字符串匹配算法，提出了基于預(yù)檢的正則表達式匹配算法。因為實際互聯(lián)網(wǎng)數(shù)據(jù)中目標數(shù)據(jù)只占有很少的比例，很多都是不相關(guān)數(shù)據(jù)，原始的正則表達式匹配算法依次對待匹配數(shù)據(jù)全部進行匹配從而降低了匹配的效率。本文提出的算法通過從正則表達式中提取確定字符串，使用具有跳躍特性的基于后綴搜索的字符串匹配算法