忘记密码   免费注册 查看新帖 | 论坛精华区

ChinaUnix.net

  平台 论坛 博客 认证专区 大话IT 视频 徽章 文库 沙龙 自测 下载 频道自动化运维 虚拟化 储存备份 C/C++ PHP MySQL 嵌入式 Linux系统
12下一页
最近访问板块 发新帖
查看: 37616 | 回复: 12

atomic group [复制链接]

求职 : 软件工程师
论坛徽章:
3
程序设计版块每日发帖之星
日期:2015-10-07 06:20:00程序设计版块每日发帖之星
日期:2015-12-13 06:20:00程序设计版块每日发帖之星
日期:2016-05-05 06:20:00
发表于 2016-08-06 12:40 |显示全部楼层
本帖最后由 104359176 于 2016-08-06 12:40 编辑

An atomic group is a group that, when the regex engine exits from it, automatically throws away all backtracking positions remembered by any tokens inside the group. Atomic groups are non-capturing. The syntax is (?>group). Lookaround groups are also atomic. Atomic grouping is supported by most modern regular expression flavors, including the JGsoft flavor, Java, PCRE, .NET, Perl and Ruby. Most of these also support possessive quantifiers, which are essentially a notational convenience for atomic grouping.

An example will make the behavior of atomic groups clear. The regular expression a(bc|b)c (capturing group) matches abcc and abc. The regex a(?>bc|b)c (atomic group) matches abcc but not abc.

When applied to abc, both regexes will match a to a, bc to bc, and then c will fail to match at the end of the string. Here their paths diverge. The regex with the capturing group has remembered a backtracking position for the alternation. The group will give up its match, b then matches b and c matches c. Match found!

The regex with the atomic group, however, exited from an atomic group after bc was matched. At that point, all backtracking positions for tokens inside the group are discarded. In this example, the alternation's option to try b at the second position in the string is discarded. As a result, when c fails, the regex engine has no alternatives left to try.

Of course, the above example isn't very useful. But it does illustrate very clearly how atomic grouping eliminates certain matches. Or more importantly, it eliminates certain match attempts.

论坛徽章:
298
程序设计版块每周发帖之星
日期:2016-04-08 00:41:33操作系统版块每日发帖之星
日期:2015-09-02 06:20:00每日论坛发贴之星
日期:2015-09-02 06:20:00程序设计版块每日发帖之星
日期:2015-09-04 06:20:00每日论坛发贴之星
日期:2015-09-04 06:20:00每周论坛发贴之星
日期:2015-09-06 22:22:00程序设计版块每日发帖之星
日期:2015-09-09 06:20:00程序设计版块每日发帖之星
日期:2015-09-19 06:20:00程序设计版块每日发帖之星
日期:2015-09-20 06:20:00每日论坛发贴之星
日期:2015-09-20 06:20:00程序设计版块每日发帖之星
日期:2015-09-22 06:20:00程序设计版块每日发帖之星
日期:2015-09-24 06:20:00
发表于 2016-08-06 12:59 |显示全部楼层
大神 能否翻译下? 有些意思看的不是很明白. 谢谢

求职 : 软件工程师
论坛徽章:
3
程序设计版块每日发帖之星
日期:2015-10-07 06:20:00程序设计版块每日发帖之星
日期:2015-12-13 06:20:00程序设计版块每日发帖之星
日期:2016-05-05 06:20:00
发表于 2016-08-06 21:29 |显示全部楼层
I think atomic group could get longest match of all branch, but it is not.

I don't understand what use of it.

论坛徽章:
0
发表于 2016-08-06 23:39 |显示全部楼层
网上找的一段文字:

13. 原子组与防止回溯

在一些特殊情况下,因为回溯会使得引擎的效率极其低下。
让我们看一个例子:要匹配这样的字串,字串中的每个字段间用逗号做分隔符,第12个字段由P开头。
我们容易想到这样的正则表达式<<^(.*?,){11}P>>。这个正则表达式在正常情况下工作的很好。但是在极端情况下,如果第12个字段不是由P开头,则会发生灾难性的回溯。如要搜索的字串为“1,2,3,4,5,6,7,8,9,10,11,12,13”。首先,正则表达式一直成功匹配直到第12个字符。这时,前面的正则表达式消耗的字串为“1,2,3,4,5,6,7,8,9,10,11,”,到了下一个字符,<<P>>并不匹配“12”。所以引擎进行回溯,这时正则表达式消耗的字串为“1,2,3,4,5,6,7,8,9,10,11”。继续下一次匹配过程,下一个正则符号为点号<<.>>,可以匹配下一个逗号“,”。然而<<,>>并不匹配字符“12”中的“1”。匹配失败,继续回溯。大家可以想象,这样的回溯组合是个非常大的数量。因此可能会造成引擎崩溃。

