首尔大学与延世大学携手，教AI像人类一样"拼图"——让正则表达式合成突破复杂度瓶颈

这项由首尔大学、庆尚国立大学和延世大学联合完成的研究，以预印本形式于2026年6月发布在arXiv平台，编号为arXiv:2603.24624v2，研究方向属于程序语言领域（cs.PL）。感兴趣的读者可通过该编号在arXiv上查阅完整论文。

你大概有过这样的经历：想在一大堆文本里搜索所有符合某种格式的内容，比如所有邮件地址、所有手机号码，或者所有以特定格式书写的日期。这时候，程序员会搬出一个叫"正则表达式"的工具。正则表达式就像是一个专门描述"文字形状"的语言，用一串看起来像乱码的符号来告诉计算机："帮我找所有长这个样子的东西。"比如 `\d{3}-\d{4}-\d{4}` 这串符号，就代表"三个数字、一个横线、四个数字、再一个横线、再四个数字"，也就是我们熟悉的电话号码格式。

然而，即使是经验丰富的程序员，写出正确的正则表达式也是一件令人头疼的事。稍微复杂一点的文本格式，对应的正则表达式就可能又长又绕，一个括号放错地方就会让整个搜索逻辑崩塌。于是，研究者们自然想到：能不能训练AI来代劳？只需要给AI几个例子——"这些字符串应该被匹配到，那些不应该"——让它自动想出对应的正则表达式？这就是所谓的"示例编程"（Programming-by-Example，PBE）方法。

近年来，基于深度学习的AI合成器在这个任务上取得了不少进展，速度远超以往的穷举搜索方法。但首尔大学等高校的研究团队发现，这些AI其实是在"刷简单题"——它们测试所用的数据集，远比真实世界里人们实际用到的正则表达式简单得多。

研究团队对这个差距做了量化分析。他们发现，一个叫RegExLib的真实正则表达式库里，表达式的结构深度（可以理解为嵌套层数）平均达到4.40，抽象语法树节点数（用来衡量表达式有多"庞大"）平均高达23.69，而且每个表达式平均含有1.25个"或者"类型的分支结构（也叫Union操作符）。相比之下，现有AI模型常用来训练和测试的合成数据集，这三个数字分别只有3.39、6.45和0.04——简单程度不在一个量级上，节点数差了将近四倍，"或者"分支更是相差超过30倍。

这意味着什么？意味着那些在测试集上表现亮眼的AI模型，换到真实世界的复杂正则表达式面前，很可能就束手无策了。研究团队将这个现象称为"基准测试与现实脱节"的问题。为了解决它，他们提出了一套名叫RESYN（Recursive Synthesis，递归合成）的完整框架，并配套开发了一个叫SET2REGEX的新模型。

---

一、现有AI为什么会在复杂正则表达式面前"翻车"

要理解RESYN解决的问题，先得明白现有AI方法为何在复杂情况下会失败。

现有的基于神经网络的正则表达式合成器，基本上采用的是"序列到序列"（Seq2Seq）的工作方式。这种方式的本质是：把给定的几个示例字符串排成一排，然后让模型"阅读"这个序列，再生成对应的正则表达式字符串。可以把它比作一个翻译员，他把中文例句排成一行，然后把这行中文翻译成英文。

这个方式有两个内在缺陷。其一，示例字符串本质上是一个"集合"，集合里的元素本来没有顺序之分——"先给猫的例子再给狗的例子"和"先给狗再给猫"，对于学习规律来说应该没有区别。但序列模型会把输入的顺序当成有意义的信息来学习，导致它在见到不同顺序的例子时，可能得出不同的答案。这叫做"违反置换不变性"。

其二，正则表达式本身有着树状的嵌套结构，就像一棵有很多分叉的树。而序列模型把这棵树"拍扁"成一条线，使得模型难以把握树枝与树干之间的深层关系。当这棵"树"又高又复杂时，模型就更加力不从心了。

除了模型架构的问题，还有一个更根本的难点。在真实的正则表达式中，大量用到了"或者"结构，也就是"这段文字要么匹配A，要么匹配B，要么匹配C"。已有的一些分治方法（把大问题分成小问题来解决）存在一个固执的假设：它们认为最外层的结构一定是"拼接"（Concatenation），也就是"先匹配A，再紧跟着匹配B"。这个假设在简单场景下通常成立，但面对现实中大量顶层就是"或者"结构的正则表达式时，就完全失效了。而且，这类方法即便能做"拼接"式的分割，也只做一层，不会递归地继续分割更深层的子问题，导致遇到深度嵌套的结构时仍然无能为力。

