Common Optimizations

聪明的正则表达式实现（implementation）有许多办法来优化，提高取得结果的速度。优化通常有两种办法：

●加速某些操作。某些类型的匹配，例如「\d+」，极为常见，引擎可能对此有特殊的处理方案，执行速度比通用的处理机制要快。

●避免冗余操作。如果引擎认为，对于产生正确结果来说，某些特殊的操作是不必要的，或者某些操作能够应用到比之前更少的文本，忽略这些操作能够节省时间。例如，一个以「\A」（行开头）开头的正则表达式只有在字符串的开头位置才能匹配，如果在此处无法匹配，传动装置不会徒劳地尝试其他位置（进行无谓的尝试）。

在下面的十几页中，我会讲解自己见过的许多种不同的天才优化措施。没有任何一种语言或者工具提供了所有这些措施，或者只是与其他语言和工具相同的优化措施；我也确信，还有许多我没见过的优化措施，但看完本章的读者，应该能够合理利用自己所用工具提供的任何优化措施。

有得必有失

No Free Lunch

通常来说优化能节省时间，但并非永远如此。只有在检测优化措施是否可行所需的时间少于节省下来的匹配时间的情况下，优化才是有益的。事实上，如果引擎检查之后认为不可能进行优化，结果总是会更慢，因为最开始的检查需要花费时间。所以，在优化所需的时间，节省的时间，以及更重要的因素——优化的可能性之间，存在互相制约的关系。

来看一个例子。表达式「\b\B」（某个位置既是单词分隔符又不是单词分隔符）是不可能匹配的。如果引擎发现提供的表达式包含「\b\B」就知道整个表达式都无法匹配，因而不会进行任何匹配操作。它会立刻报告匹配失败。如果匹配的文本很长，节省的时间就非常可观。

不过，我所知的正则引擎都没有进行这样的优化。为什么？首先，很难判断这条规则是否适用于某个特定的表达式。某个包含「\b\B」的正则表达式很可能可以匹配，所以引擎必须做一些额外的工作来预先确认。当然，节省的时间确实很可观，所以如果预计到「\b\B」经常出现，这样做还是值得的。

不幸的是，这并不常见（而且愚蠢）（注4），虽然在极少数情况下这样做可以节省大量的时间，但其他情况下速度降低的代价比这高得多。

优化各有不同

Everyone's Lunch is Different

在讲解各种优化措施时，请务必记住一点“优化各有不同（everyone’s lunch is different）”。虽然我尽量使用简单清晰的名字来命名每种措施，但不同的引擎必然可能以不同的方式来优化。对某个正则表达式进行细微的改动，在某个实现方式中可能会带来速度的大幅提升，而在另一个实现方式中大大降低速度。

正则表达式的应用原理

The Mechanics of Regex Application

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

正则表达式应用到目标字符串的过程大致分为下面几步：

1. 正则表达式编译 检查正则表达式的语法正确性，如果正确，就将其编译为内部形式（internal form）。

2. 传动开始 传动装置将正则引擎“定位”到目标字符串的起始位置。

3. 元素检测 引擎开始测试正则表达式和文本，依次测试正则表达式的各个元素（comp-onent），如第4章所说的那样。我们已经详细考察了NFA的回溯，但是还有几点需要补充：

●相连元素，例如「Subject」中的「S」、「u」、「b」、「j」、「e」等等，会依次尝试，只有当某个元素匹配失败时才会停止。

●量词修饰的元素，控制权在量词（检查量词是否应该继续匹配）和被限定的元素（测试能否匹配）之间轮换。

●控制权在捕获型括号内外进行切换会带来一些开销。括号内的表达式匹配的文本必须保留，这样才能通过$1来引用。因为一对括号可能属于某个回溯分支，括号的状态就是用于回溯的状态的一部分，所以进入和退出捕获型括号时需要修改状态。

4. 寻找匹配结果 如果找到一个匹配结果，传统型 NFA 会“锁定”在当前状态，报告匹配成功。而对POSIX NFA来说，如果这个匹配是迄今为止最长的，它会记住这个可能的匹配，然后从可用的保存状态继续下去。保存的状态都测试完毕之后返回最长的匹配。

5. 传动装置的驱动过程 如果没有找到匹配，传动装置就会驱动引擎，从文本中的下一个字符开始新一轮的尝试（回到步骤3）。

