Stack Overflow 上 262,715 个正则表达式问题尚未解答的谜团

# 262,715 个 Stack Overflow 正则表达式问题未能解答的答案 | Ian Erik Varatalu 来源：https://iev.ee/blog/what-262715-regex-questions-havent-answered/ 作为我的博士学位研究的一部分，专注于正则表达式引擎算法和效率，我一直在构建 RE#（https://github.com/ieviev/resharp），这是一个支持补集（complement）、交集（intersection）和环视（lookarounds）的正则表达式引擎。我想更新 Stack Overflow 上一些过时的正则表达式答案，但回答需要 10 点声望值，而且鉴于那里已经几乎没人提问了（https://blog.pragmaticengineer.com/stack-overflow-is-almost-dead/），我有点担心自己会错失这个机会：你需要 10 点声望才能回答。 于是我下载了 Stack Overflow 数据转储（https://stackoverflow.com/help/data-dumps），大约 106GB 的 XML 帖子，并浏览了所有 262,715 个标记为 `regex` 的问题，总浏览量达 859,351,734 次。我想测试 RE# 在人们实际使用正则表达式场景中的表现。这篇文章既是对常见正则表达式痛点的一次调查，也是展示如何用 RE# 解决这些问题的演示。许多浏览量最高的问题都关于补集和交集。所有基准测试代码都在 GitHub 上（https://github.com/ieviev/2026-05-stackoverflow）。内容太多，无法在一篇文章中涵盖，所以本文专注于与我研究最密切相关的主题。 ## 前 15 名 以下是 Stack Overflow 上浏览量最高的 15 个正则表达式问题： | 问题 | 浏览量 | 类型 | | :--- | :--- | :--- | | 1. [匹配不包含某单词的行](https://stackoverflow.com/q/406230) | 5.5M | 补集 | | 2. [如何在 JavaScript 中验证电子邮件地址？](https://stackoverflow.com/q/46155) | 4.9M | 基本验证 | | 3. [正则表达式匹配开放标签，除了 XHTML 自闭合标签](https://stackoverflow.com/q/1732348) | 4.1M | HTML 解析 | | 4. [如何使用正则表达式验证电子邮件地址？](https://stackoverflow.com/q/201323) | 2.9M | 基本验证 | | 5. [字母数字和下划线的正则表达式](https://stackoverflow.com/q/336210) | 1.9M | 基本验证 | | 6. [只接受数字 (0-9) 且不接受任何字符的正则表达式](https://stackoverflow.com/q/19715303) | 1.8M | 基本验证 | | 7. [密码正则表达式：8 个字符，1 个大写，1 个特殊字符，字母数字](https://stackoverflow.com/q/9477906) | 1.8M | 交集 | | 8. [如何在正则表达式中匹配“任意字符”？](https://stackoverflow.com/q/2912894) | 1.8M | 基础 | | 9. [按子字符串条件过滤 pandas DataFrame](https://stackoverflow.com/q/11350770) | 1.6M | API 使用 | | 10. [正则表达式：忽略大小写](https://stackoverflow.com/q/9655164) | 1.6M | 标志 | | 11. [检查字符串是否匹配 JS 中的正则表达式](https://stackoverflow.com/q/6603015) | 1.6M | API 使用 | | 12. [密码正则表达式：8 个字符，数字，大写+小写，特殊字符](https://stackoverflow.com/q/19605150) | 1.5M | 交集 | | 13. [匹配 URL 的好正则表达式是什么？](https://stackoverflow.com/q/3809401) | 1.5M | 基本验证 | | 14. [在正则表达式中匹配空格](https://stackoverflow.com/q/559363) | 1.5M | 基础 | | 15. [正则表达式匹配两个字符串之间的所有字符](https://stackoverflow.com/q/6109882) | 1.5M | 基础 | 前 15 名中的大多数都是验证、API 或基础问题。第 1 名，拥有 550 万次浏览量，询问如何匹配一个*不*包含某单词的行。这就是补集。第 7 和第 12 名是交集（同时满足多个条件）。这些答案的重要性超越了 Stack Overflow：一项针对 19.3 万多个项目的 2019 年研究（https://dl.acm.org/doi/10.1145/3338906.3338909）发现，开发人员经常将正则表达式复制到他们自己的代码中而不进行适配。 *显示 SO 作为正则表达式模式主要来源的图表* ## 补集：匹配不存在的内容 补集意味着匹配所有*不*匹配某个模式的内容。标准正则表达式引擎没有“非”运算符，但自 Brzozowski 1964 年的论文（https://dl.acm.org/doi/abs/10.1145/321239.321249）以来，其理论就已经存在。在 RE# 中，`~(R)` 匹配 `R` 不匹配的所有内容。Stack Overflow 上有 56 个关于它的问题，浏览量超过 10 万： **Stack Overflow 上顶级的补集问题** - **5.5M:** [匹配不包含某单词的行](https://stackoverflow.com/q/406230) - **1.4M:** [使用 grep 进行负匹配（匹配不包含 foo 的行）](https://stackoverflow.com/q/3548453) - **1.1M:** [排除单词/字符串的正则表达式](https://stackoverflow.com/q/2078915) - **1.1M:** [如何在正则表达式中否定特定单词？](https://stackoverflow.com/q/1240275) - **1.1M:** [如何用 grep 排除一个单词？](https://stackoverflow.com/q/4538253) - **975k:** [正则表达式非运算符](https://stackoverflow.com/q/7317043) - **939k:** [正则表达式：匹配除特定模式外的所有内容](https://stackoverflow.com/q/1687620) - **487k:** [Grep 正则表达式不包含字符串](https://stackoverflow.com/q/10411616) - **470k:** [如何用正则表达式“反向匹配”？](https://stackoverflow.com/q/164414) 顶级答案全是使用环视（lookahead）的变通方法。以下是来自顶级答案的四种常见否定环视模式，在 100 行长、每行约 100 字符的数据上进行基准测试： | 问题 | fancy-regexp | pcre2 | RE# | | :--- | :--- | :--- | :--- | | 不包含单词 ([#406230](https://stackoverflow.com/q/406230)), `^((?!W).)*$` | 386.9 us (152x) | 274.5 us (108x) | **2.55 us (1x)** | | 不包含单词 ([#406230](https://stackoverflow.com/q/406230)), `^(?!\.*W).*` | 97.3 us (36x) | 115.4 us (42x) | **2.73 us (1x)** | | 不以后缀结尾 ([#16398471](https://stackoverflow.com/q/16398471)), `.*(?<!S)$` | 69.9 us (32x) | 6.0 us (2.8x) | **2.18 us (1x)** | | 同上，单行长行 (10 KB) | 1.03 s (69,281x) | 204.6 us (14x) | **14.86 us (1x)** | | 不以开头 ([#2116328](https://stackoverflow.com/q/2116328)), `^(?!P).*` | 86.8 us (34x) | 5.2 us (2.1x) | **2.52 us (1x)** | 第一种变通方法非常普遍，以至于它有一个名字：**温顺贪婪令牌 (tempered greedy token)**（https://www.rexegg.com/regex-quantifiers.html#tempered_greed）。它在每个字符位置重新检查条件，这就是为什么即使在短行上它也要慢 150 多倍。向后看（lookbehind）`.*(?<!S)$` 在短行上看似无害（仅慢 32 倍），但它呈二次方扩展：在 10 KB 的行上，fancy-regexp 慢了 69,281 倍。 这些模式出现在日志过滤、URL 路由和输入验证中，任何需要拒绝包含某单词的字符串的地方。有了补集，所有这些遵循相同的结构： ``` ^.*$ & ~(_*word_*) | | 一行不包含 "word" ``` 其中 `_*` 意味着“任意字符串”（或 [在 Web 应用中尝试](https://ieviev.github.io/resharp-webapp/)）。 我想在这里强调的是，使用环视的标准方法之所以慢，是因为它在搜索时模拟了一个缺失的功能。当引擎直接理解补集时，否定是在编译时内置的，在搜索时没有成本。 ## 交集：一次性匹配多个条件 交集的故事类似：匹配同时满足多个模式的字符串。标准正则表达式引擎不支持它，所以标准答案是链式使用 `(?=.*X)` 环视（“在匹配之前，向前看并检查 X 是否存在”）。这有效，但每个环视都会对输入执行单独的扫描。 两个交集问题进入了前 15 名（第 7 和第 12 名），还有更多： **Stack Overflow 上顶级的交集问题** - **1.5M:** [密码正则表达式：必须包含至少八个字符，至少一个数字以及大小写字母和特殊字符](https://stackoverflow.com/q/19605150) - **1.3M:** [正则表达式：有 AND 运算符吗？](https://stackoverflow.com/q/469913) - **1.2M:** [正则表达式中 AND/OR 运算符是如何表示的？](https://stackoverflow.com/q/8020848) - **517k:** [在一行中用 grep 匹配两个字符串](https://stackoverflow.com/q/4487328) - **429k:** [如何用 grep 在多行中查找模式？](https://stackoverflow.com/q/2686147) - **386k:** [匹配包含任意顺序两个名称的字符串的正则表达式](https://stackoverflow.com/q/4389644) - **345k:** [正则表达式：允许字母、数字和空格（至少有一个字母或数字）](https://stackoverflow.com/q/576196) - **314k:** [正则表达式 AND 运算符](https://stackoverflow.com/q/3041320) - **304k:** [正则表达式确保字符串至少包含一个小写字符、一个大写字符、一个数字和一个符号](https://stackoverflow.com/q/1559751) - **234k:** [使用正则表达式按任意顺序匹配多个单词](https://stackoverflow.com/q/1177081) 以下是该组中的三个示例： | 问题 | fancy-regexp | pcre2 | RE# | | :--- | :--- | :--- | :--- | | 密码验证 ([#19605150](https://stackoverflow.com/q/19605150)) | 8.4 us (12x) | 11.4 us (17x) | **682.0 ns (1x)** | | 非匹配 | 10.5 us (15x) | 14.3 us (20x) | **703.0 ns (1x)** | | 行/文档中的两个术语 ([#4487328](https://stackoverflow.com/q/4487328)) | 66.3 us (20x) | 86.6 us (26x) | **3.4 us (1x)** | | 非匹配 | 138.0 us (308x) | 181.4 us (405x) | **448.0 ns (1x)** | | N 个单词任意顺序 ([#1177081](https://stackoverflow.com/q/1177081)) | 190.1 us (381x) | 267.1 us (535x) | **499.0 ns (1x)** | | 非匹配 | 330.2 us (23x) | 372.6 us (26x) | **14.1 us (1x)** | 有了交集，这些变成了 `R & S`，在单次扫描中求值，无需环视： ``` _*jack_* & _*james_* | | 包含 "jack" 包含 "james" ``` ## 环视不是交集 性能成本是一回事，但环视和交集实际上不是相同的操作。考虑输入 `xyz_______AB` 上的 `(?=.*A)(?=.*B).\{3\}`。点击播放查看会发生什么： `(?=.*A)(?=.*B).\{3\}` 在 `"xyz_______AB"` 上 环视独立于匹配的子串向前扫描。它们确认 A 和 B 存在于*某个地方*的前方，然后 `.\{3\}` 消耗三个字符，其中没有一个是 A 或 B。匹配结果是 `xyz`。 使用真正的交集，`(.*A.*)&(.*B.*)&.\{3\}` 要求 A 和 B 出现在**匹配的substring本身中**。在 `xyz_______AB` 的开头没有包含 A 和 B 的 3 个字符的子串，所以它不匹配。 环视恰好在一个常见情况下与交集重叠：当整个剩余字符串被消耗时（例如 `(?=.*A)(?=.*B).*`）。但是一旦匹配没有消耗完全相同的字符，环视和匹配的子串就会不同步。链式环视不是“正则表达式 AND”。 ## 匹配直到 (“匹配到 X”，“在 X 和 Y 之间”，“在第一次出现时停止”) 通常的答案是懒惰循环：`.*?DELIM`。当重复时（大多数引擎基于回溯），这可能导致灾难性的回溯。 可能让你惊讶的是，你实际上根本不需要懒惰循环来表达这一点。但让我们先看看一些例子。 **Stack Overflow 上顶级的“匹配直到”问题** - **1.5M:** [正则表达式匹配两个字符串之间的所有字符](https://stackoverflow.com/q/6109882) - **1.4M:** [如何在正则表达式中匹配“直到这一串字符”？](https://stackoverflow.com/q/7124778) - **1.2M:** [停止在第一次匹配的正则表达式](https://stackoverflow.com/q/2503413) - **1.0M:** [使用正则表达式匹配到字符的第一次出现](https://stackoverflow.com/q/2013124) - **695k:** [正则表达式匹配问号之后的所有内容？](https://stackoverflow.com/q/4419000) - **688k:** [如何编写非贪婪的正则表达式？](https://stackoverflow.com/q/11898998) - **539k:** [在正则表达式的上下文中，“懒惰”和“贪婪”是什么意思？](https://stackoverflow.com/q/2301285) - **437k:** [获取匹配字符串后单词的正则表达式](https://stackoverflow.com/q/19193251) - **185k:** [从路径中提取文件名的正则表达式](https://stackoverflow.com/q/9363145) - **159k:** [正则表达式直到但不包括](https://stackoverflow.com/q/3850074) 为了展示扩展情况，这里是相同模式在匹配与非匹配输入上的基准测试。Python 的 `re` 在此处作为代表性的未优化回溯引擎包含在内： | 问题 | python `re` | fancy-regexp | pcre2 | RE# | | :--- | :--- | :--- | :--- | :--- | | 直到序列 ([#7124778](https://stackoverflow.com/q/7124778)), `.*?END` | 24.4 us (16x) | 11.4 us (7.5x) | 35.5 us (23x) | **1.5 us (1x)** | | 非匹配 | 48.40 ms (1,125,581x) | 75.0 ns (1.7x) | **43.0 ns (1x)** | 97.0 ns (2.3x) | | 在 `[` `]` 之间 ([#6109882](https://stackoverflow.com/q/6109882)) | 7.1 us (5.0x) | 4.8 us (3.5x) | 8.8 us (6.4x) | **1.4 us (1x)** | | 非匹配 | 920.8 us (27,903x) | 656.0 ns (20x) | **33.0 ns (1x)** | 38.0 ns (1.2x) | | 5 个组 | 466.0 ns (13.6x) | 154.0 ns (4.5x) | 693.0 ns (20.2x) | **34.3 ns (1x)** | | 非匹配 | 8.00 ms (29,630x) | 459.0 ns (1.7x) | 16.72 ms (61,926x) | **270.0 ns (1x)** | Python 在这三种情况下对非匹配都爆炸了。fancy-regexp 将这些委托给 Rust 的 `regex` 引擎，因为它们不需要回溯功能，所以没问题。pcre2 优化了其中一些，但不完全：重复懒惰循环（第 3 行），它在非匹配上也慢了 60,000 多倍。任何使用重复懒惰循环从 HTML 中提取部分的模板引擎或爬虫，在格式错误的输入上都容易受到这种影响。 常见的变通方法 `[^,]*` 仅适用于单字符分隔符。对于像 `,` 这样的多字符分隔符，标准正则表达式中没有逃生舱。补集为你提供了另一种表达方式，无需懒惰循环： ``` ~(_*_*) | | 不包含 then ``` ## 其他性能和安全问题 接下来的这些看起来人畜无害，但特定的回溯引擎处理得很糟糕。正则表达式性能问题有**自己的 CWE**（https://app.opencve.io/cve/?q=cwe:CWE-1333），新的问题每天都在出现。 *大多数关于正则表达式的答案都假设是一个回溯引擎：一次尝试一种可能性，失败时回溯。每个引擎都修补了不同的爆炸问题，但并非所有问题都可以修补。我将引用 Russ Cox 的文章（https://swtch.com/~rsc/regexp/regexp1.html）。我将避免教科书案例如 `(a+)+b`。相反，这里是回溯引擎之间爆炸差异的三个真实世界场景。* ### Python `re` 在 `(.*)sol(.*)` 上的二次方爆炸 这个引起了我的注意。来自“为什么 Python 正则表达式这么慢？”（https://stackoverflow.com/q/26214328）： > 第一个测试字符串长 220K，匹配，且匹配相当快。第二个测试字符串长 20K，不匹配，计算却需要 5 秒！ 这个模式没有什么明显错误的地方，几乎所有回溯引擎都能很好地处理它。Python 的 `re` 不行： | 模式 / 输入 | python `re` | python `regex` | pcre2 | fancy-regex | | :--- | :--- | :--- | :--- | :--- | | `(.*)sol(.*)` | 245.6 us (4.5x) | **54.5 us (1x)** | 788.3 us (14.5x) | 217.2 us (4.0x) | | 非匹配 | 22.40 s (15,630,846x) | 20.9 us (14.6x) | 1.55 ms (1,079x) | **1.4 us (1x)** | | `.*foo.*bar` | 88.8 us (1.1x) | **77.6 us (1x)** | 1.08 ms (13.9x) | 220.0 us (2.8x) | | 非匹配 | 4.62 s (6,572,546x) | 101.3 us (144x) | **703.0 ns (1x)** | 1.4 us (2.0x) | Python 在匹配时表现良好。在非匹配时，**22 秒**用于 100 KB。而且不是因为捕获组：没有捕获的 `.*foo.*bar` 一样糟糕。 ### Java 的二次方向后看 `(?<=From:.*\)alice` 使用可变长度向后看在 `From:` 头之后查找 "alice"。只有**少数引擎**（pcre2、fancy-regex 和 Python 的 `re` 不支持可变长度向后看）**支持这些**。输入是 `From: [email protected]` 后跟 N 行填充内容。一次匹配。 Java： | 输入大小 | Java | python `regex` | regress | | :--- | :--- | :--- | :--- | | 1.5 KB | 4.6 ms (39,014x) | 1.2 us (10x) | **117.8 ns (1x)** | | 5.8 KB | 73.8 ms (396,774x) | 3.2 us (17x) | **186.0 ns (1x)** | | 14.5 KB | 434.5 ms (1,448,170x) | 6.0 us (20x) | **300.1 ns (1x)** | | 29 KB | 1.73 s (3,580,662x) | 11.4 us (24x) | **483.4 ns (1x)** | | 58 KB | 6.87 s (7,905,639x) | 22.0 us (25x) | **869.1 ns (1x)** | Java 尝试向后看的每个可能起始位置，使其成为 O(n²)。在不同引擎之间移植带有环视的正则表达式可能会 quietly 引入二次方行为。 ### CSV 列 10: `^(.*?,){10}P$` “给我 CSV 列 10”的常见模式，变体见 [Q21443370](https://stackoverflow.com/q/21443370), [Q26138582](https://stackoverflow.com/q/26138582), [Q53528067](https://stackoverflow.com/q/53528067)。与上面的 `.*` 示例相同的问题：重复中的懒惰循环。在非匹配时，引擎尝试每种分配方式...