本文是一篇发表于《Mathematics》期刊2026年第14卷的原创性研究论文，题为“在语法归纳中使用卡特兰数限制可能的CFG派生树数量”。作者是来自国际视觉大学工程与建筑学院的Aybeyan Selim、诺维萨德大学经济与计算机科学系的Muzafer Saracevic，以及普里什蒂纳“Ukshin Hoti”大学计算机科学学院的Arsim Susuri（通讯作者）。该研究于2025年12月11日收稿，经修订后于2026年1月9日正式发表。
一、 学术背景与研究目的
本研究的核心科学领域是计算语言学和形式语言理论，具体聚焦于语法归纳这一核心任务，即如何从原始语言数据中无监督地学习句法结构。在该领域中，使用上下文无关文法（Context-Free Grammar, CFG）作为模型时，面临一个根本性挑战：随着句子长度的增加，可能的派生树数量呈指数级爆炸式增长。这种组合复杂性导致无监督解析（Unsupervised Parsing）在计算上难以处理，且在统计上高度不确定，严重影响了语法参数估计的可靠性和语言学合理性语法的搜索。
现有方法主要通过结构限制来尝试缓解这一问题，例如深度受限解析框架会限制派生树的递归高度，这已被证明能提升认知合理性和统计可学习性。然而，深度阈值通常是启发式选取的，缺乏对深度限制如何与CFG派生空间的底层组合结构相互作用的数学化描述。其他方法采用剪枝启发式或概率阈值，虽能缩减有效搜索空间，但并未改变其派生结构的指数本质。近年来，基于神经网络的语法归纳方法（如神经PCFG）通过学习的先验或摊销推断机制引入了软结构偏置，虽然有效，但通常缺乏对派生搜索空间大小的明确组合保证。
一个关键观察是，CFG派生与几种由卡特兰数（Catalan Numbers）枚举的著名组合对象（如完全二叉树、Dyck路径、平衡括号、非交叉划分）具有相同的递归分解特性。卡特兰数提供了描述结构配置数量如何随句子长度增长的精确公式和递推关系。然而，尽管存在这种深层的结构相似性，在语法归纳过程中直接使用基于卡特兰数的约束来限制CFG派生空间的研究却很少。大多数现有模型将组合增长视为不可避免的障碍，而非一个可通过数学方法约束的可处理形状空间。此外，自然语言语法常表现出非二元分支（例如 VP → V NP PP），其结构由卡特兰数在m元树上的推广——富斯-卡特兰数（Fuss–Catalan Numbers） 所枚举。这些高阶卡特兰族为控制分支因子的语法提供了允许的派生形状数量的紧致上界，但尚未被系统地整合到语法归纳中。
基于上述研究空白，本文提出一种基于卡特兰数和富斯-卡特兰数的、数学上严谨的结构约束框架，旨在系统性地限制CFG归纳模型的派生搜索空间。研究的主要目标是：通过引入基于卡特兰数和富斯-卡特兰数的结构约束，从根本上减轻语法归纳中的组合爆炸问题，从而在保持CFG完全生成能力的前提下，显著缩小搜索空间、降低歧义性，并引导模型产生更平衡、更符合语言学直觉的句法结构。
二、 详细工作流程
本研究的工作流程是一个从理论建模到算法实现，再到实验验证的系统性过程，其核心是一个名为“卡特兰约束派生过滤算法”的新方法。
第一， 理论基础构建与界限证明： 研究首先在理论上建立了CFG派生树与组合数学之间的联系。文章证明了在乔姆斯基范式（CNF）下，生成一个长度为n的句子的不同二元派生树形状的数量恰好是第(n-1)个卡特兰数C_{n-1} = (1/n) * binom(2(n-1), n-1)。对于更一般的、最大分支因子为m的CFG，其内部节点数为n的允许派生树形状的数量，存在一个由富斯-卡特兰数F_n^{(m)} = 1/((m-1)n+1) * binom(mn, n)给出的上界。当引入最大深度d的限制时，允许的树形数量T(n, d)将严格小于不受限的卡特兰数或富斯-卡特兰数。作者通过命题严格证明了这些界限，并指出在现实假设（如固定深度d=8和分支因子m=2或3）下，搜索复杂度可以从指数级降低至近似多项式级别。这些理论结果为后续的算法设计提供了数学依据和性能保证。
第二， 核心算法设计与实现： 基于上述理论界限，研究者开发了“卡特兰约束派生过滤算法”。该算法将组合约束直接整合到解析执行过程中。其主要流程如下： 1. 初始化与预计算： 算法首先为所有相关的n值预计算卡特兰数和富斯-卡特兰数表。 2. 递归生成与记忆化： 算法以递归方式生成所有符合语法规则的候选派生。为避免指数级重复计算，它采用了一个记忆化（Memoization）表，该表以（非终结符A，子串起止位置[i, j]，当前深度d）为键进行索引。对于每个状态，算法遍历所有可能的CFG产生式。 3. 结构约束检查与剪枝： 对于每条产生式A → B1 B2 … Bk，算法需要将当前子串[i, j]划分为k个部分，并递归生成每个子成分的派生树集合。这是组合爆炸的根源。算法的创新之处在于，在组合这些子树集合之前，会先应用一个称为 “CatalanBound” 的过滤函数。该函数根据子树的大小(n1, n2, …, nk)和当前分支数k，计算出一个理论上可能的最大派生形状数量（对于二元分支使用卡特兰数乘积，对于k>2使用富斯-卡特兰数乘积）。如果算法在递归过程中发现针对当前划分、实际可能生成的子树组合数量超过了这个理论上界，它会提前终止（剪枝）这一路径的探索，认为其结构上不可行或组合冗余。这一步骤是本方法能大幅降低复杂度的核心。 4. 结构权重整合： 为了进一步引导学习过程趋向平衡结构，算法为每个派生树T分配一个结构权重 w_struct(T)。该权重是树中所有内部节点度的卡特兰数倒数的乘积。这一设计使得高度不平衡的树（其节点子节点数差异大，导致对应卡特兰数小，权重增大）的权重被降低，从而在后续的期望最大化（EM）算法等参数估计过程中，起到一种软性先验的作用，促使模型偏好更平衡、语言学上更合理的派生形状。
第三， 实验设置与评估： 为了验证方法的有效性，研究设计了全面的实验。 * 数据集： 使用了两种类型的数据集。一是合成的CFG生成语料库（12,000个句子，长度6-20），用于精确测量派生过度生成情况。二是来自通用依存（Universal Dependencies）英语网页树库的自然语言语料库（8,530个句子，长度5-25）。 * 基线系统： 设置了两个对比基线：1）无约束PCFG：使用经典的Inside-Outside EM算法训练，无任何结构限制。2）深度受限PCFG：最大深度d=7，是文献中常见的启发式方法。 * 评估指标： 1）句法分析F1分数：衡量预测的短语结构与黄金标准结构的一致性。2）派生数量减少率（DCR）：衡量与无约束模型相比，候选派生树减少的比例。3）解析时间（毫秒）。 * 参数与实施： 提出的卡特兰约束模型设置了最大深度d_max=8，最大分支因子m_max=3，并使用了预计算的卡特兰/富斯-卡特兰表。所有模型均在Python 3.10中实现，关键操作用C++加速，并进行了统计显著性检验（配对t检验，置信水平99%）。
三、 主要研究结果
实验结果全面支持了理论预期，证明了卡特兰约束框架的有效性和优越性。
在解析准确率方面： 卡特兰约束模型在两个数据集上均持续超越了基线系统。如图1所示，该模型比无约束PCFG的平均F1分数提高了2.6%至4.3%，同时优于深度受限基线。统计检验（p < 0.01）证实了这一提升的显著性。这表明，基于卡特兰数的剪枝不仅仅是排除了不可能的树，而且是主动地将模型引导向结构更平衡、语言学上更合理的派生，从而更贴近人类标注的句法模式。
在派生空间缩减方面： 研究取得了最显著的成果。如表2和图2所示，卡特兰约束模型将候选派生树的数量平均减少了约60%（59-63%）。图2清晰地展示了三种模型在句子长度增加时，派生树数量增长的轨迹：无约束模型呈现近乎卡特兰数预测的指数增长（~4^n）；深度受限模型增长放缓但仍呈指数趋势；而卡特兰约束模型的增长曲线则大幅平缓，接近多项式增长，这与理论分析中“在固定深度和分支限制下复杂度降至多项式”的预测完全吻合。这种组合爆炸的有效抑制是方法的核心贡献。
在计算效率方面： 派生空间的大幅缩减直接转化为显著的运行时优势。如表3所示，卡特兰约束模型的平均解析时间仅为67.3毫秒，相比无约束PCFG的128.5毫秒减少了47.6%，相比深度受限PCFG的103.1毫秒也有显著提升。这证明了该方法在保持甚至提升分析质量的同时，极大地提高了计算可扩展性，对于处理大规模语料库或实时解析应用具有重要意义。
定性分析结果： 除了定量指标，研究还进行了定性评估。结果发现，诱导出的语法倾向于生成更平衡的树结构，系统性地避免了在人类标注语料中不常见的深度左分支或右分支配置。这一特性与卡特兰族本身偏向平衡分支的数学性质一致，也与人类句子处理中偏好最小依存距离和有界中心嵌入的心理语言学观察相符，从外部验证了该结构偏置的合理性。
四、 研究结论与价值
本研究得出结论：利用卡特兰数和富斯-卡特兰数提供的精确组合界限，可以有效地控制语法归纳中的组合复杂性。通过将派生树的深度、分支因子和树形约束在数学上可描述的界限内，所提出的框架能够在保留语法表达力的前提下，将可能的派生树数量从指数级减少到近似多项式级别。实验证明，该方法不仅大幅降低了计算负担（解析时间减半），还提高了句法分析的准确性，并引导产生更符合语言学直觉的树结构。
其科学价值在于架起了形式组合数学与实用语法学习之间的桥梁。它表明，组合理论为语法归纳提供了一个强大而原则性的基础，精确的组合界限可以作为一种优雅的机制来控制句法歧义，超越了传统的启发式方法。在应用价值上，该方法为高效、准确的无监督句法分析提供了一种新的、有理论保证的解决方案，尤其适用于需要从无标注文本中学习语法的场景。
五、 研究亮点
六、 其他有价值内容
文章在最后展望了未来的研究方向，为后续工作提供了清晰的路径。例如，探索能够根据词汇或上下文线索动态调整的适应性结构约束，而非固定的深度和分支限制；将卡特兰约束作为结构化先验整合到神经PCFG、变分语法模型或具有编码器的Transformer等神经建模方法中，以提升其可解释性和泛化能力；在更多类型多样的语言上验证该框架，以探究是否存在更深层的语言普遍性；以及在半监督学习范式中利用卡特兰结构偏置。这些方向进一步拓展了本研究成果的应用边界和理论深度。