💬 NLP

On the Complexity of the Matching Problem of Regular Expressions with Backreferences

本文通过证明基于强指数时间假设和三角形检测假设的条件下界，确立了带反向引用的正则表达式匹配的细粒度计算复杂度，同时提出了针对单次使用反向引用的改进 $O(n \log^2 n)$ 算法。

原作者： Soh Kumabe, Yuya Uezato

发布于 2026-05-11

📖 1 分钟阅读☕ 轻松阅读

原作者： Soh Kumabe, Yuya Uezato

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

以下是论文《带后向引用的正则表达式匹配问题复杂度》的通俗解释，使用类比进行翻译。

宏观图景："Regex"交通堵塞

想象你是一家俱乐部（计算机系统）的保安。你有一份规则列表（一个正则表达式），用来决定谁能进入。

简单规则：“只允许穿红衬衫的人。”这很容易检查。你看一眼衬衫，说“红色？是的，进来。”无论队伍是 10 人还是 10,000 人，检查所需的时间都是一样的。
问题（ReDoS）：有时，黑客会精心策划一条特定的人员队伍，诱骗保安做大量不必要的无用功。保安不再检查一个人就继续下一个，而是开始检查 A 人，然后 B 人，然后又是 A 人，接着 C 人，再回到 A 人……直到保安因精疲力竭而崩溃。这被称为拒绝服务（ReDoS）攻击。

在现实世界中，这曾导致 Stack Overflow 和 Cloudflare 等大型网站崩溃。论文指出，即使是“二次方”级别的缓慢（检查 100 人需要 10,000 步），也足以让系统崩溃。

反派角色：“后向引用”

标准规则很简单。但现代"Regex"引擎拥有一个超级强大的功能，称为后向引用。

类比：
想象一条规则说：“找到一个词，记住它，然后确保完全相同的词稍后再次出现。”

例子：“找到一个词，称之为'X'。然后，再次找到'X'。”
如果输入是 apple ... apple，则匹配成功。
如果输入是 apple ... banana，则匹配失败。

这个功能对程序员来说极其有用，但它让“保安”的工作变得困难得多。保安必须记住之前看到的内容，并不断将其与当前看到的内容进行比较。论文问道：我们能否构建一个足够快的保安，在处理这些复杂规则时不会感到疲惫？

论文发现：好的、坏的和丑的

作者调查了解决这些匹配问题究竟有多难。他们将问题分为两个方面：难度（为什么困难）和算法（如何解决）。

1. 坏消息：某些规则无法加速

论文证明，对于某些类型的复杂规则，没有任何“灵丹妙药”能让它们变快。

“三角形”问题：他们表明，如果你有一条使用两个变量的规则（例如记住两个不同的词并在稍后检查它们），解决它就像在巨大的社交网络图中寻找三角形一样困难。如果你能快速解决规则问题，你就能快速解决图论问题。由于图论专家认为图论问题本质上就是缓慢的，那么规则问题也必然是缓慢的。
“正交向量”问题：对于拥有更多变量的规则，他们证明了所需时间会随着变量数量的增加呈指数级增长。这就像试图在锁中找到特定的钥匙组合；你拥有的钥匙越多，暴力破解就越不可能快速完成。

要点：如果你的规则太复杂（使用了太多“记住这个”的功能），你就无法为它构建一个快速的引擎。你总会撞上一堵墙。

2. 好消息：简单情况的“近线性”解决方案

然而，论文发现了一个甜蜜点。他们专注于一种特定且常见的规则类型：

"ABCBD"模式：“找到一个词（A），然后一个词（B），然后一个词（C），然后再次找到完全相同的词 B，最后是一个词（D）。”
- 现实例子：“找到一个用户名，然后一个密码，然后一条消息，然后再次找到相同的用户名，最后是一个签名。”

作者发现，虽然这看起来很棘手，但可以非常高效地解决。

旧方法：以前的方法就像在图书馆里检查每一种可能的组合，这需要 $O(n^2)$ 的时间（二次方）。如果书有 1,000 页，就需要 1,000,000 步。
新方法：作者构建了一种新算法，大约需要 $O(n \log^2 n)$ $O (n lo g^{2} n)$ 的时间。
- 类比：想象图书馆使用了一个神奇的索引系统（利用后缀树和因子森林）。保安不需要阅读每一页，而是可以直接跳转到相关部分。如果书有 1,000 页，新方法大约只需要 10,000 步（甚至更少），这是一个巨大的改进。

新算法如何工作（“魔法技巧”）

为了实现这种速度，作者在论文中描述了他们使用的几种巧妙技术：

后缀树（地图）：他们构建了输入字符串的巨型地图。这张地图显示了字符串的每一个可能的结尾。它帮助保安瞬间看到：“哦，这个词'B'出现在这里，也出现在那里。”
轻重路径分解（ Sorting Hat）：他们将地图分为“重”路径（非常常见的路径）和“轻”路径（罕见的路径）。他们只在罕见路径上进行繁重的处理，从而节省时间。
周期性（节奏）：他们注意到，当一个词重复出现时（如"B...B"），字符串通常具有某种节奏或模式。他们利用数学来预测这些模式，而不是检查每一个字母。
因子森林（索引）：这是一种数据结构，充当超快索引，允许保安以恒定时间检查一段文本是否符合规则，无论文本有多长。

结论总结

我们能阻止所有 ReDoS 攻击吗？ 不能。如果规则太复杂（太多的“记住这个”变量），数学上已证明它是缓慢的。
我们能修复最常见的复杂规则吗？ 可以！对于规则记住一个词并在稍后检查一次的具体情况（"ABCBD"模式），作者创建了一种新引擎，其速度几乎与简单规则一样快。
这为什么重要？ 它告诉软件工程师：“不要使用太多的后向引用，否则你会变慢。但如果你以这种特定且常见的方式使用它们，现在你可以使用我们的新方法来保持系统既安全又快速。”

这篇论文本质上在沙地上划了一条线：这里是速度限制无法被打破的地方，而这里是我们找到加速方法的地方。

技术摘要：带反向引用的正则表达式匹配问题的复杂性

1. 问题定义与动机

本文研究了**带反向引用的正则表达式匹配问题（REWB）**的细粒度计算复杂性。虽然经典正则表达式（Regex）可以使用 Thompson 构造法在相对于输入字符串长度 $|w|$ 的线性时间内完成匹配，但实际引擎支持反向引用（例如，使用 (E)x 捕获子串，并使用 \x 重用该子串）。这一功能严格扩展了 Regex 的表达能力（使其能够识别非正则语言，如 $\{ww \mid w \in \Sigma^*\}$ ），但也引入了显著的算法风险。

其动机源于**正则表达式拒绝服务（ReDoS）**攻击，攻击者通过构造特定输入来触发匹配引擎的最坏情况行为。Stack Overflow（2016 年）和 Cloudflare（2019 年）的著名事件表明，即使是基于回溯的引擎中出现的二次方时间行为（ $O(|w|^2)$ ），也可能导致灾难性的服务中断。作者提出了一个根本性问题：是否有可能构建针对 REWB 的 ReDoS 安全引擎，使其在线性或近线性时间内运行？

本文聚焦于 $r$ -use $k$ -REWB，定义为包含 $k$ 个不同变量的表达式，其中任何计算过程中反向引用的执行总数被限制为 $r$ 。

2. 方法论与技术途径

本文采用双重方法：建立条件下界（困难性）并为特定子类设计高效算法。

2.1 困难性结果

作者通过将已知困难问题归约到 REWB 匹配，加强了之前的复杂性结果：

W[2]-困难性：通过归约 $k$ -支配集（ $k$ -Dominating Set）问题，证明了当以表达式大小 $|E|$ 为参数时，REWB 匹配是 W[2]-困难的。这加强了已知的 W[1]-困难性结果。
条件下界（三角形检测）：假设三角形检测问题不存在“几乎线性时间”算法（No-Almost-Linear-Time Hypothesis），他们表明即使是高度受限的2-use 2-REWB问题，也无法在 $O(|w|^{1+\delta})$ 时间内解决（对于任意 $\delta > 0$ ）。
条件下界（ $k$ -OV）：在 $k$ -正交向量（ $k$ -OV）假设下（弱于 SETH），他们证明了 $k$ -REWB 匹配无法在 $O(|w|^{2k-\epsilon})$ 时间内解决。这意味着对于一般的 $k$ ，近线性时间是不可能的。

2.2 算法结果

主要的算法贡献集中在1-use REWB（即变量仅被引用一次的表达式）上。

