ReSyn: 一种广义递归正则表达式合成框架

TL;DR ReSyn 是一个递归分治框架，将复杂正则拆解为子任务，结合对例子顺序不敏感的 Set2Regex，在真实世界基准上显著提升合成准确率，刷新 SOTA。

问题

问题背景

正则表达式合成是 Programming-By-Example (PBE) 的核心任务之一，旨在从少量正/负示例中自动生成满足条件的正则表达式，广泛应用于日志解析、数据提取、安全规则生成等自动化场景。近年来，神经符号方法（如 DeepRegex、AlphaRegex）虽已取得显著进展，但其评估多基于结构简单的合成基准，未能反映真实场景的复杂性。

现有方法局限

主流合成器在真实世界正则表达式上性能急剧下降，根本原因在于：

• 基准与真实分布的偏差：常用数据集（如 RegExLib、DeepRegex 所用集合）的表达式深度浅、嵌套少，且较少使用联合（|）操作符，而生产环境中正则表达式（如 Web 表单验证、API 路由匹配）常包含深层嵌套分组与多分支联合，导致现有模型在遇到这些结构时搜索空间爆炸或欠拟合。
• 对示例顺序的敏感性：大多数神经合成器将示例集作为序列输入，忽略了示例集的排列不变性（permutation invariance），迫使模型学习虚假顺序依赖，既浪费参数又降低泛化能力。
• 合成器与分解策略绑定：少量尝试分治的方法（如 Regel）将分解与特定合成器强耦合，无法规模化适配不同架构。

技术挑战与重要性

真实正则表达式的高结构性复杂度带来双重挑战：

1. 搜索空间指数增长：嵌套深度每增加一层，候选模式组合呈组合爆炸；联合操作的普遍存在更使正向与负向约束交织，需要同时满足多个子模式，对合成器的全局规划能力要求极高。
2. 最优分解的 NP-hard 性：将复杂表达式示例集划分成可独立求解的子问题，本质是寻找一种划分方式使得各子表达式能正确合并——该问题被证明为 NP 难的，实际系统必须在效率与准确性间权衡。 由于正则表达式是数据预处理与安全规则的核心组件，该问题的突破可直接提升 AI 数据流水线的自动化程度，降低手工调参成本，在 ML 工程与 DevOps 领域有迫切需求。

行业类比

类似代码生成中，将具有多层条件与循环的函数直接端到端生成易出错，而引入分治式的中间表示（如先生成抽象语法树骨架再填充细节）能大幅提升成功率——正则表达式合成同样亟需这种重组复杂度的机制。

核心洞察

• - **将复杂正则表达式合成问题递归分解为子问题，是突破真实场景结构化复杂度的有效范式。** 现有 PBE 系统在简化基准上表现尚可，但面对深度嵌套和频繁并集操作的真实正则表达式时性能骤降。ReSyn 通过合成器无关的递归分解框架，将单个困难问题拆解为多个可管理子问题，显著提升各类合成器的准确率。这一思路不同于单纯改进合成器内部架构，而是从问题结构本身入手，与端到端黑盒方法形成鲜明互补。
• - **在正则表达式合成中显式建模示例的排列不变性，能够用更少的参数实现更高的泛化能力。** 提出的 Set2Regex 合成器将示例视为集合，利用排列不变网络设计避免了对示例顺序的过拟合，在保持参数高效的同时捕捉了正则语言的结构特征。这与 LSTM 或 Transformer 等顺序模型形成对比，后者容易引入虚假的顺序先验，而 Set2Regex 从根本上消除了这一归纳偏置，在小样本或乱序输入场景下更具鲁棒性。

方法

输入与任务定义

ReSyn 框架处理编程示例归纳 (PBE) 正则表达式合成任务：给定一组正例字符串和一组反例字符串，目标是自动生成一个能正确匹配所有正例、拒绝所有反例的正则表达式。现实世界正则表达式常具有深层嵌套和大量联合操作，现有单一模型难以整体合成。

核心框架：ReSyn 的三阶段递归分解

ReSyn 是一个合成器无关的分治框架，核心思想是将复杂合成问题递归分解为多个较小的子问题，每个子问题产出一个子正则表达式，最终合并为完整表达式。框架由三个可训练模块构成：

• 路由器 (Router)：根据当前示例集合的复杂度，决定是否继续分解。若判定为单步可解，则直接调用基础合成器；否则触发分区与分段。
• 分区器 (Partitioner)：当需要分解时，将正例集合划分为多个簇，每个簇对应于正则表达式中的一个联合分支。这解决了示例集的排列不变性问题，即示例顺序不影响合成结果。
• 分段器 (Segmenter)：在每个正例内部标记子字符串边界，以便提取共有的正则短语片段。

递归过程中，每个子问题（示例子集）独立调用基础合成器生成子表达式，最终由框架自动组合成支持嵌套与联合的完整正则。

基础合成器：Set2Regex

ReSyn 可搭配任意现成合成器。为最大化效率与精度，作者提出了 Set2Regex，一个参数高效的合成器，其结构天然捕获示例的排列不变性：它通过自注意力池化聚合示例信息，使得输出不依赖输入示例的先后顺序。与常规序列模型相比，Set2Regex 参数量更少，且更适合处理无界集合输入。

训练与推理

整个框架端到端训练，损失函数同时优化分解模块的决策质量和最终表达式的匹配准确率。推理时，模型自动执行递归分解，直至所有叶子节点可直接合成。由于分解粒度自适应调整，ReSyn 能处理从简单常量匹配到深度嵌套复杂模式的各种情形。