6. 匹配彻底失败 如果从目标字符串的每一个字符（包括最后一个字符之后的位置）开始的尝试都失败了，就会报告匹配彻底失败。

下面几节讲解高级的实现方式如何减少这些处理，以及如何应用这些技巧。

应用之前的优化措施

Pre-Application Optimizations

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

编译缓存

第2章的E-mail处理程序中，用于处理header各行的主循环体中是这样的：

正则表达式使用之前要做的第一件事情是进行错误检查，如果没有问题则编译为内部形式。编译之后的内部形式能用来检查各种字符串，但是这段程序的情况如何？显然，每次循环都要重新编译所有正则表达式，这很浪费时间。相反，在第一次编译之后就把内部形式保存或缓存下来，在此后的循环中重复使用它们，显然会提高速度（只是要消耗些内存）。

具体做法取决于应用程序提供的正则表达式处理方式。93页已经说过，有3种处理方式：集成式、程序式和面向对象式。

集成式处理中的编译缓存

Perl 和 awk 使用的就是集成式处理方法，非常容易进行编译缓存。从内部来说，每个正则表达式都关联到代码的某一部分，第一次执行时在编译结果与代码之间建立关联，下次执行时只需要引用即可。这样最节省时间，代价就是需要一部分内存来保存缓存的表达式。

变量插值功能（variable interpolation，即将变量的值作为正则表达式的一部分）可能会给缓存造成麻烦。例如对 m/^Subject：·\Q $DesiredSubject\E\s＊$/来说，每次循环中正则表达式的内容可能会发生改变，因为它取决于插值变量，而这个变量的值可能会变化。如果每次都会不同，那么正则表达式每次都需要编译，完全不能重复利用。

尽管正则表达式可能每次循环都会变化，但这并不是说任何时候都需要重新编译。折中的优化措施就是检查插值后的结果（也就是正则表达式的具体值），只有当具体值发生变化时才重新编译。不过，如果变化的几率很小，大多数时候就只需要检查（而不需要编译），优化效果很明显。

程序式处理中的编译缓存

在集成式处理中，正则表达式的使用与其在程序中所处的具体位置相关，所以再次执行这段代码时，编译好的正则表达式就能够缓存和重复使用。但是，程序式处理中只有通用的“应用此表达式”的函数。也就是说，编译形式并不与程序的具体位置相连，下次调用此函数时，正则表达式必须重新编译。从理论上来说就是如此，但是在实际应用中，禁止尝试缓存的效率无疑很低。相反，优化通常是把最近使用的正则表达式模式（regex pattern）保存下来，关联到最终的编译形式。

调用“应用此表达式”函数之后，作为参数的正则表达式模式会与保存的正则表达式相比较，如果存在于缓存中，就使用缓存的版本。如果没有，就直接编译这个正则表达式，将其存入缓存（如果缓存有容量限制，可能会替换一个旧的表达式）。如果缓存用完了，就必须放弃（thrown out）一个编译形式，通常是最久未使用的那个。

GNU Emacs的缓存能够保存最多20个正则表达式，Tcl能保存30个。PHP能保存四千多个。.NET Framework在默认情况下能保存15个表达式，不过数量可以动态设置，也可以禁止此功能（☞432）。

缓存的大小很重要，因为如果缓存装不下循环中用到的所有正则表达式，在循环重新开始时，最开始的正则表达式会被清除出缓存，结果每个正则表达式都需要重新编译。

面向对象式处理中的编译缓存

在面向对象式处理中，正则表达式何时编译完全由程序员决定。正则表达式的编译是用户通过New Regex、re.compile和Pattern.compile（分别对应.NET、Python和java.util.regex）之类的构造函数来进行的。第3章的简单示例对此做了介绍（从第95页开始），编译在正则表达式实际应用之前完成，但是它们也可以更早完成（有时候可以在循环之前，或者是程序的初始化阶段），然后可以随意使用。在第 235、237 和238 页的性能测试中体现了这一点。

在面向对象式处理中，程序员通过对象析构函数抛弃（thrown away）编译好的正则表达式。及时抛弃不需要的编译形式能够节省内存。

预查必须字符/子字符串优化

