小议正则表达式效率:贪婪、非贪婪与回溯

前几天看了鸟哥的BLOG上写的关于正则表达式的回溯与递归的限制时,对贪婪、非贪婪产生的回溯有疑问,遂近段时间,仔细的学习研究了一下,现在把经验心得与大家分享一下。
(我日,这里好像被左侧的图挡着了,换行换行凑字数,换行换行凑字数,换行换行凑字数,换行换行凑字数,换行换行凑字数,换行换行凑字数,换行换行凑字数,换行换行凑字数,换行换行凑字数,换行换行凑字数,换行换行凑字数,换行换行凑字数,换行换行凑字数,换行换行凑字数,换行换行凑字数)
先扫盲一下什么是正则表达式的贪婪,什么是非贪婪?或者说什么是匹配优先量词,什么是忽略优先量词?
好吧,我也不知道概念是什么,来举个例子吧。
某同学想过滤之间的内容,那是这么写正则以及程序的。

$str = preg_replace('%<script>.+?</script>%i','',$str);//非贪婪

看起来,好像没什么问题,其实则不然。若

$str = '<script<script>alert(document.cookie)</script>>alert(document.cookie)</script>';

那么经过上面的程序处理,其结果为

$str = '<script<script>alert(document.cookie)</script>>alert(document.cookie)</script>';
$str = preg_replace('%<script>.+?</script>%i','',$str);//非贪婪
print_r($str);
//$str 输出为 <script>alert(document.cookie)</script>

仍然达不到他想要的效果。上面的就是非贪婪,也有的叫惰性。其标志非贪婪的标识为量数元字符后面加? ,比如 +?、*?、??(比较特殊,以后的BLOG中,我会写到)等。即标识非贪婪,如果不写?就是贪婪。比如

$str = '<script<script>alert(document.cookie)</script>>alert(document.cookie)</script>';
$str = preg_replace('%<script>.+</script>%i','',$str);//非贪婪
print_r($str);
//$str 输出为 <script 只有这些了,好像还是不太合适,哈,您知道如何重写那个正则吗?

以上为贪婪,非贪婪的区别介绍。下面,聊下贪婪、非贪婪引起的回溯问题。先看个小例子。
正则表达式为\w*(\d+),字符串为cfc456n,那么,这个正则匹配的$1是多少??

如果您回答是 456,那么,恭喜你,回答了,其结果不是456,而是6,您知道为什么吗?

CFC4N来解释一下,当正则引擎用正则\w*(\d+)去匹配字符串cfc456n时,会先用\w*去匹配字符串cfc456n,首先,\w*会匹配字符串cfc456n的所有字符,然后再交给\d+去匹配剩下的字符串,而剩下的没了,这时,\w*规则会不情愿的吐出一个字符,给\d+去匹配,同时,在吐出字符之前,记录一个点,这个点,就是用于回溯的点,然后\d+去匹配n,发现并不能匹配成功,会再次要求\w*再吐出一个字符,\w*会先再次记录一个回溯的点,再吐出一个字符。这时,\w* 匹配的结果只有cfc45了,已经吐出6n了,\d+再去匹配6,发现匹配成功,则会通知引擎,匹配成功了,就直接显示出来了。所以,(\d+)的结果是6,而不是456。

当上面的正则表达式改为 \w*?(\d+)(注意,此处为非贪婪),字符串仍然为cfc456n,那么,这时候,正则匹配的$1是多少??
甲同学回答:结果是 456。
嗯,是的,正确,是456,CFC4N弱弱的问下,为什么是456 呢?
我在来解释一下 为什么是456
正则表达式有条规则,是量词优先匹配,所以\w*?会先去匹配字符串cfc456,由于\w*?是非贪婪,正则引擎会用表达式\w+?每次仅匹配一个字符串,然后再将控制权交给后面的\d+去匹配下一个字符,同时,记录一个点,用于在匹配不成功的时候,返回这里,再次匹配,也就是回溯点。由于\w后面是量词是*,*表示0到无数次,所以,首先是0次,也就是\w*?匹配个空,记录回溯点,将控制权交给\d+,\d+去匹配cfc456n的第一个字符c,然后,匹配失败,于是乎,接着讲控制权交给\w*?去匹配cfc456n的c,\w*?匹配c成功,由于是非贪婪,所以,他每次只匹配一个字符,记录回溯点,然后再将控制权交给\d+匹配f,接着,\d+匹配f再失败,再把控制权给\w*?,\w*?再匹配c,记录回溯点(这时\w*?匹配结果是cfc了),再把控制权给\d+,\d+去匹配4,匹配成功,然后,由于量词是+,就是1到无数次,所以,接着往后匹配,再匹配5,成功,再接着,再匹配6,成功,再接着,继续匹配操作,下一个字符是n,匹配失败,这时,\d+会吧控制权交出去。由于\d+后面已经没有正则表达式了,所以,整个正则表达式宣告匹配完成,其结果就是 cfc456, 其中第一组结果是456。亲爱的同学,您明白刚刚的题目的结果,为什么是456了吗?

好了,您是否从上面的例子了解了贪婪,非贪婪的匹配原理了?那您是否明白您在什么时候需要使用贪婪,非贪婪去处理您的字符串了?
鸟哥的文章里讲到针对
表达式、程序为

$reg = "/<script>.*?<\/script>/is";
$str = "<script>********</script>"; //长度大于100014
$ret = preg_repalce($reg, "", $str); //返回NULL

其原因就是回溯太多了,直到造成耗尽栈空间爆栈。

