算法与计算机科学swtch.com编辑精选
正则表达式匹配可以既简单又快速
Regular Expression Matching Can Be Simple And Fast
2009 — 2019，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
Russ Cox 的经典长文，讲解正则表达式匹配的两种实现思路：回溯法与基于 Thompson NFA/DFA 的自动机方法。文章用 'a?^n a^n' 这类例子说明回溯实现会指数级变慢，而 NFA/DFA 方法保持线性时间，并回顾了相关历史与实现（如 awk、grep 与 RE2）。
为什么经久不衰：它把一个看似纯理论的问题讲成了影响真实系统设计的工程教训，多年来被反复引用，至今仍是理解正则引擎性能差异的最佳入门读物。
HN 评论精选
Perl 式正则的功能扩展（捕获、反向引用、嵌入代码）正是它无法用高效 NFA/DFA 算法实现的根本原因。
教科书里的正则算法假设你只是判断字符串是否匹配、只用一组标准操作符。而 Perl 正则要把文本匹配到子表达式而不只是返回是/否，还大幅扩展了操作符集合，其中一些与常规的 NFA/DFA 算法完全不兼容，甚至允许在正则中间嵌入任意 Perl 代码。你很容易写出一个匹配问题是 NP 完全的 Perl 正则——这在教科书讨论的简化正则语言里是做不到的。
jimrandomh查看英文原文
Textbook regex algorithms assume that you're trying to determine whether a string matches an expression using a standard set of operators. Perl regular expressions have to match text to subexpressions, rather than just return a yes/no answer, and have a greatly expanded set of operators, some of which are completely incompatible with the usual NFA and DFA algorithms. It even lets you drop arbitrary perl code into the middle of a regex. You can easily write a perl regex that is NP-complete to match. You can't do that with the simplified regex language that textbooks talk about.
质疑主流语言为何不采用文中更快的算法。
那为什么 Perl、Ruby 等不使用 Thompson NFA？
chime查看英文原文
So why don't Perl, Ruby etc. use Thompson NFA?
Hyperscan 作者补充：实际工程中高性能正则匹配远比文中暗示的复杂，且历史叙述有遗漏。
参考文献/历史部分最大的遗漏是没有提到 V. Glushkov，他的 NFA 构造方法很有吸引力，而且早于 Thompson 的。从参考文献看，人们可能会以为正则实现在 1968 到 2007 年间几乎停滞了。以我们的经验，正则匹配可以既简单又快，但只是有时如此。RE2 的方法直接但朴素；我们在 Hyperscan 中构建了一个（在某些指标上）快得多、扩展性更好的系统，代价是相当高的复杂度——而且仍有许多正则和输入在两个系统中表现都不好。
glangdale查看英文原文
The biggest gap in the references/history section is the failure to mention V. Glushkov, whose NFA construction has much appeal and certainly predates Thompsons'. Reading the references, one might also draw the conclusion that regex implementation almost ceased between 1968 and 2007. In our experience, regex matching can be simple and fast, but only sometimes. RE2's approach is straightforward but naive; we built a considerably faster (on some metrics) and more scalable system in Hyperscan. The cost of this turned out to considerable complexity - and there are still many regexes and inputs that don't perform particularly well in either system.
推荐配套阅读 Pike 的极简正则实现，与本文互为对照。
这是一篇极好的文章。我建议同时（甚至先）读这一篇，它提供了你所见过的最简单（不完整但仍有用）的正则实现之一。它存在原提交文章所解决的问题（用回溯而非 DFA），但代码更短更简单，两者对比着读非常好。
thedirt0115查看英文原文
This is an excellent read. I would suggest reading this also (maybe even before), as it provides one of the simplest (incomplete, but still useful) regex implementations you'll ever see: https://www.cs.princeton.edu/courses/archive/spr09/cos333/beautiful.html It suffers from the problems remedied by the original submission (backtracking instead of DFA), but the code is shorter and simpler. They're great to compare.
历次讨论
同类还值得读
位运算技巧集
Bit Twiddling Hacks
斯坦福页面上的经典位运算技巧合集，收录了 popcount、前导/尾随零、位反转、交换、舍入等大量技巧，并附有解释和性能讨论。
算法与计算机科学上首页 8 次 · 2011–2024graphics.stanford.edu编辑精选如何不按平均评分排序
How Not To Sort By Average Rating
经典文章解释了为什么按平均评分排序不可靠：只有少量评价的条目（比如仅一条五星）会轻易排到最前，而评价数量的差异被忽略。
算法与计算机科学上首页 7 次 · 2009–2024evanmiller.org编辑精选数据结构可视化
Data Structure Visualizations
旧金山大学 David Galles 教授制作的数据结构与算法交互式可视化网站，涵盖 B 树、红黑树、排序、图算法等，可逐步操作观察其运行过程。
算法与计算机科学上首页 6 次 · 2011–2021cs.usfca.edu编辑精选1996 年以来的计算机科学最佳论文奖
Best Paper Awards in Computer Science since 1996
Jeff Huang 维护的一个汇总页面，收录了自 1996 年以来计算机科学各主要会议的“最佳论文奖”获奖名单，并按年份和会议整理，方便读者一站式浏览历届获奖论文。
算法与计算机科学上首页 6 次 · 2010–2018jeffhuang.com编辑精选算法（Jeff Erickson）
Algorithms, by Jeff Erickson
伊利诺伊大学 Jeff Erickson 教授的算法课教材，免费在线开放。
算法与计算机科学上首页 5 次 · 2018–2022jeffe.cs.illinois.edu编辑精选