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

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

正则表达式匹配算法是建立在正则表达式引擎的基础上的，目前有两种引擎：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。希望对你有所帮助。