元字符
- 正则表达式使用一些特定的元字符来检索、匹配和替换符合规则的字符串
- 元字符：普通字符、标准字符、限定字符（量词）、定位字符（边界字符）
正则表达式引擎
- 正则表达式是一个用正则符号写出来的公式
- 程序对正则表达式进行语法分析，建立语法分析树
- 再根据语法分析树结合正则表达式引擎生成执行程序（状态机），用于字符匹配
- 正则表达式引擎是一套核心算法，用于建立状态机
- 小结
- 正则表达式 => 语法分析树
- 语法分析树 + 正则表达引擎 => 状态机 => 用于字符匹配
- 目前实现正则表达式引擎的方式有两种
- DFA自动机（Deterministic Finite Automaton，确定有限状态自动机）
- NFA自动机（Nondeterministic Finite Automaton，非确定有限状态自动机）
- DFA自动机的构造代价远大于NFA自动机，但DFA自动机的执行效率高于NFA自动机
- 假设一个字符串的长度为n，如果采用DFA自动机作为正则表达式引擎，则匹配的时间复杂度为O(n)
- 如果采用NFA自动机作为正则表达式引擎，NFA自动机在匹配过程中存在大量的分支和回溯，假设NFA的状态数为s，
- 则匹配的时间复杂度为O(ns)
- NFA自动机的优势是支持更多高级功能，但都是基于子表达式独立进行匹配
- 因此在编程语言里，使用的正则表达式库都是基于NFA自动机实现的
NFA自动机
匹配过程
- NFA自动机会读取正则表达式的每一个字符，拿去和目标字符串匹配
- 匹配成功则换正则表达式的下一个字符，反之就继续就和目标字符串的下一个字符进行匹配
text="aabcab" regex="bc"
回溯
- 用NFA自动机实现的比较复杂的正则表达式，在匹配过程中经常会引起回溯问题
- 大量的回溯会长时间占用CPU，从而带来系统性能开销
text="abbc"
regex="ab{1,3}c"
读取正则表达式第一个匹配符a和字符串第一个字符a进行比较，a对a，匹配
读取正则表达式第二个匹配符b{1,3}和字符串的第二个字符b进行比较，匹配，但b{1,3}表示1~3个字符，而NFA自动机具有贪婪特性，所以不会读取正则表达式的下一个匹配符c
使用b{1,3}和字符串的第四个字符c进行比较，发现不匹配，此时就会发生回溯，已经读取的字符串第四个字符c将被吐出去，指针回到第三个字符b的位置
发生回溯后，读取正则表达式的下一个匹配符c，和字符串的第四个字符c进行比较，结果匹配
避免回溯
避免回溯的方法：使用懒惰模式和独占模式
贪婪模式（Greedy）
- 在数量匹配中，如果单独使用+、？、*、{min,max}等量词，正则表达式会匹配尽可能多的内容
- text=”abbc” , regex=”ab{1,3}c”，发生了一次匹配失败，就会引起一次回溯
- text=”abbbc” , regex=”ab{1,3}c”，匹配成功
懒惰模式（Reluctant）
- 在懒惰模式下，正则表达式会尽可能少地重复匹配字符，如果匹配成功，会继续匹配剩余的字符串
- 使用?开启懒惰模式，text=”abc” , regex=”ab{1,3}?c”
- 匹配结果是”abc”，在该模式下NFA自动机首先选择最小的匹配范围，即匹配1个b字符，避免了回溯问题
独占模式（Possessive）
- 和贪婪模式一样，独占模式一样会最大限度地匹配更多内容，但在匹配失败时会结束匹配，不会发生回溯问题
- 使用+开启懒惰模式，text=”abbc” , regex=”ab{1,3}+bc”
- 结果是不匹配，结束匹配，不会发生回溯问题
代码
match("ab{1,3}c", "abbc"); // abbc，贪婪模式，产生回溯
match("ab{1,3}c", "abbbc"); // abbbc，贪婪模式，不产生回溯
match("ab{1,3}?", "abbbb"); // ab，懒惰模式，不产生回溯
match("ab{1,3}+bc", "abbc"); // null，独占模式，不产生回溯
正则表达式的优化
- 少用贪婪模式，多用独占模式（避免回溯）
- 减少分支选择，分支选择类型”(X|Y|Z)”的正则表达式会降低性能，尽量减少使用，如果一定要使用
- 考虑选择的顺序，将比较常用的选择放在前面，使它们可以较快地被匹配
- 提取共用模式，(abcd|abef) => ab(cd|ef)
- 如果是简单的分支选择类型，可以用三次index代替(X|Y|Z)
- 减少捕获嵌套
- 捕获组：把正则表达式中，子表达式匹配的内容保存到以数字编号或显式命名的数组中，一般一个()就是一个捕获组
- 每个捕获组都有一个编号，编号0代表整个匹配到的内容
- 非捕获组：参与匹配却不进行分组编号的捕获组，其表达式一般由(?:exp)组成
- 减少不需要获取的分组，可以提高正则表达式的性能
捕获组
String text = "<input high=\"20\" weight=\"70\">test</input>";
String reg = "(<input.*?>)(.*?)(</input>)";
Pattern p = Pattern.compile(reg);
Matcher m = p.matcher(text);
while (m.find()) {
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>)
// 输出：
// <input high="20" weight="70">test</input>
// <input high="20" weight="70">
// test
// </input>
}
非捕获组
String text = "<input high=\"20\" weight=\"70\">test</input>";
String reg = "(?:<input.*?>)(.*?)(?:</input>)";
Pattern p = Pattern.compile(reg);
Matcher m = p.matcher(text);
while (m.find()) {
System.out.println(m.group(0));// 整个匹配到的内容
System.out.println(m.group(1));//(.*?)
// 输出
// <input high="20" weight="70">test</input>
// test
}
小结
在做好性能测试的前提下，可以使用正则表达式，否则能不用就不用，避免造成更多的性能问题.
文章的话到这里就结束了，希望大家在性能测试中，对正则表达式有自己的认识。今日的性能篇到此结束！
