为什么使用u和i修饰符会导致一个版本的模式比另一个版本多出10倍？
Lau*_*rel 0 regex unicode performance pcre backtracking
我正在对一个字符串测试两个几乎相同的正则表达式(在regex101.com上),我注意到他们采取的步骤数量存在巨大差异.这是两个正则表达式:
(Stake: £)(\d+(?:\.\d+)?)
(winnings: £)(\d+(?:\.\d+)?)
这是我跑他们对字符串(带修饰符g,i,m,u):
开始游戏,信用:£200.00游戏数量:1,赌注:£2.00旋转卷轴:NINE SEVEN KINGKING STAR ACEQUEEN JACK KINGtotal奖金:£0.00End游戏,信用:£198开始......
旁注:字符串/正则表达式不是我的,我只是从SE的其他地方拿走它们,看到这种情况发生了.它与这个问题无关,但我认为它需要归因.
(注意:Regex101似乎得到了PHP的PCRE正则表达式的支持."优化关闭"设置可能PCRE_NO_START_OPTIMIZE | PCRE_NO_AUTO_POSSESS.感谢Lucas Trzesniewski解决这个问题并编写一些C#代码来测试它.)
优化:第一个需要304个步骤来匹配,而第二个需要21个步骤.这是我想知道的巨大差异.
优化关闭:第一个需要333步才能匹配,而第二个需要317步.这将表明第一个模式未能优化,而不是第二个模式.
有趣的是,没有u修饰符,第一个模式(优化开启)只需要40步.(但它不会改变其他任何东西的表现,也不会改变正则表达式的最终匹配.)
我想知道regex101的优化引擎(PCRE)在步数方面造成了这种差异.我特别在寻找u启用nicode 时较长的正则表达式减少步数的原因.
有没有理由发生这种情况,或者这是引擎中的错误？
Luc*_*ski 10
Regex101使用PCRE库(默认情况下),因此其调试器与PCRE的行为有关.PCRE库通过其标志支持自动调出选项,该PCRE_AUTO_CALLOUT标志在匹配的每一步调用回调函数.我99.99%肯定regex101的调试器是如何工作的.每个callout调用都作为调试器中的一个步骤注册.
使用regex101进行测试
现在,看看所涉及的不同步骤,首先,没有u选项:
注意文本光标如何从Start Game零件直接跳到Stake零件.
添加后会发生什么u？
请注意,跳转不再发生,这是其他步骤的来源.
该u选项有什么作用？它设置PCRE_UTF8 | PCRE_UCP- 是的,同时这两个,这个PCRE_UCP标志在这里很重要.
以下是pcreunicode文档所说的内容:
不区分大小写的匹配仅适用于值小于128的字符,除非PCRE是使用Unicode属性支持构建的.一些Unicode字符(例如希腊语sigma)具有两个以上与大小写等效的代码点.直到并包括PCRE版本8.31,仅支持一对一的案例映射,但是后来的版本(具有Unicode属性支持)确实将所有版本的字符(例如希腊语sigma)视为大小写等效.
由于在Unicode模式下处理不区分大小写的额外复杂性,引擎不能只跳过所有文本.要验证这是罪魁祸首,让我们尝试使用gmu标志(即有u但没有 i):
即使使用优化也是如此u,这几乎证实了这一假设.
意见
您看到的慢速路径看起来就好像PCRE_NO_START_OPTIMIZE已经被使用过(这可能是regex101 禁用内部引擎优化的一部分,以及PCRE_NO_AUTO_POSSESS这里没有关系).
更多关于它的文档:
pcre_exec()为了加快流程,在匹配开始时会使用许多优化.例如,如果已知未锚定的匹配必须以特定字符开头,则它会在主题中搜索该字符,如果找不到该字符则立即失败,而不实际运行主匹配函数.
由于某种原因(稍后会变得明显),PCRE未能将一个s或一个k字母注册为必需的起始字符,并且不能使用锚定优化.在这方面,拉丁字母的所有其他字母都可以正常工作.
这就是为什么Stake需要更多步骤winnings:引擎只是不跳过检查.
直接用PCRE测试
这是我与PCRE 8.38一起使用的测试程序,这是本文中提供的最新PCRE1版本.
#include <stdio.h>
#include <string.h>
#include <pcre.h>
static int calloutCount;
static int callout_handler(pcre_callout_block *c) {
++calloutCount;
return 0;
}
static void test_run(const char* pattern, pcre* re, pcre_extra* extra) {
int rc, startOffset;
int ovector[3 * 3];
pcre_callout = callout_handler;
calloutCount = 0;
startOffset = 0;
const char *subject = "Start Game, Credit: £200.00game num: 1, Stake: £2.00Spinning Reels:NINE SEVEN KINGKING STAR ACEQUEEN JACK KINGtotal winnings: £0.00End Game, Credit: £198Start...";
for (;;) {
rc = pcre_exec(re, extra, subject, strlen(subject), startOffset, 0, ovector, sizeof(ovector) / sizeof(int));
if (rc < 0)
break;
startOffset = ovector[1];
}
printf("%-30s %s => %i\n", pattern, extra ? "(studied) " : "(not studied)", calloutCount);
}
static void test(const char* pattern) {
pcre *re;
const char *error;
int erroffset;
pcre_extra *extra;
re = pcre_compile(pattern, PCRE_AUTO_CALLOUT | PCRE_CASELESS | PCRE_MULTILINE | PCRE_UTF8 | PCRE_UCP, &error, &erroffset, 0);
if (re == 0)
return;
extra = pcre_study(re, 0, &error);
test_run(pattern, re, extra);
if (extra)
test_run(pattern, re, NULL);
pcre_free_study(extra);
pcre_free(re);
}
int main(int argc, char **argv) {
printf("PCRE version: %s\n\n", pcre_version());
test("(Stake: £)(\\d+(?:\\.\\d+)?)");
test("(winnings: £)(\\d+(?:\\.\\d+)?)");
return 0;
}
我得到的输出如下:
PCRE version: 8.38 2015-11-23
(Stake: £)(\d+(?:\.\d+)?) (studied) => 40
(Stake: £)(\d+(?:\.\d+)?) (not studied) => 302
(winnings: £)(\d+(?:\.\d+)?) (studied) => 21
(winnings: £)(\d+(?:\.\d+)?) (not studied) => 21
在这里,我们可以看到研究模式在第一种情况下有所不同,但在第二种情况下则不然.
研究模式意味着以下内容:
研究模式有两个作用:首先,计算匹配模式所需的主题字符串长度的下限.这并不意味着有任何匹配的字符串,但它确保没有更短的字符串匹配.该值用于通过尝试匹配短于下限的字符串来避免浪费时间.您可以通过该
pcre_fullinfo()功能在调用程序中找到该值.研究模式对于没有单个固定起始字符的非锚定模式也很有用.创建可能的起始字节的位图.这加速了在主题中找到开始匹配的位置.(在16位模式下,位图用于小于256的16位值.在32位模式下,位图用于小于256的32位值.)
从结果和文档描述中,您可以得出结论,PCRE认为该S字符不是锚定字符,并且在无情况Unicode模式下,它需要创建位图.位图允许应用优化.
现在,这是PCRE2版本,针对PCRE2 v10.21编译,这是本文的最新版本.结果将不足为奇,因为PCRE2 总是研究你提供它的模式,没有问题.
#include <stdio.h>
#include <string.h>
#define PCRE2_CODE_UNIT_WIDTH 8
#include <pcre2.h>
static int callout_handler(pcre2_callout_block *c, void *data) {
++*((int*)data);
return 0;
}
static void test(const char* pattern) {
pcre2_code *re;
int error;
PCRE2_SIZE erroffset;
pcre2_match_context *match_context;
pcre2_match_data *match_data;
int rc, startOffset = 0;
int calloutCount = 0;
PCRE2_SIZE *ovector;
const PCRE2_SPTR subject = (PCRE2_SPTR)"Start Game, Credit: £200.00game num: 1, Stake: £2.00Spinning Reels:NINE SEVEN KINGKING STAR ACEQUEEN JACK KINGtotal winnings: £0.00End Game, Credit: £198Start...";
re = pcre2_compile((PCRE2_SPTR)pattern, PCRE2_ZERO_TERMINATED, PCRE2_AUTO_CALLOUT | PCRE2_CASELESS | PCRE2_MULTILINE | PCRE2_UTF | PCRE2_UCP, &error, &erroffset, 0);
if (re == 0)
return;
match_context = pcre2_match_context_create(0);
pcre2_set_callout(match_context, callout_handler, &calloutCount);
match_data = pcre2_match_data_create_from_pattern(re, 0);
ovector = pcre2_get_ovector_pointer(match_data);
for (;;) {
rc = pcre2_match(re, subject, PCRE2_ZERO_TERMINATED, startOffset, 0, match_data, match_context);
if (rc < 0)
break;
startOffset = ovector[1];
}
printf("%-30s => %i\n", pattern, calloutCount);
pcre2_match_context_free(match_context);
pcre2_match_data_free(match_data);
pcre2_code_free(re);
}
int main(int argc, char **argv) {
char version[256];
pcre2_config(PCRE2_CONFIG_VERSION, &version);
printf("PCRE version: %s\n\n", version);
test("(Stake: £)(\\d+(?:\\.\\d+)?)");
test("(winnings: £)(\\d+(?:\\.\\d+)?)");
return 0;
}
这是结果:
PCRE version: 10.21 2016-01-12
(Stake: £)(\d+(?:\.\d+)?) => 40
(winnings: £)(\d+(?:\.\d+)?) => 21
对.使用学习时与PCRE1相同的结果.
实施细节
我们来看看实现细节吧？PCRE将模式编译为操作码,我们可以使用该pcretest程序读取.
这是输入文件:
/(Stake: £)(\d+(?:\.\d+)?)/iDW8
Start Game, Credit: £200.00game num: 1, Stake: £2.00Spinning Reels:NINE SEVEN KINGKING STAR ACEQUEEN JACK KINGtotal winnings: £0.00End Game, Credit: £198Start...
/(winnings: £)(\d+(?:\.\d+)?)/iDW8
Start Game, Credit: £200.00game num: 1, Stake: £2.00Spinning Reels:NINE SEVEN KINGKING STAR ACEQUEEN JACK KINGtotal winnings: £0.00End Game, Credit: £198Start...
它的格式很简单:分隔符中的模式后跟选项,以及一个或多个输入字符串.
选项是:
i-PCRE_CASELESSD- 打开调试模式:显示操作码和模式信息W-PCRE_UCP8-PCRE_UTF8
结果就是......
PCRE version 8.38 2015-11-23
/(Stake: £)(\d+(?:\.\d+)?)/iDW8
------------------------------------------------------------------
0 55 Bra
3 24 CBra 1
8 clist 0053 0073 017f
11 /i ta
15 clist 004b 006b 212a
18 /i e: \x{a3}
27 24 Ket
30 22 CBra 2
35 prop Nd ++
39 Brazero
40 9 Bra
43 /i .
45 prop Nd ++
49 9 Ket
52 22 Ket
55 55 Ket
58 End
------------------------------------------------------------------
Capturing subpattern count = 2
Options: caseless utf ucp
No first char
Need char = ' '
Start Game, Credit: £200.00game num: 1, Stake: £2.00Spinning Reels:NINE SEVEN KINGKING STAR ACEQUEEN JACK KINGtotal winnings: £0.00End Game, Credit: £198Start...
0: Stake: \x{a3}2.00
1: Stake: \x{a3}
2: 2.00
/(winnings: £)(\d+(?:\.\d+)?)/iDW8
------------------------------------------------------------------
0 60 Bra
3 29 CBra 1
8 /i winning
22 clist 0053 0073 017f
25 /i : \x{a3}
32 29 Ket
35 22 CBra 2
40 prop Nd ++
44 Brazero
45 9 Bra
48 /i .
50 prop Nd ++
54 9 Ket
57 22 Ket
60 60 Ket
63 End
------------------------------------------------------------------
Capturing subpattern count = 2
Options: caseless utf ucp
First char = 'w' (caseless)
Need char = ' '
Start Game, Credit: £200.00game num: 1, Stake: £2.00Spinning Reels:NINE SEVEN KINGKING STAR ACEQUEEN JACK KINGtotal winnings: £0.00End Game, Credit: £198Start...
0: winnings: \x{a3}0.00
1: winnings: \x{a3}
2: 0.00
现在这很有趣!
首先,我们看到第一个模式获得No first char,而第二个模式获得First char = 'w' (caseless).
该S标识为:clist 0053 0073 017f,而k变成clist 004b 006b 212a.这些是这些字母的匹配代码点集.它们代表什么？
S:0053 =S,0073 =s,017f =?(拉丁文小写字母S) - Yikes.k:004b =K,006b =k,212a =?(开尔文标志) - 双倍.
不应用优化,因为这两个字母的大小写折叠包括ASCII范围之外的字符.
现在你看:)
PHP的解决方案
那么,你可以用PHP做什么？您添加S修饰符:
当一个模式将被多次使用时,值得花更多时间分析它以加快匹配所需的时间.如果设置了此修改器,则执行此额外分析.目前,研究模式仅对于没有单个固定起始字符的非锚定模式有用.
Regex101不支持模式学习AFAIK.
| 归档时间： |
|
| 查看次数： |
266 次 |
| 最近记录： |