🦁 The quadratic problem nobody fixed

⭐⭐⭐⭐⭐ 5星 | 作者: iev (iev.ee) | 来源: Hacker News

正则表达式性能优化算法编译器

核心问题

搜索一个文档需要一个小时。搜索一个大100倍的文档不是需要100小时——而是接近3个小时。每个正则表达式引擎，从1970年代起就存在这个问题，至今无人解决。

            关键发现：所有标榜线性时间匹配的引擎（RE2、Go regexp、rust regex、.NET NonBacktracking），在调用 find_iter/FindAll 时保证立即失效。最坏情况复杂度是 O(m × n²)
        

以模式 .*a|b 和 n 个 'b' 的输入为例：

在每个位置，引擎先尝试 .*a - 扫描整个剩余输入寻找 'a'，找不到，失败然后 b 分支匹配单个字符前进一个位置，重复总共 n + (n-1) + (n-2) + ... = O(n²) 工作

教科书式的三角和。

几乎所有正则论文都只关注单匹配问题，然后用"只需迭代"一笔带过。理论把正则简化成"匹配或不匹配"这个二元问题——这适合证明定理，但丢弃了实践中几乎所有重要信息：

一旦简化，正则的"全部匹配"问题就消失了。

为固定字符串解决了这个问题。在一次 O(n) 扫描中找到多个固定字符串的所有匹配。但它只适用于字面字符串列表，不支持正则。

真正的线性时间全匹配引擎。使用"最早匹配"语义——一进入匹配状态就报告，而非继续找最长匹配。这改变了结果。

RE# 是第一个能在两遍扫描中找到所有匹配的引擎，无论模式和输入如何，且不改变语义：

一个匹配或一万个匹配，都是同样的两遍扫描。

可选模式，保证线性时间，即使在对抗性输入上：

输入大小	正常模式	Hardened	加速比
1,000	0.7ms	28μs	25x
10,000	73ms	303μs	241x
50,000	1.8s	1.6ms	1,125x

2663个单词的字典作为模式，匹配 ~900KB 英文散文：

            "一旦把正则简化为'匹配或不匹配'，全部匹配问题就消失了——被塞进一个与实际使用方式几乎无关的框架中。"
        

RE# 证明了这个问题可以被解决——但需要全新的算法思路。