Techniques for Faster Expressions

之前的数页介绍了我见过的传统型NFA引擎使用的各种优化。没有任何程序同时具备所有这些优化，而且无论你爱用的程序目前支持哪些，情况也会随时间而改变。但是，理解可能进行的各种优化，我们就能写出效率更高的表达式。如果你还理解传统型NFA的工作原理，把这些知识结合起来，就可以从三方面获益：

●编写适于优化的正则表达式 编写适应已知（或者未来会支持的）优化措施的表达式。举例来说，「xx＊」比「x+」能适用的优化措施更多，例如检查目标字符串中必须出现的字符（☞245），或者开头字符识别（☞247）。

●模拟优化 有时候我们知道所用的程序没有特殊的优化措施，但是通过手工模拟，我们还是能节省大量的时间。比如在「this|that」之前添加「（？=t）」，这样即使系统无法预知任何匹配结果必须以‘t’开头，我们还是能模拟开头字符识别（☞247），下文还会深入讨论这个例子。

●主导引擎的匹配 使用关于传统型 NFA 引擎工作原理的知识，能够主导引擎更快地匹配。拿「this|that」来说。每个多选分支都以「th」开头，如果第一个多选分支不能匹配「th」，第二个显然也不行，所以不必白费工夫。因此，我们可以使用「th（？：is|at）」。这样，「th」就只要检查一遍，只由在确实需要的时候才会用到代价相对高昂的多选结构功能。而且，「th（？：is|at）」开头的纯文字字符就是「th」，所以存在进行其他优化的可能。

重要的是认识到，效率和优化有时候处理起来比较麻烦。在阅读本节其他内容的时候，请不要忘记下面几点：

●进行看来确实有帮助的改动，有时反而事与愿违，因为这样可能禁止了你所不知道的，已经生效的其他优化。

●添加一些内容模拟你知道的不存在的优化措施，可能出现的情况是，处理那些添加内容的时间多于节省下来的时间。

●添加一些内容模拟一个目前未提供的优化，如果将来升级以后的软件支持此优化，反而会影响或者重复真正的优化。

●同样，控制表达式尝试触发某种当前可用的优化，将来某些软件升级之后可能无法进行某些更高级的优化。

●为提高效率修改表达式，可能导致表达式难以理解和维护。

●具体的修改带来的好处（或是坏处）的程度，基本上取决于表达式应用的数据。对某类数据来说有益的修改，可能对另一类数据来说是有害的。

我来举个极端点的例子：你在 Perl 脚本中找到「（000|999）$」，并决定把这些捕获型括号替换为非捕获型括号。你觉得这样速度更快，因为不再需要捕获文本的开销。但是奇怪的是，这个微小而且看起来有益的改动反而会把表达式的速度降低许多个数量级（比之前慢几千倍）。怎么会这样呢？原来在这里有若干因素共同作用，使用非捕获型括号时，字符串结束/行锚点优化（☞246）会被关闭。我不希望劝阻读者在Perl中使用捕获型括号——绝大多数情况下，使用他们都是有益的，但是在某些情况下，会带来灾难性的后果。

所以，检测并性能测试你期望实际应用的同类型的数据，有助于判断改动是否值得，但是，你仍然必须自己权衡众多因素。就说这么多，下面我开始讲解一些技巧，你能够用它们来挖掘引擎效率的最后一点潜能。

常识性优化

Common Sense Techniques

只需要依靠常识，就能进行一些极有成效的优化。

避免重新编译

编译和定义正则表达式的次数应该尽可能的少。在面向对象式处理中（☞95），用户能够精确控制这一点。举例来说，如果你希望在循环中应用正则表达式，就应该在循环外创建这个正则表达式对象，在循环中重复使用。

在函数式处理——例如GNU Emacs和Tcl——的情况下，应尽量保证循环中使用的正则表达式的数目少于工具所能缓存的上限（☞244）。

如果使用的是集成式处理，例如Perl，应尽量避免在循环内的正则表达式中使用变量插值，因为这样每次循环都需要重新生成正则表达式，即使值没有变化（不过，Perl提供了高效的办法来避免这个问题☞348）。

使用非捕获型括号

如果不需要引用括号内的文本，请使用非捕获型括号「（？：…）」（☞45）。这样不但能够节省捕获的时间，而且会减少回溯使用的状态的数量，从两方面提高速度。而且能够进行进一步的优化，例如消除无必要括号（☞248）。

不要滥用括号