正因如此，研究团队设计了RESYN框架——一个既能处理"拼接"也能处理"或者"，还能一层层递归深入的通用框架。

---

二、让AI学会"拼图"：RESYN框架的三层结构

RESYN的核心思想，可以用拼图来理解。假设你面前有一幅复杂的拼图（对应一个复杂的正则表达式合成任务）。硬要一次性把所有碎片拼成完整的画面太难了，但如果能先把碎片按照颜色或区域分组，然后一组一组地拼，最后再把各组拼好的小块合在一起，就容易多了。

RESYN正是这样工作的：先判断当前这一堆拼图碎片应该怎么分组，然后分组处理，再递归地对每一组内部继续拼，直到每一块小拼图小到AI可以直接处理为止，最后把所有小结果从底层向上组合成最终答案。

整个框架由三个互相配合的部分构成，分别处理数据、模型和算法三个层面的问题。

第一个部分是"正则表达式规范化器"（Regex Canonicalizer）。现实世界里，不同的人写出来的正则表达式风格各异，即使描述的是同一个模式，写法也可能大相径庭——就像不同人拼写同一个英语单词的方式可能不同。这种多样性会给AI的学习带来噪音。规范化器的工作就是把各种写法统一成一种标准形式，就像在AI学习之前先把所有材料的格式统一好，提高学习效率。

规范化的具体操作包括：过滤掉包含回溯引用（backreference）或前瞻断言（lookahead）等超出正则语言范畴特性的表达式；对抽象语法树（AST，可以理解为表达式的树状骨架）进行优化，比如把单字符类合并成字符集、消除多余的重复符号、提取公共前缀等；对长度超过2个字符的字面量进行匿名化处理（用特殊占位符替代），迫使模型学习结构规律而非死记字面内容；以及将AST序列化回字符串时，按照运算符优先级规则精简括号、选择最紧凑的量词写法等。

这套规范化流程确保训练数据的一致性，是整个框架质量的基础。

第二个部分是SET2REGEX，这是框架的"基础合成器"，也就是处理分解后每一块小拼图的那个AI。它解决的正是前面提到的"违反置换不变性"问题。

SET2REGEX采用了一种叫做"层次化集合编码器"（Hierarchical Set Encoder）的结构，分两个阶段处理输入。第一阶段是字符级别的编码：对每一个示例字符串，用一个字符级别的Transformer网络（Transformer是目前大多数语言AI的核心技术）"读取"它的内容，然后通过一种叫"多头注意力池化"（PMA）的操作，把整个字符串压缩成一个固定大小的向量表示，就像给每条字符串画了一幅"画像"。

第二阶段是字符串级别的编码：把所有字符串的"画像"收集起来，再用另一个Transformer网络处理这批画像，但这次不使用位置编码（正是位置编码才会让模型在乎顺序），而是用"类型嵌入"来区分正例和负例。这样，不管你把正例按什么顺序喂给模型，它看到的信息量都是相同的——置换不变性由此得到保证。

这批字符串画像随后再次通过PMA池化，汇聚成一个代表整个输入集合的"全局上下文向量"。最后，解码器生成正则表达式时，先通过一个注意力层关注这个全局上下文，掌握整体趋势，再通过另一个注意力层关注每条字符串的详细特征，处理局部细节。这种"先看全局、再看局部"的双层解码机制，使得SET2REGEX只用1000万个参数，就能达到甚至超越拥有3亿个参数的对标模型（PRAX，基于ByT5架构）的效果，参数量整整缩小了30倍。

第三个部分是RESYN的核心算法——递归分治框架，由三个可学习的神经模块共同驱动：ROUTER（路由器）、PARTITIONER（分组器）和SEGMENTER（分割器）。

ROUTER是整个系统的"决策中枢"。它负责判断当前这批正例字符串应该怎么处理：是直接交给SET2REGEX合成，还是先做某种分解。ROUTER的输出是三个选项之一：直接合成（Synthesize）、按"或者"分组（Partition）、按"拼接"分割（Segment）。训练时，ROUTER的标准答案来自目标正则表达式语法树的顶层操作符——如果顶层是Union，就标记为Partition；如果是Concat，就标记为Segment；其他情况就标记为Synthesize。