用于阻止这样巨大的回溯有几种方案:
一种简单的方案是尽可能的使匹配精确。用取反字符集代替点号。例如我们用如下正则表达式<<^([^,\r\n]*,){11}P>>,这样可以使失败回溯的次数下降到11次。

另一种方案是使用原子组。
原子组的目的是使正则引擎失败的更快一点。因此可以有效的阻止海量回溯。原子组的语法是<<(?>正则表达式)>>。位于(?>)之间的所有正则表达式都会被认为是一个单一的正则符号。一旦匹配失败,引擎将会回溯到原子组前面的正则表达式部分。前面的例子用原子组可以表达成<<^(?>(.*?,){11})P>>。一旦第十二个字段匹配失败,引擎回溯到原子组前面的<<^>>。

评分

参与人数 1信誉积分 +10 收起 理由
sunzhiguolu + 10 很给力!

查看全部评分

论坛徽章:
298
程序设计版块每周发帖之星
日期:2016-04-08 00:41:33操作系统版块每日发帖之星
日期:2015-09-02 06:20:00每日论坛发贴之星
日期:2015-09-02 06:20:00程序设计版块每日发帖之星
日期:2015-09-04 06:20:00每日论坛发贴之星
日期:2015-09-04 06:20:00每周论坛发贴之星
日期:2015-09-06 22:22:00程序设计版块每日发帖之星
日期:2015-09-09 06:20:00程序设计版块每日发帖之星
日期:2015-09-19 06:20:00程序设计版块每日发帖之星
日期:2015-09-20 06:20:00每日论坛发贴之星
日期:2015-09-20 06:20:00程序设计版块每日发帖之星
日期:2015-09-22 06:20:00程序设计版块每日发帖之星
日期:2015-09-24 06:20:00
发表于 2016-08-07 00:05 |显示全部楼层
hztj2005 发表于 2016-08-06 23:39
网上找的一段文字:

13. 原子组与防止回溯

发现 大神对正则的理解非常的透彻! 能否说下 有关位于环视中的分组 如何体现原子特性?

论坛徽章:
0
发表于 2016-08-08 00:44 |显示全部楼层
sunzhiguolu 发表于 2016-08-07 00:05
发现 大神对正则的理解非常的透彻! 能否说下 有关位于环视中的分组 如何体现原子特性?


这个问题,你可以看《深入掌握正则表达式》,英文版是173页,其中说到,正则表达式引擎进入环视(Lookaround)以后,引擎保存了该小范围内的回溯路径,当整个环视(Lookaround)测试成功或失败,该小范围内的回溯路径,就被丢弃了。所以,对大范围来说,就表现为“原子特性”。

论坛徽章:
0
发表于 2016-08-08 01:11 |显示全部楼层
本帖最后由 hztj2005 于 2016-08-09 11:17 编辑

一楼第三行:
Lookaround groups are also atomic.
如果不那么刻板的话,可以把atomic理解为“整体性”。这句话就是:环视(Lookaround)组测试是整体成功或失败,不是部分成功或失败。
本质上,就是构建正则表达式的引擎,根据应用需要,这么约定或规定的。

论坛徽章:
2
射手座
日期:2014-10-10 15:59:4715-16赛季CBA联赛之上海
日期:2016-03-03 10:27:14
发表于 2016-08-08 13:49 |显示全部楼层
本帖最后由 yinyuemi 于 2016-08-08 13:49 编辑

http://perldoc.perl.org/perlre.html

这里对(?>pattern)说的挺清楚的

An "independent" subexpression, one which matches the substring that a standalone pattern would match if anchored at the given position, and it matches nothing other than this substring. This construct is useful for optimizations of what would otherwise be "eternal" matches, because it will not backtrack (see Backtracking). It may also be useful in places where the "grab all you can, and do not give anything back" semantic is desirable.

For example: ^(?>a*)ab will never match, since (?>a*) (anchored at the beginning of string, as above) will match all characters a at the beginning of string, leaving no a for ab to match. In contrast, a*ab will match the same as a+b , since the match of the subgroup a* is influenced by the following group ab (see Backtracking). In particular, a* inside a*ab will match fewer characters than a standalone a* , since this makes the tail match.