在需要的时候使用括号，在其他时候使用括号会阻止某些优化措施。除非你需要知道「.＊」匹配的最后一个字符，否则请不要使用「（.）＊」。这似乎很显而易见，但是别忘了，本节的标题是“常识性优化”。

不要滥用字符组

这一点看起来也很显而易见，但是我经常在缺乏经验的程序员的表达式中看到「^.＊[：]」。我不知道为什么他们会使用只包含单个字符的字符组——这样需要付出处理字符组的代价，但并不需要用到字符组提供的多字符匹配功能。我认为，当一个字符是元字符时——例如「[.]」或者「[＊]」，可能作者不知道通过转义把它们转换为「\.」和「\＊」。我经常在宽松排列模式（☞111）下见到它们与空白字符一起出现。

同样，读过本书第一版的Perl用户可能有时候写出「^[Ff][Rr][Oo][Mm]：」，而不是用不区分大小写的「^from：」。老版本的 Perl 在进行不区分大小写的匹配时效率很低，所以我推荐使用字符组。但现在这种做法已不再适用，因为不区分大小写匹配效率低下的问题在好几年前就修正了。

使用起始锚点

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

将文字文本独立出来

Expose Literal Text

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

从量词中“提取”必须的元素

用「xx＊」替代「x+」能够暴露匹配必须的‘x’。同样的道理，「-{5，7}」可以写作「------{0，2}」。

“提取”多选结构开头的必须元素

用「th（？：is|at）」替代「（？：this|that）」，就能暴露出必须的「th」。如果不同多选分支的结尾部分相同，我们也可以从右面“提取”，例如「（？：optim|standard）ization」。我们会在下一节中看到，如果提取出来的部分包括锚点，这么做就非常有价值。

将锚点独立出来

Expose Anchors

某些效果明显的内部优化措施是利用锚点（例如「^」、「$」和「\G」），把表达式“绑定”在目标字符串的某一端。使用这些优化时，某些引擎的效果不如其他引擎，但是有一些技巧能够提供帮助。

在表达式前面独立出^和\G

「^（？：abc|123）」和「^abc|^123」在逻辑上是等价的，但是许多正则引擎只会对第一个表达式使用开头字符/字符串/字串识别优化（☞246）。所以，第一种办法的效率要高得多。PCRE （还包括使用它的工具）中两者的效率是一样的，但是大多数其他NFA工具中第一个表达式的效率更高。

比较「（^abc）」和「^（abc）」我们能发现另一个区别。前者的设置并不很合适，锚点“藏”在捕获型括号内，在检测锚点之前，必须首先进入括号，在许多系统上，这样做的效率很低。某些系统（PCRE、Perl、.NET）中两者的效率相当，但是在其他系统中（Ruby 和 Sun 的Java regex package）只会对后者进行优化。

Python 似乎不会进行锚点优化，所以这些技巧目前不适用于 Python。当然，本章介绍的大多数优化都不适用于Tcl（☞243）。

在表达式末尾独立出$

此措施与上一节的优化思想非常类似，虽然「abc$|123$」和「（？：abc|123）$」在逻辑上是等价的，但优化的表现可能不同。目前，这种优化还只适用于 Perl，因为现在只有 Perl 提供了“字符串结束/行锚点优化”（☞246）。优化只对「（…|…）$」起作用，对「（…$|…$）」不起作用。

忽略优先还是匹配优先？具体情况具体分析

Lazy Versus Greedy:Be Specific

通常，使用忽略优先量词还是匹配优先量词取决于正则表达式的具体需求。举例来说，「^.＊：」完全不同于「^.＊？：」，因为前者匹配到最后的冒号，而后者匹配到第一个冒号。但是，如果目标数据中只包含一个分号，两个表达式就没有区别了（匹配到唯一的分号为止），所以选择速度更快的表达式可能更合适。

不过并不是任何时候优劣都如此分明，大的原则是，如果目标字符串很长，而你认为分号会比较接近字符串的开头，就使用忽略优先量词，这样引擎能更快地找到分号。如果你认为分号在接近字符串末尾的位置，就使用匹配优先量词。如果数据是随机的，又不知道分号究竟会靠近哪一头，就使用匹配优先的量词，因为它们的优化一般来说都要比其他量词要好，尤其是表达式的后面部分禁止进行“忽略优先量词之后的字符优化”（☞248）时，更是如此。

如果待匹配的字符串很短，差别就不那么明显了。这时候，两个正则表达式的速度都很快，不过如果你很在乎那一点点速度差别，就对典型数据做个性能测试吧。

