5

我需要接受用户的正则表达式——我知道这很疯狂。Google RE2 正则表达式解析器比基于 PCRE 的解析器更安全，因为它不使用回溯，从而防止灾难性回溯、无限循环和一般混乱。据称它通常更快。在我的测试用例中，它只解析一条 syslog 行，它慢了 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());

更新：

  • 使用节点模块 re2@1.4.1
  • 使用 node-re2 包中包含的日期为 2016 年 11 月 30 日的 re2 C++ 代码。
  • 我安装了 libre2-dev 软件包版本 20160501+dfsg-1。也许我应该更新 node-re2 下的源代码，或者让它简单地链接到系统库。
4

1 回答 1

1

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

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

于 2019-03-12T13:23:03.843 回答