<进阶-2> 打造高效正则表达式

每个正则表达式都必须在下面两个方面求得平衡：
(1)准确匹配期望匹配的内容，忽略不期望匹配的字符。前面我们已经看到，如果应用得当，匹配优先非常有用，但如果不够小心也可能带来麻烦。
(2)NFA引擎还需要平衡另外一个因素：效率。设计糟糕的正则表达式即使没有功能错误，也足以让引擎瘫痪。

5.1 正则表达式的平衡法则
好的正则表达式必须在这些方面求得平衡：
1.只匹配期望的文本，排除不期望的文本。
2.必须易于控制和理解。
3.如果使用NFA引擎，必须保证效率（如果能够匹配，必须很快地返回匹配结果，如果不能匹配，应该在尽可能短的时间内报告匹配失败）。

这些方面常常是与具体文本相关的。如果只使用命令行，只需要快速的grep某些东西，可能不会过分关心匹配的准确性，通常也不会花太多精力来调校。但是，如果处理重要的程序，就需要花费时间精力来保证正确性，如果需要，正则表达式也可能很复杂，这些因素都需要平衡。

5.2 打造高效正则表达式
java,perl，.net, python等使用的都是表达式主导的NFA引擎，细微的改变就可能对匹配的结果及方式产生重大的影响。总的来说，关键在于彻底理解回溯背后的过程，学习些技巧来避免可能的回溯。

