大家好，上一篇我们聊了正则表达式的基础知识。

在高并发的场景中，有没有遇到过，CPU飙升，但无从下手？正则表达式是”吃CPU”的得力干将之一，以相同的并发量，案例为用正则表达式和不用直接打印，用了正则表达式的CPU使用率是不用正则不表示的2倍。

本文我们一起聊聊正则表达式的进阶知识，如何优化，才能达到性能最优，最大限度的减少正则表达式”吃CPU”。

大纲

正则表达式引擎

正则表达式引擎是处理正则表达式的核心组件，它负责解析和执行正则表达式。

概念与功能

正则表达式引擎是一套核心算法，用于处理由正则符号写出的公式。当给定一个正则表达式和一个字符串时，引擎会分析正则表达式，并根据这个分析来匹配字符串中的特定部分。

正则表达式引擎的主要功能是快速且高效地过滤和匹配字符串，从而实现对字符串的复杂控制。

分类

正则表达式引擎主要可以分为两大类：确定型有穷自动机（DFA，Deterministic Finite Automaton）和非确定型有穷自动机（NFA，Non-deterministic Finite Automaton）。

DFA

确定型有穷自动机（DFA，全称Deterministic Finite Automaton）是一种有穷级数模型，它的每一步操作都是确定的。具体地说，当面对一个输入符号时，它转换到的是一个唯一确定的状态。确定型有穷自动机在多个领域都有应用，特别是在构造各种软件时。它们提供了一种形式化的方式来描述和处理输入序列，从而根据预定义的规则进行状态转换和决策。

NFA

非确定型有穷自动机（NFA，Nondeterministic Finite Automaton）是一种有限状态自动机，与确定型有穷自动机（DFA）相比，其每一步操作可能具有多个选择。也就是说，当面对一个输入符号时，非确定型有穷自动机可以转换到多个不同的状态，而不是像DFA那样只转换到一个确定的状态。

非确定型有穷自动机的一个关键特性是其灵活性。由于NFA在每一步可以有多个选择，这使得NFA在编译原理中特别有用，例如在正则表达式的匹配和词法分析器的实现中。

DFA与NFA区别

两者之间的主要区别在于面对一个输入符号时，NFA可能转换到多个状态，而DFA只能转换到一个确定的状态。此外，NFA的开始状态是一个开始状态集，而DFA的开始状态是唯一的。

执行过程

建立语法树

当正则表达式引擎接收到一个正则表达式和待匹配的字符串时，它会首先根据正则表达式的语法进行分析，建立一个语法分析树。

生成执行程序

接着，引擎会根据这个分析树和正则表达式引擎的算法生成一个执行程序，这个执行程序通常被称为状态机或状态自动机。

尝试匹配

状态机会按照正则表达式的规则，在待匹配的字符串中尝试匹配，直到找到符合规则的部分或确定无法匹配为止。

栗子

那么NFA到底如何匹配的呢，我们以以下内容举例

text = "great"
regex = "ea"

NFA 自动机读取正则表达式的每个字符，和目标字符串匹配，匹配成功则换正则表达式的下一个字符，反之就继续和目标字符串的下一个字符匹配。

下面图解具体过程。

读取正则表达式的第一个匹配符和字符串的第一个字符进行比较，e 对 g，不匹配；继续换字符串的下一个字符，也就是 r，不匹配；继续换下一个，是 e，匹配；

同理，读取正则表达式的第二个匹配符和字符串的第四个字符进行比较，a 对 a，匹配；继续读取正则表达式的下一个字符，然而后面已经没有可匹配的字符了，结束。

这就是 NFA 自动机的匹配过程，实际应用中，碰到的正则表达式都比栗子复杂很多，但万变不离其宗，匹配方法是一样的。

特点

正则表达式引擎具有灵活性、逻辑性和功能性强的特点，可以迅速且简单地实现字符串的复杂控制。

正则表达式引擎是处理正则表达式的核心，它通过分析正则表达式的语法，生成状态机，并在字符串中执行匹配操作，从而实现对字符串的高效过滤和匹配。

NFA自动机的回溯

NFA自动机的回溯是其在处理输入字符串时的一种重要机制，特别是在匹配正则表达式时。回溯的本质在于，当NFA自动机在匹配过程中遇到多种可能的路径时，它会尝试所有可能的路径，直到找到一个成功的匹配或确定无法匹配为止。

解释

具体来说，当NFA自动机读取一个输入字符时，它会根据当前状态和输入字符，尝试转移到多个可能的状态。如果某个转移导致无法继续匹配（例如，因为后续字符不匹配或状态转移函数没有定义），NFA自动机就会回溯到之前的某个状态，重新尝试其他可能的路径。

栗子

text = "greet"
regex = "gre{1,3}t"

上面的例子，匹配目的很简单。匹配以 gr 开头，以 t 结尾，中间有 1-3 个 e 字符的字符串。NFA 自动机对其解析的过程是这样的：

读取正则表达式第一个匹配符 g 和字符串第一个字符 g 进行比较，g 对 g，匹配；继续换字符串的下一个字符，也就是 r，匹配。

