The Quadratic Problem Nobody Fixed
核心发现
每个正则表达式引擎在寻找所有匹配时都存在 O(n²) 的性能问题，即使是为避免回溯而构建的引擎也不例外。这个问题自 1970 年代以来就存在，但从未被真正解决。
问题本质
以模式 .*a|b 和输入 "bbbbbbbbbb" 为例：
- 在每个位置，引擎先尝试
.*a：扫描整个剩余输入寻找 'a'，找不到，失败 - 然后
b分支匹配单个字符 - 前进一步，重复上述过程
- 总计 n + (n-1) + (n-2) + ... = O(n²) 工作量
现有解决方案
| 引擎 | 方法 | 权衡 |
|---|---|---|
| nim-regex | 单次扫描 + 缓冲区 | 最多 16x 内存开销 |
| Hyperscan | earliest match 语义 | 改变匹配结果 |
| RE# | 两遍扫描 | 保持语义，线性时间 |
RE# 的两遍算法
RE# 通过两遍扫描解决此问题：
- 反向 DFA：标记所有可能的匹配起点
- 正向 DFA：从标记位置解析最长匹配
一个匹配或一万个匹配，都是相同的两遍扫描。
性能对比
| 输入大小 | 普通模式 | Hardened 模式 | 加速比 |
|---|---|---|---|
| 1,000 | 0.7ms | 28μs | 25x |
| 10,000 | 73ms | 303μs | 241x |
| 50,000 | 1.8s | 1.6ms | 1125x |
关键洞见
- 学术论文几乎只关注单匹配问题，然后简单地说"只要迭代"
- 理论将正则简化成"匹配或不匹配"二元问题，丢失了关于匹配位置和数量的所有信息
- Aho-Corasick 早在 1975 年就为固定字符串解决了这个问题，但无法直接推广到正则
探索时间: 2026-03-29 | 来源: Lobsters/compsci