正则表达式的优化全面详解( 三江小渡)

就像之前写的mysql全面优化详解一样，就是因为这样工具应用十分广泛，所以对这样的工具全面的进行优化策略总结是非常划算的，因为无论你是PHP、Perl、Python、C++、C#、Java等等语言的程序员，你都是有非常大可能用上Mysql、正则表达式这样的工具的。

先说一下你可能不知道的一点关于正则表达式的知识，这对我们将来的优化是有用的。
大家常见的grep（global regular expression print）算是现在的正则的起源吧（从神经学家提出正则概念到数学家建立模型到被IBM用都没有大规模使用，到最终成为grep独立工具才被更多使用）。现在大家用的正则被POSIX（portable operating system interface）分为两个流派：BREs（base regular expressions）和EREs（extended regular expressions）。POSIX程序必须支持两者之一。这两者有不同特性需要了解。详细内容请看之前的一片文章shell脚本学习指南[一]中的 “三、常见3中类型正则表达式比较” 部分。

正则的匹配引擎主要可以分为两大类：DFA和NFA。前者确定性有限自动机，后者是非确定性有限自动机。编译原理里边有讲，有兴趣的另行wiki。现在正则引擎又分三类：

1、DFA 引擎在线性时状态下执行，因为它们不要求回溯（并因此它们永远不测试相同的字符两次）。DFA 引擎还可以确保匹配最长的可能的字符串。但是，因为 DFA 引擎只包含有限的状态，所以它不能匹配具有反向引用的模式；并且因为它不构造显示扩展，所以它不可以捕获子表达式。
2、传统的 NFA 引擎运行所谓的“贪婪的”匹配回溯算法，以指定顺序测试正则表达式的所有可能的扩展并接受第一个匹配项。因为传统的 NFA 构造正则表达式的特定扩展以获得成功的匹配，所以它可以捕获子表达式匹配和匹配的反向引用。但是，因为传统的 NFA 回溯，所以它可以访问完全相同的状态多次（如果通过不同的路径到达该状态）。因此，在最坏情况下，它的执行速度可能非常慢。因为传统的 NFA 接受它找到的第一个匹配，所以它还可能会导致其他（可能更长）匹配未被发现。
3、POSIX NFA 引擎与传统的 NFA 引擎类似，不同的一点在于：在它们可以确保已找到了可能的最长的匹配之前，它们将继续回溯。因此，POSIX NFA 引擎的速度慢于传统的 NFA 引擎；并且在使用 POSIX NFA 时，您恐怕不会愿意在更改回溯搜索的顺序的情况下来支持较短的匹配搜索，而非较长的匹配搜索。

根据正则引擎的不同，我们能够总结出两条普适的规则：
1、优先选择最左端的匹配结果。
2、标准的匹配量词(* + ？ {n，m})是优先匹配的。

这里可以先举些优化的简单例子：
比如'.*[0-9][0-9]‘ 来匹配字符串”abcd12efghijklmnopqrstuvw”，这时候的匹配方式是‘.*'先匹配了整行，但是不能满足之后的两个数字的匹配，所以‘.*'就退还一个字符‘w'，还是无法匹配，继续退还一个‘v'，循环退还字符到‘2'发现匹配了一个，但是还是无法匹配两个数字，所以继续退还‘1'。这样的情况我们了解这一特性后是应该尽量避免的。如果我们希望一个字符串里含有两个数字，直接进行两个数字的匹配就好了，就不要写‘.*'这样的通配符了。对优化的学习其实就是对底层实现的学习，因为优化就是尽量顺着工具的实现方式来实现自己想要的效果，如果你不了解所使用工具的底层，你也无法很好的知道什么情况合适用什么工具高效。

由上边对DFA和NFA的介绍，我们知道他们之间的差异，简单来说就是NFA是表达式主导引擎，DFA是文本主导引擎。一般来说：DFA类引擎只会对目标字符串的每个字符匹配一次，但是NFA则会回溯，文本主导的DFA会比表达式主导的NFA快一些。

细心思考的可能会注意到了，如何尽可能的回避NFA的回溯，将会是我们针对正则NFA引擎的优化的一大问题。这中间还有一个是否忽略优先匹配的问题，也是需要优化的一点。关于优先匹配也做一个简单的解释，因为上边说的普适规则里也说到这个点。如果匹配到一个位置，需要做尝试匹配或者跳过匹配这样的选择的时候，对于量词匹配，引擎会优先作出进行尝试行为，而忽略量词优先的时候则进行跳过尝试匹配。举例来说这两点如何工作的和为什么是需要优化的地方：

用ab?c 来匹配 abc，程序流程类似这样：
先匹配a这没问题，再匹配到b的时候，引擎会因为？号考虑要不要匹配b，默认是量词优先的，所以先做匹配尝试，另一种选择放在备选状态。这样就匹配了ab了，然后又成功匹配到了c，这样程序就结束了，备选状态就放弃了。