相比正则表达式的完整应用，在字符串中搜索某个字符（或者是一串字符）是更加“轻量级”的操作，所以某些系统会在编译阶段做些额外的分析，判断是否存在成功匹配必须的字符或者字符串。在实际应用正则表达式之前，在目标字符串中快速扫描，检查所需的字符或者字符串——如果不存在，根本就不需要进行任何尝试。

举例来说，「^Subject：·（.＊）」的‘Subject：·’是必须出现的。程序可以检查整个字符串，或者使用Boyer-Moore搜索算法（这是一种很快的文件检索算法，字符串越长，效率越高）。没有采用 Boyer-Moore 算法的程序进行逐个字符检查也可以提高效率。选择目标字符串中不太可能出现的字符（例如‘Subject：·’中的‘t’之后的‘：’）能够进一步提高效率。

正则引擎必须能识别出，「^Subject：·（.＊）」的一部分是固定的文本字符串，对任意匹配来说，识别出「this|that|other」中‘th’是必须的，需要更多的工夫，而且大多数正则引擎不会这样做。此问题的答案并不是黑白分明的，某个实现方式或许不能识别出‘th’是必须的，但能够识别出‘h’和‘t’都是必须的，所以至少可以检查一个字符。

不同的应用程序能够识别出的必须字符和字符串有很大差别。许多系统会受到多选结构的干扰。在这种系统中，使用「th（is|at）」的表现好于「this|that」。同样，请参考第 247 页的“开头字符/字符组/子串识别优化”。

长度判断优化

「^Subject：·（.＊）」能匹配文本的长度是不固定的，但是至少必须包含 9 个字符。所以，如果目标字符串的长度小于 9 则根本不必尝试。当然，需要匹配的字符更长优化的效果才更明显，例如「：\d{79}：」（至少需要81个字符）。

请参见第247页的“长度识别传动优化”。

通过传动装置进行优化

Optimizations with the Transmission

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

字符串起始/行锚点优化

这种优化措施能够判断，任何以「^」开头的正则表达式只能在「^」能够匹配的情况下才可能匹配，所以只需要在这些位置应用即可。

在“预查必须字符/子字符串优化”中提到，正则引擎必须判断对某个正则表达式来说有哪些可行的优化，在这里同样有效。任何使用此优化的实现方式都必须能够识别：如果「^（this|that）」匹配成功，「^」必须能够匹配，但许多实现方式不能识别「^this|^that」。此时，用「^（this|that）」或者「^（？：this|that）」能够提高匹配的速度。

同样的优化措施还对「\A」有效，如果匹配多次进行，对「\G」也有效。

隐式锚点优化

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

更聪明的系统能够认识到，即使开头的「.＊」或「.+」在括号内，也可以进行同样的优化，但是在遇到捕获括号时必须小心。例如，「（.+）X\1」期望匹配的是字符串在‘X’两侧是相同的，添加「^」就不能匹配（注5）。

字符串结束/行锚点优化

这种优化遇到末尾为「$」或者其他结束锚点（☞129）的正则表达式时，能够从字符串末尾倒数若干字符的位置开始尝试匹配。例如正则表达式「regex（es）？$」匹配只可能从字符串末尾倒数的第8个字符（注6）开始，所以传动装置能够跳到那个位置，略过目标字符串中许多可能的字符。

开头字符/字符组/子串识别优化

这是“预查必须字符/子字符串优化”的更一般的版本，这种优化使用同样的信息（正则表达式的任何匹配必须以特定字符或文字子字符串开头），容许传动装置进行快速子字符串检查，所以它能够在字符串中合适的位置应用正则表达式。例如，「this|that|other」只能从「[ot]」的位置开始匹配，所以传动装置预先检查字符串中的每个字符，只在可能匹配的位置进行应用，这样能节省大量的时间。能够预先检查的子串越长，“错误的开始位置”就越少。

内嵌文字字符串检查优化

这有点类似初始字符串识别优化，不过更加高级，它针对的是在匹配中固定位置出现的文字字符串。如果正则表达式是「\b（perl|java）\.regex\.info\b」，那么任何匹配中都要有‘.regex.info’，所以智能的传动装置能够使用高速的Boyer-Moore字符串检索算法寻找‘.regex.info’，然后往前数4个字符，开始实际应用正则表达式。