一个与此有关的问题是，在忽略优先量词和排除型字符组之间（「^.＊？：」与「^[^：]＊：」），应该如何选择？答案还是取决于所使用的编程语言和应用的数据，但是对大多数引擎来说，排除型字符组的效率比忽略优先量词高的多。Perl是个例外，因为它能对忽略优先量词之后的字符进行优化。

拆分正则表达式

Split Into Multiple Regular Expressions

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

撰写本章时，我遇到了一个有趣的情况。用 Perl 写一个数据处理模块时，我意识到客户端程序有个bug，导致它发送奇怪的数据，类似‘HASH（0x80f60ac）’而不是真正的数据。所以，我打算修正这个模块，寻找怪异数据的来源，并报告错误。我使用的正则表达式相当直白：「\b（？：SCALAR|ARRAY|…|HASH）\（0x[0-9a-fA-F]+\）」。

在这里，效率是非常关键的。这个表达式的速度如何？Perl的调试模式（debugging mode）能够告诉你它对特定表达式使用的某些优化（☞361），所以我进行了检查。我希望启用了预查必须字符/字符串优化（☞245），因为足够先进的引擎应该能够明白‘（0x’是任何匹配所必须的。因为这个正则表达式所应用的数据几乎不包含‘（0x’，我相信预查能够节省许多时间。不幸的是，Perl没有这样做，所以程序必须在每个目标字符串的每个字符那里测试整个正则表达式的众多多选分支。速度达不到我的要求。

因为正在研究和撰写与优化有关的内容，所以我冥思苦想，这个表达式应该怎样写才能得到优化。一个办法是以复杂的方式[0-9a-fA-F]+\）」。这样，一旦「\（0x」匹配之后，肯定型顺序环视（下画线标注部分）就能确保之前匹配的是需要的文本，再检查之后的文本是否符合期望。费这番周折的原因在于，让正则表达式获得必须出现的文字文本「\（0x」，这样就能进行多种优化。尤其是，我希望进行预查必须字符串优化，以及开头字符/字符组/子串识别优化（☞247）。我确定这样速度会很快，但是Perl不支持长度不定的逆序环视（☞133），所以我得想办法来绕开它。

不过我发觉，如果Perl不会自动预查「\（0x」，我可以自己动手：

「\（0x」的检查事实上会过滤大部分文本，相对较慢的完整正则表达式只对有可能匹配的行进行检测，这样就在效率（非常高）和可读性（非常高）之间达到了完美的平衡（注7）。

模拟开头字符识别

Mimic Initial-Character Discrimination

如果你的实现方式没有进行开头字符识别优化（☞247），则可以亲自动手，在表达式的开头添加合适的环视结构（☞133）。在正则表达式的其他部分匹配之前，环视结构可以进行“预查”，选择合适的开始位置。

如果正则表达式为「Jan|Feb|…|Dec」，对应的就是「（？=[JFMASOND]）（？：Jan|Feb|…|Dec）」。开头的「[JFMASOND]」代表了英文中月份单词可能的开始字母。不过这种技巧并不是所有情况下都适用的，因为，环视结构的开销可能大于节省的时间。在这个例子中，因为多数多选分支都可能匹配失败，预查对我测试的大多数系统（Java、Perl、Python、Ruby、.NET）都是有用的，因为它们都不能自动从「Jan|Feb|…|Dec」得到开头的「[JFMASOND]」。

在默认情况下，PHP/PCRE并不会进行这种优化，但是如果使用PCRE的pcre_study（也就是PHP中的模式修饰符S，☞478）则可以。而Tcl显然能够完美地做到这一点（☞243）。

如果正则引擎能自动进行「[JFMASOND]」的检测，速度当然会比用户手工指定快得多。我们有没有办法让引擎自动进行检测呢？在许多系统上，我们可以用下面这个复杂得要命的表达式：

「[JFMASOND](?:(?＜=J)an|(?＜=F)eb|…|(?＜=D)ec)」

我可不指望你能看一眼就明白这个表达式，但是花点时间仔细琢磨倒是很值得的。表达式开头的字符组可以被大多数系统的开头字符识别优化所利用，这样传动装置就能够高效地预查「[JFMASOND]」。如果目标字符串不包含匹配字符，结果会比原来的「Jan|…|Dec」或是手工添加环视功能的表达式要快。但是，如果目标字符串中包含许多字符组能够匹配的字符，那么额外的逆序环视可能反而会减慢匹配的速度。最主要的问题是，这个正则表达式显然很难看懂。但是，这个例子倒是很有意思，也很启发人。

