匹配原理与优化原创
# 正则的匹配原理与优化原则
# 有穷状态自动机
- 有穷状态:一个具有有穷个状态的系统
- 自动机:可以根据相应的条件,自动在不同状态下进行转移。
- 有穷自动机的具体实现称为正则引擎,主要有DFA和NFA两种,NFA又包括了传统的NFA和POSIX NFA
# DFA匹配过程
- 以文本为主,先看文本,再看正则
- 整个过程字符串只看一遍,不回溯
- 没有引用功能,也不支持捕获子组
- 代表有MySQL,Golang
# NFA匹配过程
- 以正则为主,先看正则,再看文本
- 会发生回溯,同一字符可能会测多次
- 支持子组,和反向引用
- 代表有Java,Python
- POSIX NFA会尝试所有可能的匹配,返回最长最左的匹配
# 优化
- 使用ipython来测试正则性能
- 提前编译好正则
- 尽量准确表示匹配范围
- 提取公共部分
- 出现可能性大的放左边
- 警惕嵌套子组重复
- 避免不同分支重复匹配