基于嵌套与层次重复的文本距离：一种压缩视角

# 基于嵌套与层级重复的文本距离：一种压缩视角
来源：https://arxiv.org/html/2607.05416
Xiaojun Hu¹,²,³,¹¹footnotemark:1, Jing Wang¹,²,³,¹¹footnotemark:1, Jingwen Zhang¹,², Fengyao Zhai¹,²,³, Xiao Xie¹,⁴, Hao Liao⁵, Zengru Di¹,², Yu Liu¹,²,²²footnotemark:2
¹北京师范大学文理学院系统科学系，珠海，中国.
²北京师范大学国际复杂系统学术中心，珠海，中国.
³北京师范大学系统科学学院，北京，中国.
⁴中山大学物理与天文学院，珠海，中国.
⁵深圳大学计算机与软件学院，深圳，中国.

###### 摘要

我们提出了一种基于算法信息论（Algorithmic Information Theory, AIT）的结构序列分析新方法。其核心是“梯径”（Ladderpath）方法，该方法能够提取语言序列中重复子结构之间的嵌套与层级关系——这是AIT通过最小生成程序描述数据原则的具体体现。基于这些结构，我们定义了三种距离度量：一种归一化压缩距离（NCD），以及两种直接从梯径表示导出的替代距离。结合k-最近邻分类器，这些距离在分布内、分布外（OOD）和少样本文本分类任务中均表现出强劲且一致的性能。特别地，所有三种方法在OOD和低资源设置下均优于基于gzip的NCD和BERT。这些结果表明，梯径捕捉到的结构化表示保留了序列的内在属性，并为文本建模提供了一种轻量、可解释且无需训练的替代方案。本工作突显了基于AIT的方法在结构性和领域无关的序列理解方面的潜力。

*K*eywords算法信息论（AIT）⋅Normalized Compression Distance（NCD）⋅压缩⋅梯径⋅文本分类⋅层级结构

## 1 引言

