正则表达式优化 ——《精通正则表达式》总结
[TOC]
第4章：表达式的匹配原理
引擎
DFA (Deterministic Finite Automaton 确定有穷自动机): 常见的只有MySQL，文本主导，不支持反向引用和捕获括号，但快
传统型 NFA(Non-非): 大多数语言，表达式主导，编译快，内存少，写法不同有性能差异
标准 POSIX NFA: leftmost-longest，尝试所有确保最长 golang leftmost-first和leftmost-first都支持
混合：Tcl 等
规则
最左优先，尽可能多(匹配优先)
回溯
NFA 有两个可能时会根据 匹配优先* 还是 忽略优先*?
走其中一个分支，并保存备用状态
如果不成功再回溯尝试另一个分支
第5章：正则表达式实用技巧
(多选|分支)排序可能影响匹配结果
第6章：打造高效正则表达式
减少测试和回溯
- 如果顺序不影响结果时更多匹配的放前面
- 编译
- 传动(从第1个字符开始，从第2个字符开始...)
- 检测(相连 量词{m,n} * (捕获))
- 成功/->2.传动
- 失败
常见措施
编译优化
- 缓存
传动优化
- 锚点(行始
^ A起始G行末$ Z z) - 隐式锚点(
.* .开始) - 开始字符
====比={4}快100倍 - 内嵌字符(Boyer-Moore字符串检索算法后前移, 需要前面固定个数)
- 长度小于时不运行
正则优化
- 连接当做整体
-
.*特殊优化比(?:.)*快(Java 10% Python 50倍) - 消除没必要的括号
- 消除没必要的[字符组]
- 忽略优先量词
*?(尽可能少)通常比匹配优先量词慢 - 限制回溯，避免括号内外都是量词
- 避免指数级(超线性)匹配
- 使用占有优先量词( 不会回溯)减少状态
-
d{4}量词优化比dddd快(Java 几倍 Python 20%) - 引擎识别捕获括号是否需要
诀窍
xx*比x能适应的优化更多- 手工模拟优化
(000|999)$比关闭结束锚点优化的(?:000|999)$快(Perl 几千倍)- 避免重新编译，Perl避免用变量插值
- 使用(?:非捕获型括号)
- 不要滥用括号，如上面的
.*比(?:.)*快 - 不要滥用字符组，
[.]应该用. - 不区分大小写效率低已经修正
- 使用起始锚点
.*开头的前面加^或A - 从量词中提取:
xx*替代x*，-----{0,2}替代-{5,7} - 提取开头:
th(is|at)替代(this|that) - 将锚点独立出来:
^(?:abc|123)替代^abc|^123，^(abc)替代(^abc) - 末尾独立出
$ - 接近开头忽略优先
*?，接近结尾匹配优先 - 拆分成多个正则
- 使用(?>固化分组)和占有优先量词
* - 最可能匹配的分支放前面(POSIX 会全部尝试取最长就不需要)
- 结尾部分分散到各个部分(有些系统不需要如Perl的
$)
消除循环
代码语言：javascript复制"(\.|[^\"] )*"
优化为：
"[^\"]*(\.[^\"]*)*"
公式：
opening normal* (special normal*) closing
左 常规*(特殊 常规*)* 右- 常规和特殊的开头不能重合
- 特殊部分必须匹配至少一个字符
- 特殊部分必须是固化的
方法2:[^\"]匹配更多，如果是转义，后面继续，结果一样
方法3：匹配主机名
代码语言：javascript复制[a-z] (.[a-z] )*使用占有优先量词
代码语言：javascript复制"([^\"] |\.)* "使用固化分组
代码语言：javascript复制"(?>(?>[^\"] |\.)*)"
G(?:^|,)(?:((?>[^"]*)(?>""[^"]*)*)|([^",]*))消除注释
代码语言：javascript复制/*.*?*/
/*([^*]|* [^/*])** /
消除循环
/*[^*]** (?:[^/*][^*]** )*/流畅运转
代码语言：javascript复制块注释=/*[^*]** (?:[^/*][^*]** )*/
行注释=//[^n]*
双引号="[^\"]*(\.[^\"]*)*"
单引号='[^\']*(\.[^\']*)*'
(双引号|单引号)|块注释|行注释
替换为
$1
优化为：
开头集=[^"'/]
(双引号|单引号|开头集 )|块注释|行注释
优化为：
(开头集 |双引号|单引号)|块注释|行注释
优化为：
(开头集 |双引号 开头集*|单引号 开头集*)|块注释|行注释