SEGMENTER负责处理"拼接"类的分解，也就是把每条字符串按照逻辑上的分段切成若干部分。比如，面对一批电子邮件地址的例子，它会发现所有字符串都可以切成"用户名"、"@"符号和"域名"三段，然后把这三段分别作为独立的子问题递归处理。SEGMENTER采用标准的Transformer编码器-解码器架构，一次性接收所有正例字符串（用分隔符连接成一整段），在全局视野下预测每个字符属于哪个分段，避免了之前一些方法逐条处理字符串时产生的不一致问题。

PARTITIONER负责处理"或者"类的分解，也就是把字符串集合按照相似的结构模式分成若干子集。比如，面对一批包含"纯字母用户名"和"字母加数字用户名"的例子，它会判断这两类应该分成两组，分别合成子表达式，最后用"或者"连接。PARTITIONER用指针网络风格的解码器，以自回归方式逐条预测每个字符串属于哪个组，支持动态确定分组数量。

算法还包含若干防止过度分解的机制：不允许连续两次使用同一种分解策略（防止无限递归地切同一种方式）；如果PARTITIONER把每个字符串都分成了单独一组（等于没分），就直接调用基础合成器；如果基础合成器也失败了，就调用一套备用的"常见模式库"（按优先级从数字、小写字母等具体类别到任意字符的通配符依次尝试），保证最终总有一个答案可以回传，不让整棵递归树因为一片叶子失败而全盘崩溃。

---

三、"最优拼法"为何无药可解——NP困难性的证明

研究团队不仅设计了这套系统，还从理论上解释了为什么要用神经网络来学习分解策略，而不是设计一个更聪明的确定性算法来直接找到最优分解方式。

他们通过数学证明，找到最优分解方式这件事本身就是一个NP困难问题。简单来说，NP困难意味着：随着问题规模的增大，任何已知的确定性算法所需的时间都会以指数级增长，最终变得无法接受。

证明的大致逻辑是这样的：研究团队首先定义了"表达式代价"，也就是正则表达式里除操作符以外的符号数量，代价越小越简洁。然后他们证明，找最小代价正则表达式这个问题，等价于找多个字符串的"最优对齐"问题（把字符串对齐，找出最短的公共框架）。而这个最优对齐问题，又等价于理论计算机科学里著名的"最短公共超序列"（Shortest Common Supersequence，SCS）问题——这个问题早在1981年就被证明是NP完全的。三者之间的等价关系经过严格的形式化证明建立起来，最终推导出：判断一组字符串能否被一个代价不超过某个阈值的正则表达式覆盖，是NP完全问题。

这个结论说明，不存在能在多项式时间内（也就是"合理时间"内）找到最优分解的通用算法，除非P=NP这个数学界至今未解的猜想成立。因此，用神经网络来"近似学习"分解策略，在多项式时间内给出接近最优的答案，是当前技术条件下切实可行的路线。

---

四、用三个真实测试集检验效果：数字背后的故事

研究团队在三个基准数据集上评估了RESYN，这三个数据集的难度依次递增：StructuredRegex（334个实例，合成生成）、Snort（352个实例，来自网络入侵检测规则集）和RegExLib（1752个实例，来自真实的在线正则表达式库）。

评估指标也设计得相当全面。合成成功率（Synthesis Success Rate）衡量AI生成的正则表达式能否正确分类所有训练示例；简洁度比率（Conciseness Ratio）用生成表达式的长度除以标准答案的长度，比率越接近1表示AI生成的结果越简洁（如果AI只是把所有正例用"或者"列举出来，这个比率就会非常大，说明它没有真正学到规律）；语义准确率（Semantic Accuracy）在一个"保留测试集"上测试，要求生成的表达式在它没见过的额外示例上也表现正确；马修斯相关系数（MCC）则是一个综合衡量分类质量的指标，范围从-1到1，数值越高越好。

对于单独的PRAX模型（未加RESYN框架），RegExLib的成功率只有42.24%。加上FOREST（一种启发式公共子串方法）后提升到49.94%，但FOREST本身不做递归，瓶颈依然存在。加上RESYN后，PRAX的RegExLib成功率直接跳到67.29%，提升了约25个百分点。

SET2REGEX单独使用时，RegExLib成功率为38.93%，低于PRAX（这符合预期，因为SET2REGEX只有PRAX的三十分之一参数量）。但SET2REGEX加上RESYN后，成功率提升到68.26%，不仅大幅超过了PRAX单独的42.24%，还以极小的参数代价达到了与PRAX+RESYN相当的水平。语义准确率也达到41.61%，MCC分数达到58.97。

另一个对比对象是gpt-oss-120b，一个参数量约为1200亿的大规模推理模型。在RegExLib上，它的成功率达到67.29%，MCC甚至达到59.06，略高于SET2REGEX+RESYN的58.97。但这是一个有着约4000倍参数量优势的庞然大物，而且需要耗费大量推理计算资源。

研究团队还额外对比了最新发布的GPT-5（一个更强大的通用大模型）。通过采用束搜索（beam search，一种生成多个候选答案并择优的策略，候选数k=500）而非默认的贪心解码，SET2REGEX+RESYN在StructuredRegex上以100.00%的成功率完全超越GPT-5（96.71%），在Snort上以90.62%优于GPT-5的85.23%，在RegExLib上虽然成功率（85.33%）低于GPT-5（90.07%），但语义准确率（50.29%）高于GPT-5（48.86%）。这说明RESYN生成的表达式在结构上更接近真正的目标模式，而不只是凑合着能分类当前的示例。

从深度分层分析来看，数据更能说明递归方法的价值。对于语法树深度为1到3的浅层正则表达式，FOREST和SPLITREGEX等非递归方法表现与RESYN相差不多，成功率都在80%上下。但深度达到4及以上时，非递归方法的成功率急剧下跌，到深度5以上时已经接近30%甚至更低，而RESYN在深度5和6+的情况下仍能维持相对稳健的表现，充分验证了递归分解策略对付复杂嵌套结构的必要性。

---

五、消融实验：每个模块各自贡献了什么

为了搞清楚RESYN的每个组件究竟贡献了多少，研究团队做了一系列"拆件测试"，在RegExLib上比较五种不同配置的表现。

完整的RESYN（含可学习ROUTER，支持递归）MCC为58.97，成功率68.26%。去掉ROUTER换成固定交替策略（也支持递归）后，成功率反而升到73.63%，但MCC急剧下降到49.34，比RESYN低了将近10分。这个反差揭示了一个微妙的道理：固定策略因为更激进地分解问题，把很多实例切成很小的子问题，每个子问题都很容易解决，所以成功率更高——但这样做实际上是过度分解，子表达式虽然各自"正确"，拼起来的整体却失去了结构合理性，语义质量（用MCC衡量）大幅下降。可学习的ROUTER懂得何时该拆、何时不必拆，在成功率和语义质量之间取得了更好的平衡。

只用SEGMENTER（等同于SPLITREGEX方法，无递归，只做拼接分割）的成功率为65.30%，MCC为58.81。只用PARTITIONER（无递归，只做分组）成功率只有40.87%，MCC为37.44。这两组数据告诉我们，在大多数情况下，拼接确实是主要的顶层结构，所以只做拼接分割的方法能覆盖更多案例；但对于真正有"或者"结构的案例，不能处理分组就会遗漏。完整的RESYN在成功率和MCC上都优于仅用SEGMENTER的方案，尽管差距微小，但这个边际提升的背后，是对"或者"结构在语义上正确表示的真实改善。

论文中举了一个具体例子来说明这一点。目标正则表达式是 `\d{1,2}|\d{1,2}\,\d{1,3}|\x7f`，这是一个顶层就有三个"或者"分支的表达式。RESYN给出的答案是 `[2-9]\d?|[1-8]\d\,\d{1,3}|\x7f`，结构正确，只是在数字范围上有轻微的过度约束，MCC为81.65。而只用SEGMENTER的答案是 `\d?\d?[\,\x7f]?(\d{3})?`，它把三个"或者"分支强行拼成了一个拼接结构，看起来更"紧凑"，MCC反而达到90.45——但这是因为用于评估的负例是通过编辑距离生成的，缺乏真正挑战这种错误结构的边缘案例，导致错误的结构也能蒙混过关。RESYN生成的结构才是真正正确的，只是现有评估体系的不完善让这个差距在数字上显得很小。