读取正则表达式第一个匹配符 e{1,3} 和字符串的第三个字符 e 进行比较，匹配。但因为 e{1,3} 表示 1-3 个 e 字符串，NFA 自动机又具有贪婪特性，所以此时不会继续读取正则表达式的下一个匹配符，而是依旧使用 e{1,3} 和字符串的第四个字符 e 进行比较，结果还是匹配。

继续使用 e{1,3} 和字符串的第五个字符 t 进行比较，发现不匹配了，此时就会发生回溯，已经读取的字符串第五个字符 t 将被吐出去，指针回到第四个字符 e 的位置。

那么发生回溯以后，匹配过程怎么继续呢？程序会读取正则表达式的下一个匹配符 t，和字符串中的第五个字符 t 进行比较，结果匹配，结束。

正则表达式的匹配模式

正则表达式引擎匹配模式分为贪婪模式、勉强模式和侵占模式。这些模式主要影响量词（如 * 、 + 和 ? ）的匹配行为。

贪婪模式（Greedy）

概念

在匹配过程中，尽可能多地选择匹配内容，然后逐个递减，直到匹配成功。

也就是在数量匹配中，如果单独使用 + 、 ? 、 * 或 (min,) 等量词，正则表达式会匹配尽可能多的内容。

栗子

text = "greet"
regex = "gre{1,3}t"

就是在贪婪模式下，NFA自动机读取了最大的匹配范围，即匹配 3 个 e 字符。匹配发生了一次失败，就引起了一次回溯。如果匹配结果是 “greeet”，就会一次性全部匹配成功。

text = "greeet"
regex = "gre{1,3}t"

勉强模式（Reluctant）

概念

在匹配过程中，尽可能少地选择匹配内容，然后逐个增加，直到匹配成功。也被称为懒惰模式。也就是在贪婪模式字符的后面添加一个 ? 来表示的。

栗子

text = "greet"
regex = "gre{1,3}?t"

匹配结果是“greet”，该模式下 NFA 自动机会选择最小的匹配范围，即匹配 2 个 e 字符，因此避免了回溯问题。

侵占模式（Possessive）

概念

类似于贪婪模式，但在匹配过程中，匹配失败就结束，不会进行回溯。

也就是在贪婪模式字符的后面添加一个 + 来表示的。

栗子

text = "greet"
regex = "gre{1,3}+t"

结果是不匹配，结束匹配，不会发生回溯问题。

正则表达式的优化

正则表达式的优化是一个需要根据具体情况进行的过程。不同的正则表达式引擎和不同的应用场景可能需要不同的优化策略。因此，在优化正则表达式时，建议结合实际情况进行测试和调整。

通过优化正则表达式，可以节省CPU的使用时间，最大程度的减少正则表达式“吃掉”CPU，提高系统的整体性能。

简化模式

避免使用复杂的嵌套和重复结构

//推荐
ab(c|d)
//避免
(abc|abd)

枚举中，都存在ab字符，c和d为不同的，应将相同部分提取在外面，枚举的范围尽可能的小。

字符类替代枚举类

//推荐
[a-c]
//代替单个字符的枚举
a|b|c

减少回溯

明确匹配范围，避免宽泛量词

//推荐
[0-9]{16,19}
//避免
[0-9]{1,} 
[0-9]{12,} 
 [0-9]*
[0-9]+

16位到19位的数字匹配，已经明确为为16位到19位，应限定具体范围，避免范围过大或不确定

指定字符串的开始和结束

使用 ^ 和 $ 来分别指定字符串的开始和结束，确保正则表达式从字符串的开始到结束进行整体匹配，减少不必要的搜索。

确定性的模式放在前面

//推荐
([0-9]{4})([0-9]{12,15})
//避免
([0-9]{12,15})([0-9]{4})

16到19位的数字，取前4位固定的，为确定的，放前面，后面12到15位为变化的，存在一定的不确定性，放后面。

避免贪婪匹配

使用非贪婪量词替代贪婪量词

贪婪量词

*、+、?和{n,}

非贪婪量词

*?、+?、??和{n,}?

使用非捕获组

捕获组

指把正则表达式中，子表达式匹配的内容保存到以数字编号或显式命名的数组中，方便后面引用。一般一个 () 就是一个捕获组，捕获组可以进行嵌套。

非捕获组

指参与匹配却不进行分组编号的捕获组，其表达式一般由 (?:exp) 组成。

避免不必要的捕获，只捕获真正需要的部分。

//推荐
<(?:txnTp)>([0-9]{4})</(?:txnTp)>
或
(<?:txnTp>)([0-9]{4})(</?:txnTp>)
//替代
<(txnTp)>([0-9]{4})</(txnTp)>

我们需要捕获的是txnTp的值，而不需要捕获txnTp，应在txnTp的前面加 ?: 非捕获标识

总结

正则表达式，是Java开发中强大的文本处理工具，具有灵活性和高效性。但在高并发的场景下，正则表达式也很容易引起CPU使用率升高，影响系统整体性能。

通过本文，我们了解到，正则表达式的贪婪模式，会导致回溯，从而引起CPU的使用率升高。

在使用过程中，我们应从多方面入手，减少正则表达式的回溯，最大限度的减少贪婪模式的使用，减少非必要的捕获组，根据使用的具体场景进行优化调整，提升正则表达式的性能及系统的性能。