5.2.1 典型示例
前面示例提到过，我们使用”(\\.|[^\\"])*”来匹配引号字符串，其中容许出现转义的双引号，这个正则的第一个多选分支表示字符串可以出现任何转义的字符，即反斜线加一个字符；第二个多选分支可以匹配非转义符或非引号之外的所有字符。这个表达式没有错，但如果我们使用NFA引擎，对每个字符都应用多选结构的效率就会很低。对字符串中每个“正常”（非转义，非引用）的字符来说，这个引擎需要先测试\\.，必定会失败，遇到失败后回溯，最终由”[^\\"]”匹配。对于“正常”字符居多的场景下，效率必然低下。

稍加修改:先迈最好使的腿
对于一般的双引号字符串来说，普通字符的数量比转义字符要多，一个简单的改动就是调换两个多选分支的顺序。可以减少很多回溯。


5.2.2 限制匹配优先的作用范围
从上图可以看出，在任意正则表达式中，星号会对每个普通字符进行迭代（或者说是重复），重复进入-退出多选结构和括号，因为前面的分支不能匹配，所以要回溯，然后选择后面的分支尝试。这需要成本，也就是额外的处理，如果可能，我们必须避免这些额外处理。

这里还有一个更优化的方法（但只适用于传统NFA引擎，对POSIX NFA简直就是灾难），考虑到”[^\\”]”匹配普通（非引号，非反斜线）的情况，使用”[^\\"]+”会在(…)*的一次迭代中读入尽可能多的字符。对没有转义字符的字符串来说，这样会一次读入整个字符串。于是就几乎不会进行回溯，也就把星号迭代的次数减少到最小。跟上面的例子进行对比：


新增的加号大大减少了多选结构回溯的次数，以及星号的迭代次数(注意回溯和迭代是不同的动作，回溯是退回前一个保留状态重新尝试，迭代就像循环，是星号不断循环每个字符对其进行多选分支的尝试)。星号量词作用于括号内的子表达式，每次迭代都需要进入然后再退出括号，这都需要成本，因为引擎需要记录括号内的字表达式匹配的文本。

前面说过这个改动只适用于传统NFA引擎，对POSIX NFA简直就是灾难。对于一个不是很长的句子，几乎会回溯几百亿亿年。原因在于，这个正则表达式中某个元素受加号限定的同时，还受括号外的星号限定，无法区分哪个量词控制哪个特殊的字符，这种不确定性就是症结。

指数级的匹配
没有添加星号时，”[^\\"]”是星号的约束对象，真正的([^\\"])*能够匹配的字符是有限的。它先匹配一个字符，然后匹配下一个字符，如此继续，最多就是匹配目标文本中的每个字符。它也可能无法匹配目标字符串中的所有字符，不过，充其量，匹配字符的个数与目标字符串的长度成线性关系。


我们现在知道，存在许多种可能（对长度为12的字符串存在4096种可能，也就是2的12次方）。字符串的每一个字符都存在两种可能。POSIX NFA在给出结果之前必须尝试所有可能。这就是“指数级匹配”的来历。也可以叫做”超线性”。
POSIX NFA和传统型NFA的主要差别在于，传统型NFA在遇到第一个完整匹配可能时会停止。如果没有完整匹配，即使是传统型NFA也需要尝试所有的可能。

5.2.3 全面考察回溯
从局部来看，回溯就是倒退到未尝试的分支。这很容易理解，但是回溯对整个匹配影响并不容易理解。
再来看一个我们之前提到的一个例子，我们用”.*”来匹配下面的文本：
The name “McDonald’s” is said “makudonarudo” in Japanese

正则表达式会从字符串的开始位置依次尝试每个字符，但是因为开头的引号无法匹配，此后的字符也不能匹配，直到尝试到第一个引号，接着尝试表达式的其他部分，.*尝试匹配直到字符串的末尾，此时点号无法匹配，所以星号部分停止迭代，并且沿路标记了46个状态供回溯。最后，引擎开始匹配正则的最后一个引号。这时，开始回溯，直到…narudo”处最后的引号匹配成功，于是匹配结果：“McDonald’s” is said “makudonarudo”，剩下的未使用状态将会被抛弃，报告匹配成功。这就是传统NFA的匹配过程。而POSIX NFA需要更多处理，它会尝试所有可能，直到最后选择最长的匹配。

如果我们把正则的点号改为[^"]成为”[^"]*”，这样正则表达式的效率就提升了，因为它能匹配的字符更少，减少了匹配和回溯。

5.2.4 多选结构的代价很高
多选结构或许是回溯的主要原因。用上面例子中的字符串来比较”u|v|w|x|y|z”和”[uvwxyz]”的匹配，字符组一般只是简单测试，所以”[uvwxyz]”只会进行34次尝试就能成功。
The name “McDonald’s” is said “makudonarudo” in Japanese
匹配到makudonarudo中的u就算成功了，只需要匹配34个字符就可以了。但如果用多选结构，每个字符要回溯6次，就需要匹配6*34次。

5.3 常见优化措施
聪明的正则表达式实现有许多办法来优化，通常有两种思路：
1）加速某些操作。某些类型的匹配，如\d+极为常见，引擎可能对此有特殊的处理方案，执行速度比通用的处理机制要快。
2）避免冗余操作。例如，一个以”\A”（行开头）开头的正则表达式在字符串的开头位置才能匹配，如果在此处无法匹配，传动装置也不会徒劳地尝试其他位置，所以通常我们可以限定开头位置来约束传动装置。

5.3.1 正则表达式的应用原理
我们必须先掌握正则表达式应用的基本知识，然后讲解先进系统的优化原理及利用方式。之前已经了解了回溯的细节。

正则表达式应用到目标字符串的过程大致分为下面几步：
1）正则表达式编译。检查正则表达式的语法正确性，如果正确，就将其编译为内部形式。
2）传动开始。传动装置将正则引擎定位到目标字符串的起始位置。
3）元素检测。引擎开始检测正则表达式和文本，依次测试正则表达式的各个元素。之前已经考察了NFA的回溯，这里补充几点：
（3.1）相连元素，如”Subject”中的’S’,’u’,’b’,’j’,’e’,’c’,’t’会依次尝试，只有当某个元素匹配失败时才会停止。
（3.2）量词修饰的元素，控制权在量词（检测量词是否应该继续匹配）和被限定的元素（测试是否能够匹配）之间轮换。
（3.3）控制权在捕获型括号内外记性切换会带来一些开销。括号内的表达式匹配的文本必须保留，这样呢才能通过$1来引用。因为一对括号可能属于某个回溯分支，括号的状态就是用于回溯的状态的一部分，所以进入和退出捕获型括号时需要修改状态。
4）寻找匹配结果。如果找到一个匹配结果，传统型NFA会锁定在当前状态，报告成功。而对POSIX NFA来说，如果这个匹配时迄今为止最长的，它会记住这个可能的匹配，然后从可用的保存状态继续下去，保存的状态都测试完毕之后返回最长的匹配。
5）传动装置的驱动过程。如果没有找到匹配，传动装置就会驱动引擎，从文本中的下一个字符开始新一轮的尝试。
6）匹配彻底失败。如果从目标字符串的每一个字符（包括最后一个字符之后的位置）开始的尝试都失败了，就会报告匹配彻底失败。

下面就主要介绍如何减少这些处理，以及如果应用这些技巧。

5.3.2 应用之前的优化措施
优秀的正则引擎实现方式能够在正则表达式实际应用之前就进行优化，它有时候甚至能迅速判断出，某个正则表达式无论如何也无法匹配，所以根本不必应用这个表达式。

1.编译缓存
正则表达式使用之前要做的第一件事就是进行错误检查，如果没有问题则编译为内部形式。显然，如果每次使用时都重新编译所有正则表达式很浪费时间，如果第一次编译之后就把内部形式保存下来，此后的循环中重复使用它们显然会提高速度。具体做法取决于应用程序提供的正则表达式处理方式，前面说过有3种处理方式：集成式，程序式和面向对象式。

perl和awk使用的就是集成式处理方法，非常容易进行编译缓存。
java是面向对象方式，正则表达式何时编译完全由程序员决定，比如使用Pattern.compile()。

2.预查必须字符/子字符串优化
相比正则表达式的完整应用，在字符串中搜索某个字符或字符串是更加轻量级的操作，所以某些系统会在编译阶段做些额外的分析，判断是否存在成功匹配必须的字符或字符串（后面会看到很多基于此的优化，比如多选分支有公共部分可以提取出来先）。在实际应用正则表达式之前，在目标字符串中快速扫描，检查所需的字符或字符串，如果不存在，根本就不需要进行任何匹配。
举例来说，”^Subject: (.*)”的”Subject:”是必须出现的，程序可以检查整个字符串，或者使用Boyer-Moore搜索算法。

3.长度判断优化
”^Subject: (.*)”能匹配文本的长度是不固定的，但是至少包含9个字符。所以，如果目标字符串的长度小于9则根本不必尝试。当然，需要匹配的字符更长优化的效果才更明显。

5.3.3 通过传动装置进行优化
即使正则引擎无法预知某个字符串能够匹配，也能够减少传动装置真正应用正则表达式的位置。

1. 字符串开始/行锚点优化
这种优化措施能够判断，任何以”^”开头的正则表达式只能在”^”能够匹配的情况下才可能匹配，所以只需要在这些位置应用即可。如果”^(this|that)”匹配成功，”^”必须能够匹配，用”^(this|that)”或”^(?:this|that)”能够提高匹配的速度。
同样的优化措施还对”\A”,如果匹配多次，对”\G”也有效。

2.隐式锚点优化
能使用此种优化的引擎知道，如果正则表达式以”.*”或”.+”开头，而且没有全局性多选结构，则可以认为此正则表达式的开头有一个看不见的”^”，这样就能使用上“字符串起始/行锚点优化”，节省大量的事件。


3.字符串结束/行锚点优化
这种优化遇到末尾为”$”或其他结束锚点的正则表达式时，能够从字符串末尾倒数若干字符的位置开始尝试匹配。例如”regex(es)?$”匹配只可能从字符串末尾倒数的第8个字符开始，所以传动装置能够跳到那个位置，略过目标字符串中许多可能的字符。

5.3.4 优化正则表达式本身
1. 文字字符串连接优化
也许最基本的优化就是，引擎可以把”abc”当做一个整体元素，而不是3个字符’a’, ‘b’, ‘c’。如果能够这样，整个部分就可以作为迭代的一个单元，而不需要进行3次迭代。

2. 化简量词优化
约束普通元素（例如文字字符或字符组）的加号，星号之类的量词，通常需要经过优化
避免普通NFA引擎的大部分逐步处理开销。

3.消除不必要括号
如果某种实现方式认为”(?:.)*”与”.*”是完全等价的，那么它就会用后者替换前者。

4. 消除不需要的字符组
只包含单个字符的字符组有点多余，因为它要按照字符组来吹。所以，聪明的实现方式会在内部把”[.]”转换为”\.”。

5. 忽略优先量词之后的字符优化
忽略优先量词，例如”(.*?)”中的”*?”，在处理时，引擎通常必须在量词作用的对象（点号）和”之后的字符之间切换。因为种种原因，忽略优先量词通常比匹配优先量词要慢，尤其是对上下文中”化简量词优化”的匹配优先限定结构来说，更是如此。另一个原因是，如果忽略优先量词是在捕获型括号之内，控制权就必须在括号内外切换，这样会带来额外的开销。
所以这种优化的原理是，如果文字字符跟在忽略优先量词之后，只要引擎没有触及那个文字字符，忽略优先量词可以作为普通的匹配优先量词来处理。所以，包含此优化的实现方式在这种情况下会切换到特殊的忽略优先量词，迅速检测目标文本中的文字字符，在遇到此文字字符之前，跳过常规的忽略状态。

6. 使用占有优先量词削减状态
由正常量词约束的对象匹配之后，会保留若干“在此处不进行匹配”的状态（量词每一轮迭代创建一个状态）。占有优先量词则不会保留这些状态。具体做法有两种，一种是在量词全部尝试完成之后抛弃所有备用状态，效率更高的办法是每一轮迭代时抛弃上一轮的备用状态。
在迭代中及时抛弃状态的做法效率更高，因为所占的内存更少。应用”.*”会在匹配每个字符时创造一个状态，如果字符串很长，会占用大量的内存。

7. 量词等价转换
有人习惯用”\d\d\d\d”，也有人习惯使用量词”\d{4}”.对NFA来说，两者的效率是有差别的，但工具不同，结果也不同。如果对量词做了优化，则”\d{4}”会更快一点，除非未使用量词的正则表达式能进行更多的优化。测试结果表明，perl，python，php和.net中”\d{4}”大概快20%。但是，如果使用ruby和sun的java regex package, “\d\d\d\d”则要快上好几倍。
比较”====”和”={4}”，这个例子与上面的截然不同，因为此时重复的是确定的文字字符，而且直接使用”====”引擎更容易将其识别为一个文字字符串。如果是，支持的高效的开头字符/字符组/子串识别优化就可以派上用场。对python和sun的java regex package来说，情况正是如此，”====”比”={4}”快上100倍。

5.4 常识性优化
5.4.1 避免重新编译
编译和定义正则表达式的次数应该尽可能的少。在面向对象式处理中，用户能精确控制这一点。举例来说，如果你希望在循环中应用正则表达式，就应该在循环外创建这个正则表达式对象，在循环中重复使用。

5.4.2 使用非捕获型括号
如果不需要引用括号内的文本，请使用非捕获型括号”(?:…)”。这样不但能节省捕获的事件，而且会减少回溯使用的状态的数量，从两方面提高速度。

5.4.3 不要滥用括号
在需要的时候使用括号，在其他时候使用括号会阻止某些优化措施。除非你需要知道”.*”匹配的最后一个字符，否则请不要使用”(.)*”。

5.4.4 不要滥用字符组
这一点看起来也很显而易见，但是经常看到缺乏经验的程序员的表达式中看到”^.*[:]”，使用只包含单个字符的字符组需要付出处理字符组的代价，但并不需要用到字符组的多字符匹配功能。使用单个字符的字符组可能是想匹配这个特殊字符，比如元字符，想利用字符组的功能使这个字符编程普通字符，其实这时候可以使用转义，比如”\.”, “\*”。

5.4.5 使用起始锚点
除非是及其罕见的情况，否则以”.*”开头的正则表达式都应该在最前面添加”^”或者”\A”。如果这个正则表达式在某个字符串的开头不能匹配，那么显然在其他位置也不能匹配。添加锚点（无论是手工添加，还是通过优化自动添加）都能配合开头字符/字符串识别优化，节省大量不必要的工作。

5.5 将文字文本独立出来
我们前面见过的许多局部优化上，主要是依靠正则引擎的能力来识别出匹配成功必须的一些文字文本。某些引擎在这一点上做的比其他引擎更好，所以这里提供了一些手动优化措施，有助于暴露文字文本，提高引擎识别的可能性，配合与文字文本有关的优化措施。

5.5.1 从量词中提取必须的元素
用”xx*”代替”x+”能够暴露匹配必须的x。同样的道理，”-{5,7}”可以写作”------{0,2}”。也就是尽可能多的把确定的文本暴露出来。

5.5.2 提取多选结构开头的必须元素
用”th(?:is|at)”替代”(?:this|that)”就能暴露出必须的”th”。如果不同部分的结尾部分相同，我们也可以从后面提取，如”(?:optin|standard)ization”，如果提取出来的部分包括锚点，这么做就非常有价值。

5.6 将锚点独立出来
某些效果明显的内部优化措施是利用锚点（例如^,$），把表达式绑定在目标字符串的某一端。
“^(?:abc|123)”和”^abc|^123”在逻辑上是等价的，但是许多引擎只会对第一个表达式使用开头字符/字符串/字串识别优化。所以第一种办法的效率要高得多。

比较(^abc)和”^(abc)”我们能发现另一个区别，前者的设置并不合适，锚点隐藏在捕获型括号内，在检测锚点之前，必须首先进入括号，在许多系统上，这样做的效率很低。

5.7 拆分正则表达式
有时候，应用多个小正则表达式的速度比一个大正则表达式要快得多。举个极端的例子，如果你希望检查一个长字符串中是否包含月份的名字，依次检查”January”,”February”之类的速度要比”January|February|March|…”快得多。因为对后者来说，不存在匹配成功必须的文字内容，不能进行“内嵌文字字符串检查优化”。大而全的正则表达式必须在目标文本中的每个位置测试所有的自表达式，速度相当慢。

5.8 使用固化分组和占有优先量词
在许多情况下，固化分组和占有优先量词能够极大地提高匹配速度，而且他们不会改变匹配结果。举例来说，如果”^[^:]+:”中的冒号第一次尝试时无法匹配，那么任何回溯其实都是没有意义的。使用固化分组”^(?>[^:]+):”或者占有优先量词”^[^:]++:”就能够直接抛弃备用状态，或者根本不会创造多少备用状态。
不过必须强调，如果运用不当，就会在不经意间改变匹配结果，所以必须极为小心。比如，如果用”^(?>.*):”代替”^.*:”结果必然失败，因为整行都会被”.*”匹配而且不会交还任何字符。

5.8 主导引擎的匹配
提高正则表达式匹配效率的另一个办法是尽可能准确地设置匹配过程中的“控制权”。我们曾经用”th(?:is|at)”取代”this|that”，后一个表达式中，多选结构获得最高级别的控制权，而在前一个表达式中，相对代价更高昂的多选结构只有在”th”匹配之后才获得控制权。

5.8.1 将最可能匹配的多选分支放在前头
许多时候多选分支的摆放顺序非常重要。举例来说，在匹配主机名时，有人可能习惯把后缀按照字母顺序排序，例如”(?:aero|biz|com|coop|…)”。不过，某些排在前头的后缀应用并不广泛，匹配极可能失败。如果按照分布数量的排序：”(?:com|edu|org|net|…)”，更有可能获得更迅速更常见的匹配。

至此，对于NFA引擎的正则优化技巧基本就介绍完了，在实际应用中可能还会有其他技巧，需要我们边使用边发现，关键是能从引擎的工作原理上去分析正则的运行机制，提高使用效率。

评论

3 楼 su0nils000 2015-10-01  

难得的笔记

2 楼 足至迹留 2014-03-25  

文仁126520 写道

这是摘抄下来的吧！写得太长了！

摘抄非全抄，看系列第一篇可知主要参考《精通正则表达式》。长不是问题，冗余没价值才是问题~

1 楼 文仁126520 2014-03-24  

这是摘抄下来的吧！写得太长了！