正则表达式性能优化

今天说一下正则表达式，正则表达式本人也是很少研究，今天看到一些和大家一块学习

什么是正则表达式

正则表达式是计算科学的一个概念，很多语言都实现了他，正则表达式使用一些特定的元字符来检索，匹配以及替换符合规则的字符串。

构造正则表达式的元字符，有普通字符，标准字符，限定字符，定位字符组成

正则表达式是一个用正则符号写出的公式，程序对这个公式进行语法分析，建立一个语法分析树，在根据这个分析树结合正则表达式的引擎生成执行程序，用于字符匹配。而这里的正则表达式引擎就是一套核心算法，用于建立状态机.

目前实现正则表达式引擎的方式有两种,DFA自动机(确定优先状态自动机)和NFA自动机(非确定有限状态自动机)

DFA自动机的代价远大于NFA自动机，但是DFA自动机的执行效率高于NFA自动机。

假设一个字符串的长度是n,如果用DFA自动机的时间复杂度是O(N),但是如果是NFA自动机，且他的状态树是s,则他的时间复杂度是O(ns)，因为他是存在大量的分值和回溯，但是NFA自动机支持更多的功能，例如捕获group ,环视，占有优先量词等高级功能，这个都是基于子表达式独立进行匹配，仅此在编程语言里，使用的正则表达式库都是基于NFA自动机。

NFA是如何进行匹配的呢？正如下面例子

text=“aabcab”
regex=“bc”

1. 首先，读取正则表达式的第一个匹配符合目标字符串匹配，b对a，不匹配，继续换字符串的下一个字符，也就是a,不匹配，继续下一个b,匹配

1. 同理然后拿到正则表达式的第二字符c和字符串第四个字符c比较，匹配，然后在拿下一个正则表达式的字符，发现没有了则结束。

上面是就NFA自动机的匹配过程，日常我们碰到的远比这个复杂，但是匹配的方法是一样的。

NFA自动机回溯

正则表达式在匹配的过程可能产生大量的回溯，引起CPU,从而带来系统性能开销.

text=“abbc”
regex=“ab{1,3}c”

匹配的很简单，匹配以a开头，以c结尾，其中间有1-3个b的字符串，具体过程如下

1. 首先正则表达式第一个匹配符a和字符串第一个字符a匹配

1. 然后取正则表达式的第二字符b和目标字符串匹配的第二字符b匹配，匹配，但是b{1,3}表示是1-3个b,NFA具有贪婪特性，所以此时不会取正则表达式的下一个字符，而是继续b{1,3}和目标字符串第三个字符b匹配，也匹配.

1. 继续拿b{1,3}和目标字符串的第四个字符串匹配，不匹配，则此时发生了回溯，把已经读出的目标字符串的第四个字符c吐了出去，指针回到了第三个字符b的位置

1. 发生回溯之后，在去正则表达式的下一个字符c,和目标字符串第四个字符c进行匹配，匹配，则结束

如何减少回溯

我们发现发生回溯的原因是因为贪婪模式，这和正则表达式匹配模式息息相关，下面我们介绍一下几种模式

贪婪模式

顾名思义，就是在数量匹配中，如果使用+，？*,{min,max}等量词，正则表达式会匹配可能多的内容，如下

text=“abbc”
regex=“ab{1,3}c”

就是在贪婪模式下，NFA自动机读取大量的匹配范围，即匹配三个b字符，匹配发生一次失败，就引起了一次回溯，如果匹配abbbc，就会成功，

text=“abbbc”
regex=“ab{1,3}c”

懒惰模式

在该模式下，正则表达式尽可能少的重复匹配字符，如果匹配成功,就会继续匹配剩余的字符串，例如，上面例子的字符后面加一个？,就可以开启懒惰模式

text=“abc”
regex=“ab{1,3}?c”

匹配的结果是abc,在NFA自动机首先选择最小范围匹配，匹配一个b字符，因此就避免了回溯。

但是懒惰模式是无法完全避免回溯的，可以看看下面例子

text=“abbc”
regex=“ab{1,3}?c”

1. 首先读取正则表达式第一个字符a和目标字符串a匹配，匹配，然后使用正则表达式第二字符b{1,3}?和目标字符串b进行比较，匹配

1. 然后取到正则表达式的第三个字符c和目标字符串第三个字符b进行比较，不匹配

1. 这个时候会发生一次回溯，但是和贪婪模式正好相反，回溯的是正则表达式第二个字符b{1,3}?和目标字符串第三个字符b比较，匹配，则在匹配正则表达式的下一个c和目标字符串的第三个字符c比较，匹配

独占模式

独占模式和贪婪模式一样最大限度的匹配更多内容，不同的是，在独占模式下，匹配失败就会结束匹配，不会发生回溯问题，如上面的例子，字符串添加一个+，就可以开启独占模式

text=“abbc”
regex=“ab{1,3}+bc”

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

我们再看看下面例子

text=“abbc”
regex=“ab{1,3}+c”

匹配成功，这个是因为与贪婪模式一样，独占模式一样会最大限度的匹配更多内容，即匹配完b之后，再去匹配c,则匹配成功。仔细品回溯的概念.

正则表达式的优化

1. 少用贪婪模式，多用独占模式 贪婪模式会一起回溯问题，我们可以使用独占模式来避免回溯
2. 减少分支选择 分支类型(X|Y|Z)的正则表达式会降低性能，我们在开发的时候尽量减少是使用，如果一定使用按照下面规则
   1. 考虑顺序，将比较常用的选择放到前面，使他们可以较快的被匹配
   2. 尝试提取公用模式，例如将(abcd|abef)改成ab(cd|ef),后者匹配速度较快，因为NFA自动机会尝试匹配ab,如果没有找到，就不会再尝试任何选项。
3. 减少捕获嵌套 此时我们要了解什么是捕获组和非捕获组 捕获组是指正则表达式中，子表达式匹配的内容保存在以数字编码或显示命名的数组中，方便后面引用，一般一个()就是一个捕获组，捕获组可以进行嵌套。

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

在正则表达式中，每个捕获组都有一个编码，编号0代表整个匹配到的内容，我们可以看下面例子

public static void main( String[] args )
{
  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>

如果你并不需要获取某一分组的文本，那么就使用非捕获分组，例如，使用(?:exp)代替X

public static void main( String[] args )
{
  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