一般来说，这种优化只有在内嵌文字字符串与表达式起始位置的距离固定时才能进行。因此它不能用于「\b（vb|java）\.regex\.info\b」，这个表达式虽然包含文字字符串，但此字符串与匹配文本起始位置的距离是不确定的（2个或4个字符）。这种优化同样也不能用于「\b（\w+）\.regex\.info\b」，因为「（\w+）」可能匹配任意数目的字符。

长度识别传动优化

此优化与 245 页的长度识别优化直接相关，如果当前位置距离字符串末尾的长度小于成功匹配所需最小长度，传动装置会停止匹配尝试。

优化正则表达式本身

Optimizations of the Regex Itself

文字字符串连接优化

也许最基本的优化就是，引擎可以把「abc」当作“一个元素”，而不是三个元素“「a」，然后是「b」，然后是「c」”。如果能够这样，整个部分就可以作为匹配迭代的一个单元，而不需要进行三次迭代。

化简量词优化

约束普通元素——例如文字字符或者字符组——的加号、星号之类的量词，通常要经过优化，避免普通NFA引擎的大部分逐步处理开销（step-by-step overhead）。正则引擎内的主循环必须通用（general），能够处理引擎支持的所有结构。而在程序设计中，“通用”意味着“速度慢”，所以此种优化把「.＊」之类的简单量词作为一个“整体”，正则引擎便不必按照通用的办法处理，而使用高速的，专门化的处理程序。这样，通用引擎就绕过（short-circuit）了这些结构。

举例来说，「.＊」和「（？：.）＊」在逻辑上是相等的，但是在进行此优化的系统中，「.＊」实际上更快。举一些例子：在java.util.regex中，性能提升在10%左右，但是在Ruby和.NET中，大概是2.5倍。在Python中，大概是50倍。在PHP/PCRE中，大概是150倍。因为Perl实现了下一节介绍的优化措施，「.＊」和「（？：.）＊」的速度是一样的（请参考下一页的补充内容，了解如何解释这些数据）。

消除无必要括号

如果某种实现方式认为「（？：.）＊」与「.＊」是完全等价的，那么它就会用后者替换前者。

消除不需要的字符组

只包含单个字符的字符组有点儿多余，因为它要按照字符组来处理，而这么做完全没有必要。所以，聪明的实现方式会在内部把「[.]」转换为「\.」。

忽略优先量词之后的字符优化

忽略优先量词，例如「＂（.＊？）＂」中的‘＊？’，在处理时，引擎通常必须在量词作用的对象（点号）和「＂」之后的字符之间切换。因为种种原因，忽略优先量词通常比匹配优先量词要慢，尤其是对上文中“化简量词优化”的匹配优先限定结构来说，更是如此。另一个原因是，如果忽略优先量词在捕获型括号之内，控制权就必须在括号内外切换，这样会带来额外的开销。

所以这种优化的原理是，如果文字字符跟在忽略优先量词之后，只要引擎没有触及那个文字字符，忽略优先量词可以作为普通的匹配优先量词来处理。所以，包含此优化的实现方式在这种情况下会切换到特殊的忽略优先量词，迅速检测目标文本中的文字字符，在遇到此文字字符之前，跳过常规的“忽略”状态。