不要在Tcl中这么做

上面的优化例子其实降低了表达式的可读性。243页的补充内容提到，不同形式的正则表达式在Tcl中的表现是相同的，所以在Tcl中，大多数优化并没有意义。不过，有个例子中优化确实有影响。根据我的测试，手动添加「（？=[JFMASOND]）」会把速度降低到原来的1/100。

不要在PHP中这么做

之前我们已经提到过，不应该在PHP中进行优化，因为我们能够使用PHP的“study”功能——模式修饰符S——来启用优化。详见第10章第478页。

使用固化分组和占有优先量词

Use Atomic Grouping and Possessive Quantifiers

在许多情况下，固化分组（☞139）和占有优先量词（☞142）能够极大地提高匹配速度，而且它们不会改变匹配结果。举例来说，如果「^[^：]+：」中的冒号第一次尝试时无法匹配，那么任何回溯其实都是没有意义的，因为根据定义，回溯“交还”的任何字符都不可能是冒号。使用固化分组「^（？＞[^：]+）：」或者占有优先量词「^[^：]++：」就能够直接抛弃备用状态，或者根本不会创造多少备用状态。因为引擎没有内容状态可以回溯，就不会进行不必要的回溯（第251页的补充内容说明，足够聪明的引擎能够自动进行这种优化）。

不过，我必须强调，这两种结构运用不当，就会在不经意间改变匹配结果，所以必须极为小心。如果不用「^.＊：」而用「^（？＞.＊）：」，结果必然会失败。整行文本都会被「.＊」匹配，后面的「：」就无法匹配任何字符。固化分组阻止最后的「：」匹配必须进行的回溯，所以匹配必定失败。

主导引擎的匹配

Lead the Engine to a Match

提高正则表达式匹配效率的另一个办法是尽可能准确地设置匹配过程中的“控制权”。我们曾经看过的用「th（？：is|at）」取代「this|that」的例子。在后一个表达式中，多选结构获得最高级别的控制权，而在前一个表达式中，相对代价更高昂的多选结构只有在「th」匹配之后才获得控制权。

下一节“消除循环”是这种技巧的高级形式，此处再介绍些简单的技巧。

将最可能匹配的多选分支放在前头

在本书中我们看到，许多时候多选分支的摆放顺序非常重要（☞28、176、189、216）。在这些情况下，摆放顺序比优化更重要，但相反，如果顺序与匹配正确无关，就应该把最可能匹配的多选分支放在首位。

举例来说，在匹配主机名的正则表达式（☞205）中，有人可能习惯把后缀按照字母顺序排序，例如「（？：aero|biz|com|coop|…）」。不过，某些排在前头的后缀应用并不广泛，匹配极有可能失败，为什么要把他们排在前头呢？如果按照分布数量的排序：「（？：com|edu|org|net|…）」，更有可能获得更迅速更常见的匹配。

当然，这只有对传统型NFA引擎才适用，而且只有存在匹配的时候才适用。如果使用POSIX NFA，或是不存在匹配，此时所有的多选分支都必须检测，所以顺序是无关紧要的。

将结尾部分分散到多选结构内

接下来我们比较「（？：com|edu|…|[a-z][a-z]）\b」和「com\b|edu\b|…\b|[a-z][a-z]\b」。在后一个表达式中，多选结构之后的「\b」被分散到每个多选分支。可能的收益就是，它可能容许一个多选分支能够匹配，但多选分支之后的「\b」可能导致这个匹配不成功，把「\b」加到多选结构之内，匹配失败的更快。这样不需要退出多选结构就能发现失败。

要说明这个技巧的价值，这可能还不是最好的办法，因为它只是适用于一种特殊情形，即多选分支可能能够匹配，但是之后紧接的字符可能令匹配失败。在本章中我们会看到一个更合适的例子——请参考280页关于$OTHER＊的讨论。

这个优化是有风险的。切记，使用这个功能时要小心，不要因此阻止了本来可以进行的其他优化。举例来说，如果“分散的”子表达式是文字文本，那么把「（？：this|that）：）」更换为「this：|that：」就违背了“将文字文本独立出来”（☞255）中的某些思想。各种优化都是平等的，所以在优化时请务必小心，不要因小失大。

在能够进行独立结尾锚点（☞256）的系统上把正则表达式末尾的「$」分散，也会遇到这种问题。在这些系统上，「（？：com|edu|…）$」比「com$|edu$|…$」快得多（我测试了各种系统，只有Perl使用了这种优化）。