从重复模式的层次复用角度衡量语言复杂性

# 从重复模式的层级复用测量语言复杂性
来源：https://arxiv.org/html/2606.11531
刘睿3,4† 刘鹏宇6,7∗ 刘宇1,2∗  
1 系统科学系，文理学院，  
2 国际复杂系统研究中心，  
3 中国语言文学系，文理学院，以及  
4 语言学科学中心，北京师范大学，珠海 519087，广东，中国。  
5 系统科学学院，北京师范大学，北京 100875，中国。  
6 数学与应用数学系以及  
7 细胞与分子生物学系，罗德岛大学，金斯顿，RI 02881，美国。

###### 摘要

我们引入阶梯路径指数作为基于算法信息论的语言复杂性度量。它通过重复子结构的层次化复用来重建一个序列所需的最小步骤数，捕捉了一种可精确计算但受约束的算法可压缩性形式，与柯尔莫哥洛夫复杂度相关但又有区别。我们将阶梯路径方法应用于并行通用依存关系数据集中的21个平行语料库。阶梯路径指数在不同语言间近似不变，且其变化幅度远小于语料库长度。当所有语料库映射到统一的二进制表示时，这一现象更为明显，从而从表示独立的角度为等复杂度假说提供了证据。我们还观察到字符库大小与语料库长度之间，以及词汇级与语料库级重建复杂度之间的权衡，支持了总复杂度守恒并在不同语言层面重新分配的权衡假说。阶梯路径方法识别的可重用子结构，无需任何语言输入，与自然词汇中存在的单词和形态成分重叠。阶梯路径方法捕捉的层级复用与认知科学中提出的组块机制相似，其中人类认知系统在共享记忆和处理约束下将语言输入压缩成嵌套的、可重用的单元。这种认知组块与阶梯路径方法之间的联系为等复杂度和权衡假说提供了新的解释，将两者都植根于支撑跨人类语言处理的共享认知架构。

\\nonumnote

†这些作者对本工作贡献相等。  
∗共同通讯作者，对本工作贡献相等；通讯应联系刘鹏宇 ([email protected]) 或刘宇 ([email protected])

## 引言