自然语言处理（NLP）和机器学习的快速发展显著提升了文本分类和回归任务的性能[1 (https://arxiv.org/html/2607.05416#bib.bib1),2 (https://arxiv.org/html/2607.05416#bib.bib2)]。从传统的词袋模型到深度神经架构以及像BERT这样的预训练语言模型[3 (https://arxiv.org/html/2607.05416#bib.bib3)]，已有多种方法用于解决这些任务。然而，这些模型在低资源或分布不一致的场景中部署仍面临重大挑战，因为它们严重依赖大量标注数据和高计算需求[4 (https://arxiv.org/html/2607.05416#bib.bib4),5 (https://arxiv.org/html/2607.05416#bib.bib5)]。尽管这些模型在理想条件下表现良好，但在数据稀缺或存在领域偏移的情况下，其泛化能力往往会下降[6 (https://arxiv.org/html/2607.05416#bib.bib6)]。

传统模型和基于词嵌入的分类器需要特征工程或微调[7 (https://arxiv.org/html/2607.05416#bib.bib7),8 (https://arxiv.org/html/2607.05416#bib.bib8)]，而大规模模型则在超高维空间中对数据编码了高度压缩的映射。从信息论的视角来看，从数据中提取模式的过程可以被视为一种压缩形式——识别并只保留最具信息量的结构[9 (https://arxiv.org/html/2607.05416#bib.bib9),10 (https://arxiv.org/html/2607.05416#bib.bib10)]。受此启发，Jiang等人提出了一种无需参数分类方法，该方法结合标准压缩器（如gzip）与k-最近邻（k-NN）分类器，在无需训练的情况下近似深度学习般的性能[11 (https://arxiv.org/html/2607.05416#bib.bib11),12 (https://arxiv.org/html/2607.05416#bib.bib12)]。该方法使用归一化压缩距离（Normalized Compression Distance, NCD）来衡量文本相似度，提供了一种轻量且泛化的解决方案，特别适用于低资源和异构数据。该方法的理论基础源于信息距离和柯尔莫哥洛夫复杂度的概念[13 (https://arxiv.org/html/2607.05416#bib.bib13)]。Bennett等人引入了归一化信息距离（NID）的概念，这是一种基于柯尔莫哥洛夫复杂度的通用相似度度量[14 (https://arxiv.org/html/2607.05416#bib.bib14)]。然而，由于柯尔莫哥洛夫复杂度的不可计算性，NID无法直接应用于实践。为克服这一局限，Li等人提出使用压缩算法来近似复杂度，并引入了NCD作为可计算的替代方案[15 (https://arxiv.org/html/2607.05416#bib.bib15)]。Cilibrasi和Vitanyi后来将此思想扩展到聚类任务[16 (https://arxiv.org/html/2607.05416#bib.bib16)]。通过压缩来估计数据对象的复杂度，NCD提供了一种无模型的距离度量方法，支持无需训练的分类框架[17 (https://arxiv.org/html/2607.05416#bib.bib17)]。

如上所述，基于压缩的技术在文本分类中已展现出良好性能，例如通过结合标准压缩器与k-NN的方法[11 (https://arxiv.org/html/2607.05416#bib.bib11)]。该方法的吸引力在于其不依赖大量训练或先验领域知识——通过通用压缩捕捉数据中的内在规律。然而，像gzip这样的通用压缩器并非针对自然人类语言常见的语义或层级文本结构进行优化，这限制了它们的分类精度。

为应对这些局限，我们提出了一种基于梯径方法[18 (https://arxiv.org/html/2607.05416#bib.bib18),19 (https://arxiv.org/html/2607.05416#bib.bib19)]的替代压缩分类框架，该方法属于算法信息论（AIT）的范畴。梯径通过计算重建给定字符串或其他数据对象所需的最小层级重构步数来实现高效压缩[20 (https://arxiv.org/html/2607.05416#bib.bib20)]。这使得它比传统压缩器更能有效捕捉嵌套结构特征。与预训练模型或参数调优系统不同，梯径保持无模型且无参数，这显著增强了其在动态或数据稀疏环境中的适应性[21 (https://arxiv.org/html/2607.05416#bib.bib21),5 (https://arxiv.org/html/2607.05416#bib.bib5)]。这使得它特别适用于低数据可用性或分布不一致的现实场景。

本文的主要贡献总结如下：(1) 我们提出了一种基于AIT的新方法，利用梯径方法提取语言序列中重复子结构之间的嵌套与层级关系，并将其用于压缩。(2) 我们证明，这些结构关系既可用于基于压缩的距离计算——产生一种新的归一化压缩距离 \(NCD_{lp}\)——也可用于定义基于梯径表示的距离，思路类似于Dice系数和Jaccard指数，从而得到 \(L_{Dice}\) 和 \(L_{Jaccard}\)。(3) 实验表明，所有三种距离度量均能有效用于文本分类任务。\(NCD_{lp}\) 表现出与以往最强的基于压缩的方法（即 \(NCD_{gzip}\)）相当的性能，而 \(L_{Dice}\) 和 \(L_{Jaccard}\) 相较于 \(NCD_{lp}\) 持续取得更优性能。值得注意的是，在分布外（OOD）和少样本设置中，所有三种方法均优于BERT。这不仅为标注数据有限的场景提供了一种实用解决方案，更重要的是，突显了梯径提取的嵌套与层级关系捕捉了序列的内在结构属性——使得无需任何训练即可进行分类。

## 2 方法

### 2.1 回顾梯径方法：捕捉嵌套与层级关系

梯径方法属于AIT的范畴，旨在寻找重建一个对象（此处为字符串）的最短路径，其关键假设是先前重建的子结构可在后续步骤中直接重用——这一思想呼应了François Jacob关于进化修补的论述[22 (https://arxiv.org/html/2607.05416#bib.bib22),23 (https://arxiv.org/html/2607.05416#bib.bib23),24 (https://arxiv.org/html/2607.05416#bib.bib24)]。它通过识别重复子结构及其层级关系来实现这一目标。该最短路径的长度被定义为梯径指数 \(\lambda\)。这些层级与嵌套关系可以被表示为一个偏序多重集，或等价地，一个有向无环图，称为梯图（laddergraph）（参见图1 (https://arxiv.org/html/2607.05416#S2.F1)a 和 1 (https://arxiv.org/html/2607.05416#S2.F1)b 两个示例）。关于梯径方法的详细描述可见文献[18 (https://arxiv.org/html/2607.05416#bib.bib18),25 (https://arxiv.org/html/2607.05416#bib.bib25),26 (https://arxiv.org/html/2607.05416#bib.bib26)]；此处仅做简要回顾。

作为一个示例，考虑字符串 ‘ABCDBCDBCDCDEFEF’。其梯径通过一个匿名实现（见补充材料）计算，并可以表示为偏序多重集：\{\{A, B, C, D, E, F // CD, EF // BCD(2)\}\}。对应的梯图如图1 (https://arxiv.org/html/2607.05416#S2.F1)a 所示。该字符串的梯径指数 \(\lambda\) 也可计算得出，值为10，表示重建目标字符串所需的最小步数。

参见说明图1：利用梯径方法分析字符串中重复子结构的嵌套与层级关系示例。面板(a)和(c)展示了两个示例字符串，分别表示为命名梯图。面板(b)说明了字符串(a)的压缩过程，而面板(d)显示了字符串(c)的相应压缩过程。我们可以自然地将梯径方法应用于压缩，因为它通过算法识别重复子结构（称为梯子单元，ladderons）并捕捉其嵌套与层级关系，从而计算出最短重建路径。每个梯子单元可以在字典中用唯一ID编码，这样当它再次出现时，我们只需引用其ID（参见第2.2 (https://arxiv.org/html/2607.05416#S2.SS2)节关于压缩过程的详细描述）。

### 2.2 基于梯径的压缩器

图1 (https://arxiv.org/html/2607.05416#S2.F1)a 演示了使用梯径方法压缩单个字符串的过程，以之前讨论的字符串 ‘ABCDBCDBCDCDEFEF’ 为例。计算其梯径后，每个梯子单元被分配一个唯一ID：‘BCD’获得ID 0，‘CD’获得ID 1，‘EF’获得ID 2（ID编号越高，层级越低，通常梯子单元越短）。参照图1 (https://arxiv.org/html/2607.05416#S2.F1)b，从最高ID向下，‘EF’由基本构建块‘E’和‘F’组成，因此直接表示为 (E,F)。类似地，‘CD’由基本构建块‘C’和‘D’组成，表示为 (C,D)。梯子单元‘BCD’由‘B’和梯子单元1（即‘CD’）组成，因此表示为 (B,1)。这种构造减少了独特符号的数量：我们不再需要写出完整的序列‘B’, ‘C’, ‘D’，有效压缩了一个字符。

接下来，对于目标字符串，我们为其分配一个负ID，此处记为 \(-1\)，并将其表示为 \((A,0,0,0,1,2,2)\)。每次出现ID 0时，我们避免重写‘BCD’，从而每次节省两个字符。由于ID 0出现三次，总共节省六个字符。类似地，每次出现ID 1节省一个字符，因此两次出现节省两个字符，以此类推。这种消除冗余重写的策略是梯径方法中压缩的基础。

根据上述定义和构造，所有相关信息都可以编码成一个单一的序列。梯径框架下的最终压缩结果可以表示为

\[z = (1; A,0,0,0,1,2,2; B,1; C,D; E,F)\]

其中第一个数字表示目标字符串的总数——此处为1。第一个分号分隔的部分使用梯子单元ID编码目标字符串。随后由分号分隔的部分定义了所有梯子单元：‘B,1’对应梯子单元ID 0，‘C,D’对应ID 1，‘E,F’对应ID 2。

不包括初始数字1，压缩字符串 \(z\) 的总长度为13，等于 \(\lambda\) 加上梯子单元的总数。在此例中，\(\lambda\) 等于10，共有3个梯子单元。这可以清晰展示，因为 \(\lambda\) 本身表示从基本单元重建目标字符串所需的最短步数。压缩字符串直接反映了这一最小重建路径。注意，梯子单元的数量（此处为3）被加入，因为组合 \(n\) 个梯子单元只涉及 \(n-1\) 步；例如，从‘E’和‘F’形成‘EF’计为一步，但在压缩序列中我们必须明确写出两个字符‘E’和‘F’。类似地，从‘B’和梯子单元1构建‘BCD’是一步，但我们在压缩输出中必须同时写出‘B’和1。最后，图1 (https://arxiv.org/html/2607.05416#S2.F1)b 演示了使用相同方法压缩两个目标字符串的过程。

原则上，序列 \(z\) 可以进一步压缩为二进制序列，例如使用霍夫曼编码或将最终压缩序列转换为其他格式（更多细节见附录A (https://arxiv.org/html/2607.05416#A1)）。然而，此处不考虑这些额外步骤，因为重点是定义基于梯径压缩的距离度量并执行文本分类。总之，由于梯径指数 \(\lambda\) 被定义为从重复子串的层级和嵌套关系导出的最短重建路径长度，\(\lambda\) 可以作为最优压缩长度的有效代理。

最后，根据文献[16 (https://arxiv.org/html/2607.05416#bib.bib16)]，为了使用压缩器定义NCD，该压缩器应满足以下四个关键性质：**幂等性**（Idempotency），确保重复数据不影响压缩效率；**单调性**（Monotonicity），要求压缩多个字符串的结果不小于压缩单个字符串的结果；**对称性**（Symmetry），表明压缩结果应独立于输入数据的顺序；**分配性**（Distributivity），确保无论数据结构、顺序或分块方法如何，都能一致地处理不同的字符串组合。满足这些性质且在可接受误差范围内的压缩器被称为**标准压缩器**（normal compressor）[16 (https://arxiv.org/html/2607.05416#bib.bib16)]。并非所有压缩器都严格...