正则表达式匹配算法并行化技术研究
发布时间：2024-03-17 13:29
正则表达式匹配是网络内容分析与过滤系统中的核心关键技术。随着互联网技术的快速发展,新型网络应用和协议不断涌现,待检测数据量急遽增长,检测规则数量庞大且语法日益复杂,这对正则表达式匹配技术在匹配速度和存储空间方面提出了双重挑战。新型并行化硬件发展迅速,但由于传统的正则表达式匹配技术基于串行处理,无法直接利用并行硬件提升正则表达式匹配的性能。 本文对正则表达式匹配算法的并行化技术展开研究,具体研究内容包括：DFA构建并行加速技术、DFA并行分解技术和DFA最小化并行加速技术。本文的主要研究成果总结如下： (1)DFA并行构建算法：本文在沿用k-Reduction算法对DFA的组织方法的基础上,研究经典的子集构造法的多线程并行加速技术。本文提出两种DFA并行构建算法：基于并行读写的DFA构建算法PRW通过对状态映射表的加锁和解锁操作,保证公共数据的多线程安全性,该算法的DFA构建速度最快达到k-Reduction算法的1.716倍；基于多线程和单线程循环交替的DFA构建算法SMA从状态映射表读取频率显著高于写入频率这一现象入手,拆分状态映射表的读写权限,该算法的DFA构建速度最快达到k-Re...
【文章页数】：80 页
【学位级别】：硕士
【文章目录】：
摘要
ABSTRACT
第一章 引言
1.1 研究背景与意义
1.2 研究内容
1.3 论文的组织结构
第二章 正则表达式匹配技术综述
2.1 正则表达式的基本概念
2.2 经典的正则表达式匹配方法
2.2.1 正则表达式匹配的一般流程
2.2.2 NFA和DFA的基本概念与比较
2.3 基于确定型有限状态自动机的正则表达式匹配的研究现状
2.3.1 DFA的空间压缩技术
2.3.2 DFA构建加速技术
2.3.3 DFA最小化及其并行技术
2.3.4 基于硬件加速的匹配技术
2.4 本章小结
第三章 DFA构建的并行加速技术
3.1 问题的提出
3.2 经典的DFA构建算法：子集构造法
3.3 基于多线程并行读写的DFA并行构建算法：PRW
3.3.1 PRW算法的基本思想
3.3.2 PRW算法的设计与实现
3.4 基于单线程和多线程循环交替的DFA并行构建算法：SMA
3.4.1 SMA算法的基本思想
3.4.2 SMA算法的设计与实现
3.5 实验评估
3.5.1 实验环境与实验数据
3.5.2 PRW算法与k-Reduction算法的比较
3.5.3 线程数量对PRW算法的影响
3.5.4 SMA算法与k-Reduction算法的比较
3.5.5 线程数量对SMA算法的影响
3.5.6 切换阈值对SMA算法的影响
3.6 本章小结
第四章 DFA并行分解技术
4.1 问题的提出
4.2 基于字符集分解的DFA并行分解算法PDFA
4.2.1 PDFA算法的基本思想
4.2.2 PDFA算法的形式化定义与正确性证明
4.2.3 PDFA算法的整体流程
4.2.4 PDFA算法的预处理阶段
4.2.5 PDFA算法的过滤与校验阶段
4.2.6 PDFA算法对状态转移表大小的影响
4.3 实验评估
4.3.1 实验环境与实验数据
4.3.2 实验一：PDFA算法的空间压缩效果
4.3.3 实验二：PDFA算法的压缩效果与相关压缩算法的比较
4.3.4 实验三：PDFA算法的过滤效果
4.3.5 实验四：PDFA算法的匹配用时
4.4 本章小结
第五章 DFA最小化的并行加速技术
5.1 问题的提出
5.2 经典的DFA最小化算法Hopcroft
5.3 基于多线程并行的DFA最小化算法P-Hopcroft
5.3.1 P-Hopcroft算法的基本思想
5.3.2 P-Hopcroft算法的设计与实现
5.4 实验评估
5.4.1 实验环境与实验数据
5.4.2 实验一：P-Hopcroft算法与原始Hopcroft算法的比较
5.4.3 8实验二：线程数量对P-Hopcroft算法性能的影响
5.5 本章小结
第六章 总结与展望
6.1 本文工作总结
6.2 下一步的研究工作
参考文献
致谢
攻读学位期间发表或已录用的学术论文
本文编号：3931099
【文章页数】：80 页
【学位级别】：硕士
【文章目录】：
摘要
ABSTRACT
第一章 引言
1.1 研究背景与意义
1.2 研究内容
1.3 论文的组织结构
第二章 正则表达式匹配技术综述
2.1 正则表达式的基本概念
2.2 经典的正则表达式匹配方法
2.2.1 正则表达式匹配的一般流程
2.2.2 NFA和DFA的基本概念与比较
2.3 基于确定型有限状态自动机的正则表达式匹配的研究现状
2.3.1 DFA的空间压缩技术
2.3.2 DFA构建加速技术
2.3.3 DFA最小化及其并行技术
2.3.4 基于硬件加速的匹配技术
2.4 本章小结
第三章 DFA构建的并行加速技术
3.1 问题的提出
3.2 经典的DFA构建算法：子集构造法
3.3 基于多线程并行读写的DFA并行构建算法：PRW
3.3.1 PRW算法的基本思想
3.3.2 PRW算法的设计与实现
3.4 基于单线程和多线程循环交替的DFA并行构建算法：SMA
3.4.1 SMA算法的基本思想
3.4.2 SMA算法的设计与实现
3.5 实验评估
3.5.1 实验环境与实验数据
3.5.2 PRW算法与k-Reduction算法的比较
3.5.3 线程数量对PRW算法的影响
3.5.4 SMA算法与k-Reduction算法的比较
3.5.5 线程数量对SMA算法的影响
3.5.6 切换阈值对SMA算法的影响
3.6 本章小结
第四章 DFA并行分解技术
4.1 问题的提出
4.2 基于字符集分解的DFA并行分解算法PDFA
4.2.1 PDFA算法的基本思想
4.2.2 PDFA算法的形式化定义与正确性证明
4.2.3 PDFA算法的整体流程
4.2.4 PDFA算法的预处理阶段
4.2.5 PDFA算法的过滤与校验阶段
4.2.6 PDFA算法对状态转移表大小的影响
4.3 实验评估
4.3.1 实验环境与实验数据
4.3.2 实验一：PDFA算法的空间压缩效果
4.3.3 实验二：PDFA算法的压缩效果与相关压缩算法的比较
4.3.4 实验三：PDFA算法的过滤效果
4.3.5 实验四：PDFA算法的匹配用时
4.4 本章小结
第五章 DFA最小化的并行加速技术
5.1 问题的提出
5.2 经典的DFA最小化算法Hopcroft
5.3 基于多线程并行的DFA最小化算法P-Hopcroft
5.3.1 P-Hopcroft算法的基本思想
5.3.2 P-Hopcroft算法的设计与实现
5.4 实验评估
5.4.1 实验环境与实验数据
5.4.2 实验一：P-Hopcroft算法与原始Hopcroft算法的比较
5.4.3 8实验二：线程数量对P-Hopcroft算法性能的影响
5.5 本章小结
第六章 总结与展望
6.1 本文工作总结
6.2 下一步的研究工作
参考文献
致谢
攻读学位期间发表或已录用的学术论文
本文编号：3931099
本文链接：https://www.wllwen.com/kejilunwen/jisuanjikexuelunwen/3931099.html
