论文部分内容阅读
正则表达式匹配是网络内容分析与过滤系统中的核心关键技术。随着互联网技术的快速发展,新型网络应用和协议不断涌现,待检测数据量急遽增长,检测规则数量庞大且语法日益复杂,这对正则表达式匹配技术在匹配速度和存储空间方面提出了双重挑战。新型并行化硬件发展迅速,但由于传统的正则表达式匹配技术基于串行处理,无法直接利用并行硬件提升正则表达式匹配的性能。本文对正则表达式匹配算法的并行化技术展开研究,具体研究内容包括：DFA构建并行加速技术、DFA并行分解技术和DFA最小化并行加速技术。本文的主要研究成果总结如下：(1)DFA并行构建算法：本文在沿用k-Reduction算法对DFA的组织方法的基础上,研究经典的子集构造法的多线程并行加速技术。本文提出两种DFA并行构建算法：基于并行读写的DFA构建算法PRW通过对状态映射表的加锁和解锁操作,保证公共数据的多线程安全性,该算法的DFA构建速度最快达到k-Reduction算法的1.716倍；基于多线程和单线程循环交替的DFA构建算法SMA从状态映射表读取频率显著高于写入频率这一现象入手,拆分状态映射表的读写权限,该算法的DFA构建速度最快达到k-Reduction算法的2.714倍。(2)DFA并行分解算法：本文从字符集分解的角度出发,提出DFA并行分解算法PDFA,该算法将大字符集上的DFA分解为多个小字符集上的DFA,用小字符集上的DFA模拟原DFA的状态转移。在多核并行加速情况下,PDFA算法的状态转移时间复杂度为O(1)。实验结果显示,PDFA算法能显著压缩绝大多数DFA的存储空间,空间压缩率优于相关DFA空间压缩算法。(3)DFA并行最小化算法：本文针对经典的DFA最小化算法Hopcroft进行多线程并行加速研究,提出基于多线程并行的DFA最小化算法P-Hopcroft,该算法通过划分等价类的分割权限,实现对Hopcroft算法的并行加速。实验结果显示,最优情况下,P-Hopcroft算法的DFA最小化速度为原始Hopcroft算法的2.236倍。