Russ Cox 揭秘：Thompson NFA 让正则匹配快百万倍

两种正则引擎的百万倍性能鸿沟

2007 年 1 月，Russ Cox 发表了一篇论文，把正则匹配分成两条路。一条是主流语言标准解释器用的回溯法，另一条是只在少数工具里见得到的 Thompson NFA 来源：Cox 原文。他拿了一个基准测试来对比，模式是 a? 重复 n 次后接 a 重复 n 次，目标匹配一个 a 重复 n 次的字符串。结果出乎意料，Perl 处理 29 个字符花了超过 60 秒，Thompson NFA 只用 20 微秒。Cox 专门注明这不是笔误，因为两张图的单位不同，前者用秒，后者用微秒，差了一百万倍 来源：Cox 原文。

扩展到 100 个字符，差距更炸裂。Thompson NFA 不到 200 微秒完成，Perl 需要超过 10 的 15 次方年 来源：Cox 原文。更关键的是，回溯算法不只在 Perl 里用，Python、PHP、Ruby、Java 的正则引擎底层跑的都是同一套逻辑 来源：Cox 原文。Thompson NFA 反而是少数派，主要出现在 awk 和 grep 的大部分实现里 来源：Cox 原文。一个性能差百万倍的算法，居然主宰了几乎所有主流语言的正则实现。

Thompson NFA 的算法思路与 Cox 的反直觉判断

Cox 的副标题直接点名，"(but is slow in Java, Perl, PHP, Python, Ruby, ...)"，一长串主流语言名字被塞进括号里 来源：Cox 原文。他并没有止步于批评，同时承认了一个反直觉的事实："多数时候，Perl 的正则匹配速度其实是够用的" 来源：Cox 原文。日常写正则确实很少碰到让回溯法崩溃的输入。但 Cox 指出存在所谓"pathological"正则表达式，能让 Perl 式引擎性能断崖下跌 来源：Cox 原文。Thompson NFA 不存在这个问题，它没有病态输入的概念 来源：Cox 原文。

Cox 的可视化方法很直观，两张图并排放，Perl 用秒做纵轴，Thompson NFA 用微秒做纵轴，两条曲线的增长形态一眼就能看出谁在正常爬坡，谁在指数爆炸 来源：Cox 原文。用不同单位画图通常意味着不可比，Cox 偏偏用这种方式让数量级差距变得无法忽视。他文中没有拆解回溯法为什么慢的机制，直接给出了结论和数据 来源：Cox 原文。

跨语言实现对比：回溯法阵营 vs Thompson NFA 阵营

回溯法阵营名单很长，Perl、Python、PHP、Ruby、Java 的标准正则引擎清一色用回溯法 来源：Cox 原文。Thompson NFA 阵营只有 awk 和 grep 的大部分实现 来源：Cox 原文。Cox 提到后面会有更详细的图表展示其他实现的对比，但从素材来看这部分我没有看到完整展开 来源：Cox 原文。

Hacker News 上关于这篇文章的讨论结果是 2 分、0 条评论 来源：HN 讨论。一篇把百万倍差距摆到台面、点名批评五大语言正则引擎的文章，在开发者社区几乎无人响应。Cox 在文中的表述让我印象很深，"这张图完全可以画成 Python，或者 PHP，或者 Ruby，或者很多其他语言" 来源：Cox 原文。问题的根源不在某个语言，在于一种被广泛复制的算法选择。

我的判断是，Cox 揭示的性能鸿沟在 2007 年之后大概率依然存在，但我无法确认具体哪些语言或版本已经换用了 Thompson NFA。有一件事是确定的，Thompson NFA 在理论上不存在病态输入导致的性能崩塌，这个稳定性优势比任何基准数字都更值得记住 来源：Cox 原文。

原文：

Regular Expression Matching Can Be Simple and Fast (2007) · 来源：Hacker News

作者：itfan123 值班编辑 · 发布于 2026年10月24日