| 摘要 | 第5-9页 |
| Abstract | 第9-12页 |
| 第一章 绪论 | 第17-31页 |
| 1.1 研究背景及意义 | 第17-22页 |
| 1.1.1 研究构造正则表达式的有限自动机的重要意义 | 第17-18页 |
| 1.1.2 计算机内一切都是字符串 | 第18-19页 |
| 1.1.3 理论计算科学研究的核心问题领域 | 第19-20页 |
| 1.1.4 本文的研究内容及意义 | 第20-22页 |
| 1.2 国内外研究现状 | 第22-27页 |
| 1.2.1 研究现状概述 | 第22-23页 |
| 1.2.2 有限自动机构造理论研究综述 | 第23-24页 |
| 1.2.3 DFA引擎及其空间膨胀问题的研究现状 | 第24-25页 |
| 1.2.4 基于FPGA的硬件正则引擎研究现状 | 第25-27页 |
| 1.3 本文的主要工作及内容安排 | 第27-31页 |
| 第二章 基础理论及基本概念 | 第31-55页 |
| 2.1 计算理论 | 第31-32页 |
| 2.2 形式语言与自动机理论 | 第32-40页 |
| 2.2.1 几个基本的概念 | 第32-34页 |
| 2.2.2 形式语言与自动机之间等价对应关系 | 第34-36页 |
| 2.2.3 语言与判定性问题 | 第36-37页 |
| 2.2.4 基于机器的语言类层次 | 第37-39页 |
| 2.2.5 语言判定性问题的计算复杂性 | 第39-40页 |
| 2.3 正则语言及其表示工具 | 第40-43页 |
| 2.3.1 正则文法 | 第40-41页 |
| 2.3.2 正则表达式 | 第41-42页 |
| 2.3.3 有限状态自动机 | 第42-43页 |
| 2.4 正则语言的基本性质与可判定性 | 第43-45页 |
| 2.4.1 正则集的泵浦引理 | 第44页 |
| 2.4.2 正则集的封闭性原理 | 第44-45页 |
| 2.4.3 正则集上的可判定性定理 | 第45页 |
| 2.5 基于正则表达式的模式匹配 | 第45-48页 |
| 2.5.1 字符串匹配概述 | 第46-47页 |
| 2.5.2 基于正则表达式的柔性多模式匹配技术 | 第47页 |
| 2.5.3 模式匹配技术在网络安全领域的应用概述 | 第47-48页 |
| 2.6 四类经典自动机构造算法原理及规模 | 第48-54页 |
| 2.6.1 Thompson自动机构造法则 | 第48-49页 |
| 2.6.2 Position自动机构造理论 | 第49-51页 |
| 2.6.3 Follow Automata构造理论 | 第51-52页 |
| 2.6.4 Partial Derivative Automata构造理论 | 第52-54页 |
| 2.7 本章小结 | 第54-55页 |
| 第三章 PFA理论及其计算复杂性 | 第55-81页 |
| 3.1 PFA的概念及其性质 | 第55-60页 |
| 3.1.1 PFA理论及特征简述 | 第55-56页 |
| 3.1.2 PFA相关的基本概念和定义 | 第56-58页 |
| 3.1.3 PFA及其所接受的正则语言集的特征性质和可判定性 | 第58-60页 |
| 3.2 PFA理论的完备性及其规模压缩有效性 | 第60-65页 |
| 3.2.1 连接运算规模最小性定理 | 第60-62页 |
| 3.2.2 连接运算恒等元定理 | 第62页 |
| 3.2.3 扩展的或运算幂等律 | 第62-63页 |
| 3.2.4 闭包连接组合运算的吸收律 | 第63-65页 |
| 3.3 PFA构造方法 | 第65-74页 |
| 3.3.1 几个操作的定义 | 第65页 |
| 3.3.2 将中缀式等价变换为后缀式 | 第65-67页 |
| 3.3.3 构造后缀正则表达式的解析树 | 第67-70页 |
| 3.3.4 编码解析树获取NFA的状态空间 | 第70-72页 |
| 3.3.5 遍历编码解析树构造NFA | 第72-74页 |
| 3.4 PFA构造理论正确性及算法复杂性分析 | 第74-76页 |
| 3.4.1 正确性证明 | 第74页 |
| 3.4.2 PFA规模压缩效果 | 第74-75页 |
| 3.4.3 PFA算法复杂性分析 | 第75-76页 |
| 3.5 PFA与四类经典方法的算法复杂性及规模压缩对比分析 | 第76-79页 |
| 3.5.1 Thompson NFA的算法复杂性及规模 | 第76-77页 |
| 3.5.2 Position Automata的算法复杂性及规模 | 第77页 |
| 3.5.3 Follow Automata的计算复杂性和规模 | 第77页 |
| 3.5.4 Partial Derivative Automata的计算复杂性和规模 | 第77页 |
| 3.5.5 PFA的计算复杂性和规模 | 第77-79页 |
| 3.6 本章小结 | 第79-81页 |
| 第四章 PFA正则引擎构造及模拟 | 第81-107页 |
| 4.1 正则引擎及其效率 | 第81-85页 |
| 4.1.1 正则引擎效率低下问题概述 | 第81-82页 |
| 4.1.2 各类正则引擎匹配机制及特点 | 第82-85页 |
| 4.2 三类正则引擎优缺点对比分析 | 第85-87页 |
| 4.2.1 DFA模拟优缺点分析 | 第85页 |
| 4.2.2 NFA模拟优缺点分析 | 第85-87页 |
| 4.2.3 NFA/DFA混合方式 | 第87页 |
| 4.3 两种最常用的NFA正则引擎构造法 | 第87-95页 |
| 4.3.1 Thompson构造法和Glushkov构造法 | 第87页 |
| 4.3.2 Thompson自动机构造及其匹配引擎分析 | 第87-90页 |
| 4.3.3 Glushkov自动机构造及其匹配引擎分析 | 第90-95页 |
| 4.4 PFA引擎构造及模拟算法 | 第95-102页 |
| 4.4.1 预处理算法 | 第95-97页 |
| 4.4.2 构造正则解析树 | 第97-99页 |
| 4.4.3 编码正则解析树获得正则编码树 | 第99-100页 |
| 4.4.4 依据正则编码树构造NFA | 第100-102页 |
| 4.5 PFA自动机计算复杂性及性质分析 | 第102-104页 |
| 4.5.1 PFA计算复杂性分析 | 第102页 |
| 4.5.2 PFA自动机性质分析 | 第102-103页 |
| 4.5.3 PFA与Thompson和Glushkov自动机的综合对比分析 | 第103-104页 |
| 4.6 模拟PFA | 第104-105页 |
| 4.6.1 PFA Simulator算法描述伪代码 | 第104-105页 |
| 4.6.2 PFA Simulator算法复杂性分析 | 第105页 |
| 4.7 本章小结 | 第105-107页 |
| 第五章 优化的NFA/DFA混合引擎构造方法 | 第107-125页 |
| 5.1 更小NFA片段的GREC构造算法 | 第107-112页 |
| 5.1.1 GREC构造法的基本思想 | 第107-110页 |
| 5.1.2 GREC算法的构造规则 | 第110页 |
| 5.1.3 GREC算法描述 | 第110-111页 |
| 5.1.4 一个典型的实例 | 第111-112页 |
| 5.2 GREC算法的正确性及有效性分析 | 第112-114页 |
| 5.2.1 正确性证明 | 第112-113页 |
| 5.2.2 有效性分析 | 第113-114页 |
| 5.3 NFA确定化与最小化问题 | 第114-115页 |
| 5.4 NFA确定化算法的优化 | 第115-118页 |
| 5.4.1 子集法的原理及构造过程 | 第115-116页 |
| 5.4.2 子集法算法中的重复遍历现象分析 | 第116-118页 |
| 5.5 一种改进的子集法算法 | 第118-123页 |
| 5.5.1 优化改进的基本思想 | 第118页 |
| 5.5.2 MF-SUBSET中的运算定义 | 第118-119页 |
| 5.5.3 MF-SUBSET算法描述 | 第119-122页 |
| 5.5.4 MF-SUBSET算法的正确性及有效性分析 | 第122-123页 |
| 5.6 本章小结 | 第123-125页 |
| 第六章 FPGA正则引擎设计与仿真 | 第125-143页 |
| 6.1 纯正则表达式与扩展正则表达式 | 第125-126页 |
| 6.2 硬件正则引擎研究概述 | 第126-127页 |
| 6.3 PFA在FPGA上的模块设计 | 第127-141页 |
| 6.3.1 设计思想 | 第127页 |
| 6.3.2 扩展正则表达式语法 | 第127-128页 |
| 6.3.3 通用子模块的设计 | 第128-136页 |
| 6.3.4 仿真及性能分析 | 第136-141页 |
| 6.4 本章小结 | 第141-143页 |
| 第七章 结论与展望 | 第143-147页 |
| 参考文献 | 第147-156页 |
| 致谢 | 第156-157页 |
| 作者攻读博士学位期间发表的学术论文 | 第157-158页 |
| 作者攻读博士学位期间获得专利情况 | 第158页 |
