在此示例中，为什么节点的回溯正则表达式比RE2快

Question

我需要接受用户的正则表达式 - 疯了，我知道。 Google RE2正则表达式解析器比基于PCRE的解析器更安全，因为它不使用回溯，因此可以防止灾难性的回溯，无限循环和一般混乱。据称通常会更快。在我只测试系统日志行的测试用例中，它的速度慢了300％。有什么想法吗？

我在Ubuntu上使用Node v7.7.3。

有问题的代码：

const SYSLOG_LINE_REGEX = new RegExp([
    /(<[0-9]+>)?/, // 1 - optional priority
    /([a-z]{3})\s+/, // 2 - month
    /([0-9]{1,2})\s+/, // 3 - date
    /([0-9]{2}):/, // 4 - hours
    /([0-9]{2}):/, // 5 - minutes
    /([0-9]{2})/, // 6 - seconds
    /(\s+[\w.-]+)?\s+/, // 7 - host
    /([\w\-().0-9/]+)/, // 8 - process
    /(?:\[([a-z0-9-.]+)\])?:/, // 9 - optional pid
    /(.+)/ // 10  message
].map(regex => regex.source).join(''), 'i');
const parts = SYSLOG_LINE_REGEX.exec(log.trim());

更新：

• 使用节点模块[email protected]
• 使用node-re2包中包含的2016年11月30日的re2 C ++代码。
• 我安装了libre2-dev软件包版本20160501 + dfsg-1。也许我应该更新node-re2下的源代码，或者只是链接到系统库。

Answer 1

RE2具有线性最坏情况复杂性。 Node.js的Irregexp引擎具有指数最坏情况的复杂性。

但！引擎的最坏情况行为不仅是正则表达式的函数，也是正在测试的输入的函数。正则表达式/(a+)+$/在Node.js中是最坏情况的指数，但如果你匹配除了aaaaaaaaaa...a以外的任何东西它会很快运行。正则表达式的平均情况匹配时间与其最坏情况的复杂性不同。 Node.js引擎开发人员可能优化了最坏情况复杂性的平均情况复杂性。