原子团清晰度
vks*_*vks 10 regex pcre backtracking
考虑这个正则表达式.
a*b
这将失败的情况下 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac
这会使67调试器中的步骤失败.
现在考虑这个正则表达式.
(?>a*)b
这将失败的情况下 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac
这会使133调试器中的步骤失败.
最后这个正则表达式:
a*+b (a variant of atomic group)
这将失败的情况下 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac
这会使67调试器中的步骤失败.
当我检查基准测试atomic group (?>a*)b执行179%得更快.
现在原子组禁用回溯.所以比赛中的表现很好.
但为什么步数更多呢？有人可以解释一下吗？
为什么会有差异.在两个原子团
(?>a*)b和之间的步骤a*+b.
他们的工作方式不同吗
什么是回溯？
该发动机来量词是贪婪的默认.贪婪的修饰符可根据需求匹配所有可能和回溯,从而实现高效匹配,
由Greedy vs. Reluctant vs. Possessive Quantifiers引用:
一个贪婪的量词首先匹配尽可能多地.所以
.*匹配整个字符串.然后匹配器尝试匹配f以下内容,但没有剩下的字符.因此它"回溯",使得贪婪的量词匹配少一点(在字符串末尾留下"o"不匹配).这仍然f与正则表达式中的不匹配,因此它"再回溯"了一步,使得贪婪的量词再次减少一点(在字符串末尾留下"oo"无法比拟).这仍然f与正则表达式中的不匹配,因此它再回溯一步(在字符串末尾留下"foo"不匹配).现在,匹配器最终匹配f正则表达式,并且o下一个o匹配.成功![...]
这与这有什么关系a*+b？
在/a*+b/:
a字面意思是"a".-
*+零或更多,占有欲. b字面字符"b".
正如Greedy vs. Reluctant vs. Possessive Quantifiers所引用:
一个占有欲量词就像贪婪的量词,但它不会回溯.所以它从
.*匹配整个字符串开始,没有任何不匹配的东西.然后没有什么可以与f正则表达式中的匹配.由于占有量词不会回溯,因此匹配失败.
为什么这有关系？
如果它自己进行(有效)匹配,机器将无法实现.在这里看一个不错的例子:程序在匹配正则表达式时永远运行.在许多情况下,快速编写的正则表达式可能效率不高,并且可能很容易在部署中出现问题.
什么是原子团？
在原子组内的模式完成匹配之后,它永远不会放手.研究这个例子:
Pattern: (?>\d\w{2}|12)c
Matching string: 12c
看起来完全合法,但这场比赛失败了.步骤很简单:原子组的第一次交替完全匹配 - \d\w{2}消耗12c.然后该小组完成其匹配 - 现在这是我们的指针位置:
Pattern: (?>\d\w{2}|12)c
^
Matching string: 12c
^
模式进展.现在我们尝试匹配c,但没有c.匹配失败,而不是试图回溯(释放\d\w{2}和消费12).
那么这是一个坏主意!为什么我们会阻止回击,Unihedron？
现在假设我们正在使用JSON对象进行操作.这个文件不小.从最后回溯将是一个坏主意.
"2597401":[{"jobID":"2597401",
"account":"TG-CCR120014",
"user":"charngda",
"pkgT":{"pgi/7.2- 5":{"libA":["libpgc.so"],
"flavor":["default"]}},
"startEpoch":"1338497979",
"runTime":"1022",
"execType":"user:binary",
"exec":"ft.D.64",
"numNodes":"4",
"sha1":"5a79879235aa31b6a46e73b43879428e2a175db5",
"execEpoch":1336766742,
"execModify":"Fri May 11 15:05:42 2012",
"startTime":"Thu May 31 15:59:39 2012",
"numCores":"64",
"sizeT":{"bss":"1881400168","text":"239574","data":"22504"}},
{"jobID":"2597401",
"account":"TG-CCR120014",
"user":"charngda",
"pkgT":{"pgi/7.2-5":{"libA":["libpgc.so"],
"flavor":["default"]}},
"startEpoch":"1338497946",
"runTime":"33" "execType":"user:binary",
"exec":"cg.C.64",
"numNodes":"4",
"sha1":"caf415e011e28b7e4e5b050fb61cbf71a62a9789",
"execEpoch":1336766735,
"execModify":"Fri May 11 15:05:35 2012",
"startTime":"Thu May 31 15:59:06 2012",
"numCores":"64",
"sizeT":{"bss":"29630984","text":"225749","data":"20360"}},
{"jobID":"2597401",
"account":"TG-CCR120014",
"user":"charngda",
"pkgT":{"pgi/7.2-5": {"libA":["libpgc.so"],
"flavor":["default"]}},
"startEpoch":"1338500447",
"runTime":"145",
"execType":"user:binary",
"exec":"mg.D.64",
"numNodes":"4",
"sha1":"173de32e1514ad097b1c051ec49c4eb240f2001f",
"execEpoch":1336766756,
"execModify":"Fri May 11 15:05:56 2012",
"startTime":"Thu May 31 16:40:47 2012",
"numCores":"64",
"sizeT":{"bss":"456954120","text":"426186","data":"22184"}},{"jobID":"2597401",
"account":"TG-CCR120014",
"user":"charngda",
"pkgT":{"pgi/7.2-5":{"libA":["libpgc.so"],
"flavor":["default"]}},
"startEpoch":"1338499002",
"runTime":"1444",
"execType":"user:binary",
"exec":"lu.D.64",
"numNodes":"4",
"sha1":"c6dc16d25c2f23d2a3321d4feed16ab7e10c2cc1",
"execEpoch":1336766748,
"execModify":"Fri May 11 15:05:48 2012",
"startTime":"Thu May 31 16:16:42 2012",
"numCores":"64",
"sizeT":{"bss":"199850984","text":"474218","data":"27064"}}],
哦,哦......
你明白我的意思吗？:P
我会让你弄清楚剩下的,并试图找到更多关于占有量词和原子群的信息; 我在这篇文章中没有写任何其他内容.这里是JSON的来源,几天前我看到了答案,非常鼓舞人心:REGEX重新格式化.
阅读
作者注:
这个答案针对问题1,由赏金文本提供"我期待调试器需要更多步骤的确切原因.我不需要解释原子组如何工作的答案." ;
杰里的回答非常好地解决了其他问题,而我的另一个答案是通过所提到的结构,它们如何工作以及为什么它们很重要.要获得全部知识,仅仅阅读这篇文章是不够的!
正则表达式中的每个组都需要一步进入和退出组.
什么？!
是的,我很认真,继续读下去......
首先,我想向你展示量化的非捕获组,而没有组:
Pattern 1: (?:c)at
Pattern 2: cat
那么到底发生了什么？我们将模式与"concat"正则表达式引擎上的测试字符串进行匹配,并禁用优化:
当我们参与其中时,我会向您展示更多群组:
不好了!我要避免使用群组!
可是等等!请注意,采取相匹配的步数有没有与本场比赛的表现相关.正如我所提到的,pcre引擎优化了大部分"不必要的步骤".尽管在禁用优化的引擎上采取了更多步骤,但原子组仍然是最有效的.
也许相关: