正则表达式的优化

正则表达式的优化

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

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

正则表达式引擎

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

引擎 编程语言 / 程序
DFA egrep(大多数版本), MySql
传统 NFA GNU Emacs, Java, grep(大部分版本),.NET, Perl, PHP, Python, Ruby
POSIX NFA mawk(), GNU Emacs(明确指定时)
DFA/NFA 混合 GNU awk,GUN grep/egrep, Tel

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

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

下面根据例子,更好的说明匹配过程:

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

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

继续下去,to成功匹配,表达式中有三个多选分支,执行其一其他备用,假设按顺序选择。no无法匹配 'ni' ,尝试下一分支,k显然会立即失败,尝试nightnig也无法匹配 '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个字符,引擎将报告失败而不检查整个正则表达式。

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

匹配优先和忽略优先量词

规则 常用表达式 说明
匹配优先/greedy *, +, ?, {m, n} 优先匹配最大长度,匹配尽可能多的内容
忽略优先/reluctan *?, +?, ??, {m, n}? 尽可能匹配最少内容,满足下限即成功

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

占有优先量词和固化分组

固化分组

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

(?>.*?)

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

「\w+:」  匹配 subject

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

占有优先量词

规则 常用表达式 说明
匹配优先/greedy *, +, ?, {m, n} 优先匹配最大长度,匹配尽可能多的内容
占有优先/possesive *+, ++, ?+, {m, n}+ 优先匹配最大长度,放弃备用状态

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

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

如何优化正则表达式

现在考虑一个例子:

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

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

环视结构

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

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

规则 常用表达式 说明
Positive lookahead (?=X) 肯定型,先向后(右)匹配与X相符内容
Negative lookahead (?!X) 否定型,先向后(右)匹配与X不相符内容
Positive lookbehind (?<=X) 肯定型,先向前(左)匹配与X相符内容
Negative lookbehind (?<!X) 否定型,先向前(左)匹配与X不相符内容

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