再来看个例子。
字符串

$str = '<script>123456</script>';

正则表达式为

$strRegex1 = '%<script>.+<\/script>%';
$strRegex2 = '%<script>.+?<\/script>%';
$strRegex3 = '%<script>(?:(?!<\/script>).)+<\/script>%';

这三个正则,分别会造成几次回溯呢??

答案见下篇 PHP正则表达式的效率:回溯与固化分组

关注微信公众号,手机阅读更方便: 程序员的阅微草堂

知识共享许可协议莿鸟栖草堂CFC4N 创作,采用 知识共享 署名-非商业性使用-相同方式共享(3.0未本地化版本)许可协议进行许可。基于http://www.cnxct.com上的作品创作。转载请注明转自:小议正则表达式效率:贪婪、非贪婪与回溯

12 thoughts on “小议正则表达式效率:贪婪、非贪婪与回溯

  1. […] 对于上篇BLOG上提到的鸟哥谈到一个非贪婪引起的大量回溯问题,大家可以知道,回溯,确实是浪费资源的罪魁祸首,那么,我们能否不让其回溯呢? 答案是肯定的,NFA引擎中,有个概念,叫固化分组。引用一下书上的概念 具体来说,使用「(?&gt;…)」的匹配与正常的匹配并无差别,但是如果匹配进行到此结构之后(也就是,进行到闭括号之后),那么此结构体中的所有备用状态都会被放弃。也就是说,在固化分组匹配结束时,它已经匹配的文本已经固化为一个单元,只能作为整体而保留或放弃。括号内的子表达式中未尝试过的备用状态都不复存在了,所以回溯永远也不能选择其中的状态(至少是,当此结构匹配完成时,“锁定(locked in)”在其中的状态)。 […]

  2. […] 对于上篇BLOG上提到的鸟哥谈到一个非贪婪引起的大量回溯问题,大家可以知道,回溯,确实是浪费资源的罪魁祸首,那么,我们能否不让其回溯呢? 答案是肯定的,NFA引擎中,有个概念,叫固化分组。引用一下书上的概念 具体来说,使用「(?&amp;gt;…)」的匹配与正常的匹配并无差别,但是如果匹配进行到此结构之后(也就是,进行到闭括号之后),那么此结构体中的所有备用状态都会被放弃。也就是说,在固化分组匹配结束时,它已经匹配的文本已经固化为一个单元,只能作为整体而保留或放弃。括号内的子表达式中未尝试过的备用状态都不复存在了,所以回溯永远也不能选择其中的状态(至少是,当此结构匹配完成时,“锁定(locked in)”在其中的状态)。 […]

  3. 谢谢 lz的分享。 看lz的blog 受益匪浅。

    同时想请教下, 正则应该怎么才能用好。我只有点基础。但是发现,想用好正则太难了。想系统的学习下。但是又不知道从何下手。望 不吝赐教

    • 呵呵,互相学习。我觉得,想用好某个技术,必先知道其原理。知道其原理之后,优化,提高效率的问题,自然迎刃而解了。对于NFA引擎的正则的灵魂是回溯,而回溯恰恰又是造成浪费资源的一个罪魁祸首,在匹配长字符串的时候,如果能避免,或者减少回溯,可以提高很多效率。避免回溯的方法有固化分组,还有占有优先量词。呵呵,下次有时间,我再写篇占有有限量词的博文跟大家一起探讨一下。 :mrgreen:

  4. […] 先来解释一下U(大写字母U,非小写,小写的是uincode字符模式)是干吗的? 是对“匹配优先量词(贪婪)”与“忽略优先量词(非贪婪)”的取反,也就是说,原来是【*】、【 】的,会按照【*?】、【 ?】来执行,如果是【*?】、【 ?】的,则按照【*】、【 】来执行,这个修饰符很怪,很乱,如果正则为【w 】,为了达到“非贪婪匹配”,使用了修饰符U。过几天,你修改了这个正则,修改为【w s ?】,你的本意是在原来的基础上,加上非贪婪的空白字符的匹配,可是,后面的大写字母U修饰符也对你前面的非贪婪取反了,从而,导致匹配错误,所以,建议大家不要使用大写字母的U修饰符,直接在表达式里写好贪婪还是非贪婪。 […]

  5. […] 继续刚刚的正则,分为两个分支,其一为【^1?$】和【^(11 ?)1 $】。其中【^】脱字符在正则语法中,除了在中括号【[]】中都是代表开头的意思,在中括号中的表示非。 第一个分支【^1?$】匹配的是“1”或者“”(空字符串)。 第二个分支【^(11 ?)1 $】,先看下括号内的【(11 ?)】匹配的是字符“1”后面接着【1 】就是1到无数个1。后面的【?】问号表示非贪婪,就是尽量少的匹配。 接着往后看【1 】中,【1】表示引用已匹配的第一个组的结果。也就是第一个【()】括号匹配的结果。同理【2】就是第二个括号捕获的结果。(小提示:上面提到的【(?:)写法就是不分配组,这样引用的话,就引用不到了】) 【 】就是1到无数个了。这个表达式我们可以这么看。【(11 ?)】看成数学中的1 n,其中n为大于0的正整数。外面的【1 】也就是引用前面这个组的次数。理解成m倍,其中m为大于0的正整数。 那整个表达式就是(1 n)*m。因为n、m都大于0,那么1 n肯定大于1,最小为2,最大为无穷大;m最小为1,最大为无穷大。 那么,一个大于2的正整数的任何大于零的倍数永远都是合数,也就是非素数。 […]

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.