我刚刚发布了一篇重要的Quamina PR，它代表了我几个月的工作，主要是为一个小型的正则表达式基本功能添加新功能。这篇漫谈的思路并不流畅，但我还是发了出来，因为我知道有很多人对状态机工程感兴趣，而他们就是我的同仁。
据我所知，我试图解决的几个问题之前从未有人解决过，至少没有发表过相关研究成果的人提出过。部分原因在于此，我开始琢磨，这些杂乱无章的Quamina帖子能否整理成一本小册子或专著之类的。状态机真是个非常有用的软件构造！所以，没错，这是一篇实战故事，而不是一篇散文，但如果你喜欢有限自动机，你可能会对其中的一些内容感兴趣。
迄今为止的故事
在开始研究正则表达式之前，我已经将 Shell 风格的“ * ”通配符连接到 Quamina，这迫使我开始使用 NFA 和 ε-transition。实现起来并不难，性能也……还算可以。
这让我想到了“地狱基准测试”。我想知道通配符功能在高负载下会如何工作，所以我从 Wordle 源代码中提取了 12,959 个五个字母的字符串列表，并在每个字符串的随机位置插入一个“ * ”。以下是前十个：
aalii* *aargh aar*ti abaca* a*baci a*back ab*acs ab*aft abak*a
我为每个自动机创建了一个 NFA，并按照这里描述的方式将它们合并在一起。构建和合并自动机的速度足够快，合并后的 NFA 有 46,424 个状态，这感觉还算合理。与它匹配字符串的速度不到每秒一万次，考虑到 Quamina 每秒可以处理一两百万次 DFA 编码模式匹配，这个速度相当糟糕。
但我认为，仍然相当有用。
被诅咒的“ ? ”
去年，我慢慢钻研正则表达式的特性，终于找到了零或一量词“ ? ”。这类东西的状态机并不是什么高深的学问；我最近的Epsilon Wrangling里有一段带图的讨论。
于是我实现了这个功能，并运行了单元测试，虽然大部分测试我都不需要写，但结果都失败了。我想这并不奇怪。
事实证明，我为通配符实现 ε 转换的方式部分是错误的，因为它适用于紧密循环状态到自身的 ε 转换，但不适用于“ ? ”所需的更通用的东西。
事实上，合并 NFA 很难（DFA 很容易），而且我在网上几乎找不到任何帮助。Thompson的构造确实给出了答案：构造一个原本为空的状态，其中包含两个 ε-转换，分别指向两个自动机，这样就能得到正确的结果。我们称之为“拼接状态”。它很容易实现，所以我就这么做了。在 Quamina 的理解中，拼接很难算作“合并”，但仍然如此。
不幸的是，性能极其糟糕，在CPU占用率极高的情况下，每秒只能匹配几个。最终的NFA让人一眼望去，简直令人发指：无穷无尽的拼接状态链，有的长达数千条。
这时我变得非常不开心，几个月来一直在处理现实生活中的问题，而这个问题一直潜伏在我的脑海深处，偶尔会咆哮着引起我的注意。
最后，我把咆哮者从洞穴里放了出来，开始思考解决办法。不过首先……
值得解决吗？
真的吗？哪个理智的人会去搜索成千上万个正则表达式的并集，或者搜索通配符字符串？
我完全没想过这个问题，因为我之前用过 Quamina 的母公司Ruler 。当它在 AWS 和 Amazon 的几个团队中流行起来时，人们有时会发现匹配不止数千个，而是上百万个甚至更多不同模式的并集很有用。当你编写有人实际使用的软件时，不要指望使用它的人会和你一样，认为什么是合理的，什么是不合理的。所以，除非我解决了这个问题，否则我的内心是不会平静的。
我最终决定有三种方法值得尝试：
-
找到一种真正合并通配符模式（而不仅仅是拼接）的方法，以生成更简单的自动机。
-
优化NFA遍历代码路径。
-
计算机科学理论认为，任何 NFA 都可以转换为 DFA。所以就这么做吧，因为 Quamina 在基于 DFA 的匹配方面速度非常快。
Nfa2Dfa
我最终完成了所有这些工作，并且没有完全放弃其中任何一个。其中最巧妙的方法是将数据转换为 DFA，因为如果我这样做，就可以从 Quamina 中移除相当复杂的 NFA 遍历逻辑。
事实证明，网络上有很多关于如何进行 NFA 到 DFA 转换的教科书摘录、YouTube 视频和幻灯片。最终，它变成了一段相当不错的代码，只有几百行。
坏消息是：将每个单独的通配符 NFA 转换为 DFA 的速度惊人，但当我逐个合并它们时，自动机状态的数量开始爆炸式增长，处理速度变得非常慢，以至于我根本没有耐心让它完成。有限自动机理论警告说这种情况可能会发生，但很难描述这种情况发生的具体情况。我想这就是其中之一。
话虽如此，我并没有放弃nfa2Dfa代码，因为如果你有一些模式集合，希望它们运行得非常快，并且愿意等待一段时间才能完成转换，或许我应该提供一个 Quamina 选项来应用它。另外，我可能错过了优化转换的机会；也许它产生的状态比它需要的多？
更快的 NFA 遍历
最近在Epsilon 争论中，我描述了 NFA 遍历如何工作，很大程度上依赖于实现一种称为 ε-闭包的东西。
因此，我分析了遍历过程，不出所料地发现，大部分时间都花在了计算这些 ε 闭包的内存分配上。所以现在 Quamina 有了一个 ε 闭包缓存，每个闭包只会计算一次。
这很有帮助，但还远远不够，分析器仍然告诉我问题出在 Go 的分配和垃圾收集机制上。削减这类东西并不是什么高深的学问。我见过一次又一次的标准 Go 技巧是将所有数据保存在切片中，不断重复使用它们，然后在每次请求时将它们切回到[:0] 。一段时间后，它们会增长到所有操作都只是复制字节的地步，无需分配内存。
这也有帮助，但速度还达不到我想要的速度。
合并通配符自动机
我编写了多种方法来实现这一点，但总是失败。但我最终找到了一种构建这些自动机的方法，使得任意两个自动机，或者任意一个自动机和一个DFA，都可以合并，从而显著减少ε-转移链的数量。我不会在这里写这些，原因有二：首先，这没什么意思；其次，我担心随着我继续实现新的正则表达式运算符，可能不得不进一步修改这种方法。
具体来说，有一次我查看了代码，发现它不起作用，我发现如果添加一个特定的条件，它就能工作，但我实在想不出一个原则性的理由来这么做。显然，我最终得解决这个问题。与此同时，如果你是那种好奇心爆棚的“特殊人士”，可以看看我那个 PR 的分支，看看它的spinout类型。
无论如何，尽管它让我有点困惑，我还是添加了这个条件。现在你可以以每秒 80K 的速度向 Quamina 添加通配符模式，而我的 12.9K 个通配符可以生成一个包含近 70K 个状态的 NFA，它可以以近 400K 每秒的速度扫描事件。这足以让我们发布“?”功能了。
顺便说一句，我尝试将那个 70K 状态自动机输入到 DFA 转换器，但在它消耗了一个小时的 CPU 并占用了许多 GB 的 RAM 之后，我放弃了。
后续步骤Next steps
添加“ + ”和“ * ”，真心希望我不必再次重新设计 NFA 机制。
另外，弄清楚那个令人费解的if语句的解释。
我应该说……
尽管这个系列的关注点非常狭窄，甚至可以说是过于偏执，但我还是收到了一些零星的积极反馈。所以还是有一些人关心这个系列。感谢你们所有人。
原文： https://www.tbray.org/ongoing/When/202x/2025/07/21/Automaton-merge-war