此优化还有各种其他形式，例如预查一组字符，而不是特殊的一个字符（例如，检查「['＂] （.＊？）[＂']」中的「['＂]」，这有点类似前面介绍的开头字符识别优化）。

“过度”回溯检测

第226页的“实测”揭示的问题是，「（.+）＊」之类的量词结合结构，能够制造指数级的回溯。避免这种情况的简单办法就是限定回溯的次数，在“超限”时停止匹配。在某些实际情况中这非常有用，但是它也为正则表达式能够应用的文本人为设置了限制。

例如，如果上限是10 000次回溯，「.＊？」就不能匹配长于10 000的字符，因为每个匹配的字符都对应一次回溯。这种情况并不罕见，尤其在处理Web页时更是如此，所以这种限制非常糟糕。

出于不同的原因，某些实现方式限制了回溯堆栈的大小（也就是同时能够保存的状态的上限）。例如，Python的上限是10 000。就像回溯上限一样，这也会限制正则表达式所能处理的文本的长度。

因为存在这个问题，本书中的某些性能测试构建起来非常困难。为了获得最准确的结果，性能测试中计时部分应该尽可能多地完成正则表达式的匹配，所以我创建了极长的字符串，比较例如「＂（.＊）＂」，「＂（.）＊＂」，「＂（.）＊？＂」和「＂（[^＂]）＊？＂」的执行时间。为了保证结果有意义，我必须限制字符串的长度，以避免回溯计数或者堆栈大小的限制。你可以在 239 页看到这个例子。

避免指数级（也就是超线性super-linear）匹配

避免无休止的指数级匹配的更好办法是，在匹配尝试进入超线性状态时进行检测。这样就能做些额外的工作，来记录每个量词对应的子表达式尝试匹配的位置，绕过重复尝试。

实际上，超线性匹配发生时是很容易检测出来的。单个量词“迭代”（循环）的次数不应该比目标字符串的字符数量更多。否则肯定发生了指数级匹配。如果根据这个线索发现匹配已经无法终止，检测和消除冗余的匹配是更复杂的问题，但是因为多选分支匹配次数太多，这么做或许值得。

检测超线性匹配并迅速报告匹配失败的副作用（side effect）之一就是，真正缺乏效率的正则表达式并不会体现出效率的低下。即使使用这种优化，避免了指数级匹配，所花的时间也远远高于真正需要的时间，但是不会慢到很容易被用户发现（不像是等到太阳落山一样漫长，而可能是多消耗1/100s，对我们来说这很快，但对计算机来说很漫长）。

当然，总的来看可能还是利大于弊。许多人不关心正则表达式的效率——它们对正则表达式怀着一种恐惧心理，只希望能完成任务，而不关心如何完成。（你可能没见过这种情况，但是我希望这本书能够加强你的信心，就像标题说的那样，精通正则表达式）。

使用占有优先量词削减状态

由正常量词约束的对象匹配之后，会保留若干“在此处不进行匹配”的状态（量词每一轮迭代创建一个状态）。占有优先量词（☞142）则不会保留这些状态。具体做法有两种，一

种是在量词全部尝试完成之后抛弃所有备用状态，效率更高的办法是每一轮迭代时抛弃上一轮的备用状态（匹配时总需要保存一个状态，这样在量词无法继续匹配的时候引擎还能继续运转）。

在迭代中即时抛弃状态的做法效率更高，因为所占的内存更少。应用「.＊ 」会在匹配每个字符时创造一个状态，如果字符串很长，会占用大量的内存。

量词等价转换

有人习惯用「\d\d\d\d」，也有人则习惯使用量词「\d{4}」。两者的效率有差别吗？对NFA来说，答案几乎是肯定的，但工具不同，结果也不同。如果对量词做了优化，则「\d{4}」会更快一些，除非未使用量词的正则表达式能够进行更多的优化。听起来有点迷惑？但事实确实如此。

我的测试结果表明，Perl、Python、PHP/PCRE和.NET中，「\d{4}」大概要快20%。但是，如果使用Ruby和Sun的Java regex package，「\d\d\d\d」则要快上好几倍。所以，看起来量词在某些工具中要更好一些，在另一些工具中则要差一些。不过，情况远非如此简单。

比较「====」和「={4}」。这个例子与上面的截然不同，因为此时重复的是确定的文字字符，而直接使用「====」引擎更容易将其识别为一个文字字符串。如果是，支持的高效的开头字符/字符组/子串识别优化（☞247）就可以派上用场。对Python和Sun的Java regex package来说，情况正是如此，「====」比「={4}」快上100倍。

Perl、Ruby和.NET的优化手段更高级，它们不会区分「====」和「={4}」，结果，两者是一样快的（而且都比「\d\d\d\d」和「\d{4}」的例子快成百上千倍）。

需求识别

另一种简单的优化措施是，引擎会预先取消它认为对匹配结果没有价值的（例如，在不必捕获文本的地方使用了捕获型括号）工作。识别能力在很大程度上依赖于编程语言，不过这种优化实现起来也可以很容易，如果在匹配时能够指定某些选项，就能禁止某些代价高昂的特性。

Tcl就能够进行这种优化。除非用户明确要求，否则它的捕获型括号并不会真正捕获文本。而.NET的正则表达式提供了一个选项，容许程序员指定捕获型括号是否需要捕获。