R·ex / Zeng


音游狗、安全狗、攻城狮、业余设计师、段子手、苦学日语的少年。

从 DFS 的角度看 NFA 正则与优化技巧

前言

今年七月初 CloudFlare 由于一条正则表达式宕机的事情大家应该都听说过了,究其原因,是因为正则表达式匹配时产生了大量的回溯,从而耗尽了 CPU 资源。具体的技术分析网上都有,这儿就不赘述了。

从小到大我都被教育:正则表达式可以高效的匹配字符串,正则会先被转换成 NFA,再被确定化为 DFA(这算法我现在还是能记住的),然后就可以用一个“与输入长度相关的线性时间复杂度”的算法来匹配了。CloudFlare 这件事情让我对正则表达式的效率十分失望,因此我花了一段时间了解了一下正则表达式的引擎,并且学习了如何写出更高效的正则表达式。这些资源网上也都有,这儿也不赘述了。

在了解的过程中,我发现绝大部分语言自带的正则表达式引擎都是 NFA 而不是 DFA,因为它们都支持了 Lookaround 之类的高级特性,回溯也就成了绕不过去的一道坎。“回溯”这个概念,我在当年学习深度优先搜索(DFS)的时候就被多次提及。由于 NFA 的匹配方式看起来跟 DFS 非常像,这两个“回溯”看起来也是一样的,于是我开始尝试从 DFS 的角度来看待 NFA 的正则匹配。

P.S. 本文有两个相似的简写:

  • DFS:Depth First Search(深度优先搜索),一种搜索算法;
  • DFA:Deterministic Finite Automaton(确定有限状态自动机),一种数据结构。

从 DFS 视角看正则匹配

NFA 引擎的匹配方式是:

  1. 将正则引擎“定位”到目标字符串的起始位置;
  2. 正则引擎开始测试正则表达式和文本,依次测试表达式的各个元素,若没有可以匹配的元素则回溯;
  3. 若匹配到一个结果,则“锁定”当前状态,报告匹配成功;
  4. 若未找到匹配,传动装置就会驱动引擎,从文本的下一个字符开始新一轮的尝试(从 2 继续);
  5. 如果从目标字符串的每个字符开始尝试都失败了,就会报告匹配彻底失败。

DFS(递归写法)的一般思路是:

  1. 对于每一个可能的起始状态,使用如下递归算法:

    1. 如果终止条件达成,表明找到了目标,结束搜索(递归出口);
    2. 对于每个符合条件的规则:

      1. 记录必要的信息;
      2. 应用该条规则计算下一状态;
      3. 从计算出的状态开始递归搜索;
      4. 删除刚刚记录的信息(回溯);
  2. 如果没有找到目标,则表示搜索失败。

可以发现,如果做一下适当的顺序调整,这两个算法是可以对上的:

NFADFS
定位到起始位置……若未找到匹配则从下一字符开始对于每个可能的起始状态
测试各个元素对于每个符合条件的规则,应用该条规则计算下一状态,并递归搜索
若没有可以匹配的元素则回溯删除刚刚记录的信息
若匹配到结果则结束如果终止条件达成则结束
若每个字符都失败则彻底失败如果没有找到目标则搜索失败

一个暴力的正则

以一个简单但很暴力的正则为例:.*.*=.*?;,是不是感觉这个正则很眼熟?被你发现了,这就是导致 CloudFlare 宕机的元凶(的修改版本)。我们先将它分割为基本的元素:

.*.*=.*?;

对于 NFA 的正则引擎来说,如果发现了 * 这样的可以匹配“零次或多次”的量词,会优先匹配最长的模式,当失败时才会回退;但如果后面接了 ?(忽略优先量词),则会优先匹配最短的模式。

结合上面的匹配方式,可以写出一段程序,来模拟匹配的过程。程序源代码和运行结果我放到了 这个 Gist 里。代码虽然看起来比较长,但除掉 Log 之类的内容之后,逻辑其实非常简单,仅考虑了上面几个元素的匹配,没有对正则本身的编译过程以及对复杂正则(例如带有括号)的判断。

从输出结果可以看出,大量的时间被用于回溯,当匹配不到的时候更是如此。我们可以粗略的计算一下时间复杂度:去掉几乎不怎么占用时间的 =;,是否贪婪匹配也只是修改了匹配长度的枚举顺序而不影响总体的时间复杂度,因此需要分析的只有 .*.*.* 了。我们把注意力放到相关的代码片段,经过简化之后是这样的:

