41

正则表达式优化

 4 years ago
source link: https://www.tuicool.com/articles/2ea2ayb
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

正则表达式优化

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

[TOC]

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

引擎

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

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

传统型 NFA(Non-非):

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

标准 POSIX NFA:

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

golang leftmost-first和leftmost-first都支持

混合:Tcl 等

规则

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

回溯

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

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

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

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

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK