积极的后视与匹配重置 (K) 正则表达式功能

Question

我刚刚了解到 Ruby 正则表达式中明显未记录的K行为(感谢 anubhava 的这个回答(。这个特性(可能被命名为Keep？(也存在于PHP、Perl和Python正则表达式风格中。它在其他地方被描述为">从要返回的匹配项中删除到目前为止匹配的内容"。

"abc".match(/abKc/)     # matches "c"

此行为是否与下面使用的正后视标记相同？

"abc".match(/(?<=ab)c/)  # matches "c"

如果不是，两者有什么区别？

Answer 1

使用 String#scan 方法更容易看出K和(?<=...)之间的区别。

回溯是一个零宽度断言，它不使用字符，并且从当前位置(向后(测试：

> "abcdefg".scan(/(?<=.)./)
=> ["b", "c", "d", "e", "f", "g"]

"keep"功能K(不是锚点(定义了模式中的一个位置，在该位置中，到目前为止与左侧模式匹配的所有内容都将从匹配结果中删除。但是在消耗K之前匹配的所有字符，它们只是不会出现在结果中：

> "abcdefg".scan(/.K./)
=> ["b", "d", "f"]

行为与没有K的行为相同：

> "abcdefg".scan(/../)
=> ["ab", "cd", "ef"]

除了从结果中删除K之前的字符。

K的一个有趣用途是模拟可变长度的回溯，这在 Ruby 中是不允许的(PHP 和 Perl 也是如此(，或者避免创建唯一的捕获组。例如，可以使用K实现(?<=a.*)f.：

> "abcdefg".match(/a.*Kf./)
=> #<MatchData "fg">

另一种方法是编写/a.*(f.)/，但K避免了创建捕获组的需要。

请注意，K功能也存在于 python 正则表达式模块中，即使这个模块也允许可变长度的回溯。

Answer 2

在回答了另一个问题并包括一个隐喻之后，我被要求在这个规范页面上发布一个答案。

在完善给定的正则表达式时，我努力通过简单的层次结构来优化模式。准确性，然后是效率，然后是可重复性，然后是简洁性。 当高阶标准不完美/次优时，通常不考虑低阶标准。

<小时 />

请允许我简化所问问题中已经简化的任务。与其匹配c，不如让我们与 PHP 进行一个或多个零宽度匹配，并比较/aK/与/(?<=a)/，两者都返回相同的结果。

1. 在这个简单的演示中比较两种图案设计时，精度是相同的。

2. 效率是确定赢家和输家的地方。

   $string = 'abcbacbacbabcbabcbabcccbbaaabacbabbcacbabca';
   $regex1 = '/aK/'; // 14 matches, 42 steps https://regex101.com/r/j4Jrrj/1
   $regex2 = '/(?<=a)/'; // 14 matches, 167 steps https://regex101.com/r/JuZJDE/1
   

原因如下：使用 $regex2 ，正则表达式引擎采取的每一步(字符串中的每个字符遍历(，它都必须转身检查可能的a。 相反，$regex1在角色中快速行进(除了最直接的角色之外别无处寻找(，如果遇到a，那么就会进行匹配，不需要环顾四周。作为一般提示，环顾(和捕获组(可能会导致效率损失 - 值得运行一些测试，看看小的调整如何影响您的模式效率。

<小时 />

一种常见的方案是在不使用任何字符的情况下拆分字符串。将oneTwoThreeFourFiveSix拆分为小写字母和大写字母，使用preg_split()可以通过以下方式完成：

1. "双向查看" - /(?<=[a-z])(?=[A-Z])/ 将在 22 个字符的字符串上执行 70 个步骤(因为它需要在每个位置查看一个或两个方向(。
2. "匹配任何更低、释放、展望" - /[a-z]K(?=[A-Z])/将采取 78 步(因为小写字母的数量，然后采取 2 个后续操作(。
3. "匹配连续的低点、释放、展望" - /[a-z]+K(?=[A-Z])/将采取 41 个步骤(因为它只对最后一个低点执行其他操作(。

当然：preg_match()可以分 38 步遍历带有 /(?:^|[A-Z])[a-z]*/ 的字符串，但这可能是在实际项目上下文中对准确性的不同讨论。

<小时 />

当我们停止要求正则表达式引擎停止在每个字符上时，竞争可能会加剧。

   $string = 'abcbacbacbabcbabcbabcccbbaaabacbabbcacbabca';
   $regex1 = '/abKc/'; // 5 matches, 45 steps https://regex101.com/r/j4Jrrj/2
   $regex2 = '/(?<=ab)c/'; // 5 matches, 44 steps https://regex101.com/r/JuZJDE/2

$regex1遍历字符串，直到找到一个a，然后是一个b，然后是一个c。
$regex2遍历琴弦，直到找到c，然后向后寻找b，然后寻找a。

示例字符串包含 a 14x、c 24x、ab 7x 和 bc 6x。字符的存在和顺序对步数有直接影响。根据记录，/abc/只需要 38 个步骤，因此K需要 7 个步骤(对于匹配的每个ab(，但/ab(c)/成本更高——50 个步骤。

<小时 />

为了显示外观优于K，请搜索出现在Price: $5666;Weight: 7145;Height: 420;Width: 411;数字之后的分号。由于数字出现的频率远远高于分号，因此/(?<=d);/需要 20 个步骤，/dK;/需要 46 个步骤。

外卖

要求正则表达式引擎对字符串中的每个位置执行操作是一项低效的任务 - 即使您更喜欢可读性。

除此之外，字符的频率和顺序通常决定了正则表达式引擎的性能。