if match(s, rules, sIndex+1, ruleIndex) {
    return true
}
if match(s, rules, sIndex, ruleIndex+1) {
    return true
}

假设字符串长度为 N,正则表达式中一共有 M 个 .*,那么我们可以整理出一个匹配彻底失败(穷尽了所有可能性)时的递归式:

[math]F(i,j) = \left \{ \begin{matrix} 1 & i=N \text{ or } j=M \text{,} \\ F(i+1, j) + F(i, j+1) & \text{Other.} \end{matrix} \right.[/math]

在试着解递归式之前,先回忆一道递推题:有个 [math]N \times M[/math] 的棋盘,从左上角走到右下角,只能往右或往下走,一共有多少种走法?学过算法的同学估计很快就能想出来 f[i, j] = f[i-1, j] + f[i, j-1] 这个式子,也就是 [math]C_N^M[/math]。刚刚的递归式也是这个答案,因为只要把起点规定在右下角,终点规定到左上角就可以了。当 M = 3 的时候,答案是 [math]\frac{N\times(N-1)\times(N-2)}{6}[/math],也就是说,时间复杂度是输入字符串长度的三次方。

一个惨绝人寰的正则

我们来看一个可以用“惨绝人寰”来形容的正则:(.*)*;,为什么说惨绝人寰呢?分析一下它在最坏情况下(字符串全程没有分号)的时间复杂度就知道了。刚才的程序无法解决括号(分组)的问题,所以我们需要扩展一下 match 函数的逻辑:

  1. 如果发现了括号,就使用括号内的正则继续递归匹配;
  2. 如果匹配成功了,并且发现是在括号内,不直接返回匹配成功,而是将控制权交给括号外的元素继续递归匹配;
  3. 如果外层后续匹配失败了,这个括号的内容也算失败,需要回溯。

在这个例子中,我们假设第一个 () 是括号 1,由于外层的 * 带来的第二个括号是括号 2,第三个括号是括号 3……以此类推,那么:

  1. 我们发现一开始就有一个括号,于是就将控制权交给括号 1 内,使用 .* 来匹配;
  2. 当匹配到字符串最后一位的时候匹配成功,于是将控制权交给括号外的 ()*
  3. 由于已经无法重新执行 .*,因此该元素的匹配成功结束;
  4. 然而下一个元素是 ;,匹配失败,于是回退到括号 1 里面;
  5. 括号 1 回溯到字符串的倒数第二位,再次将控制权交给括号外;
  6. 括号外重新执行 ()*,将控制权交给括号 2 内,执行 .* 的匹配;
  7. 不出意料括号 2 又失败了,于是回溯;
  8. 括号 1 回溯到字符串的倒数第三位,第三次将控制权交给括号外,然后进入括号 2 内匹配;
  9. 括号 2 匹配到字符串的最后一位发现失败,于是回溯到倒数第二位,将控制权交给括号外;
  10. 于是括号 3 从字符串的倒数第一位开始匹配;
  11. 又失败了,直到括号 1 回溯到字符串的起始位置,将控制权交给括号 2;
  12. 经历了许多次尝试之后,引擎宣布匹配彻底失败。

在每次失配的时候,每个括号匹配到的字符数依次是:

N
N-1, 1
N-2, 2
N-2, 1, 1
N-3, 3
N-3, 2, 1
N-3, 1, 1, 1
...
1, 1, 1, ..., 1

这个问题估计也是相当的眼熟了:在一排 N 个球的 N-1 条缝隙中随意插入木板,不允许多个木板在同一个缝隙中,问一共有多少种方案。不管是排列组合还是二进制枚举,最终的答案都是 [math]2^{N-1}[/math],也就是说,这个正则表达式在最坏情况下需要指数级的时间复杂度。大家都是好孩子,就不要写这种惨绝人寰的正则表达式来折磨引擎了。

一个小练习

有个正则表达式可以用来判断一个全是 "1" 的字符串的长度是否是质数,它的其中一部分是 ^(11+?)\1+$,请分析一下这部分的时间复杂度。

  • 提示一:括号后面的 \1 的意思是“匹配左起第一个括号匹配到的内容”;
  • 提示二:这段正则的原理是经典的“试除法”,通过枚举除数来试除;
  • 提示三:最终的答案不是指数级别,而是多项式级别。

从 DFS 视角看正则优化

正则引擎自身的优化

由于写出惨绝人寰的正则的智障开发者到处都是(包括我),所以正则引擎也不会坐以待毙,有一些通用的优化方法可以适当的降低匹配所用的时间。

  1. 如果正则的开头是 ^,引擎会只从字符串开始进行尝试,而不去尝试其它的位置;
  2. 如果正则的结尾是 $ 并且没有 +* 这种可以无限重复的量词,正则引擎会尝试从末尾的倒数若干字符进行尝试,例如 rex(-zeng)?$ 最多匹配 8 个字符,因此引擎会从倒数第八个字符开始尝试;
  3. 如果当前剩余的正则可以成功匹配的最小长度大于字符串的剩余长度,引擎会直接报告本次匹配失败;
  4. 把连续的确定字符当作一个元素,例如 \srex\d 只有三个元素:\srex\d
  5. 特判一些简单量词,例如 .* 可以不用每次尝试匹配,而是直接使用倒序循环,每次用 O(1) 的时间匹配一定长度的字符串,.*? 则可以使用正序循环;
  6. 消除不必要的括号,例如 (?:a+)$ 可以被转换为 a+$[a]+ 可以被转换为 a+

站在 DFS 的角度来看,这几个优化中,1、2 属于减少搜索的初始状态,3 属于利用矛盾来提前剪枝,4 和 5 则是减少递归层数,6 则是一点常数优化。

毕竟通用的优化方法能做的比较有限,所以开发者还是要从自身做起,多对正则本身进行优化。

使用更精确的元素和量词

这是最基本的优化技巧了,毕竟 .\d 相比,后者只有十种情况能匹配,前者可能需要浪费非常多的尝试次数;\d+\d\d\d\d?\d{3,4} 三者相比,第一个可能递归无限层并且随时会有回溯,第二个需要递归四层(外加一层回溯),最后一个则只需要递归和回溯一层。

站在 DFS 的角度来看,这属于针对某一节点的剪枝。

占有优先量词和固化分组

占有优先量词(?+*+++{m,n}+)我觉得是一个很好用的东西,只可惜 JavaScript 目前还不支持。假设我需要匹配的字符串是一行 YAML,它的 Key 是单个单词,Value 是单个数字,例如 size: 233,那么可以用 \w++:\s?\d++$ 这个正则来匹配。其中的 ++ 非常贪婪,匹配成功之后坚决不会回溯,如果后续匹配失败则只能回溯整个的 \w++ 或者 \d++ 部分。

如果不使用占有优先量词(^\w+:\s?\d+$),那么 \w+ 会先匹配 size,“假设”匹配失败,会回溯到 siz,然后是 si,效率就低了好多。

但是需要注意的一点是,由于占有优先量词不会回溯,所以 \w++a 是不可能匹配任何字符串的,因为即使字符串的最后有个 a,也会被之前的 \w++ 占有,从而导致匹配失败。

固化分组((?>a))的作用跟占有优先量词类似,二者可以互相转换,只可惜 JavaScript 也不支持。

站在 DFS 的角度来看,这两者属于针对某棵子树的剪枝。

优化多选分支

例如这个用来匹配域名的正则 \.(?:com|org|net|cn|me|info)\b,因为更多的域名是 .com 的,引擎在更多的情况下第一次尝试就可以匹配到结果。

DFS 本身很少有类似的优化,但“为每个备选状态计算权重”正是 A* 搜索的核心思想。与其不同的是,这儿的“权重”是人为指定的。

总结

基于 NFA 的正则引擎由于支持了多种高级特性(非贪婪匹配、环视)而使用了回溯,也就造成了与 DFA 引擎相比性能的急剧下降。我们从深度优先搜索(DFS)的角度分析了回溯所需的时间复杂度,以及一些常见的优化方法在 DFS 中代表的技术。

CloudFlare 博客中引用的“线性时间的 NFA 匹配”,看起来感觉就是 NFA 的确定化(DFA 化),但那些高级特性该如何确定化呢?甚至“环视”这个特性我都不确定能否在 DFA 中体现,因为可能会使用到之前输入的字符,这在 DFA 看来是不可能的。


参考文章

版权声明:除文章开头有特殊声明的情况外,所有文章均可在遵从 CC BY 4.0 协议的情况下转载。
下一篇: 没有了

这是我们共同度过的

第 1369 天