正则表达式的优化

正则表达式的用途很多，比如web爬虫数据匹配，各种raw数据的清洗，或者是简单的字符串的截取。如果在写循环体内，正则表达式不够高效，会大幅影响性能。

本文主要介绍java中正则表达式的优化，其中很多内容与其他平台相同。

正则表达式引擎

正则表达式的引擎有两大类，分别为DFA和NFA，被主流的编程语言和工具所使用：

其中 Java 的正则表达式引擎是传统的NFA(Nondeterministic Finite Automaton)，一般用其单独支持的忽略优先（Reluctant）量词与其他引擎进行区分。

NFA引擎最主要的性质是回溯（backtracking），在匹配时会依次处理各个子表达式或组成元素，遇到可能成功匹配的分支时，会选择其一同时记住另一个。需要做出分支选择的情况包括量词（决定是否尝试另一次）和多选结构。无论选择哪一分支，如果匹配成功，且表达式余下的部分也全部匹配成功，匹配完成。如果余下部分最终匹配失败，引擎会回溯到之前做出选择的地方，使用备用分支继续匹配。如此反复，直到匹配成功或最终尝试所有可能并失败。

下面根据例子，更好的说明匹配过程：

正则表达式: 「to(note|knight|night)」匹配'hot tonic tonight!'

第一个元素t从最左端开始尝试，匹配到第三个字符 't' ，接下来o无法匹配空格，本轮尝试失败。

继续下去，to成功匹配，表达式中有三个多选分支，执行其一其他备用，假设按顺序选择。no无法匹配 'ni' ，尝试下一分支，k显然会立即失败，尝试night，nig也无法匹配 'nic'，本轮尝试失败。

再往下，重复以上匹配过程，最终多选分支night成功匹配，引擎宣告匹配成功。

回溯优化分析

如果在匹配过程中有过多的回溯，将会影响性能，所以正则表达式优化的一个主要组成部分就是减少回溯次数。

Java模式匹配引擎具有多项优化功能，可以自动应用。 但是，实际情况中无法始终依靠引擎来优化正则表达式。 在上面的例子中，正则表达式实际上匹配得很快，但更多真实的情况是，表达式太复杂，输入字符串太大，引擎优化难以发挥效果。

在现实应用场景中，可能遇到数小时才能完成的匹配。这段时间大部分都花费在不成功的匹配过程上，然后执行无尽的回溯动作，越是接近目标的结果消耗时间越多。

回溯有两个关键性的原则，分别是：

• 如果在“尝试”和“跳过”中选择，遇到“匹配优先量词”则尝试，遇到“忽略优先量词”则跳过
• 回溯分支选择上使用LIFO（last in first out）原则

优化正则表达式的简单方法

此处先介绍一些简单的优化方法：

使用Pattern.compile()编译模式

如果同一正则表达式被多次，确保使用Pattern.compile()编译模式，而不是Pattern.matches()。 因为Pattern.matches()每次调用都会重新编译表达式，如果在循环中会消耗过多不必要的时间。另外，reset()可以重置陪配器。

Pattern p = Pattern.compile("a*b");
Matcher m = p.matcher("aaaaab");
boolean b = m.matches();

优化多选结构

多选结构(X | Y | Z)是效率的一大杀手。 首先，将最常见的内容放在第一位置，以便更快地匹配。 其次，尝试提取常见的模式，例如将(abcd | abef)提取为ab(cd | ef)，NFA引擎尝试匹配ab时，如果匹配失败，将不会尝试任何替代方案。另外，有其他方案替换，如表达式.*(abcd|efgh|ijkl).*比使用三个String.indexOf()的调用慢。

使用非捕获组

获取捕获组会额外消耗一些时间，如果不需要捕获组内的文本，始终使用非捕获组。 例如，使用(?:X)替换(X)。

使用引擎优化

如前所述，java.util.regex引擎可以在编译时以多种方式优化正则表达式。 例如，如果正则表达式包含必须存在的内容块（否则整个表达式将不匹配），则引擎有时可以首先搜索该字符串并报告失败（如果没有找到匹配项） ，而不必检查整个正则表达式。

自动优化的另一个非常有用的方法，是引擎将正则表达式结果预期长度与目标长度进行比对。 例如，表达式\d{100}在内部进行了优化，使得如果输入字符串的长度不是100个字符，引擎将报告失败而不检查整个正则表达式。

所以每当编写复杂的正则表达式时，尝试找到一种书写方式，让引擎能够识别和优化这些特定的情况。 例如，不要将强制匹配的内容块写在分组或替换中，这样引擎将无法识别；如果可能，指定要匹配的输入字符串的长度。

匹配优先和忽略优先量词

一般情况下忽略优先量词会匹配更快，尽量避免使用类似.*的子结构，它会引起过多的回溯，尤其是剩余部分不能匹配时。如在查找两个字符间的所有内容时，使用a([^a]*)a比a(.*)a效率更高。

占有优先量词和固化分组

固化分组

固化分组的结构为(?>X)，如果匹配进行到此结构之后，其内被所有的备用分支都被放弃，即固定分组匹配结束后，其匹配的文本作为一个固化部分，只能整体保留或放弃。在其结构块中，回溯失去了功能，但是可能会影响匹配结果，如下示例：

(?>.*?)

上述表达式无法匹配任何内容，因为.*?为忽略优先模式，默认不匹配内容但保留点好匹配的分支，而固化分组又放弃分支，结果是不匹配任何内容，所以固化分组中使用忽略优先量词时要格外谨慎。下面是一个优化的示例：

「\w+:」  匹配 subject

很显然结果会失败，因为目标字符串不包括冒号，但是\w+是匹配优先，会先匹配subject，遇到冒号失败；然后回溯匹配subjec，如此循环，最终失败。如果使用(?>\w+):匹配，一次性得到匹配失败的结果。

占有优先量词

上表中可以看到，优先占有和匹配优先相比，会放弃备用状态，和固化分组十分相似，如\w++和(?>\w+)的匹配结果完全相同，只是写起来更方便。

写起来相似就会出现混淆的问题。如(X)*+和(?>X)*，前者即X*+，会放弃X子表达式和*整体的备用状态；后者只放弃X的备用状态，如果X中不存在量词匹配问题，那么这样书写就没有意义，改写为(?>X*)后与X*+意义一致。

如何优化正则表达式

现在考虑一个例子：

[^a]*a   匹配字符串：bbbbbbbbbbbbbbbb

由于目标字符串不包含a，匹配结果显然会失败，但是正则表达式匹配引擎并不知道这一点。由于[^a]*是匹配优先模式，失败后会不断回溯。将[^a]*a改为[^a]*+a后，由于占有优先匹配失败时直接失败，不会回溯，效率更高。

环视结构

如果需要匹配某些字符以外的内容，可以使用类似[^abc]*的表达式，它匹配除a或b或c意外的任意字符。但如果需要匹配如abc或cab这种字符串以外的内容，就需要环视结构。

java.util.regex中包含四种环视结构，包括肯定型和否定型，顺序环视和逆序环视，它们只是简单的测试，其中表达式能否在当前的位置匹配后面的内容（顺序），或者前面的内容（逆序），并不改变当前位置。分别是：

上面的问题可以使用((?!abc).)*来匹配，向后查找与abc不同的内容。