正则表达式一个问号引发的血案

2021-01-03  本文已影响0人  代码狂魔

起因

一个java进程，通过top命令查看到其CPU使用量400%多(八核CPU)，于是通过进程查线程，再通过线程查询调用堆栈发现是Java的replaceAll方法在消耗CPU，再具体一点就是Java的正则表达式处理在消耗大量CPU
进程查线程，查堆栈信息看这里：Linux中找出Java程序占用大量CPU的元凶

堆栈信息如下

java.lang.Thread.state: RUNABBLE
    at java.util.regex.Pattern$Curly.match1(Pattern.java:4300)
    at java.util.regex.Pattern$Curly.match(Pattern.java:4236)
    at java.util.regex.Pattern$start.match1(Pattern.java:3461)
    at java.util.regex.Matcher.search(Matcher.java:1248)
    at java.util.regex.Matcher.find(Matcher.java:637)
    at java.util.regex.Matcher.replaceAll(Matcher.java:951)
    at java.lang.String.replaceAll(String.java.2210)
    .......
    at java.lang.Thread.run(Thread.java:745)

再怎么也不可能怀疑Java本身出了问题，两个关键词，replaceAll和正则，一看就是正则表达式出的问题。

有问题的正则表达式

把目光聚集在有问题的正则表达式上，代码中有这么一句

xml = xml.replaceAll("(?is).*?<file>(.*?)</file>.*", "$1");

这段代码意思是将字符串掐头去尾，取"<file></file>"之间的文本，再细分一下
(?is).*?<file>(.*?)</file>.*

<soap:Envelope><soap:Body><FILE><RESULTINFO>...非常长的一段数据...</RESULTINFO></FILE></soap:Body></soap:Envelope>

匹配过程是这样的

解决问题

现在原因已经很明显了，上面第三步不应该用非贪婪，因为数据的长度是不一定的，而且长度一般很大，所以数据有多长这个正则就要匹配多少次，新的正则表达式

(?is).*?<file>(.*)</file>.*

新的正则匹配步骤，和上面相比只有第三步和第四步不一样

回溯

其实上面说的非贪婪模式就是正则表达式中的回溯，写正则表达式一般要写回溯较少的或者说是回溯固定且在能接受的范围之内，上面这种案列（回溯很多且不确定）称之为灾难性回溯

对于正则而言，回溯并不是必需的，这跟具体的正则引擎有关。简单地说，正则引擎分为NFA和DFA。这东西难懂且无聊，我就挑重点说。DFA（确定型有穷自动机），从匹配文本入手，从左到右，每个字符不会匹配两次，它的时间复杂度是多项式的，所以通常情况下，它的速度更快，但支持的特性很少，不支持捕获组、各种引用等等；而NFA（非确定型有穷自动机）则是从正则表达式入手，不断读入字符，尝试是否匹配当前正则，不匹配则吐出字符重新尝试，通常它的速度比较慢，最优时间复杂度为多项式的，最差情况为指数级的。但NFA支持更多的特性，因而绝大多数编程场景下（包括js），我们面对的是NFA。DFA（确定型有穷自动机），从匹配文本入手，从左到右，每个字符不会匹配两次，它的时间复杂度是多项式的，所以通常情况下，它的速度更快，但支持的特性很少，不支持捕获组、各种引用等等；而NFA（非确定型有穷自动机）则是从正则表达式入手，不断读入字符，尝试是否匹配当前正则，不匹配则吐出字符重新尝试，通常它的速度比较慢，最优时间复杂度为多项式的，最差情况为指数级的。但NFA支持更多的特性，因而绝大多数编程场景下（包括js），我们面对的是NFA。

可以简单的理解为DFA是某种确定状态下的NFA，如果把NFA想成一个球，那DFA就是这个球的一个横截面，只有在NFA中才会引起回溯

有个哥们儿写的很好，在此我引用过来

