PHP正则表达式的效率 回溯与固化分组
先来看下问题。
$str = '<script>123456</script>';
$strRegex1 = '%<script>.+<\/script>%';
$strRegex2 = '%<script>.+?<\/script>%';
$strRegex3 = '%<script>(?:(?!<\/script>).)+<\/script>%';
$strRegex1 = '%<script>.+<\/script>%'; //9次，记得区别转义符号。
$strRegex2 = '%<script>.+?<\/script>%'; //5次
$strRegex3 = '%<script>(?:(?!<\/script>).)+<\/script>%'; //7次
对于第一种贪婪匹配的匹配规则，回溯的9次是正则【】对字符串“”匹配时，构成的回溯，回溯的次数，恰好是字符串的长度。
第二种非贪婪匹配规则，回溯5次，是正则【.+?】对字符串“123456”匹配时构成的回溯。回溯的次数，为字符串长度减去最小次数。也就是6-1=5次。如果正则表达式为【.*?】那么，回溯次数就是6次了。
第三种正则是零宽断言，或者叫环视。（暂且不说。）
在NFA正则引擎中，回溯是他的灵魂，所以，不管是贪婪，非贪婪，环视等写法中肯定会有回溯的出现的，这个我们无法避免（用词不太准确），但是，我们可以减少回溯的次数，或者保护其中一部分匹配的规则不进行回溯。
对于上篇BLOG上提到的鸟哥谈到一个非贪婪引起的大量回溯问题，大家可以知道，回溯，确实是浪费资源的罪魁祸首，那么，我们能否不让其回溯呢？
答案是肯定的，NFA引擎中，有个概念，叫固化分组。引用一下书上的概念
代码如下:
具体来说，使用「(?>…)」的匹配与正常的匹配并无差别，但是如果匹配进行到此结构之后（也就是，进行到闭括号之后），那么此结构体中的所有备用状态都会被放弃。也就是说，在固化分组匹配结束时，它已经匹配的文本已经固化为一个单元，只能作为整体而保留或放弃。括号内的子表达式中未尝试过的备用状态都不复存在了，所以回溯永远也不能选择其中的状态（至少是，当此结构匹配完成时，“锁定（locked in）”在其中的状态）。
那么，固化分组到底有什么用处呢？我们来举个例子。（找不到合适的例子，俺只好借用一下书上的例子了）
比如要处理一批数据，原来格式为123.456，后来因为浮点数显示问题，部分数据格式变为123.456000000789这种，，要求做到只保留小数点后面2-3位，但是，最后一位不能为0，这个正则如何写呢？（下面直接考虑小数点后面的数字），写出正则之后，我们还要用这个正则去匹配数据，把原来的数据替换成匹配的结果。
首先，我们可以立刻写出这样的正则【\.\d\d[1-9]?\d*】，PHP代码为
代码如下:
$str = preg_replace('\.(\d\d[1-9]?)\d*','\\1',$str); //匹配结果的group1进行反向引用
很明显，这种写法，对于部分数据格式为123.456的这种格式，白白的处理了一遍，为了提高效率，我们还要对这个正则进行处理。从123.456这个字符串跟其他的比较一下，我们发现，是疑问123.456这个数据后面没数字了，所以，白白处理一遍。那好办，我们对这个正则改造一下，把后面的量词*改成+，这样对于123.45 小数点后面1，2位数字的，不会去白白处理，而且，对三位以上数字的，处理正常。其PHP代码为
代码如下:
$str = preg_replace('\.(\d\d[1-9]?)\d+','\\1',$str);
好了，这个正则真的没问题吗？？确定吗？上篇博文，我们了解了匹配原理，那么，我们也分析一下这个正则的匹配过程吧。
字符串"123.456",正则表达式为【\.(\d\d[1-9]?)\d+】，我们来看下
首先（小数点前123不说了），【\.】匹配"."，匹配成功，把控制权给下一个【\d】，【\d】匹配“4”成功，把控制权给第二个【\d】，这个【\d】匹配“5”成功，然后，把控制权给了【[1-9]?】，由于量词是【?】，正则表达式遵循“量词优先匹配”，而且，此处是【?】，还会留下一个回溯点。然后匹配"6"成功，然后把控制权给【\d+】，【\d+】发现后面没字符了，最遵循“后进先出”规则，回到上一个回溯点，进行匹配，这时，【[1-9]?】会交还出其匹配的字符“6”，【[1-9]?】匹配“6”成功。匹配完成了。大家发现【(\d\d[1-9]?)】匹配的结果确是"45",并不是我们想要的“456”，“6”被【\d+】匹配去了。那么，我们该如何办呢？ 能否让【[1-9]?】匹配一旦成功，不进行回溯呢？这就用到了我们上面说的"固化分组", PHP（preg_replace函数）中使用的正则引擎支持固化分组，我们根据固化分组的写法，可以把代码改成如下方式
代码如下:
$str = preg_replace('\.(\d\d(?>[1-9]?))\d+','\\1',$str);
改成这样的话，那字符串“123.456“是不符合要求，不会被匹配的。那我们就可以实现我们的要求了。
从上面的例子中，知道了固化分组的作用，那么对于鸟哥BLOG上写的那个非贪婪的回溯问题，我们能否也对其改造，使得其不回溯呢？
先看下鸟哥给的答案
代码如下:
/<script>[^<]*<\/script>/is
鸟哥写的很精悍。排除“<”之外的所有字符都符合，而且，中间部分不回溯，效率高。可是，如果中间有字符“<“的话（如下代码）
代码如下:
<script>
if a < b
</script>
那鸟哥的这个正则就不能匹配，就不能实现我们想要的功能了。
那我们可以根据 固化分组、环视(零宽断言)来实现这个要求，最后，CFC4N给出的正则以及PHP代码事例如下
代码如下:
$reg = '%<script>(?>[^<]*)(?>(?!</?script>)<[^<]*)*</script>%is';
$str = str_pad("<script>", 111111, "*"); //字符长度大于PHP回溯限制的100000
$str .= 'if a < b ; if b > c;</script>'; //随便加几个包含 < > 的测试字符
$ret = preg_replace($reg, "OK", $str);
print_r($ret); //打印结果 OK，证明匹配正确
var_dump(preg_last_error()); //上一次匹配错误。其输出为 int(0)
嗨，同学，你看明白了吗？
以上为小菜CFC4N的愚文，如有错误，欢迎指出。
相关推荐
-
php实现猴子选大王问题算法实例
本文实例讲述了php实现猴子选大王问题算法.分享给大家供大家参考.具体分析如下: 一.问题: n只猴子围坐成一个圈,按顺时针方向从1到n编号. 然后从1号猴子开始沿顺时针方向从1开始报数,报到m的猴子出局,再从刚出局猴子的下一个位置重新开始报数, 如此重复,直至剩下一个猴子,它就是大王. 设计并编写程序,实现如下功能: (1) 要求由用户输入开始时的猴子数$n.报数的最后一个数$m. (2) 给出当选猴王的初始编号. 二.解决方法: /** * @param int $n 开始时的猴子数
-
PHP实现基于回溯法求解迷宫问题的方法详解
本文实例讲述了PHP实现基于回溯法求解迷宫问题的方法.分享给大家供大家参考,具体如下: 引言 最近在leetcode上看了些算法题,有些看着很简单的很常用的东西,竟然一下子想不出来怎么求解,比如说:实现sqrt函数,求数组的排列.如果高数学的不好,这些看似简单的问题,第一次碰到也会感觉很难求解,当然了,今天要说的是这样一个问题,求解迷宫的所有解,这个问题的求解用到了回溯法的思想,不了解这个思想的话,很多稍微复杂点的问题都很难解了. 问题描述 这个问题是在实在瞎逛的时候碰到的,具体哪里记不太清了.
-
PHP基于回溯算法解决n皇后问题的方法示例
本文实例讲述了PHP基于回溯算法解决n皇后问题的方法.分享给大家供大家参考,具体如下: 这里对于n皇后问题就不做太多的介绍,相关的介绍与算法分析可参考前面一篇C++基于回溯法解决八皇后问题. 回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法.这种方法适用于解一些组合数相当大的问题. 回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树.算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解.如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向
-
PHP 正则表达式效率 贪婪、非贪婪与回溯分析(推荐)
先扫盲一下什么是正则表达式的贪婪,什么是非贪婪?或者说什么是匹配优先量词,什么是忽略优先量词? 好吧,我也不知道概念是什么,来举个例子吧. 某同学想过滤之间的内容,那是这么写正则以及程序的. $str = preg_replace('%<script>.+?</script>%i','',$str);//非贪婪 看起来,好像没什么问题,其实则不然.若 $str = '<script<script>alert(document.cookie)</script&
-
php约瑟夫问题解决关于处死犯人的算法
本文实例讲述了php约瑟夫问题解决关于处死犯人的算法.分享给大家供大家参考.具体分析如下: 古代某法官要判决IV个犯人的死刑,他有一条荒唐的法律将犯人站成一个圆圈,从第s个人开始数起,每到第D个人就拉出来处死,然后再数D个,再拉出来处决-- 直到剩下最后一个可以赦免. function getNum($n,$m){ //用于把所有的数存到数组初始化 $a = array(); //遍历,存入数组 for($i=1;$i<=$n;$i++){ $a[$i] = $i; } //指针归0 reset
-
PHP回溯法解决0-1背包问题实例分析
本文实例讲述了PHP回溯法解决0-1背包问题的方法.分享给大家供大家参考.具体分析如下: 这段代码是根据<软件设计师>教程的伪代码写的: 最麻烦的不是伪代码改成php,而是数组下标从0开始,及相应的下标判断问题: 带着调试输出一块写上 <?php $v_arr = array(11,21,31,33,43,53,55,65); $w_arr = array(1,11,21,23,33,43,45,55); $n = count($w_arr ); //测试输出 var_dump(bkna
-
PHP贪婪算法解决0-1背包问题实例分析
本文实例讲述了PHP贪婪算法解决0-1背包问题的方法.分享给大家供大家参考.具体分析如下: 贪心算法解决0-1背包问题,全局最优解通过局部最优解来获得!比动态规划解决背包问题更灵活! //0-1背包贪心算法问题 class tanxin{ public $weight; public $price; public function __construct($weight=0,$price=0) { $this->weight=$weight; $this->price=$price; } }
-
PHP使用栈解决约瑟夫环问题算法示例
本文实例讲述了PHP使用栈解决约瑟夫环问题算法.分享给大家供大家参考,具体如下: 约瑟夫环问题: 39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓.于是决定了自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀.然后下一个重新报数,直到所有人都自杀身亡为止.然而Josephus 和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏. <?php cla
-
PHP实现的回溯算法示例
本文实例讲述了PHP实现的回溯算法.分享给大家供大家参考,具体如下: 问题: 一头大牛驼2袋大米,一头中牛驼一袋大米,两头小牛驼一袋大米,请问100袋大米需要多少头大牛,多少头中牛,多少头小牛? 实现代码: <?php /* * k = 2x + y + 1/2z 取值范围 * 0 <= x <= 1/2k * 0 <= y <= k * 0 <= z < = 2k * x,y,z最大值 2k */ $daMi = 100; $result = array();
-
PHP正则表达式的效率 回溯与固化分组
先来看下问题. 字符串 复制代码 代码如下: $str = '<script>123456</script>'; 正则表达式为 复制代码 代码如下: $strRegex1 = '%<script>.+<\/script>%'; $strRegex2 = '%<script>.+?<\/script>%'; $strRegex3 = '%<script>(?:(?!<\/script>).)+<\/scri
-
正则用(?>…)实现固化分组提高效率
具体来说,使用「(?>-)」的匹配与正常的匹配并无差别,但是如果匹配进行到此结构之后(也就是,进行到闭括号之后),那么此结构体中的所有备用状态都会被放弃(不能被回溯). 也就是说,在固化分组匹配结束时,它已经匹配的文本已经固化为一个单元,只能作为整体而保留或放弃.括号内的子表达式中未尝试过的备用状态都不复存在了,所以回溯永远也不能选择其中的状态(至少是,当此结构匹配完成时,"锁定(locked in)"在其中的状态). 例子: 比如要处理一批数据,原来格式为123.456,后来因
-
js正则表达式之前瞻后顾与非捕获分组
目录 前瞻后顾与捕获分组的结合使用 捕获分组与非捕获分组 前瞻.后顾与负前瞻.负后顾 总结 前瞻后顾与捕获分组的结合使用 在现实的应用场景中,捕获分组或非捕获分组通常被限制在前瞻后顾条件内,举例来说,对数字12345678格式化,结果为12,345,678.其正则实现如下: let formatSum = '12345678'.replace(/\B(?=(?:\d{3})+(?!\d))/g, ',') 捕获分组与非捕获分组 为了理解前瞻与后顾,首先要先理解捕获分组与非捕获分组 在js中, (
-
python中通过预先编译正则表达式提高效率
前言 在re的正则表达式模块里,可以通过模块的方式来访问正则表达式,但是如果重复多次地使用正则表达式,最好是使用compile函数把正则表达式编译成对象RegexObject,这样会大大地提高搜索的效率,因为基于非编译方式访问时,是使用模块里的一小块缓冲来进行的. 如下面的例子: import re # Precompile the patterns regexes = [ re.compile(p) for p in ['this', 'that'] ] text = 'http://blog
-
PHP实现正则表达式分组捕获操作示例
本文实例讲述了PHP实现正则表达式分组捕获操作.分享给大家供大家参考,具体如下: 经过测试,发现php正则表达式获取分组捕获是从$0开始,而平时工作中JavaScript中的正则是$1..$9 在提取项目代码中的汉字时,因为当时操作速度很快(赶时间),很担心当时.properties的文件{\d}的数字顺序搞错了: 1.可能从{1}开始,而不是从{0}开始 2.可能跳着写了,比如第一个是{0}第二个需要替换的地方却写着{2} 因为使用人工手动操作的,所以这种情况是难以避免,只能说减少误操作.写完
-
小议正则表达式效率 贪婪、非贪婪与回溯
先扫盲一下什么是正则表达式的贪婪,什么是非贪婪?或者说什么是匹配优先量词,什么是忽略优先量词? 好吧,我也不知道概念是什么,来举个例子吧. 某同学想过滤之间的内容,那是这么写正则以及程序的. 复制代码 代码如下: $str = preg_replace('%<script>.+?</script>%i','',$str);//非贪婪 看起来,好像没什么问题,其实则不然.若 复制代码 代码如下: $str = '<script<script>alert(docume
-
正则表达式的优化全面详解( 三江小渡)
就像之前写的mysql全面优化详解一样,就是因为这样工具应用十分广泛,所以对这样的工具全面的进行优化策略总结是非常划算的,因为无论你是PHP.Perl.Python.C++.C#.Java等等语言的程序员,你都是有非常大可能用上Mysql.正则表达式这样的工具的. 先说一下你可能不知道的一点关于正则表达式的知识,这对我们将来的优化是有用的. 大家常见的grep(global regular expression print)算是现在的正则的起源吧(从神经学家提出正则概念到数学家建立模型到被IBM
-
编写高质量的js之正确理解正则表达式回溯
当一个正则表达式扫描目标字符串时,从左到右逐个扫描正则表达式的组成部分,在每个位置上测试能不能找到一个匹配.对于每一个量词和分支,都必须确定如何继续进行.如果是一个量词(如*.+?或者{2,}),那么正则表达式必须确定何时尝试匹配更多的字符:如果遇到分支(通过|操作符),那么正则表达式必须从这些选项中选择一个进行尝试. 当正则表达式做出这样的决定时,如果有必要,它会记住另一个选项,以备返回后使用.如果所选方案匹配成功,正则表达式将继续扫描正则表达式模板,如果其余部分匹配也成功了,那么匹配就结束了
-
Python re正则表达式元字符分组()用法分享
分组小括号() 有直接分组和命名分组 直接分组: ()分组只显示小括号括起来的内容 re.findall(r"(name)+","namename") 这里匹配到了namename 但是值显示括号中的name 直接分组实例 re.search()方法: 搜索结果返回对象,可以用ret.group()方法打印结果 它跟findall不同在于找到一个结果就不再往下找了 re.match()方法: 只匹配字符串开始的位置 有名分组: 给分组取名?P<name>
-
正则表达式、分组、子匹配（子模式）、非捕获子匹配（子模式）
前面我们知道正则表达式有很多元字符表示匹配次数(量词),都是可以重复匹配前面出现的单个字符次数.有时候,我们可能需要匹配一组多个字符一起出现的次数.这个时候,我们需要分组了.就是用小括号来括起这些字符,指定子表达式(也叫做分组).然后你就可以指定这个子表达式的重复次数了,你也可以对子表达式进行其它一些操作.这个时候,可以把括号中一组字符,看作一个整体了. 分组模式举例说明 如:查找字符串中,连续出现多个win字符串的字符.可以这样完 <?php $str = "this is win wi