浅谈正则表达式回溯陷阱

展翅的鹰 發表於 2023-11-27 09:35:34

<div id="navCategory"><h5 class="catalogue">目录</h5><ul class="first_class_ul"><li><a href="#_label0">一、匹配场景</a></li><li><a href="#_label1">二、性能测试</a></li><li><a href="#_label2">三、正则的回溯陷阱</a></li><ul class="second_class_ul"><li><a href="#_lab2_2_0">1、了解下NFA与DFA</a></li><li><a href="#_lab2_2_1">2、NFA的回溯</a></li><li><a href="#_lab2_2_2">3、简易例子分析</a></li><li><a href="#_lab2_2_3">4、咋优化?</a></li></ul></ul></div><a name="_label0"></a><h2>一、匹配场景</h2>
判断一个句子是不是正规英文句子
<div class="jb51code"><pre class="brush:plain;">text = "I am a student"</pre></div>
一个正常的英文句子如上，英文单词  + 空格隔开
英文单词 = 多个英文字符  
空格用 \s 表示
那么一个句子就是单词 + 空格（一个或者多个，最后那个单词是0个）（可能有多个单词+空格）+ 最后一个句号 .
那正则就是 
<div class="jb51code"><pre class="brush:plain;">^(+(\s)*)+$</pre></div>
 JAVA代码
<div class="jb51code"><pre class="brush:java;">public static void main(String[] args) {
 String text = "I am a good student";
 String regex = "^(+(\\s)*)+$";

 Pattern pattern = Pattern.compile(regex);
 Matcher matcher = pattern.matcher(text);
 System.out.println(matcher.find());
 System.out.println(matcher.group(0));
}</pre></div>
输出结果： 
<blockquote>true I am a good student</blockquote>
<a name="_label1"></a><h2>二、性能测试</h2>
<a href="https://regex101.com/" rel="external nofollow" target="_blank">regex101: build, test, and debug regex.</a>
<img alt="icon-default.png?t=N7T8" src="https://img.jbzj.com/file_images/article/202311/2023112709283426.png" />
句子改成：I am a good good student
<img alt="" src="https://img.jbzj.com/file_images/article/202311/2023112709283427.png" />
匹配成功了。39 step，耗时0.1ms，
但是假如把句子拉长点，最后加上一个问号 ？
I am a good good student？
<img alt="" src="https://img.jbzj.com/file_images/article/202311/2023112709283428.png" />
83408 step，耗时5.4ms
假如把句子再拉长点，那么直接就干爆CPU，耗时指数增长，
为啥会这样呢？
<a name="_label2"></a><h2>三、正则的回溯陷阱</h2>
<a name="_lab2_2_0"></a><h3>1、了解下NFA与DFA</h3>
<ul><li>DFA (Deterministic finite automaton) 确定型有穷自动机</li><li>NFA (Non-deterministic finite automaton) 非确定型有穷自动机</li></ul>
DFA ：遍历text字符串，去和Pattern匹配
NFA：遍历Pattern，去与text匹配
DFA（是电动机）和NFA（汽油机）都有很长的历史，不过，正如汽油机一样，NFA 的历史更长一些。也有些系统采用了混合引擎，它们会根据任务的不同选择合适的引擎（甚至对同一表达式中的不同部分采用不同的引擎，以求得功能与速度之间的最佳平衡）。 ——《精通正则表达式》
绝大多数编程语言都选择的引擎——NFA (非确定型有穷自动机) 引擎
<img alt="" src="https://img.jbzj.com/file_images/article/202311/2023112709283429.png" />
<a name="_lab2_2_1"></a><h3>2、NFA的回溯</h3>
字符串：abc
表达式：a(d|b)c
<img alt="" src="https://img.jbzj.com/file_images/article/202311/2023112709283430.png" />
<img alt="" src="https://img.jbzj.com/file_images/article/202311/2023112709283431.png" />
<img alt="" src="https://img.jbzj.com/file_images/article/202311/2023112709283432.png" />
<img alt="" src="https://img.jbzj.com/file_images/article/202311/2023112709283433.png" />
注意这个位置回退！！！
<img alt="" src="https://img.jbzj.com/file_images/article/202311/2023112709283434.png" />
<a name="_lab2_2_2"></a><h3>3、简易例子分析</h3>
<div class="jb51code"><pre class="brush:plain;">表达式 = ^(a*)+$
文本 = aaaaaaaaaaaaaaab</pre></div>
走了16w步，花了7.3ms
<img alt="" src="https://img.jbzj.com/file_images/article/202311/2023112709283435.png" />
<ul><li>首先 (a*) 已经匹配到 aaaaaaaaaaaaaaa 了，</li><li> (a*)+ 也匹配到 aaaaaaaaaaaaaaa ，</li><li>结束符$去匹配的时候，发现text不是结束，而是一个b</li><li>那吐出最后的a，变成 (aaaaaaaaaaaaaa) a ，没匹配上，继续吐</li></ul>
<div class="jb51code"><pre class="brush:plain;">a* a*
(aaaaaaaaaaaaa) (aa)

a* a* a*
(aaaaaaaaaaaaa) (a)(a)

a* a*
(aaaaaaaaaaaa) (aaa)

a* a* a*
(aaaaaaaaaaaa) (aa)(a)

a* a* a* a*
(aaaaaaaaaaaa) (a)(a)(a)

--> 吐到最后
(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)</pre></div>
直接干爆CPU 
<a name="_lab2_2_3"></a><h3>4、咋优化?</h3>
1、对于  ^(a*)+$
直接把表达式
 ^(a*)+$
改成 ^(a*)$
把后面的 + 号去掉。
直接就是 5 Step，0.1ms
<img alt="" src="https://img.jbzj.com/file_images/article/202311/2023112709283436.png" />
2、对于 ^(+(\s)*)+$
把后面的 + 号去掉。就不回溯了，
但是匹配不上，因为语句有问题，就是空格必须存在，但是最后的空格不存在
<img alt="" src="https://img.jbzj.com/file_images/article/202311/2023112709283537.png" />
所以改成：^+(\s+)*$
遇到问号也不回溯
<img alt="" src="https://img.jbzj.com/file_images/article/202311/2023112709283538.png" />
去掉问号也匹配上了
<img alt="" src="https://img-blog.csdnimg.cn/654ca6bc3d2245d99f3bbd2b2b8f9304.png" />

頁: [1]

琼殿技术论坛's Archiver

浅谈正则表达式回溯陷阱