正则表达式优化

林万程 · · 772 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

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

[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

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

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

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

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:林万程

查看原文:正则表达式优化

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

772 次点击  ∙  1 赞  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传