正则的匹配原理以及优化原则

简介: 【2月更文挑战第17天】

正则之所以能够处理复杂文本,就是因为采用了有穷状态自动机(finite automaton)。那什么是有穷自动机呢?有穷状态是指一个系统具有有穷个状态,不同的状态代表不同的意义。自动机是指系统可以根据相应的条件,在不同的状态下进行转移。从一个初始状态,根据对应的操作(比如录入的字符集)执行状态转移,最终达到终止状态(可能有一到多个终止状态)。


有穷自动机的具体实现称为正则引擎,主要有 DFA 和 NFA 两种,其中 NFA 又分为传统的 NFA 和 POSIX NFA。

DFA:确定性有穷自动机(Deterministic finite automaton)
NFA:非确定性有穷自动机(Non-deterministic finite automaton)

image.gif

NFA 引擎的工作方式是,先看正则,再看文本,而且以正则为主导。 而DFA 不是这样的,DFA 会先看文本,再看正则表达式,是以文本为主导的。


一般来说,DFA 引擎会更快一些,因为整个匹配过程中,字符串只看一遍,不会发生回溯,相同的字符不会被测试两次。也就是说 DFA 引擎执行的时间一般是线性的。DFA 引擎可以确保匹配到可能的最长字符串。但由于 DFA 引擎只包含有限的状态,所以它没有反向引用功能;并且因为它不构造显示扩展,它也不支持捕获子组。


NFA  以表达式为主导,它的引擎是使用贪心匹配回溯算法实现。NFA  通过构造特定扩展,支持子组和反向引用。但由于 NFA 引擎会发生回溯,即它会对字符串中的同一部分,进行很多次对比。因此,在最坏情况下,它的执行速度可能非常慢。


因为传统的 NFA 引擎“急于”报告匹配结果,找到第一个匹配上的就返回了,所以可能会导致还有更长的匹配未被发现。比如使用正则 pos|posix 在文本 posix 中进行匹配,传统的 NFA 从文本中找到的是 pos,而不是 posix,而 POSIX NFA 找到的是 posix。


POSIX NFA 的应用很少,主要是 Unix/Linux 中的某些工具。POSIX NFA 引擎与传统的 NFA 引擎类似,但不同之处在于,POSIX NFA 在找到可能的最长匹配之前会继续回溯,也就是说它会尽可能找最长的,如果分支一样长,以最左边的为准(“The Longest-Leftmost”)。因此,POSIX NFA 引擎的速度要慢于传统的 NFA 引擎。

image.gif 回溯是 NFA 引擎才有的,并且只有在正则中出现量词或多选分支结构时,才可能会发生回溯。


学习了原理之后,有助于我们写出更好的正则。我们必须先保证正则的功能是正确的,然后再进行优化性能。


1、测试性能的方法

可以使用 ipython 来测试正则的性能,ipython 是一个 Python shell 增强交互工具,在 macOS/Windows/Linux 上都可以安装使用。在测试正则表达式时,它非常有用,比如下面通过一个示例,来测试在字符串中查找 abc 时的时间消耗。

In [1]: import re
In [2]: x = '-' * 1000000 + 'abc'
In [3]: timeit re.search('abc', x)
480 µs ± 8.06 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

image.gif

2、提前编译好正则

编程语言中一般都有“编译”方法,我们可以使用这个方法提前将正则处理好,这样不用在每次使用的时候去反复构造自动机,从而可以提高正则匹配的性能。


3、尽量准确表示匹配范围

比如我们要匹配引号里面的内容,除了写成 “.+?” 之外,我们可以写成 “[^"]+”。使用 [^"] 要比使用点号好很多,虽然使用的是贪婪模式,但它不会出现点号将引号匹配上,再吐出的问题。


4、提取出公共部分

通过上面对 NFA 引擎的学习,相信你应该明白(abcd|abxy)这样的表达式,可以优化成ab(cd|xy),因为 NFA 以正则为主导,会导致字符串中的某些部分重复匹配多次,影响效率。


