正则表达式优化

正则表达式优化

——《精通正则表达式》阅读笔记

[TOC]

第4章：表达式的匹配原理

引擎

DFA (Deterministic Finite Automaton 确定有穷自动机):

常见的只有MySQL，文本主导，不支持反向引用和捕获括号，但快

传统型 NFA(Non-非):

大多数语言，表达式主导，编译快，内存少，写法不同有性能差异

标准 POSIX NFA:

leftmost-longest，尝试所有确保最长

混合 Tcl 等:

Perl、Python、Go(leftmost-first)

规则

最左优先，尽可能多(匹配优先)

回溯

NFA 有两个可能时会根据 匹配优先

*

还是 忽略优先

*?

走其中一个分支，并保存备用状态

如果不成功再回溯尝试另一个分支

第5章：正则表达式实用技巧

(多选|分支)排序可能影响匹配结果

第6章：打造高效正则表达式

减少测试和回溯

• 如果顺序不影响结果时更多匹配的放前面

1. 编译
2. 传动(从第1个字符开始，从第2个字符开始...)
3. 检测(相连 量词{m,n}+* (捕获))
4. 成功/->2.传动
5. 失败

常见措施

编译优化

• 缓存

传动优化

• 锚点(行始

  ^ \A

  起始

  \G

  行末

  $ \Z \z

  )
• 隐式锚点(

  .* .+

  开始)
• 开始字符

  ====

  比

  ={4}

  快100倍
• 内嵌字符(Boyer-Moore字符串检索算法后前移, 需要前面固定个数)
• 长度小于时不运行

正则优化

• 连接当做整体

• .*

  特殊优化比

  (?:.)*

  快(Java 10% Python 50倍)
• 消除没必要的括号
• 消除没必要的[字符组]
• 忽略优先量词

  *?

  (尽可能少)通常比匹配优先量词慢
• 限制回溯，避免括号内外都是量词
• 避免指数级(超线性)匹配
• 使用占有优先量词(+不会回溯)减少状态

• \d{4}

  量词优化比

  \d\d\d\d

  快(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的

  $

消除循环

"(\\.|[^\\"]+)*"

优化为：
"[^\\"]*(\\.[^\\"]*)*"

公式：
opening normal* (special normal*) closing
左 常规*(特殊 常规*)* 右           

1. 常规和特殊的开头不能重合
2. 特殊部分必须匹配至少一个字符
3. 特殊部分必须是固化的

方法2:

[^\\"]

匹配更多，如果是转义，后面继续，结果一样

方法3：匹配主机名

[a-z]+(\.[a-z]+)*           

使用占有优先量词

"([^\\"]++|\\.)*+"           

使用固化分组

"(?>(?>[^\\"]+|\\.)*)"
\G(?:^|,)(?:((?>[^"]*)(?>""[^"]*)*)|([^",]*))           

消除注释

/\*.*?\*/
/\*([^*]|\*+[^/*])*\*+/

消除循环
/\*[^*]*\*+(?:[^/*][^*]*\*+)*/           

流畅运转

块注释=/\*[^*]*\*+(?:[^/*][^*]*\*+)*/
行注释=//[^\n]*
双引号="[^\\"]*(\\.[^\\"]*)*"
单引号='[^\\']*(\\.[^\\']*)*'
(双引号|单引号)|块注释|行注释
替换为
$1

优化为：
开头集=[^"'/]
(双引号|单引号|开头集+)|块注释|行注释

优化为：
(开头集+|双引号|单引号)|块注释|行注释

优化为：
(开头集+|双引号 开头集*|单引号 开头集*)|块注释|行注释