欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

正则表达式回溯-导致CPU偏高

程序员文章站 2022-05-14 08:28:37
最近了解了下有关正则表达式回溯的内容,想想就写下来,方便自己。 正则表达式匹配算法是建立在正则表达式引擎的基础上的,目前有两种引擎:DFA(确定型有穷自动机)和NFA(不确定型有穷自动机)。这两种引擎的区别主要在于被匹配对象不同。 DFA是用文本去匹配表达式。而NFA是用表达式去匹配文本。这个了解一 ......

最近了解了下有关正则表达式回溯的内容,想想就写下来,方便自己。

正则表达式匹配算法是建立在正则表达式引擎的基础上的,目前有两种引擎:DFA(确定型有穷自动机)和NFA(不确定型有穷自动机)。这两种引擎的区别主要在于被匹配对象不同。

DFA是用文本去匹配表达式。而NFA是用表达式去匹配文本。这个了解一下就信了。目前我们用的是NFA自动机。

为什么有时候正则表达式的使用会导致CPU飙升呢?这个与正则表达式的回溯有关。什么就正则表达式的回溯以及为什么会发生回溯呢?请看下面的例子。

regex="b{1,3}ac";

text="bbac";

表达式在匹配文本的时候是一个一个的去校验。b{1,3}表示最少出现一个b,最多3个b连续出现。这样在我们的文本中出现了连续的两个b,所以文本是符合这条表达式的。但是由于NFA的贪婪特性,也就是会更多的去匹配文本。表达式会用第三个b去和文本中的所处第三位置的a去匹配,结果不符合。这样就结束了吗?并没有,接下来表达式会在已经匹配的三个字符中“吐”出字符a,这就是回溯。然后就从表达式中的a开始逐一匹配剩余文本ac。直到结束。

如果想要解决这种问题,就需要改变表达式的匹配模式。表达式有三种模式:贪婪模式、懒惰模式、独占模式。

刚刚我们所用到的是贪婪模式,尽可能多的去匹配。

而懒惰模式,尽可能少的去匹配,但仍会发生回溯。独占模式,尽可能多的去匹配,但不回溯。

那如何将表达式改为懒惰模式呢:

regex="b{1,3}?ac";

独立模式呢?

regex="b{1,3}+ac";这种就可以解决回溯的问题。

 

 

这些只是个人的理解,有什么不足之处,还望指出,如果不理解的可以参考:http://www.cnblogs.com/study-everyday/p/7426862.html。希望对你有所帮助。