第 4 章 · 04 匹配策略:DFA 式 vs 回溯式

第 4 章 · 04 匹配策略:DFA 式 vs 回溯式

本节摘要:正则编译成自动机后,要用它跑文本。这一节讲两条匹配路线:DFA 式(把 NFA 转成 DFA,匹配快但不支持反向引用)与回溯式(深搜 NFA,支持丰富特性但最坏情况慢)。多数生产引擎(PCRE、Python re、grep -P)选回溯式——支持反向引用是关键原因,但代价是「正则灾难」(指数级回溯)。理解这两条路线,你就懂得为什么不同正则引擎表现不同,以及如何避免性能陷阱。

内容来源:基于正则引擎实现整理的导读。

学习目标

阅读完本节,你应当能够:

1. 说清 DFA 式匹配的工作方式:NFA 转成 DFA 后,每读一字符走唯一转移,O(n) 匹配。
2. 说清回溯式匹配:深搜 NFA 的所有可能路径,走不通回退,最坏情况指数级。
3. 解释两者的取舍:DFA 式快但不支持反向引用;回溯式支持丰富特性但有性能陷阱。
4. 理解「正则灾难」(catastrophic backtracking)的产生原因。
5. 说明为什么多数引擎选回溯式(支持反向引用、捕获组等)。

一、学习价值:这是正则引擎的「路线之争」

正则引擎的实现,世界上存在两条主要路线。理解它们的取舍,能让你:

• 选对工具:grep 默认 DFA(快但无反向引用),grep -P 与 Python re 回溯(支持反向引用)。
• 避开性能陷阱:回溯式在某些正则上会指数级爆炸(「ReDoS 攻击」),理解原理才能避开。
• 理解「为什么正则不能匹配配对括号」(下一节讲边界):有限自动机无栈,而回溯虽深搜但能力仍受限于正则语言。

二、子系统拆解:两条路线

路线 A:DFA 式匹配

把 NFA 用「子集构造法」转成 DFA,然后匹配:

1. 子集构造:把「NFA 可能同时处于的多个状态」作为一个 DFA 状态。NFA 的非确定性被「预先算尽」,得到一个 DFA——每状态每输入唯一转移。
2. 匹配:从 DFA 起始状态出发,逐字符读输入,每步走唯一转移,O(n) 读完看在不接受状态。

NFA: 状态可能并行在 {0,1,3}
子集构造: 把 {0,1,3} 作为一个 DFA 状态, 算它读 a 后变成哪个子集
匹配: 纯状态查表, 无回溯, 快
​

优势:匹配快(O(n),与正则复杂度无关)。劣势:子集构造可能指数爆炸;不支持反向引用(\1 引用之前的捕获——DFA 是「无状态地向前跑」,记不住之前匹配了什么)。

路线 B:回溯式匹配

不转 DFA,直接在 NFA 上深搜:

1. 从起始状态出发,选一条转移走。
2. 走到死路(没有匹配的转移)就回退到上一个选择点,试另一条。
3. 用递归或显式栈实现。

NFA 有分叉: 走左边, 卡住, 回溯, 走右边
最坏情况: 每个分叉都试一遍, 指数级
​

优势:支持反向引用(深搜时记住了之前的路径);实现相对直观。劣势:最坏情况指数级——「正则灾难」。

正则灾难(catastrophic backtracking)

某些正则在特定输入上会让回溯式引擎指数级慢。经典例子:(a+)+b 配上 aaaaaaaaaaaaaaaaaaaaaaaa(很多 a 但没 b)。引擎会尝试 a+ 的各种分组方式,组合数指数爆炸。

这是 ReDoS(正则拒绝服务)攻击的原理——恶意输入让正则引擎卡死。理解它,你才能写出安全的正则(避免嵌套量词 (a+)+ 这类模式)。

为什么多数引擎选回溯

尽管回溯有性能陷阱,PCRE、Python re、Java、JavaScript 的正则都用回溯式。关键原因:反向引用(\1)。\1 让你能写「匹配重复单词」((\w+) \1)这类模式,DFA 做不到(它无状态地向前跑,记不住之前的内容)。反向引用让正则超越了「纯正则语言」,但代价是放弃 DFA 的性能保证。

grep 的默认是 DFA(快、用于简单搜索,不需要反向引用);grep -P(Perl 兼容)切回溯(支持反向引用但可能慢)——这个设计差异正源于本节的取舍。

三、上手第一步:实现两种匹配

1. 先实现回溯式(更简单、支持特性多):对 NFA 写递归深搜,带「已访问状态集」防无限循环。
2. 进阶实现 DFA 式(更快但复杂):写子集构造把 NFA 转 DFA,再线性匹配。
3. 对比:同一正则分别用两种引擎跑,观察哪些输入在回溯式上慢。

本节要点回顾

1. DFA 式:NFA 转成 DFA(子集构造),匹配 O(n) 快;但可能状态爆炸,不支持反向引用。
2. 回溯式:NFA 上深搜,走不通回退;支持反向引用等丰富特性,但最坏情况指数级。
3. 正则灾难:嵌套量词((a+)+)配特定输入,回溯指数爆炸,是 ReDoS 攻击原理。
4. 多数生产引擎选回溯:为支持反向引用(超越纯正则语言),代价是放弃 DFA 的性能保证。
5. grep 默认 DFA(快无反向引用),grep -P 切回溯——这个设计差异正是本节取舍的体现。

推荐上手顺序

1. 先实现回溯式匹配(递归深搜 NFA),它能让你引擎跑起来、支持捕获组。
2. 用 (a+)+b 配 aaaa...(无 b)测试,观察回溯爆炸,理解灾难。
3. 进阶:实现子集构造(NFA→DFA),再做 DFA 式匹配,对比速度。
4. 测试反向引用 (\w+) \1,体会为什么回溯式能而 DFA 不能。

下一节讲正则的实现细节——字符类、量词、锚点、分组捕获。