(?>pattern) does not disable backtracking altogether once it has matched. It is still possible to backtrack past the construct, but not into it. So ((?>a*)|(?>b*))ar will still match "bar".

论坛徽章:
0
发表于 2016-08-09 11:45 |显示全部楼层
8楼第一段没有理解透,不翻译。翻译下后面2段:
For example: ^(?>a*)ab will never match, since (?>a*) (anchored at the beginning of string, as above) will match all characters a at the beginning of string, leaving no a for ab to match.
例如:^(?>a*)ab 不能匹配成功任何字符串,因为(?>a*) (锚定在字符串的开头)将匹配吞噬掉字符串开始所有的a,不给后面的ab留下一个a。
In contrast, a*ab will match the same as a+b , since the match of the subgroup a* is influenced by the following group ab (see Backtracking). 相对而言,a*ab 匹配效果类似a+b,因为 子模式a*的匹配受跟随的子模式ab的影响(看回溯相关部分,如果字符串是aaaaaabc,子模式a*开始将匹配吞噬掉6个a,但这样子模式ab将无法匹配,为了整体成功,进行回溯,a*吐出一个a,只匹配5个a,使子模式ab也能匹配成功)。
In particular, a* inside a*ab will match fewer characters than a standalone a* , since this makes the tail match.
特殊之处在于,a*ab 内部的a* 匹配吞噬的字符,比单独的a*匹配吞噬的字符少,这一点使尾部的ab能够匹配。
(?>pattern) does not disable backtracking altogether once it has matched. It is still possible to backtrack past the construct, but not into it. So ((?>a*)|(?>b*))ar will still match "bar".
(?>pattern) 匹配成功之后,没有一直阻止回溯。回溯绕过整个(?>pattern) 是可以的,只是不能局部回溯。所以 ((?>a*)|(?>b*))ar 可以匹配"bar".

评分

参与人数 1信誉积分 +10 收起 理由
sunzhiguolu + 10 好牛 B 啊!!!

查看全部评分

论坛徽章:
298
程序设计版块每周发帖之星
日期:2016-04-08 00:41:33操作系统版块每日发帖之星
日期:2015-09-02 06:20:00每日论坛发贴之星
日期:2015-09-02 06:20:00程序设计版块每日发帖之星
日期:2015-09-04 06:20:00每日论坛发贴之星
日期:2015-09-04 06:20:00每周论坛发贴之星
日期:2015-09-06 22:22:00程序设计版块每日发帖之星
日期:2015-09-09 06:20:00程序设计版块每日发帖之星
日期:2015-09-19 06:20:00程序设计版块每日发帖之星
日期:2015-09-20 06:20:00每日论坛发贴之星
日期:2015-09-20 06:20:00程序设计版块每日发帖之星
日期:2015-09-22 06:20:00程序设计版块每日发帖之星
日期:2015-09-24 06:20:00
发表于 2016-08-09 12:15 |显示全部楼层
本帖最后由 sunzhiguolu 于 2016-08-09 12:17 编辑
yinyuemi 发表于 2016-08-08 13:49
http://perldoc.perl.org/perlre.html

这里对(?>pattern)说的挺清楚的
For example: ^(?>a*)ab will never match, since (?>a*) (anchored at the beginning of string, as above) will match all characters a at the beginning of string, leaving no a for ab to match. In contrast, a*ab will match the same as a+b , since the match of the subgroup a* is influenced by the following group ab (see Backtracking). In particular, a* inside a*ab will match fewer characters than a standalone a* , since this makes the tail match.

这个例子 不好!
pattern ^(?>a*)ab 对于字符串 aab 或者 ab 来说, 匹配成功与否 跟 定位符 ^ 没有半毛钱关系!
上面这个模式与 模式 a*+b 等价.
您需要登录后才可以回帖 登录 | 注册

本版积分规则

久等啦!10张门票开启你的DTCC2017之旅

2017中国数据库技术大会将于2017年5月11-13日如约而至,本届大会以“数据驱动•价值发现”为主题,共设定2大主场和21个技术专场,云集海内外120+位技术大牛,共同探讨Oracle、MySQL、NoSQL、云端数据库、区块链、深度学习等领域的前瞻性热点话题。
即日起,填写DTCC2017会前调查问卷,即有机会赢取价值2600元的大会门票1张!仅限10张!
----------------------------------------
活动截止时间:2017年5月5日统一公布

问卷入口>>
  

北京皓辰网域网络信息技术有限公司. 版权所有 京ICP证:060528号 北京市公安局海淀分局网监中心备案编号:1101082001
广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员  联系我们:
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP