正则表达式与优化
- 2020 年 1 月 21 日
- 笔记
整体已整理成思维导图：
1. 元字符
1.1 普通字符
字母[a-zA-Z]，数字[0-9]，下划线[_]，汉字。标点符号等
1.2 标准字符
- 能够与“多种普通字符”匹配的简单表达式
- 比如：d、w、s等
1.3 限定字符
- 用于表示匹配的字符数量
- 比如：*、+、?、{n}等
1.4 定位字符
- “零宽”，标记符合某种条件的位置
- 比如：$,^等。
2.引擎
2.1 DFA自动机
- Deterministic Final Automata 确定有限状态自动机
- 从匹配文本入手，从左到右，每个字符不会匹配两次
2.2 NFA自动机
- Non Deterministic Final Automata 非确定有限状态自动机
- 从正则表达式入手，不断读入字符，尝试是否匹配当前正则，不匹配则吐出字符重新尝试
2.2.1 NFA自动机的回溯
用 NFA 自动机实现的比较复杂的正则表达式，在匹配过程中经常会引起回溯问题。大量的回溯会长时间地占用 CPU，从而带来系统性能开销。
下面以如下为例：
// 待匹配字符串 text = "abbc"; // 正则表达式 regex = "ab{1,3}c";
NFA 自动机对其解析如下：
- 第一步，读取正则表达式第一个匹配符
a和字符串第一个字符a进行比较，a对a，匹配。 - 第二步，读取正则表达式第二个匹配符
b{1,3}和字符串的第二个字符b进行比较，匹配。 - 第三步，因为
b{1,3}表示 1-3 个 b 字符串，NFA 自动机又具有贪婪特性，所以此时不会继续读取正则表达式的下一个匹配符，而是依旧使用b{1,3}和字符串的第三个字符b进行比较，结果还是匹配。 - 第四步，继续使用
b{1,3}和字符串的第四个字符c进行比较，发现不匹配了，此时就会发生回溯，已经读取的字符串第四个字符c将被吐出去，指针回到第三个字符 b 的位置。 - 第五步， 程序会读取正则表达式的下一个匹配符
c，和字符串中的第四个字符c进行比较，结果匹配，结束。
2.3不同
- 构造DFA自动机的代价远大于NFA,但DFA自动机的执行效率高于NFA自动机
- 假设一个字符串的长度是 n，如果用 DFA 自动机作为正则表达式引擎，则匹配的时间复杂度为 O(n)；
- 如果用 NFA 自动机作为正则表达式引擎，由于 NFA 自动机在匹配过程中存在大量的分支和回溯，假设 NFA 的状态数为 s，则该匹配算法的时间复杂度为 O（ns）。
- NFA自动机的优势是支持更多功能。如捕获group、环视、占有优先量词等高级功能。
3. 匹配模式
3.1 贪婪模式（Greedy）
在数量匹配中，如果单独使用 +、 ? 、* 或{min,max} 等量词，正则表达式会匹配尽可能多的内容
3.2 懒惰模式（Reluctant）
- 正则表达式会尽可能少地重复匹配字符。如果匹配成功，它会继续匹配剩余的字符串。
- NFA 自动机首先选择最小的匹配范围
匹配解析
对于如下实例：
// 待匹配字符串 text = "abbc"; // 正则表达式 regex = "ab{1,3}?c";
在网上搜到一篇[《藏在正则表达式里的陷阱》，里面说懒惰模式也会有回溯，具体如下：
- 正则表达式的第一个操作符
a与 字符串第一个字符 a 匹配，匹配成。 - 正则表达式的第二个操作符
b{1,3}?和 字符串第二个字符 b 匹配，匹配成功。 - 因为最小匹配原则，所以拿正则表达式第三个操作符
c与字符串第三个字符b匹配，发现不匹配。 - 此时回溯回去，拿正则表达式第二个操作符
b{1,3}?和字符串第三个字符b匹配，匹配成功。 - 于是再拿正则表达式第三个操作符
c与字符串第四个字符c匹配，匹配成功。于是结束。
询问《Java性能调优实战》专栏的老师被告知与贪婪模式的区别在于它不会使用b{1,3}与c匹配，在匹配完成abb之后，会使用regex中的c匹配text中的c。
3.3 独占模式（Possessive）
- 同贪婪模式一样，独占模式一样会最大限度地匹配更多内容；
- 不同的是，在独占模式下，匹配失败就会结束匹配，不会发生回溯问题。
4. 优化
4.1 少用贪婪模式，多用独占模式
贪婪模式会引起回溯问题，可用独占模式避免
4.2 减少分支选择
分支选择类型“(X|Y|Z)”的表达式会降低性能，尽量减少使用。
4.2.1 分支选择优化
- 比较常用的选择项放在前面，使它们可以较快地被匹配到
- 尝试提取共用模式。例如，将“(abcd|abef)”替换为“ab(cd|ef)”，后者匹配速度较快，因为 NFA 自动机会尝试匹配 ab，如果没有找到，就不会再尝试任何选项；
- 若是简单的分支选择类型，可以用三次index代替“(X|Y|Z)”，前者效率比后者高出一些。index即String中的indexof方法。
4.3 减少捕获嵌套
- 捕获组是指把正则表达式中，子表达式匹配的内容保存到以数字编号或显式命名的数组中，方便后面引用。一般一个
()就是一个捕获组，捕获组可以进行嵌套。 - 非捕获组则是指参与匹配却不进行分组编号的捕获组，其表达式一般由
（?:exp）组成。 - 在正则表达式中，每个捕获组都有一个编号，编号 0 代表整个匹配到的内容。
public static void main( String[] args ){ String text = "<input high="20" weight="70">test</input>"; // reg有三个捕获组：(<input.*?>)、(.*?)、(</input>) String reg="(<input.*?>)(.*?)(</input>)"; // regOfNot有两个非捕获组：(?:<input.*?>)和(?:</input>)，一个捕获组：(.*?) String regOfNot="(?:<input.*?>)(.*?)(?:</input>)"; Pattern p = Pattern.compile(reg); Matcher m = p.matcher(text); while(m.find()) { // group用来提取()分组截获的字符串 System.out.println(m.group(0));// 整个匹配到的内容 System.out.println(m.group(1));//(<input.*?>) System.out.println(m.group(2));//(.*?) System.out.println(m.group(3));//(</input>) } }
最后推荐个可以检查写的正则表达式和对应的字符串匹配时会不会有问题的网站： Online regex tester and debugger: PHP, PCRE, Python, Golang and JavaScript 。
