正则表达式
正则表达式是计算机科学的一个概念，使用一些特定的元字符进行检索匹配及替换符合规则的字符串，很多语言实现了正则表达式。
构造正则表达式语法的元字符由普通字符、标准字符、限定字符(量词)、定位字符(边界字符)组成。如图：
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>) } }
如果并不需要获取某个分组内的文本，那么就使用非捕获分组。例如使用"(?:X)"代替"(X)"<input hight=\'20\' weight=\'70\'>test</input> <input hight=\'20\' weight=\'70\'> test </input>
运行结果：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
总结
如果正则表达式能使代码简洁方便，那么在做好性能排除的前提下，可以使用；如果能，那么正则表达式能不用就不用，以此避免性能问题。
网友评论