研究团队在结论部分也坦诚指出了这个局限性：当前的负例生成策略基于随机编辑操作（插入、删除、替换），无法覆盖与特定错误结构相关的语义边缘案例。未来的改进方向是引入"语义硬负例挖掘"（semantic hard-negative mining），针对模型容易犯的结构性错误，主动生成更有区分力的负例，使评估指标能更真实地反映结构正确性。

---

六、一个生动的案例：RESYN如何"看穿"字母规律

论文中还用一个具体案例展示了RESYN处理"拼接中含有或者"结构时的优势。目标正则表达式是 `(I{2,10}|V{2,10})[A-Z]{3,4}`，意思是"2到10个I或者2到10个V，后面跟3到4个大写字母"。

RESYN的处理过程是：先用SEGMENTER把问题分成前缀和后缀两段，发现后缀是统一的大写字母模式（`[A-Z]{3,4}`），容易处理。前缀这批字符串则包含了"I开头的"和"V开头的"两种，ROUTER判断前缀部分应该再次用Partition分组，于是PARTITIONER把以I打头的例子和以V打头的例子分成两组，分别合成 `I{2,10}` 和 `V{2,10}`，然后用"或者"连接成 `(I{2,10}|V{2,10})`，最终拼接后缀，得到与目标完全一致的答案。

相比之下，gpt-oss-120b给出的答案是 `(V{2,}[A-Z]*V?|I{2,}[A-Z]*I?)`，它把前后缀混在了一起，结构糊成一团，不仅冗长，还因为末尾的 `V?` 和 `I?` 带来了多余的匹配空间，是典型的过拟合到具体例子、未能提炼出干净规律的结果。

---

说到底，RESYN这套系统做的事情，和人类在解决复杂问题时的直觉是相通的：遇到复杂的东西，先想想能不能切开分别处理；切开后的小问题如果还是复杂，就再切；直到每个小问题小到能直接搞定为止，然后再把结果拼回来。

这套"分而治之"的思路在算法世界里历史悠久，RESYN的贡献在于用可学习的神经网络替代了原来僵硬的规则，让"何时切、怎么切"这两个关键决策变得智能而灵活。与此同时，理论上证明最优切法是NP困难的，也为这种"学习近似"的路线提供了坚实的理论依据——不是因为懒得设计完美算法，而是完美算法在数学意义上就不存在。

对普通用户来说，RESYN的意义在于：未来你有可能直接告诉软件"我需要匹配所有长这样子的字符串"，给几个例子，系统就能自动帮你生成可靠的搜索规则，不再需要手动调试那些看起来像天书的符号组合。对于文本处理、数据清洗、安全规则配置等领域，这意味着一大类繁琐的专业工作有望被大大简化。

有兴趣深入了解技术细节的读者，可以通过编号arXiv:2603.24624在arXiv平台找到完整论文，研究团队也已将代码、数据集和预训练模型权重公开在GitHub上（mrseongminkim/ReSyn），可以直接下载使用。

---

Q&A

Q1：正则表达式合成的"示例编程"方法和直接让GPT写正则表达式有什么区别？

A：示例编程是给AI几个"应该匹配"和"不该匹配"的字符串，让它自动推断规则，不需要用自然语言描述需求。GPT等大模型则需要用户用文字说清楚需求，然后生成代码。前者更自动化、不依赖语言表达能力，但对AI的结构理解要求更高。RESYN属于前者，并且证明在结构正确性上优于GPT类方法。

Q2：RESYN框架能用在正则表达式之外的程序合成任务上吗？

A：研究团队在论文结论中明确指出，这套递归分治框架的思路具有通用性，理论上可以推广到任何目标程序具有递归嵌套结构的合成任务，比如XML或JSON格式规则的推断、某些类型的逻辑公式合成等。不过目前的具体实现和实验仍限于正则表达式领域，进一步的推广需要后续研究。

Q3：SET2REGEX只有1000万参数，为什么能和3亿参数的模型相比？

A：核心在于结构设计与任务的匹配程度。传统Seq2Seq模型（如PRAX）需要用大量参数去"学会忽略"输入顺序带来的干扰，浪费了大量容量在无意义的排列信息上。SET2REGEX从设计上就保证了置换不变性，不需要用参数去纠正顺序偏差，因此同等参数下能更高效地学习真正有用的结构规律。这说明架构与问题特性的契合度，有时比单纯堆叠参数量更重要。