《深入浅出 Hyperscan：高性能正则表达式算法原理与设计》系统、循序渐进地介绍Hyperscan技术。全书共8章，主要介绍正则表达式、匹配算法和正则表达式匹配所依赖的自动机原理、正则表达式匹配库等，并重点介绍Hyperscan的功能特性、设计原理和性能调优技巧，以及匹配引擎的核心算法和SIMD加速技术的运用，还展示了Hyperscan多样化的应用场景。

《深入浅出 Hyperscan：高性能正则表达式算法原理与设计》既适合作为Hyperscan开发者的学习用书，也适合作为高等院校计算机相关专业的师生用书和相关培训学校的教材。

1.由浅入深介绍正则表达式相关知识、Hyperscan算法库功能特性及总体设计原则

2.伪码源码相辅相成，方便读者学习基础算法及实现步骤

3.算法实例搭配图例表格，加深读者对算法的理解

4.理论与实践兼收并重学习Hyperscan与开源产品整合案例分析

王翔，英特尔数据中心网络平台部资深工程师，Hyperscan 项目主要技术负责人。昌昊，英特尔资深软件工程师,负责Hyperscan算法开发和性能调优等相关工作。洪杨，英特尔资深软件工程师,负责 Hyperscan研发。张磊，英特尔网络平台部门软件应用工程师,主要负责DPDK、Hyperscan、QAT等网络加速方案的技术支持。

目　　录

第 1章　正则表达式简介1

1.1　正则表达式的语法1

1.2　正则表达式的流派与标准7

1.2.1 PCRE简介7

1.2.2 POSIX标准8

1.3　本章参考10

第 2章　正则表达式匹配算法11

2.1　纯字符串匹配11

2.1.1 单字符串匹配KMP算法11

2.1.2 单字符串匹配BM算法16

2.1.3 多字符串匹配AC算法21

2.1.4 AC算法与单字符串匹配24

2.1.5 SHIFT-OR算法25

2.2　非确定性有限状态自动机28

2.2.1 定义28

2.2.2 运算优先级29

2.2.3 Thompson构造法31

2.2.4 ε-NFA的简化34

2.2.5 Glushkov构造法36

2.3　确定性有限状态自动机40

2.3.1 定义40

2.3.2 从NFA到DFA40

2.3.3 DFA的状态规模46

2.3.4 DFA的状态小化52

2.4　本章参考55

第3章　正则表达式匹配库56

3.1　PCRE56

3.1.1 语法支持56

3.1.2 设计概述57

3.1.3 基本API和示例代码58

3.2　RE260

3.2.1 语法支持60

3.2.2 设计概述60

3.2.3 基本API和示例代码60

3.3　Hyperscan61

3.3.1 语法支持61

3.3.2 匹配模式62

3.3.3 设计概述63

3.3.4 基本API和示例代码64

3.4　正则表达式匹配库的比较65

3.4.1 概述65

3.4.2 语法支持65

3.4.3 设计原理66

3.4.4 性能68

3.5　本章参考70

第4章　Hyperscan特性71

4.1　Hyperscan的语义71

4.2　编译期和运行期71

4.2.1 编译期72

4.2.2 运行期74

4.3　Hyperscan高级特性77

4.3.1 流状态压缩77

4.3.2 近似匹配78

4.3.3 逻辑组合79

4.3.4 Chimera80

4.4　Hyperscan工具82

4.4.1 hsbench82

4.4.2 hscheck84

4.4.3 hscollider85

4.4.4 hsdump88

第5章　Hyperscan设计原理92

5.1　设计原则92

5.1.1 实用性优先92

5.1.2 情况可用93

5.1.3 流模式支持93

5.1.4 大规模可扩展93

5.1.5 小规模高性能94

5.1.6 性能优先94

5.1.7 平衡开销94

5.1.8 渐进主义95

5.1.9 可测试性设计和自动可测试性设计96

5.2　运行原理96

5.2.1 匹配组件97

5.2.2 匹配原则100

5.2.3 运行期实现103

5.2.4 运行期优化108

5.3　图分解112

5.3.1 支配路径分析114

5.3.2 支配区域分析115

5.3.3 网络流分析116

5.3.4 图分解流程117

5.4　图优化122

5.4.1 节点冗余123

5.4.2 边冗余129

5.5　本章参考132

第6章　Hyperscan引擎133

6.1　SIMD加速133

6.1.1 搜索单字符的加速133

6.1.2 搜索双字符序列的加速134

6.1.3 搜索小规模单字符集的加速136

6.1.4 搜索大规模单字符集的加速140

6.1.5 环视机制143

6.2　纯字符串匹配148

6.2.1 纯字符串匹配在Hyperscan中的作用148

6.2.2 单字符串匹配器“Noodle”148

6.2.3 大规模多字符串匹配器“FDR”150

6.2.4 小规模多字符串匹配器“Teddy”156

6.3　正则引擎160

6.3.1 NFA引擎160

6.3.2 DFA引擎168

6.3.3 重复引擎186

6.3.4 Tamarama197

第7章　Hyperscan性能优化199

7.1　Hyperscan性能测试199

7.1.1 性能测试目的199

7.1.2 基于性能的硬件和GRUB配置199

7.1.3 hsbench测试201

7.2　Hyperscan性能调优技巧205

7.2.1 正则表达式构造206

7.2.2 软件库的使用207

7.2.3 块模式207

7.2.4 数据库分配209

7.2.5 scratch内存分配209

7.2.6 锚定规则211

7.2.7 随处匹配的规则212

7.2.8 流模式下的重复语义213

7.2.9 青睐字符串214

7.2.10 DOTALL标志215

7.2.11 单次匹配标志216

7.2.12 Start of Match标志217

7.2.13 近似匹配218

第8章　Hyperscan实际案例学习221

8.1　Snort221

8.1.1 介绍221

8.1.2 Hyperscan集成222

8.1.3 基于内存的性能测试225

8.2　Suricata229

8.2.1 介绍229

8.2.2 Hyperscan集成229

8.2.3 基于内存的性能测试234

8.3　垃圾邮件检测238

8.4　深度报文检测242

8.4.1 nDPI242

8.4.2 UDPI245

8.5　数据库247

8.5.1 整合概述248

8.5.2 实验结果与分析250

8.6　Web应用防火墙254