正则表达式匹配字符串的这种方式，有个学名，叫回溯法。

回溯法也称试探法，它的基本思想是：从问题的某一种状态（初始状态）出发，搜索从这种状态出发所能达到的所有“状态”，当一条路走到“尽头”的时候（不能再前进），再后退一步或若干步，从另一种可能“状态”出发，继续搜索，直到所有的“路径”（状态）都试探过。这种不断“前进”、不断“回溯”寻找解的方法，就称作“回溯法”。（copy于百度百科）。

本质上就是深度优先搜索算法。其中退到之前的某一步这一过程，我们称为“回溯”。从上面的描述过程中，可以看出，路走不通时，就会发生“回溯”。即，尝试匹配失败时，接下来的一步通常就是回溯。

大家都知道 * 表示匹配前面的子表达式 0 次或多次（且尽可能多的匹配）。但这个逻辑具体是如何执行的呢？让我们通过几个小例子来看一下。

Round 1
假设有正则表达式 /^(a*)b$/ 和字符串 aaaaab。如果用该正则匹配这个字符串会得到什么呢？

答案很简单。两者匹配，且捕获组捕获到字符串 aaaaa。

Round 2
这次让我们把正则改写成 /^(a*)ab$/。再次和字符串 aaaaab 匹配。结果如何呢？

两者依然匹配，但捕获组捕获到字符串 aaaa。因为捕获组后续的表达式占用了 1 个 a 字符。但是你有没有考虑过这个看似简单结果是经过何种过程得到的呢？

让我们一步一步来看：

匹配开始 (a) 捕获尽可能多的字符 a。
(a) 一直捕获，直到遇到字符 b。这时 (a) 已经捕获了 aaaaa。
正则表达式继续执行 (a) 之后的 ab 匹配。但此时由于字符串仅剩一个 b 字符。导致无法完成匹配。
(a*) 从已捕获的字符串中“吐”出一个字符 a。这时捕获结果为 aaaa，剩余字符串为 ab。
重新执行正则中 ab的匹配。发现正好与剩余字符串匹配。整个匹配过程结束。返回捕获结果 aaaa。
从第3，4步可以看到，暂时的无法匹配并不会立即导致整体匹配失败。而是会从捕获组中“吐出”字符以尝试。这个“吐出”的过程就叫回溯。

回溯并不仅执行一次，而是会一直回溯到另一个极端。对于 * 符号而言，就是匹配 0 次的情况。

Round 3
这次我们把正则改为 /^(a*)aaaab$/。字符串依然为 aaaaab。根据前边的介绍很容易直到。此次要回溯 4 次才可以完成匹配。具体执行过程不再赘述。

悲观回溯
了解了回溯的工作原理，再来看悲观回溯就很容易理解了。

Round 4
这次我们的正则改为 /^(a*)b$/。但是把要匹配的字符串改为 aaaaa。去掉了结尾的字符 b。

让我们看看此时的执行流程：

(a*) 首先匹配了所有 aaaaa。
尝试匹配 b。但是匹配失败。
回溯 1 个字符。此时剩余字符串为 a。依然无法匹配字符 b。
回溯一直进行。直到匹配 0 次的情况。此时剩余字符串为 aaaaa。依然无法匹配 b。
所有的可能性均已尝试过，依然无法匹配。最终导致整体匹配失败。
可以看到，虽然我们可以一眼看出二者无法匹配。但正则表达式在执行时还要“傻傻的”逐一回溯所有可能性，才能确定最终结果。这个“傻傻的”回溯过程就叫悲观回溯。

贪婪模式，非贪婪模式，独占模式

正则表达式DEBUG工具

  1. https://regex101.com/
    该网站可以动态展示正则表达式的匹配过程
  2. 客户端工具RegexBuddy
    该工具也可以展示正则表达式匹配的过程

参考

上一篇 下一篇

猜你喜欢

热点阅读