如果依然用ab?c来匹配ac，程序运行到b的时候会首先尝试匹配b，发现不行，这时候就会回溯，即回到匹配好a了的状态，然后程序继续运行匹配c，然后成功结束。这个过程就进行了回溯，学过算法的这个过程很好理解。就是类似栈的后进先出，这样总能比较方便的回溯的上一个合法的状态。

再来看忽略优先的匹配，如用ab??c 来匹配ac，程序先匹配a，成功然后到b??，这时候会放弃量词优先，跳过b的匹配先匹配c，这样就匹配成功结束，没有了之前的回溯过程。

再看一下不成功的匹配，让ab?x 来匹配abc，你会发现这次程序匹配a，然后尝试b，b成了然后尝试c，c不行回溯到不匹配b的状态尝试匹配x，依然无法匹配。然后回溯，然后移动起始位置从b开始尝试，不成功再尝试从c开始这样最后得出无法匹配的报告。

总的来看，就是你写的正则需要注意尽量避免回溯和确定你的正则什么地方需要回避优先匹配的原则这两点。上边例子非常简单，但是如果避免回溯就能把程序的时间复杂度从 平方级O(n*n)降到线性的O(n)，当然这是理想状态。

*号和+号的回溯类似上述过程，比如x*，就可以看成x?x?x?x?……这样或者(x(x(x…?)?)?)? 这样。试想这样迭代的深入了很多层，突然来一个不能匹配的x，这是需要一层层向前回溯的。还有就是如果匹配.*[0-9]，这样的表达式，首先这个匹配会先匹配.*，这使它能匹配完整的整个字符串，然后再一步步回溯，把退回的字符来匹配是否是数字，其实是可以直接匹配一个数字的。所以上边提到.*这样的通配符，如果非必须，就不要写这样的通配符。

另外DFA是不支持忽略优先的，只支持匹配优先。并且.*这一贪婪特点十分容易忽略，使用不当会得到我们未必需要的结果。比如我们想匹配（.*）括号内的内容，目标串是 abcd(aaaa)efg(ggg)h，根据.*的天性，会从匹配到的第一个（开始一直匹配到行尾，这时候再根据）的需求一个字符一个字符的退还以期能匹配），问题就出现了，最终匹配得到的结果是(aaaa)efg(ggg)，这却不是我们期望的结果。事实上我们需要的正则表达式是([^()]*)。这种错误尤其小心发生在html标签里，像<b>123</b>456<b>789</b>，如果你要匹配替换的话，你会错的很离谱。但是你过你尝试使用类似([^()]*)这样的方法，拜托，请你思考一下问题，你这样会错的更离谱。比如<b>123/b><b</b>, 使用<b>[^</b>]</b>，很明显了，完全无法匹配。你想到办法了吗？只需要放弃匹配优先这一原则就很好实现了，类似这样：<br /><b>.*?</b>，会放弃.*的优先尝试匹配，会先匹配</b>不行的话才让.*吸收掉。或许你已经发现这样做仍然有问题，因为针对 <b>123<b>456</b>,这匹配结果仍然不会是我们所喜欢的，因为匹配回来的是 <b>123<b>456</b> ，而我们期望得到的是<b>456</b>。比较好的解决办法是使用正则里的环视功能，需要了解的另行google。

上边介绍了优先尝试和跳过尝试两种模式，使用得当是有助于正则优化的，还有一种模式是固化分组（?> expression ）。具体说固化分组与正常的匹配没有任何差别，但是expression匹配成功的话，会固化这一结果，放弃任何备选状态。看一个实例：\w+: ，让他尝试匹配helloworld，我们一眼都能看出这是无法匹配的，因为它并不含冒号，为了对比固化匹配，我们还是描述一下这个过程：首先\w会匹配到字符串结束，然后尝试匹配：号，明显的d不能匹配，所以/w需要退回下个字符让：号来匹配，r也不行，最终退到h还是无法匹配然后报告无法匹配这一结果。如果你使用固化分组模式的话(?>\w+):来匹配helloworld的匹配过程：首先会匹配到行尾，然后发现无法匹配冒号，报告匹配不成功。因为我们知道\w是无法匹配符号的，所以如果\w能够匹配的内容，肯定不会是冒号，所以就没必要保留\w产生的备选状态让匹配过程产生回溯，固化分组能很好的消除这些备选状态。你如果想尝试，请确保你的工具是支持正则的固化分组。

还有一种占有量词优先：?+ , *+ , ++ , {m,n}+ 。这种模式匹配，量词会优先匹配，与量词优先匹配不同的是这种模式下的量词匹配的部分不会退回，也就是会移除量词匹配过程中产生的备选模式。

