优化正则表达式本身
传统型 NFA 引擎让我们更应该关注正则表达式本身,从表达式本身上进行以下优化:
文字字符串连接优化
这应该是最基本的优化了,正则引擎能把ako
当成“一个元素”进行匹配,而不是a
k
o
。这样就能匹配迭代一个单元,而不是迭代三次。
化简量词优化
该优化避免了NFA
引擎的大部分逐步处理开销。正则引擎中的主循环必须通用,才能处理引擎支持的所有结构,而通用意味着“速度慢”,所以将.*
之类的简单量词作为一个整体,此时正则引擎便不必按通用的办法处理,而使用专门化、高速的处理程序来绕过这些结构。
比如:.*
和(?:.)*
在逻辑上是相等的,而.*
的性能远高于(?:.)*
。
消除非必要括号
若某种实现方式认为(?:.)*
与.*
等价时,则使用后者。
消除非必要字符组
包含单个字符的字符组是多余的。
比如:可以将[.]
转换为\.
。
忽略优先量词之后的字符优化
忽略优先量词通常比匹配优先量词要慢,如果忽略优先量词在捕获型括号内部,其控制权必须在括号内外切换,还会带来额外的开销。该优化的原理就是:若文字字符跟在忽略优先量词之后,只要引擎没有触及那个字符,忽略优先量词可以作为普通的匹配优先量词来处理。
比如,预查一组字符,而不是特殊的一个字符['"](.*?)["']
中的['"]
。
避免“过度”回溯与指数级匹配
时刻注意,不要编写(.+)*
之类的量词结合结构,因为这种结构会制造指数级回溯,效率极低。
使用占有优先量词削减状态
由正常量词约束的对象匹配之后,会保留若干“在此处不进行匹配”的状态(即量词的每一轮迭代创建一个状态),而占有优先量词则不会保留这些状态(每一轮迭代时抛弃上一轮的备用状态)。
比如:使用^\w+:
来匹配Subject
,\w+
匹配到字符串末尾时,最后的冒号无法匹配,回溯机制强迫\w+
逐个交换字符,在每个位置对:进行徒劳的尝试。可以使用固化分组^(?>\w+):
或占有优先量词^\w++:
来避免无谓的劳动。
使用量词进行等价转换
在JavaScript
中,\d\d\d\d
和\d{4}
在逻辑上虽然相同,但在性能上\d{4}
远优于\d\d\d\d
的,所以,编写正则表达式出现类似的结构时,应尽量使用量词对其进行替换。