系统优化专题3——正则表达式

2020-10-13 本文已影响0人我菠菜今天就是要为所欲为

正则表达式

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

构造正则表达式语法的元字符由普通字符、标准字符、限定字符(量词)、定位字符(边界字符)组成。如图：

image.png

正则表达式引擎

正则表达式是一个用正则符号写出的公式，程序对这个公式进行语法分析，建立一个语法分析树，再根据分析树结合正则表达式的引擎生成执行程序(这个执行程序我们称为状态机，也叫状态自动机),用于字符匹配。

而这里的正则表达式引擎就是一套核心算法，用于建立状态机。

目前实现正则表达式引擎的方式有两种

DFA自动机(Deterministic Final Automation 确定有限状态自动机)
NFA自动机(Non Deterministic Finite Automation 非确定有限状态自动机)

以下是两种状态机的对比：

状态机	构造代价	执行效率
DFA	远大于NFA	高
NFA	远小于DFA	低

假设，有字符串长度为n，若用DFA自动机作为正则表达式，则匹配的时间复杂度为O(n)；若用NFA自动机作为正则表达式引擎，由于NFA自动机在匹配过程中存在大量分支和回溯，假设NFA的状态数为s，则该匹配算法的时间复杂度为O(ns)。

NFA自动机的优势是支持更多的功能。例如，捕获group、环视、占有优先量词等高级功能。这些功能都是基于子表达式独立进行匹配，因此在编程语言里，使用的正则表达式库都是基于NFA实现的。

那么NFA自动机是如何进行匹配的？

text = "aabcab";
regex = "bc";

首先，读取正则表达式的第一个匹配符b和字符串的第一个字符a进行比较，不匹配；继续换字符串的下一个匹配字符a，不匹配；继续换下一个b，匹配。

image.png

然后，同理，读取正则表达式的第二个匹配符c和字符串的第四个字符c比较，匹配；继续读取正则表达式的下一个字符，下一个字符为空，没有可以匹配的字符，匹配结束。

image.png

以上就是NFA自动机的匹配过程，在实际使用中，碰到的正则表达式都要比这个例子复杂，但匹配的过程是相同的。

NFA自动机的回溯

用NFA自动机实现的比较复杂的正则表达式，在匹配过程中经常会引起回溯问题。大量的回溯会长时间占用CPU，带来系统性能开销。

举例：

text = "abbc";
regex = "ab{1,3}c"

这个例子，匹配的规则比较简单。以a开头，以c结尾，中间包含1-3个b的字符串。NFA自动机对其解析的过程如下:

首先，读取正则表达式第一个匹配符a和字符串第一个字符a比较，匹配。

image.png

然后，读取正则表达式第二个匹配符b{1，3}和字符串的第二个字符b进行比较，匹配。

由于b{1,3}表示1-3个字符串，NFA的贪婪特性不会继续读取正则表达式的下一个匹配符，而是依旧使用b{1,3}和字符串的第三个字符b进行比较，结果还是匹配。

image.png

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

image.png

发生回溯后，程序会读取正则表达式的下一个匹配符c，和字符串的第四个字符c进行比较，结果匹配，正则判断结束。

image.png

如何减少回溯问题

从上面的案例可知，回溯的原因是NFA自动机的贪婪特性，这和正则表达式的匹配模式息息相关。

贪婪模式(Greedy)
故名思意，就是在数量匹配中，如果单独使用+、？、*或{min,max}等量词，正则表达式会匹配尽可能多的内容。
例如上边的例子，在贪婪模式下，NFA自动机读取了最大的匹配范围，匹配发生了一次失败，就引发了一次回溯。
懒惰模式(Reluctant)
在该模式下，正则表达式会尽可能少地匹配字符。如果匹配成功，则继续匹配剩余的字符串。在上例的字符串后加一个'?'就可以开启懒惰模式。
若匹配的字符串是"abc"。
该模式下NFA自动机首选匹配'abc'，即最小范围的匹配一个b字符，因此避免了回溯问题。
懒惰模式是无法完全避免回溯的，上例中匹配字符为"abbc"，那么，首先正则会读取第一个匹配符a和字符串中第一个字符a匹配，成功。然后读取第二个匹配符b{1,3}和字符串的第二个字符b进行比较，匹配。

image.png
其次，懒惰模式下，正则表达式会尽可能少的匹配重复字符，则匹配字符放弃匹配b，转而匹配c。

image.png
此时，匹配字符c与字符串中第二个字符b不匹配，此时会发生回溯，这次的回溯与贪婪模式相反，回溯的是匹配字符c。

image.png
独占模式
同贪婪模式一样，独占模式会最大限度地匹配更多的内容，不同的是，独占模式匹配失败就会结束匹配，不会发生回溯问题。上例中，在字符串后加一个"+"就可以开启独占模式。
```
text = "abbc";
regex = "ab{1,3}+bc";
```
结果是不匹配，不会发生回溯问题。
同样，独占模式也不能避免回溯的发生，如上例
```
text = "abbc";
regex = "ab{1,3}+c";
```
结果是匹配的，因为独占模式会最大限度的匹配更多的内容，完成所有的b，再去匹配c。

优化

少用贪婪模式，多用独占模式
贪婪模式会引起回溯问题，我们可以使用独占模式避免回溯。
减少分支选择
分支选择类型"(X|Y|Z)"的正则表达式会降低性能，开发时需要尽量减少使用。如果一定要使用，我们可以通过以下几种方式来优化：
a. 首先，需要考虑选择的顺序，将比较常用的选择项放在前面，使其可以优先匹配；
b. 我们可以尝试提取共用模式，如将"(abcd|abef)"替换为"ab(cd|ef)"，NFA自动机如果没有匹配到ab将不会继续匹配。
c. 如果是简单的分支选择类型，使用三次index的效率要高一些。

减少捕获嵌套
捕获组：把正则表达式中，子表达式匹配的内容保存到以数字编号或显示命名的数组中，方便后面引用。捕获组可以进行嵌套。
非捕获组：参与匹配却不进行分组编号的捕获组，表达式一般由(?:exp)组成。
在正则表达式中，每个捕获组都有一个编号，编号0代表整个匹配到的内容。

public static void mian(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 hight=\'20\' weight=\'70\'>test</input>
<input hight=\'20\' weight=\'70\'>
test
</input>

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

public static void mian(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 hight=\'20\' weight=\'70\'>test</input>
test

减少不需要获取的分组，可以提高正则表达式的性能。

总结

如果正则表达式能使代码简洁方便，那么在做好性能排除的前提下，可以使用；如果能，那么正则表达式能不用就不用，以此避免性能问题。

系统优化专题3——正则表达式

正则表达式

正则表达式引擎

NFA自动机的回溯

如何减少回溯问题

优化

总结

猜你喜欢

热点阅读