多结构的匹配类似 a|b|c 这样的，传统的NFA都会执行顺序匹配，每一分支都会穷尽所有备选状态。这一有序匹配的特点是能够发掘一点优化方法的，就是让匹配成功可能性大的情况尽量放前边。

上边说了很多，大多多是跟NFA相关的，正则优化的许多工作也就是针对NFA引擎而作的。DFA和NFA在预编译阶段都是把正则表达式转化成各自适合自己算法的规则式，只是DFA需要较多的内存，别且较NFA慢一些，但是正式匹配执行的过程中DFA是快于NFA的，甚至有些时候你正则表达式写的不好，NFA还会陷入无法结束匹配的尴尬境况。但是NFA依然存在依然主流的原因还是它能够提供DFA不能提供的功能的。比如上边刚才提到的种种匹配模式，都是DFA不能提供的。

NFA和DFA并非是不能并存的，有些工具是兼具两种匹配引擎的，来使自身具备DFA的高效和NFA的多功能的。比如GNU的grep和awk，在完成是否匹配的任务的时候使用高效的DFA引擎，完成复杂任务的时候也是尽量使用DFA，如果功能上无法满足需要就切换成NFA引擎。

上边算是比较混乱的介绍了DFA和NFA的正则引擎的一些知识和正则优化的例子。我们也知道了针对DFA引擎的正则式没有太多优化策略的，有的是你在书写正则表达式时的尽可能的准确和尽可能少的匹配尝试。针对NFA引擎的正则表达式我们是有较大优化空间的，但是在这个前边你要区分你所使用的工具是基于传统的NFA还是POSIX NFA。有些问题可能只针对某一引擎存在，对另一种却没太大影响。

避免回溯，更要避免指数级增长的回溯。比如表达式 ([^/]+)*：每次匹配一个字符都要考虑是应该属于+量词还是属于*量词，这样如果匹配一个长度为10的字符串，这样需要回溯1023次，第一次不算回溯，这是2的指数级增长的速度，如果这个字符串增长到20个，就超过了一百万种可能，时常若干秒，如果是30个，就超过十亿中可能，你要跑数小时，如果是字符串长超过40个，那要请你等一年多了。这其实给了我们一种判别自己所使用的工具用的正则引擎的所属：
1、如果某个表达式即便不能匹配，也能给出结果，那么它可能是DFA，只是可能。
2、如果能够匹配才能很快给出结果，那是传统NFA。
3、总是很慢的话，那就是POSIX NFA了。

第一个只是说可能，因为经过高级优化的NFA是能够迅速给出结果的。

再有一个是多选结构的回溯代价很高，比如：a|b|c|d|e|f 和 [a-f] ，字符数组[a-f]只需要做简单的测试，但是该多选结构在匹配时每个位置都将多出6个备选状态以便回溯。

现在很多的正则编译器会进行许多你不知道的优化，但是常识性优化如果你注意到总是好的，因为你用的工具是否对这块进行了优化是不确定的。

1.如果你的正则工具支持，在不需要引用括号内文本的时候使用非捕获型括号：(?:expression) 。
2.如果括号是非必须的，请不要加括号。
3.不要滥用字符数组，比如[.],请直接用\. 。
4.使用锚点^ $ ，这会加速定位。
5.从两次中提取必须元素，如:x+写成xx*，a{2,4}写成aa{0,2}。
6.提取多选结构开头的相同字符，如the|this 改成th(?:e|is)。（如果你的正则引擎不支持这么使用就改成th(e|is)）；尤其是锚点，一定要独立出来，这样很多正则编译器会根据锚点进行特别的优化: ^123|^abc 改成^(?:123|abc)。同样的$也尽量独立出来。
7.多选结构后边的一个表达式放入多选结构内，这样能够在匹配任何一个多选结构的时候在不退出多选结构的状态下查看后一匹配，匹配失败的更快。这种优化需要谨慎使用。
8.忽略优先匹配和优先匹配需要你视情况而定。如果你不确定，请使用匹配优先，它的速度是比忽略优先快的。
9.拆分较大正则表达式成一个个小的正则表达式，这是非常有利于提高效率的。
10.模拟锚点，使用合适的环视结构来预测合适的开始匹配位置，如匹配十二个月份，可以先预查首字符是否匹配：(?=JFMASOND)(?:Jan|Feb|…|Dec)。这种优化请根据实际情况使用，有时候环视结构开销可能更大。
11.很多情况下使用固化分组和占有优先量词能够极大提高速度。
12.避免像(this|that)*这样的几乎无尽的匹配。上边提到的 (…+)*也类似。
13.如果能简单的匹配大幅缩短目标字符串，可以进行多次正则匹配，经过实践十分有效。
ps：行文可能比较混乱，主要参考[精通正则表达式（第三版）](美)Jeffrey.E.F.Friedl 这本书，另外也看了两篇别人的blog，基本上这本书函盖完了。