规范形式转换：作者证明了任何 1-use REWB 都可以转换为一种规范形式，涉及形如 $A (B)_x C \backslash x D$ 的项之和，其中 $A, B, C, D$ 是经典正则表达式。这被称为ABCBD 问题。
分解策略：ABCBD 问题被分解为两个子问题：
1. XYYZ 问题： $B$ 的两个出现位置相邻的情况（ $w = w_A w_B w_B w_D$ ）。该情况利用Crochemore 的最大局部幂枚举以及由转换幺半群导出的最终周期集的性质来解决。
2. 分支 ABCBD 问题： $B$ 的两个出现位置被非空的 $C$ 分隔，且紧随两个 $B$ 出现位置之后的字符不同的情况。
后缀树与轻重链分解：对于分支情况，算法利用输入字符串 $w$ 的后缀树。它采用轻重链分解（heavy-light decomposition）来划分搜索空间。
数据结构：
- 因子分解森林（Factorization Forests）：用于在线性预处理后，以常数时间评估子串上的正则表达式成员资格。
- 转换幺半群（Transition Monoids）：利用其高效跟踪正则表达式 $A, B, C, D$ 的状态。
- 自定义枚举器：作者设计了专门的数据结构（RightEnumerator、LeftEnumerator、AuxiliaryEnumerator）来处理转换枚举。这些结构使用惰性更新和**不相交集合合并（DSU）**策略来管理与子串 $w_B$ 长度相关的约束。

3. 关键结果

困难性

定理 3：REWB 匹配在以表达式大小为参数时是 W[2]-困难的。
定理 4：假设三角形检测假设成立，2-use 2-REWB 匹配需要超线性时间（具体而言，不是 $O(|w|^{1+\delta})$ ）。
定理 5：在 $k$ -OV 假设下， $k$ -REWB 匹配需要 $\Omega(|w|^{2k-\epsilon})$ 时间。

算法

定理 7（主要结果）：ABCBD 问题存在一个 $O(|w| \log^2 |w|)$ 时间算法。隐藏常数以正则表达式 $A, B, C, D$ 的大小呈指数级依赖（ $2^{O((|A|+|B|+|C|+|D|)^2)}$ ）。
定理 8：因此，1-use REWB 匹配问题存在一个 $O(|w| \log^2 |w|)$ 时间算法。
定理 9：XY $\alpha$ Z 问题（将 XYYZ 推广到 $\alpha$ 次重复）存在一个 $O(|w| \log |w|)$ 时间算法。

这些结果代表了相对于 Nogami 和 Terauchi（MFCS 2025）之前针对 ABCBD 问题的最佳已知 $O(|w|^2)$ 算法的重大改进。

4. 意义与主张

本文声称提供了对 REWB 匹配复杂性景观的根本性理解：

ReDoS 安全性：它确立了虽然通用的 REWB 匹配在近线性时间内可能是不可处理的，但一个具有实际意义的子类（1-use REWB）可以在近线性时间内完成匹配。这表明支持 1-use 反向引用的引擎在理论上可以变得 ReDoS 安全。
细粒度复杂性：这项工作划定了可处理与不可处理情况之间的界限。它表明，即使只有 2 个变量，将反向引用的使用次数从 1 增加到 2，也可能将问题推离近线性区域。
算法创新：本文引入了一个复杂但高度非平凡的算法框架，结合后缀树、因子分解森林和转换幺半群，解决了此前被认为需要二次方时间的问题。

作者明确指出，他们的算法是统一的（uniform），意味着它同时处理表达式和输入字符串，而不依赖于依赖于固定表达式的非统一建议。他们承认，对表达式大小 $|E|$ 的指数级依赖仍然是处理非常大表达式时的局限性，并且他们留下了以下未解问题：是否存在真正的线性时间算法（ $O(|w|)$ ），或者是否可以去除对数因子。

5. 局限性与开放问题

本文指出了几个开放方向：

$r$ -use 1-REWB 的复杂性：当 $r \ge 2$ 时， $r$ -use 1-REWB 的复杂性仍然未解。
线性时间： $O(|w| \log^2 |w|)$ 的界限能否改进为 $O(|w|)$ 。
表达式依赖：在保持对 $|w|$ 近线性依赖的同时，将对 $|E|$ 的指数依赖降低到多项式级别。
更广泛的功能：将这些结果扩展到其他实用的正则表达式功能，如 lookahead/lookbehind（前瞻/后顾）、原子分组以及贪婪/懒惰星号。