测量自然语言的复杂性是一个长期的语言学挑战，部分原因在于其多面性和多层级性质 [Ehret 等人, 2023](https://arxiv.org/html/2606.11531#bib.bib36)。语言在词汇、形态、句法和音系层面编码信息，不同层面的复杂性可能不同 [House 等人, 2019](https://arxiv.org/html/2606.11531#bib.bib30)。没有一个单一的度量能够全面量化语言复杂性，度量方法的选择通常取决于研究的方面 [Ortega, 2012](https://arxiv.org/html/2606.11531#bib.bib31)。量化语言复杂性的方法大致可分为两类：基于特征的语言度量和基于信息论的度量。

基于特征的语言度量针对语言在不同层面的特定、定义明确的结构属性。常见的句法级度量包括平均依存距离 (MDD)，它反映了句子内句法相关词对之间的平均线性跨度 [Liu, 2008](https://arxiv.org/html/2606.11531#bib.bib29); [Liu 等人, 2017](https://arxiv.org/html/2606.11531#bib.bib42)；T单位平均长度 (MLT)，它量化了最小独立句法单位的平均长度 [Ortega, 2003](https://arxiv.org/html/2606.11531#bib.bib28); [Lu, 2011](https://arxiv.org/html/2606.11531#bib.bib27)；以及句子依存结构之间的全局距离 [Liu 等人, 2022a](https://arxiv.org/html/2606.11531#bib.bib41)。形态学层面的指标包括综合指数，即每词的平均语素数量 [Çöltekin 和 Rama, 2023](https://arxiv.org/html/2606.11531#bib.bib25)，以及范式熵，它衡量语言范式系统内屈折形式的不可预测性 [Cotterell 等人, 2019](https://arxiv.org/html/2606.11531#bib.bib26)。在词汇层面，诸如类型-标记比 (TTR) 和文本词汇多样性度量 (MTLD) 等度量旨在量化文本词汇的范围和丰富性 [Jarvis, 2013](https://arxiv.org/html/2606.11531#bib.bib24)。

基于信息论的方法从整个文本的层面而非孤立的语言特征来刻画复杂性。香农熵应用于自然语言的符号分布，提供了每个符号平均信息含量的度量，并已用于估计多个语料库和语言的熵率 [Shannon, 1948](https://arxiv.org/html/2606.11531#bib.bib44); [Koplenig 等人, 2023](https://arxiv.org/html/2606.11531#bib.bib40)。然而，香农熵仅对符号的频率分布敏感，并不直接考虑文本内重复子结构带来的结构复杂性。基于柯尔莫哥洛夫复杂度的度量解决了这一局限性，因为它们将文本的复杂性定义为能够重建它的最短程序的长度——这个量原则上捕捉了多尺度上重复模式引入的冗余 [Kolmogorov, 1968](https://arxiv.org/html/2606.11531#bib.bib19); [Ehret, 2021](https://arxiv.org/html/2606.11531#bib.bib22); [Liu 等人, 2024](https://arxiv.org/html/2606.11531#bib.bib23)]。在实践中，柯尔莫哥洛夫复杂度无法精确计算，只能近似，通常通过压缩算法 [Vitányi, 2020](https://arxiv.org/html/2606.11531#bib.bib20)。

在本文中，我们关注算法可压缩性的一个可计算来源：序列内重复子结构的复用。阶梯路径方法 [Liu 等人, 2022b](https://arxiv.org/html/2606.11531#bib.bib6); [Zhang 等人, 2024](https://arxiv.org/html/2606.11531#bib.bib3) 通过从基本单元出发，经过可重用子序列的最短层级结构来重建目标序列，从而形式化了这一思想。由此产生的**阶梯路径指数** (λ) 是在此约束方案下的最小重建步骤数；我们将其用作语言复杂性度量，以比较跨语言的平行语料库。

## 结果

### 阶梯路径指数作为语言复杂性度量。

阶梯路径方法是一种将序列分解为基于重复元素的层级结构的方法。关于阶梯路径方法的详细描述可见 [Liu 等人, 2022b](https://arxiv.org/html/2606.11531#bib.bib6); [Xu 等人, 2024](https://arxiv.org/html/2606.11531#bib.bib5); [Li 等人, 2024](https://arxiv.org/html/2606.11531#bib.bib4)；这里仅作简要回顾。给定一个目标序列和一组基本构建块（在所选择的分析层面上最小的不可分割元素），阶梯路径方法寻找最有效的方式来重建目标序列：将基本构建块组合成中间构建块，将中间构建块组合成更大的构建块，并在任何出现重复的地方重复使用任何已构建的块。这些中间可重用的构建块被称为**阶梯子**：即被构建一次并在重建过程中至少被重复使用一次的重复子序列。每个阶梯子和每个基本构建块都关联一个**多重性**，定义为重建过程中被重复使用的次数。阶梯子和基本构建块一起形成一种层级组织的结构，称为**阶梯图**，它对所有被重用组件的嵌套组合关系进行编码。

重建通过一系列**生成操作**进行。每个生成操作将两个先前引入或构建的子序列（基本构建块或阶梯子）连接起来，形成更长的子序列。一旦一个子序列被构建，它就可以在后续的生成操作中被重用：每次重用算作一次生成操作，无论被重用的子序列长度如何。目标序列的**最短路径**，即**阶梯路径**，是在此重用原则下从基本构建块重建它所需的最小生成操作链。由于重用消除了独立重建相同子序列的需要，具有更多内部重复的目标序列相对于其长度需要更少的生成操作。

从阶梯路径方法中产生了两个复杂性度量，该方法旨在寻找重建序列的最短路径。**阶梯路径指数** (λ) 是该最短路径的长度，即重建目标序列所需的最小生成操作数。因为此度量衡量了通过层级复用从基本构建块重建序列的操作成本，我们也将其称为**重建成本**，并在本文中互换使用这两个术语。**大小指数** (S) 是不允许重用的平凡重建过程的长度；对于字符串，这等于字符数。例如，考虑在字符层面分析的目标序列“ABCDBCDBCDCDEFEF”，其中每个不同的字符是一个基本构建块（图 1a）。该序列有16个字符，因此无重用的平凡重建需要16次生成操作，得出 S=16。该序列包含可重用的重复子序列。在阶梯路径分解中，这些共享的子序列就是阶梯子，它们被构建一次，然后在后续步骤中被重用。例如，“CD”由其组成字符构建而成，并在构建“BCD”和目标序列时被重用。因为“CD”在被构建后被重复使用一次，其多重性为1（在图 1a 中，为视觉简洁，多重性等于1的被省略）；相比之下，“BCD”在重建目标序列时被使用了三次，因此在其构建后又被重用两次，其多重性为2，在图中以括号显示。结果形成了一个嵌套层级：字符组合成较短的阶梯子，较短的阶梯子组合成更长的阶梯子，最终这些组件重建为目标序列。

在图 1a 中，目标序列的阶梯路径指数为 λ=10。首先，三个操作构建可重用的子序列：“C” + “D” 得到 “CD”，“B” + “CD” 得到 “BCD”，“E” + “F” 得到 “EF”。这里，“CD”在构建“BCD”时可以直接重用，因为它已经在之前的步骤中被构建。接下来，六个操作连接七个组件：“A”、“BCD”、“BCD”、“BCD”、“CD”、“EF”、“EF”。最后一个操作完成后得到完整的目标序列，总共 3+6+1=10 个操作。此外，图 1b 显示了对一个自然语言序列的相同分析，其中大小指数 S=73，阶梯路径指数 λ=52。

![图注](图 1：序列的阶梯路径分解。  
(a) 一个玩具示例说明了阶梯路径方法如何通过将基本构建块组合成可重用子序列来重建目标序列。白色节点表示基本构建块，灰色框表示阶梯子，箭头表示用于构建目标序列的组合关系。每个块的多重性在块标签后的括号中显示；为视觉清晰，多重性等于1的已省略。大小指数 S 计算无重用时的重建成本，而阶梯路径指数 λ 计算当重复子序列可以被层级重用时的最小重建成本。  
(b) 一个自然语言示例显示了从字符级重复子序列中提取出的阶梯子。为视觉清晰，面板 (b) 中的基本构建块已省略。)

阶梯路径指数在概念上与柯尔莫哥洛夫复杂度相关，后者衡量产生给定字符串作为输出的最短计算机程序的长度 [Kolmogorov, 1965](https://arxiv.org/html/2606.11531#bib.bib47)]。这两个量都涉及一个相关的基本问题，即一个对象可以被多简洁地描述，但它们在范围上有所不同：柯尔莫哥洛夫复杂度捕捉任何可计算的规律性，包括对称性、算术级数和递归规则，而阶梯路径指数则专门捕捉通过重复子结构的复用所能实现的缩减。另一个根本区别是柯尔莫哥洛夫复杂度是不可计算的，即没有算法能够确定任意字符串的确切值 [Vitányi, 2020](https://arxiv.org/html/2606.11531#bib.bib20); [Liu 等人, 2021](https://arxiv.org/html/2606.11531#bib.bib7)]。在实践中，柯尔莫哥洛夫复杂度只能近似，例如通过压缩算法如 Lempel-Ziv [Ziv 和 Lempel, 2006](https://arxiv.org/html/2606.11531#bib.bib17)]。相比之下，阶梯路径指数是精确可计算的。尽管计算通常是 NP-难的，但已开发出算法并应用于实际长度的序列 [Zhang 等人, 2024](https://arxiv.org/html/2606.11531#bib.bib3), 2026](https://arxiv.org/html/2606.11531#bib.bib2)]。因此，阶梯路径指数提供了一种可计算的、确定性的度量，捕捉了柯尔莫哥洛夫复杂度原则上衡量的一个特定方面：通过重复子结构的复用所能实现的描述长度缩减。

阶梯路径方法产生的层级分解在认知科学中具有自然的解释。认知科学中的一个基本概念是**组块** [Miller, 1956](https://arxiv.org/html/2606.11531#bib.bib16)]，其中认知系统将单个项目分组为更大的单元，以克服短期记忆的有限容量。这一概念已被扩展到语言处理模型中 [Christiansen 和 Chater, 2016](https://arxiv.org/html/2606.11531#bib.bib15)]。由于语言输入的记忆非常短暂，认知系统必须迅速将输入材料压缩成越来越抽象的表示层级。在形态学层面，频繁共现的字符序列被整合为公认的语素和词形。在句法层面，经常一起出现的词被分组为固定短语、搭配和构式模式，这些作为单一处理单元起作用。例如，像“in front of”这样的短语不会被逐个词解析，而是作为一个介词组块被提取。这些认知组块形成一个嵌套层级。较小的组块作为较大组块的构建块，所有组块都存储在记忆中，以便在语言理解和生成过程中快速检索和重用。

阶梯路径方法识别的阶梯子类似于这些认知组块。它们是多个粒度级别的可重用子结构，并层级地组成更大的单元。