与同类方法的差异

以往正则合成方法通常采用整体生成或简单模板填充，无法应对真实世界中高频出现的嵌套分组与多分支联合；ReSyn 首次将学习式递归分解引入正则合成，并在任意基础合成器上验证了增益，而 Set2Regex 则提供了对示例顺序无偏的参数化表示。

实验

实验设计

研究围绕四个核心问题展开：RQ1 验证 ReSyn 框架在真实世界正则基准上对不同合成器的提升效果；RQ2 考察递归分解的必要性；RQ3 评估 Set2Regex 的参数效率；RQ4 对比先进大语言模型（如 GPT 系列）的表现。基线包含传统基于规约的合成器、现有神经合成器以及通用 LLM。消融实验分析了分解策略选择与可学习路由器的贡献。数据集源自真实代码库，经规范化与结构过滤，确保覆盖深层嵌套、并集操作等复杂模式。

关键发现

ReSyn 显著提高了各类合成器的准确率，在深层嵌套场景下改善尤为明显。结合 Set2Regex 后达到新 SOTA，该合成器通过置换不变性设计实现了参数高效。递归分解被证实是性能提升的核心：去除分解后准确率大幅下降。与 LLM 对比，专用合成器加分解框架在精确匹配正则语法时表现更可靠，推理成本更低。参数效率方面，Set2Regex 以更少参数量达到与更大模型相当的质量。

深度对比

与传统 PBE 系统和现有神经合成器相比，ReSyn+Set2Regex 在复杂基准上的优势说明分治策略有效缓解了长序列与复杂组合的合成困难。框架的合成器无关性使基线方法无需修改内部结构即可受益。LLM 在零样本场景虽有竞争力，但在需保证语法正确的正则合成中，专用方法在准确性和资源消耗上更具优势。消融研究揭示自适应路由器能根据问题难度动态选择分解策略，避免无效分解带来的性能损失，这对工程部署中的健壮性尤为关键。

行业影响

落地场景

ReSyn 框架与 Set2Regex 合成器可直接嵌入需要从少量示例推断正则表达式的产品中，典型如：

• 日志分析与监控平台：运维人员选中少量日志行，系统自动生成匹配规则，用于实时告警或数据提取。
• 数据清洗与 ETL 工具：在无代码/低代码数据准备流程中，用户通过正负例示范期望的抽取或替换模式，合成器自动推导正则，降低手动编写复杂表达式的门槛。
• 智能表单与文档解析：从 PDF、扫描件中提取结构化字段时，利用示例引导正则生成，替代人工反复调试。

商业价值

• 降本：减少人工编写、测试复杂正则的时间，尤其对于嵌套深、联合多的现实需求。divide-and-conquer 分解策略将长尾困难 case 的求解成功率大幅提升，降低对高级正则专家的依赖。
• 体验提升：最终用户只需提供少量示例即可获得准确的正则表达式，交互型 product 的易用性显著增强，降低使用门槛。
• 增收：作为基础设施增强组件集成到数据集成平台（如 Fivetran、Airbyte）、云日志服务或 RPA 工具中，可成为差异化卖点，带动订阅或企业许可收入。

与现有产品/工作流的接口

ReSyn 框架设计为合成器无关，这意味着：

1. 可作为轻量级前置模块接入现有 regex 合成系统，无需改动内部模型的架构。
2. 输入仅为示例字符串与目标平台无关，可通过 REST API 或 gRPC 封装为独立微服务，对接各类数据管道。
3. Set2Regex 作为参数高效的合成器，可直接替代现有基于 RNN/Transformer 的 decoder，支持批处理且对示例顺序不变，适合高并发在线推理。

具体落地 Use Case

1. 电商评论情感分析管线：在用户反馈文本中需动态抽取产品属性（如尺寸、颜色），运营人员通过 5~10 个正反例在交互界面标记，ReSyn 自动生成提取规则，大幅缩短从需求到上线的时间，支持非技术人员的自助服务。
2. 金融合规文档审查：合规团队需要从合同中识别特定条款（如利率调整规则）的起止位置，传统方法需工程师反复调试正则；利用 ReSyn，合规官仅需标注少量样例，系统生成高精度匹配模式，直接导入现有文档审查工作流，降低沟通成本与误标注风险。

局限

• - **分解路由的可靠性**：ReSyn 框架的性能高度依赖路由器（Router）对复杂问题分解的准确性。路由器作为神经模块，在样本有限或歧义较高的情况下可能产生次优分割，导致错误沿递归阶段传播。论文未详细分析路由失败的具体模式及其对最终合成成功率的影响，也未提供针对路由不确定性的缓解策略（如置信度阈值或回退机制），这在实际部署中可能成为可靠性瓶颈。
• - **分治策略的适用边界**：ReSyn 通过递归分解应对深层嵌套和联合操作，但并非所有正则表达式都具有显著的层次结构。对于结构扁平或较短的正则，分解可能引入不必要的计算开销，甚至因为子问题划分不当导致性能略低于端到端合成。实验部分未展示在简单正则基准上的性能对比，难以评估框架的普适性下限。
• - **合成器无关性的内在限制**：虽然 ReSyn 标榜合成器无关，但它仍依赖底层合成器有效解决子问题。如果子问题依然超出合成器能力范围，分治无法改善局面。此外，Set2Regex 专为排列不变性设计，却未必能捕捉长距离字符依存等复杂语法关系，这可能限制其在某些类型正则（如带有后向引用或复杂断言）任务中的表现。