因此我们会知道th(?:is|at)要比this|that要快一些,但从可读性上看,后者要好一些,这个就需要用的时候去权衡,也可以添加代码注释让代码更容易理解。


类似地,如果是锚点,比如(^this|^that) is这样的,锚点部分也应该独立出来,可以写成比如^th(is|at) is的形式,因为锚点部分也是需要尝试去匹配的,匹配次数要尽可能少。


5、出现可能性大的放左边

由于正则是从左到右看的,把出现概率大的放左边,域名中 .com 的使用是比 .net 多的,所以我们可以写成\.(?:com|net)\b,而不是\.(?:net|com)\b。


6、只在必要时才使用子组

在正则中,括号可以用于归组,但如果某部分后续不会再用到,就不需要保存成子组。通常的做法是,在写好正则后,把不需要保存子组的括号中加上 ?: 来表示只用于归组。如果保存成子组,正则引擎必须做一些额外工作来保存匹配到的内容,因为后面可能会用到,这会降低正则的匹配性能。


7、警惕嵌套的子组重复

如果一个组里面包含重复,接着这个组整体也可以重复,比如 (.*)* 这个正则,匹配的次数会呈指数级增长,所以尽量不要写这样的正则。


8、避免不同分支重复匹配

在多选分支选择中,要避免不同分支出现相同范围的情况,上面回溯的例子中,我们已经进行了比较详细的讲解。

相关文章
|
4月前
|
Java API 数据安全/隐私保护
访问修饰符 public private protected 及默认情况的区别解析
在Java编程中,访问修饰符(`public`、`private`、`protected`和默认)用于控制类、方法、字段及构造函数的访问范围。`public`允许所有类访问;`private`仅限类内部访问;`protected`允许同一包内或子类访问;默认(无修饰符)仅限同一包内访问。通过合理使用这些修饰符,可实现数据封装、提高安全性和代码可维护性。了解它们的区别与应用场景,是掌握Java面向对象编程的关键。
651 6
|
安全 Java Apache
SpringBoot+Shiro(一)
SpringBoot+Shiro(一)
|
9月前
|
机器学习/深度学习 开发框架 人工智能
操作系统生态兼容与创新的平衡艺术
本次分享的主题是操作系统生态兼容与创新的平衡艺术,由中科方德周杰分享。主要分为五个部分: 1.操作系统生态中的兼容与创新之争 2.版本进化中库兼容与隔离平衡 3.跨架构生态的隔离与统一 4.多系统融合的生态新可能 5.生态兼容与创新平衡
197 2
|
JavaScript 编译器 IDE
36.【TypeScript 教程】tsconfig.json 配置
36.【TypeScript 教程】tsconfig.json 配置
376 0
|
监控 Java 数据安全/隐私保护
Sentinel黑白名单授权规则解读
Sentinel黑白名单授权规则解读
|
JavaScript
Vue3瀑布流(Waterfall)
这是一个基于 Vue2 的瀑布流(Waterfall)组件,支持多种自定义属性,如图片数组、列数、间隙、宽度、圆角、背景色及 Spin 加载样式。组件通过计算每张图片的位置实现动态布局,并利用 Vue 的响应式系统自动调整布局。提供了在线预览和详细代码示例,方便集成到项目中。
597 1
Vue3瀑布流(Waterfall)
|
存储 NoSQL 安全
保障安全与可扩展性:Redis安全设置与集群扩展
本篇深入探讨了Redis的安全性设置以及构建可扩展的Redis集群的方法。我们首先介绍了如何通过设置密码、禁用危险命令和限制访问来加强Redis的安全性。进一步地,我们讨论了如何进行访问控制和权限管理,以确保只有授权用户可以访问和操作Redis。
978 2
保障安全与可扩展性:Redis安全设置与集群扩展
|
算法 Python
Aho-Corasick 算法 AC自动机实现
Aho-Corasick 算法 AC自动机实现
475 0
|
数据采集 JSON JavaScript
|
算法
Aho Corasick Algorithm
Aho Corasick Algorithm
175 0