正则表达式优化技艺总结

正则表达式优化技巧总结

正则引擎的分类
正则引擎可以粗略地分为3类：

以文本为主导的DFA（确定型有穷自动机）以正则表达式为主导的传统型NFA（非确定型有穷自动机）POSIX NFA

部分程序及其使用的正则引擎

DFA
awk（大多数版本）、egrep（大多数版本）、mysql
传统NFA
GNU Emacs、java、grep（大多数版本）、less、more、perl、PHP、sed、vi
POSIX NFA
mawk、GNU Emacs（明确指定时使用）
DFA/NFA混合
GNU awk、GNU grep/egrep


影响正则表达式匹配的重要概念--回溯

??? NFA引擎最重要的性质是，它会依次处理各个子表达式或组成元素，遇到需要在两个可能成功的可能中进行选择的时候，它会选择其一，同时记住另一个，以备稍后可能的需要。需要做出选择的情形包括量词（决定是否尝试另一次匹配） 和多选结构（决定选择哪个多选分去）。
??? 不论选择哪一种途径，如果它匹配成功，而且正则表达式的余下部分也成功了，匹配即告成功。如果正则表达式中余下的部分最终匹配失败，引擎会知道需要回溯到之前做出选择的地方，选择其他的备用分支继续尝试。这样引擎最终会尝试表达式的所有可能途径（或者是匹配完成之前需要的所有途径）。

??? 回溯的两个要点：
??? 如果需要在“进行尝试”和“跳过尝试”之间选择，对于匹配优先量词，引擎会优先选择“进行尝试”，而对于忽略优先量词，会选择“跳过尝试”。
距离当前最近储存的选项就是本地失败强制回溯时返回的。使用的原则是LIFO（后进先出）。
多选结构既不是匹配优先的，也不是忽略优先的，而是按顺序排列的，至少对传统型NFA来说是如此。也不是所有的流派都支持按序排列的多选结构。DFA和POSIX NFA确实有匹配优先的多选结构，它们总是匹配所有多选分支中能匹配最多文本的那个。但是，如果你使用的是Perl、PHP、.NET、java.util.regex，或者其他使用传统型NFA的工具，多选结构就是按序排列的。

??? 性能调优时评价的几个方面：

哪种引擎从中获益？传统型NFA、或者POSIX NFA，或者两者？什么情况下，这种修改带来的收益最大？在文本能够匹配时，无法匹配时，还是所有时候？

技巧：

如果多选分支是有序的，而能够匹配同样文本的多选分支又不只一个，就要小心安排多选分支的先后顺序。加速某些操作。某些类型的匹配，例如\d+，极为常见，引擎可能对此有特殊的处理方案，执行速度比通用的处理机制要快。避免冗余操作。如果引擎认为，对于产生正确结果来说，某些特殊的操作是不必要的，或者某些操作能够应用到比之前更少的文本，忽略这些操作能够节省时间。例如，一个以\A开头的正则表达式只有在字符串的开头位置才能匹配，如果在此处无法匹配，传动装置不会徒劳地尝试其他位置。消除无必要括号。正则引擎对捕获型括号，每次匹配都会记录状态，回退时需要清除状态。除非必要尽量不要使用捕获型括号。消除不需要的字符组。比如使用转义后的\.代替[.]对(.+)*之类的量词结合结构，避免制造指级的回溯使用占有优先量词消减回溯状态使用起始锚点。某些正则引擎会对此类表达式进行匹配优化。提取多选开头的必须元素。比如用th(is|at)代替this|that根据具体情况分析，使用忽略优先还是匹配优先，或使用固化分组和占有优先量词，以减少回溯拆分正则表达式。有时，在代码里多次执行拆分后的正则表达式比用一个正则表达式完成的同样的功能，执行时间反而更少。将最可能匹配的多选分支放在前头消除循环：常用的解法是opening normal*(special normal)*closing。避免无休止匹配的三个要点：1)special部分和normal部分匹配的开头不能重合。2)normal部分必须匹配至少一个字符。3)special部分必须是固化的。 亦可使用固化分组和占有优先量词。

实施优化时请谨记：有得必有失。实施了某个优化，可能对不同的正则引擎执行效率会产生很大的不同。请谨慎测试。

?

查看更多 下一篇