如何写出高效率的正则表达式

2020-06-05 00:00:00 字符串字符匹配正则表达式括号

正则表达式引擎(DFA/NFA)

NFA 是不确定的有限自动机，也就是说在状态的迁移过程中，下一个状态可能有好几种可能，而对于 DFA 确定有限自动机而言，下一个状态只有一种可能。
DFA引擎因为不需要回溯，所以匹配快速，但不支持捕获组，所以也就不支持反向引用和$number这种引用方式，目前使用DFA引擎的语言和工具主要有awk、egrep 和 lex。
而NFA又基本上可以分为传统型NFA和POSIX NFA，
POSIX NFA主要指符合POSIX标准的NFA引擎，它的特点主要是提供longest-leftmost匹配，也就是在找到左侧长匹配之前，它将继续回溯。同DFA一样，非贪婪模式或者说忽略优先量词对于POSIX NFA同样是没有意义的。

Java使用的是传统型NFA引擎,所以我们接下来讨论的内容也是基于传统型NFA引擎的

效率问题

因为 DFA 在匹配过程中是跟正则表达式无关的，所以接下来效率提升方面的讨论只针对 NFA。
匹配失败发生回朔的次数是一个指标，而为什么会发生回朔呢?
因为基本的元字符是贪婪的 (*, +)，因为有选择性的匹配 (|), 于是在匹配过程中每一次这样的选择，都会记录一个回朔点，在匹配失败时，就会回朔到之前一个回朔点，继续匹配，也就是类似于栈的机制，后进先出。

学会使用工具

在这里安利一个RegexBuddy工具，使用它可以很简单的在各种语言环境下测试、使用以及debug正则表达式，不要使用网页版本的正则表达式匹配工具，那些大多数是匹配js的，有些甚至连js都匹配不准确。

开始优化正则表达式

使用字符组代替分支条件

匹配abcd字符请使用[a-d]而不是使用a|b|c|d,前者匹配一次即可匹配需要的字符，而后者需要进行匹配四次(因为需要进行回溯)

尽量使用锚点优化(^或者$)

如果知道一个字符串开头是什么，尽量使用^,如果知道结尾是什么尽量使用$,它可以从字符串末尾倒数若干个字符开始进行匹配，比如regex$只可能从字符串默认倒数的第五个字符开始匹配，这样可以略过很多字符，达到优化的效果。

尽量使用长度优化

如果你知道一个字符串的长度不超过多少，或者这个字符串是定长的，那么请一定加上长度匹配，比如\d{11}匹配11位的数字，\d{4,8}匹配4到8位的数字，在匹配的时候就不会匹配小于4位的数字。

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

占有优先量词

?+  *+ ++  {m,n}+

占有优先量词与匹配优先量词很相似,只是它们从来不会交还已经匹配的字符。

固化分组

(?>...)       ...是指具体内容

固化分组的内容与正常的匹配并无区别，只是当匹配完括号中的内容后，括号中的备用状态会全部舍去。

是否使用非捕获型括号

在上一篇文章正则表达式的基本使用中指出了使用非捕获型括号有利于性能提升，因为你不在需要捕获文本的开销,但是这也不是必然的，比如(000|999)$使用了非捕获型括号之后反而比之前还变慢了，那是因为非捕获型括号不会使用$这个锚结尾优化，但是大多数时候非捕获型括号都是有益的，所以这个使用就需要自己权衡。

尽可能少的编译

正则表达式的编辑也是需要耗费时间的，不要每次在循环内重新编辑正则表达式

不要滥用括号

只有在需要的时候才使用括号，要不然括号会阻止某些优化措施，比如.*请不要用成(.)\*

不要滥用字符组

字符组使用时有好处，但是不要滥用呀,并不需要用到字符组提供的多字符匹配功能的时候请不要使用字符组

像写代码一样优化

这个是什么意思？其实就是尽量将常量字符串提取出来,将共同的部分提取出来

别写太长的正则表达式

太长的正则表达式效率不一定高，而且后期不好维护，所以尽量不要写太长的表达式，就算有长的也尽量拆分成比较短的正则表达式，能用字符串处理解决的就尽量不用正则表达式。

使用环视模拟开头符识别

如果正则表达式为 Jan|Feb|Dec，对应的就是(?=[JFMASOND])(?:Jan|Feb|Dec)。
开头的[JFMASOND]代表了英文中月份单词可能的开始字母。

将尽可能多的多选分支放在前面

多选分支下尽可能将出现概率比较大的表达式放在前面，比如匹配主机名的表达式中(?:aero|biz|com|cooph|...)的效率没有(?:com|net|edu|org|...)的效率高

消除循环

如果你写了一个较复杂的表达式,可以使用消除循环来提高效率,消除循环的常用解法:

opening normal* (special normal\*)* closing

需要注意的几点

1. special 部分和normal部分匹配的开头不能重合
2. normal 部分必须匹配至少一个字符
3. special部分必须是固化的,部分匹配的文本不能由该部分的多次迭代完成,比如(abc*)*重要比.*好一些

是否必须使用正则表达式?

有时候正则表达式确实能为我们带来便捷，但是滥用正则表达式的后果同样是非常严重的,可能会导致死循环，让你程序的效率显著的下降，所以如果能用字符串解决的问题尽量不使用正则表达式，如果使用正则表达式请尽量多测试，写出高水平的正则表达式。

相关文章