regex - 为什么字符类比交替更快？

Question

似乎使用字符类比在示例中的交替更快：
[abc]vs(a|b|c)
我听说它被推荐，并通过一个简单的测试使用Time::HiRes我验证了它（慢了大约 10 倍）。
在捕获括号产生影响的情况下使用(?:a|b|c)也不会改变结果。
但我不明白为什么。我认为这是因为回溯，但我在每个位置看到它的方式有 3 个字符比较，所以我不确定回溯如何影响交替。这是实施的交替性质的结果吗？

Answer 1

这是因为“OR”构造在交替之间| 回溯：如果第一个交替不匹配，则引擎必须在交替匹配期间指针位置移动之前返回，以继续匹配下一个交替；而字符类可以按顺序前进。在禁用优化的正则表达式引擎上查看此匹配：

Pattern: (r|f)at
Match string: carat

Pattern: [rf]at
Match string: carat

---

但简而言之，pcre引擎优化这个（单个文字字符 -> 字符类）这一事实已经很好地暗示了交替效率低下。

Answer 2

因为字符类 like[abc]是不可约的并且可以优化，而替代 like(?:a|b|c)也可能是(?:aa(?!xx)|[^xba]*?|t(?=.[^t])t).

作者选择不优化正则表达式编译器来检查替代的所有元素都是单个字符。

“检查下一个字符是否在此字符类中”和“检查字符串的其余部分是否与这些正则表达式中的任何一个匹配”之间存在很大差异。